LeetCode 1

【1. 题目描述】

数轴上放置了一些筹码，每个筹码的位置存在数组?chips?当中。

你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

• 将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
• 将第 i 个筹码向左或者右移动 1 个单位，代价为 1。

最开始的时候，同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/play-with-chips

【示例 1】

输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。

【示例 2】

输入：chips = [2,2,2,3,3]
输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。

【解题思路】
由题目条件可知，当我们将砝码移动偶数个单位的时候，代价为0，而要移动奇数个单位的时候，我们可以首先移动偶数个单位，然后再移动一个单位，这样，代价就是1。因此，我们只要统计所给出的数组中奇数和偶数的个数，然后返回个数更少的那一个。

【示例代码】

class Solution:
    def minCostToMoveChips(self, chips: List[int]) -> int:
        if len(chips) == 1:
            return 0
        odd_num = 0
        even_num = 0
        for item in chips:
            if item % 2 == 0:
                even_num += 1
            else:
                odd_num += 1
        if even_num < odd_num:
            return even_num
        else:
            return odd_num

【2. 题目描述】

给定一组不含重复元素的整数数组?nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets

【示例】

输入: nums = [1,2,3]
输出:
[
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
]

【解题思路】

由题目条件可知是让我们构造集合 \(X\) 的真子集。容易想到的方法是：假设真子集集合为\(\Theta\)。我们先构造一个空的子集，可知道空子集一定属于\(\Theta\)。然后每次从 \(X\) 中获取一个元素为下一个待添加元素 \(\theta\) ，将 \(\theta\) 与已经存在于 \(\Theta\) 中的所有元素进行组合，如此进行下去即可获得完整的真子集 \(\Theta\)。

【代码示例】

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        sub = [[nums[0]]]
        for i in range(1, len(nums)):
            sub_len = len(sub)
            for j in range(sub_len):
                tmp = list(sub[j])
                tmp.append(nums[i])
                sub.append(tmp)
            sub.append([nums[i]])
        sub.append([])
        return sub

【3. 题目描述】

给定一个非负整数?\(c\)?，你要判断是否存在两个整数 \(a\) 和 \(b\)，使得?\(a^2\) + \(b^2\) = \(c\)。

【示例1】

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

【示例2】

输入: 3
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-square-numbers

【解题思路】

由题意可知，我们只需要遍历一下小于 \(sqrt(x)\) 的数字 \(m\) ，然后查看一下 \(x - m*m\) 是否为某一个整数的平方即可。

【示例代码】

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        if c == 0:
            return True
        for i in range(1, int(c**0.5)+1):
            if i*i == c:
                return True
            if i*i < c:
                another = int((c - i * i)**0.5)
                if another * another == c - i * i:
                    return True
        return False

LeetCode 1

原文：https://www.cnblogs.com/zhhfan/p/13021920.html