思路1：
class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count=0 while n!=0: if n%2==1: count+=1 n=n>>1 return(count)
思路2：每次去掉二进制中最右边的1
class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count=0 while n!=0: count=count+1 n=n&(n-1)#每次去掉最右边的1 return(count)1、动态规划
自底而上的，申请一维数组就可以
class Solution(object): def minimumTotal(self, triangle): res=triangle[-1] for i in range(len(triangle)-2,-1,-1): for j in range(len(triangle[i])): res[j]=triangle[i][j]+min(res[j],res[j+1]) return res[0]#使用二维矩阵 class Solution(object): def minimumTotal(self, triangle): res= [[0 for i in range(len(triangle[-1]))] for i in range(len(triangle))] res[-1]=triangle[-1] for i in range(len(triangle)-2,-1,-1): for j in range(len(triangle[i])): res[i][j]=triangle[i][j]+min(res[i+1][j],res[i+1][j+1]) return res[0][0]
这个题的tag是贪心，贪心策略是我们每次都选取最优的策略，然后前面已经选好了的就不用管了。
这个贪心的方法是，我们使用一个变量reach 保存当前能达到的最后位置索引，那么在每个位置的时候判断这个位置能不能到达，即位置的索引大于这个reach，说明前面无论怎么走也走不到这个位置，返回False。如果这个位置可以到达，要维护一下这个reach，更新策略是：当前索引位置+这个数字表示能向右走多少步，这个代表了到达当前位置的时候向右边能到达 的最远距离，在这个最远距离以内的任何位置都能到，因为每次跳的步数可以变小的。进行了一次循环后，每个位置都能到达，结果可以返回True.
时间复杂度o(n) 空间复杂度o(1)
class Solution(object): def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ reach = 0 for i, num in enumerate(nums): if i > reach: return False reach = max(reach, i + num) return True贪心和DP的比较：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，他所作出的是在某种意义上的局部最优解。贪心算法和动态规划算法都是由局部最优导出全局最优，这里不得不比较下二者的区别。
贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留； 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解； 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解； 3.边界条件：即最简单的，可以直接得出的局部最优解。参考： 原文：https://blog.csdn.net/fuxuemingzhu/article/details/83504437
我们每次贪心的找在自己当前能到达的几个位置里面，跳到哪个位置的时候，在下一步能跳的最远。然后，我们当前步就跳到这个位置上去，所以我们在这一步的跳跃时，给下一步留下了最好的结果。
所以，使用一个cur表示当前步能到达的最远位置，使用pre表示上一次能到达的最远位置。所以，我们应该遍历在上一步的覆盖范围内，当前能跳的最远位置来更新cur。一个节省计算资源的方式是，保存以前已经检查了的位置为Pos，这样每次检查的范围是pos~pre。
class Solution(object): def jump(self, nums): cur = 0 N = len(nums) count = 0 pos = 0 while cur < N - 1: count += 1 pre = cur while pos <= pre: cur = max(cur, pos + nums[pos]) pos += 1 return count参考：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
dp[l][r] 表示子串 s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。即如果子串 s[l, r] 是回文串，那么 dp[l][r] = true。
class Solution: def longestPalindrome(self, s: str) -> str: size = len(s) if size <= 1: return s # 二维 dp 问题 # 状态：dp[l,r]: s[l:r] 包括 l，r ，表示的字符串是不是回文串 # 设置为 None 是为了方便调试，看清楚代码执行流程 dp = [[False for _ in range(size)] for _ in range(size)] longest_l = 1#初始化 res = s[0] # 因为只有 1 个字符的情况在最开始做了判断 # 左边界一定要比右边界小，因此右边界从 1 开始 for r in range(1, size): for l in range(r): # 状态转移方程：如果头尾字符相等并且中间也是回文 # 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可 # 否则要继续看收缩以后的区间的回文性 # 重点理解 or 的短路性质在这里的作用 if s[l] == s[r] and (l-r>=-2 or dp[l + 1][r - 1]): dp[l][r] = True cur_len = r - l + 1 if cur_len > longest_l: longest_l = cur_len res = s[l:r + 1] # 调试语句 # for item in dp: # print(item) # print('---') return res参考：https://unclegem.cn/2018/08/27/Leetcode学习笔记-892-三维形体的表面积/
def surfaceArea(self, grid): """ :type grid: List[List[int]] :rtype: int """ area = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] > 0: area += 4 * grid[i][j] + 2 if i > 0: area -= 2 * min(grid[i][j], grid[i - 1][j]) if j > 0: area -= 2 * min(grid[i][j], grid[i][j - 1]) return area本来以为是图着色?后来发现题中限制一个节点的度最多就为3，而颜色一共有4种，也就是一定可以染上色，这样我们先把图构造出来，然后遍历每个节点的邻节点，当前节点+邻节点最多四个，这样就用邻节点没有用过的一个颜色将当前节点染色即可。
class Solution: def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: graph=[[] for _ in range(N)] for path in paths: graph[path[0]-1].append(path[1]-1) graph[path[1]-1].append(path[0]-1) res=[0 for i in range(N)] for i in range(N): res[i]=({1,2,3,4}-{res[j] for j in graph[i]}).pop() return res12、困于环中的机器人
https://blog.csdn.net/qq_32424059/article/details/90140487
13、2. 两数相加
https://blog.csdn.net/qq_32424059/article/details/90708493
