【1. 题目描述】
数轴上放置了一些筹码,每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一(不限操作次数,0 次也可以):
最开始的时候,同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置(任意位置)上所需要的最小代价。
来源:力扣(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],
[]
]
【解题思路】
由题目条件可知是让我们构造集合
的真子集。容易想到的方法是:假设真子集集合为
。我们先构造一个空的子集,可知道空子集一定属于
。然后每次从
中获取一个元素为下一个待添加元素
,将
与已经存在于
中的所有元素进行组合,如此进行下去即可获得完整的真子集
。
【代码示例】
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. 题目描述】
给定一个非负整数
,你要判断是否存在两个整数
和
,使得
+
=
。
【示例1】
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
【示例2】
输入: 3
输出: False
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sum-of-square-numbers
【解题思路】
由题意可知,我们只需要遍历一下小于
的数字
,然后查看一下
是否为某一个整数的平方即可。
【示例代码】
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