ARTS第四周打卡(2019.04.08~2019.04.14)

栏目: 编程工具 · 发布时间: 5年前

内容简介:. 每周至少做一个 leetcode 的算法题. 阅读并点评至少一篇英文技术文章. 学习至少一个技术技巧

所谓A(Algorithm)R(Review)T(Tips)S(Share):

. 每周至少做一个 leetcode 的算法题

. 阅读并点评至少一篇英文技术文章

. 学习至少一个技术技巧

. 分享一篇有观点和思考的技术文章

3 week

Algorithm 算法

#
# @lc app=leetcode.cn id=5 lang=python
#
# [5] 最长回文子串
#
# https://leetcode-cn.com/problems/longest-palindromic-substring/description/
#
# algorithms
# Medium (24.34%)
# Total Accepted:    48.5K
# Total Submissions: 195.6K
# Testcase Example:  '"babad"'
#
# 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
# 
# 示例 1:
# 
# 输入: "babad"
# 输出: "bab"
# 注意: "aba" 也是一个有效答案。
# 
# 
# 示例 2:
# 
# 输入: "cbbd"
# 输出: "bb"
# 
# 
#
#
# @lc app=leetcode.cn id=5 lang=python
#
# [5] 最长回文子串
#
# https://leetcode-cn.com/problems/longest-palindromic-substring/description/
#
# algorithms
# Medium (24.34%)
# Total Accepted:    48.5K
# Total Submissions: 195.6K
# Testcase Example:  '"babad"'
#
# 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
# 
# 示例 1:
# 
# 输入: "babad"
# 输出: "bab"
# 注意: "aba" 也是一个有效答案。
# 
# 
# 示例 2:
# 
# 输入: "cbbd"
# 输出: "bb"
# 
# 
#
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 使用动态规划,用空间换时间,把问题拆分
        # 获取字符串s的长度
        str_length = len(s)
        # 记录最大字符串长度
        max_length = 0
        # 记录位置
        start = 0
        # 循环遍历字符串的每一个字符
        for i in range(str_length):
            # 如果当前循环次数-当前最大长度大于等于1  并  字符串[当前循环次数-当前最大长度-1:当前循环次数+1]  == 取反后字符串
            print("i", i)
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                # 记录当前开始位置
                print("max_length", max_length)
                print("i-max_length-1:", i-max_length-1, " :  i+1", i+1)
                start = i - max_length - 1
                # 取字符串最小长度为2,所以+=2,s[i-max_length-1: i+1]
                print("start",start)
                max_length += 2
                print("max_length", max_length)
                continue
            # 如果当前循环次数-当前最大长度大于等于0  并  字符串[当前循环次数-当前最大长度:当前循环次数+1]  == 取反后字符串
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                print("max_length", max_length)
                print("i-max_length :", i-max_length , " :  i+1", i+1)
                start = i - max_length
                print("start",start)
                # 取字符串最小长度为1,所以+=1,s[i-max_length: i+1]
                max_length += 1
                print("max_length", max_length)
        # 返回最长回文子串
        return s[start: start + max_length] 
        


if __name__ == "__main__":
    s = Solution()
    print(s.longestPalindrome("3314ab1bac223"))
    print(s.longestPalindrome("331ab1ba1c223"))
    print(s.longestPalindrome("12abbac"))

# 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题)
# 再根据子问题的解以得出原问题的解。

# 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:
# 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。
# 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
# 动态规划算法的核心就是记住已经解决过的子问题的解
# 基本思路是对任意字符串,如果头和尾相同,那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。
# 如果头和尾不同,那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。 

#根据回文的特性,一个大回文按比例缩小后的字符串也必定是回文,比如ABCCBA,那BCCB肯定也是回文。
#所以我们可以根据动态规划的两个特点: 
#(1)把大问题拆解为小问题 
#(2)重复利用之前的计算结果 
#这道题。如何划分小问题,我们可以先把所有长度最短为1的子字符串计算出来,根据起始位置从左向右,这些必定是回文。
#然后计算所有长度为2的子字符串,再根据起始位置从左向右。到长度为3的时候,我们就可以利用上次的计算结果:
#如果中心对称的短字符串不是回文,那长字符串也不是,如果短字符串是回文,那就要看长字符串两头是否一样。
#这样,一直到长度最大的子字符串,我们就把整个字符串集穷举完了。

Review 英文技术文章

Tip 技术点

hgetall hscan scan keys

Share 分享文章


以上所述就是小编给大家介绍的《ARTS第四周打卡(2019.04.08~2019.04.14)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

罗辑思维:迷茫时代的明白人

罗辑思维:迷茫时代的明白人

罗振宇 / 北京联合出版公司 / 2015-9 / 42

编辑推荐 1、 罗振宇,自媒体视频脱口秀《罗辑思维》主讲人,互联网知识型社群试水者,资深媒体人和传播专家。曾任CCTV《经济与法》《对话》制片人等。2012年底打造知识型视频脱口秀《罗辑思维》。半年内,由一款互联网自媒体视频产品,逐渐延伸成长为全新的互联网社群品牌。 他对商业和互联网的独到见解,影响了互联网一代的知识结构和对互联网的认识:人类正在从工业化时代进入互联网时代。新的时代将彻......一起来看看 《罗辑思维:迷茫时代的明白人》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器