leetcode

5.最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

描述

给你一个字符串 s，找到 s 中最长的回文子串。

代码

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

754. 到达终点数字

问题

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。

返回到达终点需要的最小移动次数。

解题思路

由于对称性，target的正负对结果无影响，所以可以对其取一个绝对值。
先用求和公式或者while循环找到一个大于等于target的数，记为dis，一共s步。
然后dis减去target，一共有三种情况：
1.差为零，则直接返回s的值
2.差为偶数，那可以通过翻转一个偶数来完成等式，最后任需s步，返回s的值。
3.差为奇数，那么sum-target+1是一个偶数，此时又有两种情况：
1）s为偶数，需再走一步差值才能为偶数，则返回s+1。
2）s为奇数，需再走两步差值才能变为偶数，则返回s+2。

代码

class Solution(object):
    def reachNumber(self, target):
        """
        :type target: int
        :rtype: int
        """
        target = abs(target)
        k = 0
        while target > 0:
            k += 1
            target -= k

        return k if target % 2 == 0 else k + 1 + k%2

581. 最短无序连续子数组

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/

描述

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

思路

右边的数字总要比左端的数字大

从左往右循环，并记录循环时的最大值 max，如果 nums[i] < max，表示当前位置i需要调整，如果后续所有位置均满足 nums[i+1] > max ，则表示 i+1 位置之后均不需要调整
同理从右向左，并记录循环时的最小值 min

代码

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        maxn, right = float("-inf"), -1
        minn, left = float("inf"), -1

        for i in range(n):
            if maxn > nums[i]:
                right = i
            else:
                maxn = nums[i]
            
            if minn < nums[n - i - 1]:
                left = n - i - 1
            else:
                minn = nums[n - i - 1]
        
        return 0 if right == -1 else right - left + 1

206.反转链表

描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p, rev = head, None
        while p:
            # rev, rev.next, p = p, rev, p.next
            n = p.next
            p.next = rev
            rev = p
            p = n
        return rev

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路

最长公共子序列的长度,比如 hello 和 eillok 的最长公共子序列是4，即ello。

思路： 用二维数组res[i][j]来记录公共序列的长度，共有三种可能：
1、当i=0或j=0时，res[i][j] = 0
2、当A[i] = B[j]的时候 res[i][j]= res[i-1][j-1] + 1
3、当A[i] != B[j]的时候，res[i][j] = max(res[i-1][j],res[i][j-1])

代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1)
        len2 = len(text2)
        res = [[0] * (len1 + 1) for _ in range(len2 + 1)]
        for i in range(0, len2):
            for j in range(0, len1):
                
                if text2[i] == text1[j]:
                    res[i][j] = res[i-1][j-1] + 1
                else:
                    res[i][j] = max(res[i][j-1], res[i-1][j])
                
        return res[i][j]

相似题型：【动态规划】两个字符串的最长公共子串

解题思路：利用动态规划，遍历比较两个字符是否相等，如果相等，则标记为1，并存储。显而易见，相邻字符之间对角线元素之和的最大就是最长公共子串。

def LCstring(string1,string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1+1)] for j in range(len2+1)]
    result = 0
    for i in range(1,len2+1):
        for j in range(1,len1+1):
            if string2[i-1] == string1[j-1]:
                res[i][j] = res[i-1][j-1]+1
                result = max(result,res[i][j])
    return result
print(LCstring("helloworld","looper"))

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

思路一：动态规划

动态规划最重要的思想就是利用上一个状态, 对于本题而言就是: 到底要不要加上上一个状态f(i-1)的信息, 这完全取决于f(i-1)的正负情况, 这样我们就能得出了动态规划的递推公式: f(i)=max{f(i−1)+ai,ai}

得到了递推公式后就可以编写代码了, 代码中的一个技巧就是对于空间复杂度的优化. 当使用动态规划只需要一个数(并不需要整个dp数组)时, 我们就没必要将整个dp数组都保存下来, 我们只需用变量来记录下我们需要的某个量即可, 这个优化方法在动态规划中还是非常常用的方法, 具体的实现参考代码.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ret = nums[0]
        count = nums[0]
        for i in range(1, len(nums)):
            count += nums[i]
            count = max(count, nums[i])
            ret = max(ret, count)
        return ret

思路二：贪心法的思想

贪心的思想是: 从左向右迭代, 一个个数字加过去如果sum<0, 那说明加上它只会变得越来越小, 所以我们将sum置零后重新开始找子序串.

在迭代的过程中要注意, 我们需要用result来不断维持当前的最大子序和, 因为sum的值是在不断更新的, 所以我们要及时记录下它的最大值.

有一个注意点是: 有的朋友可能觉得当数组全是负数的时候可能会出现问题, 其实是没有问题的. 因为在sum不断遍历的过程中, 早已将最大值不断传给result, 即使sum一直是负数被不断置零也不用担心, result还是会记录下最大的那个负数.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ret = nums[0]
        count = 0
        for i in nums:
            if count > 0:
                count += i
            else:
                count = i
            ret = max(ret, count)
        return ret

一个正整数组成的数组，分成连续的M段，问每段的数之和的最大值最小是多少？

例如：a=[10,6,2,7,3],M=2,答案为16，两段分为[10,6][2,7,3]

思路

使用动态规划

1, 2, 3, 4, 5
[[1]]
[[1+2], [1, 2]]
[[1+2+3], [[1+2, 3], [1, 2+3]], [1, 2, 3]]
[[1+2+3+4], [ [1+2+3, 4],[1+2, 3+4], [1, 2+3+4] ], [[1,2,3+4], [1+2, 3, 4], [1, 2+3, 4]], [1, 2, 3, 4]]
[[1+2+3+4+5], [ [1+2+3+4, 5], [1+2+3, 4+5], [1+2, 3+4+5], [1, 2+3+4+5]], [[1+2+3, 4, 5],[1+2, 3+4, 5], [1, 2+3+4, 5], [1,2,3+4, 5], [1+2, 3, 4+5], [1, 2+3, 4+5]], ... ]