小李飞刀：做题第九弹！

Bamboy 发布于2019-07-31 10:11 / 1507人阅读

摘要：不过可能还没有抓到动态规划的真谛，总觉得哪里需要再校正下思路。这题也是动态规划的题目，目标总是要分解为子问题。总结看算法图解的时候，涉及动态规划的小结中有这样的每种动态规划解决方案都涉及网格。

写在前面的话

感觉做题越多遇到的写法越多，有种跃跃欲试的感觉~

认真做题

第一题

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],
和少棉在讨论的时候，非常真挚的为了为什么他知道需要是左边的值加上上方的值，
给的说法是最优解的目标就是从左上角到该位置的最优解，局部最优再到全局最优。
这题也是动态规划的题目，目标总是要分解为子问题。

总结

看《算法图解》的时候，涉及动态规划的小结中有这样的

每种动态规划解决方案都涉及网格。

单元格中的值通常就是你要优化的值

每个单元格都是一个子问题，因为你需要考虑如何将问题分解为子问题。

云服务器私有云飞刀小李做题 php做题系统

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43407.html

小李飞刀：做题第十二弹！

摘要：写在前面今天没有叨逼叨但是又一次错过了竞赛爱睡觉的小李下周要上班，下下周一定要参加了握拳认真做题的分割线第一题两地调度公司计划面试人。第人飞往市的费用为，飞往市的费用为。示例输入输出解释第一个人去市，费用为。写在前面今天没有叨逼叨...但是又一次错过了竞赛...爱睡觉的小李...下周要上班，下下周一定要参加了（握拳认真做题的分割线第一题 1029. 两地调度公司计划面试2N人。...

yagami 2019-07-31 10:19 评论0 收藏0
小李飞刀：做题第六弹！

摘要：给定的字符串只含有小写英文字母，并且长度不超过。其他这题了，要重做看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。万万没想到居然用到了泰勒公式手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。写在前面的话今天持续做题ing，python有意思~今天的题有点虐心...兴许是我太笨了...会努力学习的！动态规划我来啦~ 开始做题第一题 459. 重...

BigNerdCoding 2019-07-31 10:08 评论0 收藏0
小李飞刀：做题第十弹！

摘要：第二题汉明距离难度简单两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数和，计算它们之间的汉明距离。第三题买卖股票的最佳时机难度简单给定一个数组，它的第个元素是一支给定股票第天的价格。写在前面这几天断断续续做了题目，也在慢慢体会一些数据思维。终于不用边做视频边写题目啦~开心~把这几天的题解发一下~ 认真做题的分割线第一题 977. 有序数组的平方难度...

bingo 2019-07-31 10:13 评论0 收藏0
小李飞刀：做题第八弹！

摘要：认真做题的分割线第一题乘积最大子序列难度中等给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。写在前面的话慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。认真做题的分割线第一题 152. 乘积最大子序列难度：中等给定一个整数数组nums，找出一个...

ztyzz 2019-07-31 10:11 评论0 收藏0
小李飞刀：做题第七弹！

摘要：给定一个大小为的数组，找到其中的众数。第五题合并两个有序数组难度简单给定两个有序整数数组和，将合并到中，使得成为一个有序数组。说明初始化和的元素数量分别为和。第六题二叉树的最大深度难度简单给定一个二叉树，找出其最大深度。写在前面的话做做做题，慢慢上手了就觉得刷题速度变快了，果然还是有点笨~希望最后一窍快点通吧~ 开始做题第一题 169. 求众数难度：简单给定一个大小为 n 的数组...

AlphaWatch 2019-07-31 10:09 评论0 收藏0