刷LeetCode的时候觉得比较有意思的解法。

3.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

方法：滑动窗口+哈希表

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d,start,max_l = {},-1,0
        for i in range(len(s)):
            if s[i] in d and d[s[i]]>start:
                start = d[s[i]]
                d[s[i]] = i
            else:
                d[s[i]]=i
                max_l = max(max_l,i-start)
        return max_l

5.最大回文串

给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。

方法：对于每个回文串，每增加一个字母，最多增加1或2个长度，故只需要判断这两个字符串是否为回文即可，同时最大长度不回溯

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        maxlen = 0
        begin = 0
        if n < 2 or s == s[::-1]:
            return s
        for i in range(1, n):
            a = s[i-maxlen-1:i+1]
            b = s[i-maxlen:i+1]
            if i-maxlen-1 >= 0 and a == a[::-1]: #增加2的情况
                begin = i-maxlen-1
                maxlen += 2
                continue
            if b == b[::-1]: #增加1的情况
                begin = i-maxlen
                maxlen += 1
        return s[begin:begin+maxlen]

15.三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<3:
            return []
        nums.sort()
        p,q,l = 0,0,[]
        for i in range(len(nums)):
            if i>0 and nums[i-1]==nums[i]: #如果前面出现就跳过
                continue
            if nums[i]>0:
                continue
            p,q = i+1,len(nums)-1
            while p<q:
                tmp=nums[i]+nums[p]+nums[q]
                if tmp==0:
                    l.append([nums[i],nums[p],nums[q]])
                    while(p<q and nums[p]==nums[p+1]): #去掉后面重复的部分
                        p=p+1
                    while(p<q and nums[q]==nums[q-1]): #去掉前面重复的部分
                        q=q-1
                    p,q = p+1,q-1
                elif tmp>0:
                    q = q-1
                elif tmp<0:
                    p = p+1
        return l

思路：排序后再进行查找，同时可以跳过部分重复的地方。

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

回溯法：（多用于排列组合）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        phone = {'2':['a','b','c'],
                 '3':['d','e','f'],
                 '4':['g','h','i'],
                 '5':['j','k','l'],
                 '6':['m','n','o'],
                 '7':['p','q','r','s'],
                 '8':['t','u','v'],
                 '9':['w','x','y','z']}
        res = []
        def back(comb,n_d):
            if len(n_d)==0:
                res.append(comb)
            else:
                for i in phone[n_d[0]]:
                    back(comb+i,n_d[1:])
        back("",digits)
        return res

18.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等。找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        length = len(nums)
        if length<4:
            return []
        res = []
        nums.sort()
        for i in range(length-3):
            if i>0 and nums[i-1]==nums[i]:
                continue
            if sum(nums[i:i+4])>target: #min
                break
            if sum(nums[-3:])+nums[i]<target: #max
                continue
            for j in range(i+1,length-2):
                if j>i+1 and nums[j-1]==nums[j]:
                    continue
                if nums[i]+sum(nums[j:j+3])>target: #min
                    break
                if nums[i]+nums[j]+nums[-2]+nums[-1]<target: #max
                    continue
                k,l = j+1,length-1
                while k<l:
                    tmp = nums[i]+nums[j]+nums[k]+nums[l]
                    if tmp==target:
                        res.append([nums[i],nums[j],nums[k],nums[l]])
                        k=k+1
                        while k<l and nums[k]==nums[k-1]:
                            k+=1
                        l=l-1
                        while k<l and nums[l]==nums[l+1]:
                            l-=1
                    elif tmp<target:
                        k+=1
                    elif tmp>target:
                        l-=1
        return res

注：在三数之和问题上更进一步。思路为固定两个指针，然后两个指针遍历。中间可判断最大最小来简化计算量。

19.删除链表的倒数第n个结点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        s = ListNode(0) #新建一个伪头，用来防止特殊情况
        s.next = head
        p,q = s,s
        for _ in range(n):
            q = q.next #使得两个指针的距离为n
        while q.next:
            p,q = p.next,q.next
        p.next = p.next.next
        return s.next

注：使用双指针保持固定距离来获得倒数第n个的位置。同时添加伪头来确保特殊情况能成立。

22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

回溯法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        l = []
        def back(s,left,right):
            if left+right==2*n:
                l.append(s)
            if left<n:
                back(s+"(",left+1,right)
            if left>right:
                back(s+")",left,right+1)
        back("",0,0)
        return l

如果左括号少于n个，就可以添加左括号。如果右括号少于左括号就可添加左括号。

39.组合总和

给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

candidates中的数字可以无限制重复被选取。

说明：

所有数字（包括target）都是正整数。

