本文主要是介绍Leetcode Day19 技巧类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
75 颜色分类
136 一个数字出现一次, 其他出现两次
class Solution:def singleNumber(self, nums: List[int]) -> int:return reduce(lambda x, y: x ^ y, nums)
这个解法基于以下异或运算的性质：
任何数与 0 异或得到的结果是其本身：a ^ 0 = a
任何数与其自身异或得到的结果是 0：a ^ a = 0
异或运算满足交换律和结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
因此，当我们对列表中的所有数字进行异或操作时：
出现两次的数字会相互抵消（因为 a ^ a = 0）
只出现一次的数字会保留下来（因为 a ^ 0 = a）
最终，reduce 函数返回的结果就是只出现一次的那个数字。
reduce相当于1101s中的accumulate, 你也可以自己指定起始值,
137 一个数字出现一次, 其他三次
6 Z字形表达一个string
class Solution:def convert(self, s: str, numRows: int) -> str:if numRows == 1:return sres = [[] for _ in range(numRows)]pos = 0row = 0down = Truewhile pos < len(s):if down and row < numRows - 1:res[row].append(s[pos])pos += 1row += 1continueif down and row == numRows - 1:down = Falseres[row].append(s[pos])pos += 1row -= 1continueif not down and row > 0:res[row].append(s[pos])pos += 1row -= 1continueif not down and row == 0:res[row].append(s[pos])pos += 1row += 1down = Truecontinuereturn "".join([''.join(x) for x in res])
我就直接这样模拟了, 没什么技巧
134 加油站
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:n = len(gas)spare = 0min_spare = float('inf')min_index = 0for i in range(n):spare += gas[i] - cost[i]if spare < min_spare:min_spare = sparemin_index = ireturn -1 if spare < 0 else (min_index + 1) % n
“亏空最严重的一个点必须放在最后一步走，等着前面剩余的救助”, 这一句话直接醍醐灌顶了.
但是还存在一个问题, 为什么最后的spare >= 0就代表能通过呢?
135 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
class Solution:def candy(self, ratings: List[int]) -> int:dp1 = [1] * len(ratings)for i in range(1, len(ratings)):if ratings[i] > ratings[i-1]:dp1[i] = dp1[i - 1] + 1dp2 = [1] * len(ratings)for i in range(len(ratings) - 2, -1, -1):if ratings[i] > ratings[i + 1]:dp2[i] = dp2[i + 1] + 1ans = [1] * len(ratings)for i in range(len(ratings)):ans[i] = max(dp1[i], dp2[i])return sum(ans)
左边一次, 右边一次即可
191 二进制中1的个数
class Solution:def hammingWeight(self, n: int) -> int:res = 0while n:res += n & 1n >>= 1return res
可以优化, 利用n & (n-1)
n&(n−1)作用: 二进制数字 n 最右边的 1 变成 0 ，其余不变。
def hammingWeight(self, n: int) -> int:res = 0while n:res += 1n &= n - 1return res
这篇关于Leetcode Day19 技巧类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
