写在前面的话感觉做题越多遇到的写法越多，有种跃跃欲试的感觉~认真做题第一题70. 爬楼梯难度：简单假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定n是一个正整数。我的题解：class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ old = 1 new = 1 for i in range(2,n+1): old,new = new,new+old return newv我的思路：这题是一个标准的动态规划的题目，第二步所需要的步数其实是基于第一步，第三步则基于第二步。用笔计算就可以看出，有一定的规律，新的一步的最优解等于前面一步的最优解+之前所有步数的最优解。不过可能还没有抓到动态规划的真谛，总觉得哪里需要再校正下思路。第二题771. 宝石与石头难度：简单给定字符串J代表石头中宝石的类型，和字符串S代表你拥有的石头。S中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。J中的字母不重复，J和S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。我的题解：class Solution(object): def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ num = 0 if not J or not S: return 0 map = {} for i in J: map[i] = 1 for j in S: if j in map: num += map[j] return num我的思路：这题用了hash表的思路，将J里的每个字母单独存成哈希表的一个键，且对应的值为1。这样当S进行搜索的时候，对应将值相加即可得到结果。第三题709. 转换成小写字母难度：简单实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。我的题解：class Solution(object): def toLowerCase(self, str): """ :type str: str :rtype: str """ s = list(str) map = {‘A’:‘a’,‘B’:‘b’,‘C’:‘c’,‘D’:’d’,‘E’:’e’,‘F’:‘f’,‘G’:‘g’,‘H’:‘h’,‘I’:‘i’,‘J’:‘j’,‘K’:‘k’,‘L’:’l’,‘M’:’m’,‘N’:’n’,‘O’:‘o’,‘P’:‘p’,‘Q’:‘q’,‘R’:‘r’,‘S’:’s’,‘T’:’t’,‘U’:‘u’,‘V’:‘v’,‘W’:‘w’,‘X’:‘x’,‘Y’:‘y’,‘Z’:‘z’} for i in range(len(s)): if s[i] in map: s[i] = map[s[i]] s1=’’.join(s) return s1 我的思路：这题….大概写法非常土了….emmm认真的写了个字典，然后对应的写一下，效率也还可以，但是只能用于数量少的情况下，还可以看下有没有其他的写法。第四题62. 不同路径难度：中等我的题解：class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ dp = [[0 for _ in range(m)] for _ in range(n)] #建立二维数组 for i in range(n): for j in range(m): if i ==0 or j ==0: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1]我的思路：非常粗暴的画了网格图，然后发现了规律，dp[i][j] = dp[i-1][j] + dp[i][j-1],和少棉在讨论的时候，非常真挚的为了为什么他知道需要是左边的值加上上方的值，给的说法是最优解的目标就是从左上角到该位置的最优解，局部最优再到全局最优。这题也是动态规划的题目，目标总是要分解为子问题。总结看《算法图解》的时候，涉及动态规划的小结中有这样的每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值每个单元格都是一个子问题，因为你需要考虑如何将问题分解为子问题。