解集不能包含重复的组合。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        n = len(candidates)
        res = []
        candidates.sort()

        def helper(i,tmp,target):  #i用于索引所有数组元素
            if target == 0:
                res.append(tmp)
                return
            if i == n or candidates[i]>target:
                return
            helper(i,tmp+[candidates[i]],target-candidates[i])
            helper(i+1,tmp,target)
        helper(0,[],target)
        return res

注：从小到大依次计算，每次扩展两种，这样可做到不重复计数。

179.最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

实例：

输入: [10,2]
输出: 210

class larger(str):
    def __lt__(x,y):
        return x+y>y+x

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        largest = "".join(sorted(map(str,nums),key = larger))
        return '0' if largest[0]=='0' else largest

304. 二维区域和检索-矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为(row1,col1)，右下角为(row2,col2)。

示例：

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.mat = [[0 for _ in range(n+1)]for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                self.mat[i+1][j+1] = self.mat[i+1][j]+self.mat[i][j+1]-self.mat[i][j]+matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.mat[row2+1][col2+1]-self.mat[row1][col2+1]-self.mat[row2+1][col1]+self.mat[row1][col1]

注：通过动态规划计算二维前缀和，继而在计算卷积和的时候可以直接利用二维前缀和快速计算。

395. 至少有K个重复字符的最长子串

给你一个字符串s和一个整数k，请你找出s中的最长子串，要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。

示例：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为"ababb"，其中'a'重复了2次，'b'重复了3次。

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        stack = [s]
        ans = 0
        while stack:
            cur = stack.pop()
            for c in set(cur):
                if cur.count(c) < k:
                    stack.extend([t for t in cur.split(c)])
                    break
            else:
                ans = max(ans, len(cur))
        return ans

注：使用分治法，对于每一个子串，计算元素出现的次数，若小于k则将子串进行划分。直到所有子串都计算过，输出最大子串的长度。

413. 等差数列划分

函数要返回数组A中所有为等差数组的子数组个数。

示例：

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        length = len(A)
        if length<3:
            return 0
        cur,res=0,0
        for i in range(length-2):
            if A[i+1]-A[i]==A[i+2]-A[i+1]:
                cur+=1
                res+=cur
            else:
                cur=0
        return res

424.替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换k次。在执行上述操作后，找到包含重复字母的最长子串的长度。

示例：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。子串 "BBBB" 有最长重复字母, 答案为 4。

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        num = [0] * 26
        n = len(s)
        maxn = left = right = 0
        while right < n:
            num[ord(s[right]) - ord("A")] += 1
            maxn = max(maxn, num[ord(s[right]) - ord("A")])
            if right - left + 1 - maxn > k:
                num[ord(s[left]) - ord("A")] -= 1
                left += 1
            right += 1
        return right - left

注：使用滑动窗口计算最长长度。维持当前所有字符在窗口内出现的次数，即可判断右边界增加后是否还可以满足要求。如果需要的字符超过可替换的字符则左边界和右边界同时右移。窗口的大小永远不会缩小。

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。

示例：

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个1的下一个更大的数是2；
数字2找不到下一个更大的数； 
第二个1的下一个最大的数需要循环搜索，结果也是2。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        res = [-1] * N
        stack = []
        for i in range(N * 2):
            while stack and nums[stack[-1]] < nums[i % N]:
                res[stack.pop()] = nums[i % N]
            stack.append(i % N)
        return res

注：使用单调栈，将递减数列保存在栈中，再每次判断元素是否比栈顶大，若大则出栈，之后压栈。对数组循环两次得到结果。

946.验证栈序列

给定pushed和popped两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入push和弹出pop操作序列的结果时，返回true；否则，返回false。

示例：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        cnt,stack,length=0,[],len(popped)
        for i in pushed:
            stack.append(i)
            while stack and popped[cnt]==stack[-1]:
                stack.pop()
                cnt+=1
        return cnt==length

注：模拟栈的出入情况。如果当前入栈元素和出栈序列的下一个元素相同，则该元素必然出栈，之后的元素同理。最后判断出栈的元素数量是否等于总元素数量，即可判断是否是正确的出栈顺序。

面试题01.07.旋转矩阵

给你一幅由 N × N 矩阵表示的图像，请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间？

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range((n+1)//2):
            for j in range(n//2):
                matrix[i][j],matrix[j][n-i-1],matrix[n-i-1][n-j-1],matrix[n-j-1][i] = matrix[n-j-1][i],matrix[i][j],matrix[j][n-i-1],matrix[n-i-1][n-j-1]

注：计算每次旋转中四个轮换的点的坐标表示，然后只需要对左上角的点进行操作，每个点进行轮换，即可完成所有点的旋转