2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

我的垃圾代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        elif not l2:
            return l1
            
        list1,list2 = [],[]

        while l1:
            list1.append(str(l1.val))
            l1 = l1.next
        while l2:
            list2.append(str(l2.val))
            l2 = l2.next

        x = ''.join(reversed(list1))
        y = ''.join(reversed(list2))

        val = str(int(x) + int(y))[::-1]
        dummy = l3 = ListNode(val[0])

        for idx in range(1,len(val)):
            node = ListNode(val[idx])
            l3.next = node
            l3 = l3.next
        return dummy

上面23/24行已经反转了一回,然后26行再次反转了一回.那么就不必反转了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def addTwoNumbers(self, l1, l2):
        r = re = ListNode(0)
        # 是否进位
        carry = 0
        # 当任意一方存在
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = carry + x + y
            carry = s // 10
            r.next = ListNode(s % 10)
            r = r.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        if carry > 0:
            r.next = ListNode(1)
        return re.next

经验:不要再使用dummy = l3 = ListNode(val[0])了,直接使用dummyHead.

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

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

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

我的代码(是错的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = tot = 0
        d = {}
        for idx in range(len(s)):
            if s[idx] not in d:
                d[s[idx]] = idx
                tot += 1
            else:
                res = max(tot,res)
                tot = idx - d[s[idx]]
                d[s[idx]] = idx
                res = max(tot,res)
        return max(tot,res)

正确代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# idx 表示子串终止位置，i表示字串起始位置 
# 当未出现重复时，字符串的长度即为字符串的结束位置减去起始位置。
# 发生重复时，重新利用字符串的结束位置idx减去新的起始位置i，并与之前的未重复字串的长度作比较取较大者
class Solution:
    def lengthOfLongestSubstring(self, s):
        d = {}
        i, res = 0, 0
        for idx in range(len(s)):
            if s[idx] in d:
                i = max(d[s[idx]], i)
            # idx - i + 1就是新子串的长度
            res = max(res, idx - i + 1)
            d[s[idx]] = idx + 1
        return res

5. 最长回文子串

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

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

代码如下:

  • 中心扩散法的想法很简单：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

  • 要注意一个细节：回文串的长度可能是奇数，也可能是偶数。

  • 我们完全可以设计一个方法，兼容以上两种情况：

    1. 如果传入重合的索引编码，进行中心扩散，此时得到的最长回文子串的长度是奇数；
    2. 如果传入相邻的索引编码，进行中心扩散，此时得到的最长回文子串的长度是偶数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def longestPalindrome(self, s):
        size = len(s)
        if size == 0:
            return ''

        # 至少是 1
        longest_palindrome = 1
        longest_palindrome_str = s[0]

        for i in range(size):
            palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
            palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)

            # 当前找到的最长回文子串
            cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
            if len(cur_max_sub) > longest_palindrome:
                longest_palindrome = len(cur_max_sub)
                longest_palindrome_str = cur_max_sub

        return longest_palindrome_str
        
    # 中心扩散法
    def __center_spread(self, s, size, left, right):
        """
        left = right 的时候，此时回文中心是一条线，回文串的长度是奇数
        right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数
        """
        l = left
        r = right

        while l >= 0 and r < size and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r], r - l - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 动态规划
class Solution(object):
    def longestPalindrome(self, s):
        return self.longestPalindromecore(s)
    def longestPalindromecore(self, s):
        if len(s)<=1:
            return s
        if len(s)==2:
            if s[0]==s[1]:
                return s
            else:
                return s[1]#或者s[0]?
        max_s = self.longestPalindromecore(s[:-1])
        if len(max_s)==1:
            if s[-1]==s[-3]:
                return s[-3:]
            elif s[-2]==s[-1]:
                return s[-2:]
            else:
                return s[-1]   
        if self.judge_palindrome(s[-len(max_s)-2:]):
            return s[-len(max_s)-2:]
        elif self.judge_palindrome(s[-len(max_s)-1:]):
            return s[-len(max_s)-1:]
        else:
            return max_s
    def judge_palindrome(self, sub_s):
        if len(sub_s)==1:
            return True
        for i in range(len(sub_s)//2):
            if sub_s[i]!=sub_s[-i-1]:
                return False
        return True

6. Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 N 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

1
2
3
L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1:

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

1
2
3
4
5
6
7
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L     D     R
E   O E   I I
E C   I H   N
T     S     G

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 其实就是先正序存储后逆序存储
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        d = dict.fromkeys(range(numRows),'')
        for idx in range(len(s)):
            remain = idx % (2*numRows-2)
            if remain < numRows:
                d[remain] += s[idx]
            else:
                d[numRows - (remain - numRows)-2] += s[idx]

        res = ''
        for each in range(numRows):
            for i in d[each]:
                res += i
        return res

经验:

  1. 这道题的本质就是先正序存储,后逆序存储.
  2. 当要创建n个列表的时候可以考虑使用dict.fromkeys

8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31^, 2^31^ − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31^ − 1) 或 INT_MIN (−2^31^) 。

示例 1:

1
2
输入: "42"
输出: 42

示例 2:

1
2
3
4
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

1
2
3
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

1
2
3
4
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

1
2
3
4
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−2^31) 。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def myAtoi(self, str: str) -> int:
        if not str:
            return 0
        
        str = str.lstrip()

        sym = ''
        if str[0] == '-':
            sym = '-'
            str = str[1:]
        elif str[0] == '+':
            str = str[1:]

        for idx in range(len(str)):
            if not str[idx].isdigit():
                str = str[:idx]
                break

        res = int(sym + str) if str else 0
        if res > 2**31 -1:
            return 2**31 -1
        elif res <-(2**31):
            return -(2**31)
        else:
            return res

11. 盛最多水的容器

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

1
2
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

最傻逼的代码:

1
2
3
4
5
6
7
class Solution:
    def maxArea(self, height):
        res = 0
        for idx1 in range(len(height)):
            for idx2 in range(idx1+1,len(height)):
                res = max(res,(idx2-idx1)*min(height[idx1],height[idx2]))
        return res

正确的代码是使用动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxArea(self, height):
        left = 0
        right = len(height) - 1
        maxArea = 0
        
        while left < right:
            b = right - left
            # 左边短就左边移动一根,右边短就右边移动一根.
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            area = b*h
            if maxArea < area:
                maxArea = area
        return maxArea

简化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxArea(self, height):
        left = 0
        right = len(height) - 1
        res = 0

        while left < right:
            b = right-left
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            res = max(res,h*b)

        return res

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: 3
输出: "III"

示例 2:

1
2
输入: 4
输出: "IV"

示例 3:

1
2
输入: 9
输出: "IX"

示例 4:

1
2
3
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

1
2
3
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def intToRoman(self, num):
        #用列表保存所有可能的情况
        L1 = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']
        L2 = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        
        # 判断num是在1-10,10-100,100-1000,>1000中的那个区间
        j = 0
        L = len(str(num))
        if L ==1:
            j = 9
        elif L ==2:
            j = 5
        elif L ==3:
            j = 1

        # 在相应区间依次取出个十百千位
        s = ''
        for i in range(j,13):
            while num >= L2[i]:
                s += L1[i]
                num -= L2[i]     
        
        return s

经验:

==使用字典,但是又苦于键无法排序,这时可以使用两个排序列表,然后idx取值即可.==

15. 三数之和

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

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

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路:

要求的是a+b+c=0 其实就是要求a+b=-c，那么问题可以转化为依次遍历数组元素c，然后在剩下的数中做两数之和为-c的问题。

问题在于如何简化算法以及优化复杂度。

  1. 首先可以先排序（O(nlogn)），这样保证数组有序之后可以利用大小关系判断
  2. 设置两个指针left、right，分别从左边以及右边向中间遍历，
    如果找到a+b+c==0，那么可以将这个答案加入到答案集里
    如果a+b+c<0，此时固定的是c，说明a+b太小了，因此left+=1；
    如果a+b+c>0，此时a+b过大，因此right-=1
  3. 去重，这一步则是利用了有序性，
    如果两个数相同，那他们在数组的位置一定是相邻的（连着几个数相同也是可能的），
    因此 去重的操作就能简单遍历一下相邻的是否相同即可。由于数组有序性使得去重这一步很简单，
    因此也可以看出第一步的作用。
  4. 此外还有一些小细节的地方，
    比如说当遍历到c>0的时候，由于之后的数都是正数，那三数之和一定大于0，就没必要继续遍历c了
    (因为 继续向后遍历c只会更大，那之后的数加起来一定大于0)；
    或者固定c，如果c及其后面连着两个数a,b，他们的和已经大于0了，就没必要进行下一步的操作，此时遍历下一个c；
    同理，如果c和数组最后两个数的和仍然小于0，也没必要进行下一步操作。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()

        # 遍历到倒数第三即可
        for i in range(len(nums)-2):
            # 排好序之后，如果nums[i]>0，说明后面的数全部大于0
            if nums[i] > 0:
                break
            # 去重  
            if i == 0 or nums[i] > nums[i-1]:  
                left,right = i+1,len(nums)-1
                # 剪枝
                # 如果c及其后面连着两个数a,b，他们的和已经大于0了，就没必要进行下一步的操作
                # 同理，如果c和数组最后两个数的和仍然小于0，也没必要进行下一步操作。
                if nums[i] + nums[left] + nums[left+1] > 0 or nums[i] + nums[right-1] + nums[right] < 0:
                    continue
                while left < right:
                    ident = nums[i] + nums[left] + nums[right]
                    if ident == 0:
                        res.append([nums[i],nums[left],nums[right]])
                        left += 1
                        right -= 1
                        # 去重,去除连续排列的数字
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                    elif ident < 0:
                        left += 1
                    else:
                        right -= 1
        return res

经验:
要求的是a+b+c=0 其实就是要求a+b=-c，那么==问题可以转化为依次遍历数组元素c，然后在剩下的数中做两数之和为-c的问题。==

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        res = nums[0] + nums[1] + nums[2]

        for idx in range(len(nums)-2):
            left = idx + 1
            right = len(nums) - 1

            while left < right:
                count = nums[idx] + nums[left] + nums[right]
                if count < target:
                    left += 1
                elif count > target:
                    right -= 1
                else:
                    return count
                if abs(count-target) < abs(res-target):
                    res = count
                
        return res

还有做一些优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        res = nums[0] + nums[1] + nums[2]

        for idx in range(len(nums)-2):
            left = idx + 1
            right = len(nums) - 1

            while left < right:
                count = nums[idx] + nums[left] + nums[right]
                if count < target:
                    left += 1
                elif count > target:
                    right -= 1
                else:
                    return count
                if abs(count-target) < abs(res-target):
                    res = count

                # 优化部分
                while left < right and nums[left] == nums[left-1]:
                    left += 1
                while left < right and right+1 < len(nums) and nums[right] == nums[right+1]:
                    right -= 1 
                
        return res

17. 电话号码的字母组合

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

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

img

示例:

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def letterCombinations(self, digits):
        themap = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        digits_list = list(digits)

        output = []
        for digit in digits_list:
            if len(output) == 0:
                for char in themap[digit]:
                    output.append(char)
            else:
                temp = []
                for elem in output:
                    for char in themap[digit]:
                        temp.append(elem + char)
                output += temp

        y = lambda x : len(x) == len(digits_list)
        return list(filter(y,output))

可以简化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []

        themap = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        
        output = list(themap[digits[0]])

        for idx in range(1,len(digits)):
            temp = []
            for elem in output:
                for char in themap[digits[idx]]:
                    temp.append(elem + char)
            output += temp

        y = lambda x : len(x) == len(digits)
        return list(filter(y,output))

可以使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }
        len_s = len(digits)
        
        def dfs(n, s):
            if n == len_s:
                res.append(s)
                return
            for ch in dic[digits[n]]:
                dfs(n+1, s+ch)
                
        if len_s == 0:
            return []
        dfs(0, '')
        return res

经验:
==循环的个数不固定，这种情况得用递归==

总结使用递归时的思路:

  1. 确定基线条件和递归条件
  2. 每次递归都要缩小问题的的规模,不断向基线条件靠拢
  3. 不过递归的多深,迟早是要return的
  4. (重要)==使用递归时,不要管多层的递归栈,只要满足递归条件,只考虑一层栈即可,使用递归的时候一定要搞清楚这个递归函数是干什么的,不然就不知道什么时候使用这个函数.==
  5. ==在递归中,需要需要计数,那么就计数的变量return出来.==

18. 四数之和

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

注意：

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

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

没有优化的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def fourSum(self, nums, target):
        res = []
        if not nums:
            return res

        nums.sort()

        for idx1 in range(len(nums)-3):
            for idx2 in range(idx1+1,len(nums)-2):
                left = idx2 + 1
                right = len(nums) - 1

                while left < right:
                    val = nums[idx1]+nums[idx2]+nums[left]+nums[right]
                    if val < target:
                        left += 1
                    elif val > target:
                        right -= 1
                    else:
                        if [nums[idx1],nums[idx2],nums[left],nums[right]] not in res:
                            res.append([nums[idx1],nums[idx2],nums[left],nums[right]])
                        left += 1
                        right -= 1
        return res

优化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def fourSum(self, nums, target):
        res = []
        if not nums:
            return res

        nums.sort()

        for idx1 in range(len(nums)-3):
            # 优化1
            if idx1 != 0 and nums[idx1] == nums[idx1-1]:
                continue
            for idx2 in range(idx1+1,len(nums)-2):
                # 优化2
                if idx2 != idx1 + 1 and nums[idx2] == nums[idx2-1]:
                    continue

                left = idx2 + 1
                right = len(nums) - 1

                while left < right:
                    val = nums[idx1] + nums[idx2] + nums[left] + nums[right]
                    if val < target:
                        left += 1
                    elif val > target:
                        right -= 1
                    else:
                        if [nums[idx1],nums[idx2],nums[left],nums[right]] not in res:
                            res.append([nums[idx1],nums[idx2],nums[left],nums[right]])
                        left += 1
                        right -= 1
                        # 优化3
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        # 优化4
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
        return res

19. 删除链表的倒数第N个节点

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

示例：

1
2
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

使用双指针法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeNthFromEnd(self, head, n):
        slow = fast = head
        # 先让fast走n步
        for i in range(n):          
            fast = fast.next
        # 若走了n步后为None，则表明删除的为head节点
        if fast == None:            
            return head.next

        # slow和fast同时往前走
        # 当fast走到头时，second即是要删除节点的前一个节点位置
        while fast.next != None:    
            slow = slow.next        
            fast = fast.next
        # 删除该节点
        slow.next = slow.next.next  
        return head

22. 括号生成

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

例如，给出 n = 3，生成结果为：

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def generateParenthesis(self, n):

        def fun(strs):
            for i in range(len(strs)):
                if strs[i].count('(') == n:
                    strs[i]+=')'
                elif strs[i].count('(') > strs[i].count(')'):
                    strs.append(strs[i]+'(')
                    strs[i]+=')'
                else:
                    strs[i]+='('
            if len(strs[0])==2*n: return
            fun(strs)

        strs=['(']
        fun(strs)
        return strs

或者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def generateParenthesis(self, n):
        res = ['()']
        if n==0: return 
        if n==1: return res
        
        for i in range(n-1):
            tmp = []
            for item in res:
                for j in range(len(item)):
                    # 每一个位置都加一个括号
                    tmp.append(item[:j+1]+'()'+item[j+1:])
            res = list(set(tmp))
        return res

经验:注意加括号问题,可以在每一个位置都加一个括号.

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_h = ListNode(-1)
        new_h.next = head
        p1 = new_h
        p2 = p1.next
        
        while p2!=None and p2.next!=None:
            p1.next = p2.next
            p2.next = p1.next.next
            p1.next.next = p2
            
            p1 = p2
            p2 = p2.next
        
        return new_h.next

经验:

  1. ==写链表代码的时候,跨度最多为1.==
    (也就是对于1->2->3->4,最多就是从1跨越到3,因为这个可以保证在pre.next !=None的条件下不会出错)
  2. 写链表的时候一般都是要循环的.此时==注意节点p1,p2要归位==,保证下次的循环.

也可以使用递归:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        l1 = head
        l2 = head.next
        l1.next = self.swapPairs(l2.next)
        l2.next = l1
        return l2

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

1
2
输入: dividend = 10, divisor = 3
输出: 3

示例 2:

1
2
输入: dividend = 7, divisor = -3
输出: -2

说明:

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31^, 2^31^ − 1]。本题中，如果除法结果溢出，则返回 2^31^ − 1。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
商×除数+余数=被除数。
要求商，我们首先想到的是减法，能被减多少次，那么商就为多少，但是明显减法的效率太低
可以用位移法，因为计算机在做位移时效率特别高，向左移1相当于乘以2，向右位移1相当于除以2

我们可以把一个dividend（被除数）先除以2^n，n最初为31，不断减小n去试探,当某个n满足dividend/2^n>=divisor时，
表示我们找到了一个足够大的数，这个数*divisor是不大于dividend的
(也就是说dividend>=(2^n)*divisor)
所以我们就可以减去2^n个divisor，以此类推

以100/3为例
2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3
所以一共是减去了33个3，所以商就是33
这其中得处理一些特殊的数，比如divisor是不能为0的，

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 记录答案的正负号。1为负号
        nagflag = 0
        if abs(dividend+divisor) != abs(dividend) + abs(divisor):
            nagflag = 1

        ans = 0

        # 取绝对值来运算
        dd = abs(dividend)
        ds = abs(divisor)

        # 位运算
        for i in range(31,-1,-1):
            # 被除数每次右移一位
            if dd>>i >=ds:
                ans += 1<<i
                dd -=  ds<<i

        # 判断最终答案符号以及边界
        if nagflag and ans >= 2**31:
            return -2**31
        elif ans >= 2**31:
            return 2**31 - 1
        elif nagflag:
            return -ans
        else:
            return ans

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

img

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
输入: m = 3, n = 2
输出: 3
解释:从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

答案:

机器人一定会走m+n-2步，即从m+n-2中挑出m-1步向下走即可.
即 $C_{m+n-2}^{m-1} ​$

1
2
3
4
5
from math import factorial

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return int(factorial(m+n-2)/(factorial(n-1)*factorial(m-1)))

如果使用动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 到达某个格子的方法等于到达上方格子与左侧格子的方法和.
# 状态转移方程：f(x,y) = f(x-1, y) + f(x, y-1)
# f(x,y)定义为："到达坐标为(x,y)的格子的不同路径数的总和"
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for i in range(n)] for j in range(m)]
        
        for j in range(1,n):
            for i in range(1,m):
                # 创建一个填满数据的二维数组
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]
    
# 或者
class Solution:
    def uniquePaths(self, m, n):
        path_list = [1] * m
        for i in range(1, n):
            for j in range(1,m):
                path_list[j] += path_list[j-1]
        return path_list[-1]

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

img

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]):
        if not obstacleGrid:
            return 0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        matrix = [[0]*n for i in range(m)]

        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    matrix[i][j] = 0
                else:
                    if i==0 and j==0:
                        matrix[i][j] = 1
                    else:
                        matrix[i][j]=matrix[i-1][j]+matrix[i][j-1]
        return matrix[m-1][n-1]

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

当前单元格的值等于min(左边单元格的值,上面单元格的值)+自己单元格的值

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minPathSum(self, grid):
        path_list = [[0]*len(grid[0]) for _ in range(len(grid))]
        for j in range(len(grid[0])):
            for i in range(len(grid)):
                if i == 0 and j == 0:
                    path_list[i][j] = grid[i][j]
                elif i == 0 and j != 0:
                    path_list[i][j] = path_list[i][j-1] + grid[i][j]   
                elif i != 0 and j == 0:
                    path_list[i][j] = path_list[i-1][j] + grid[i][j]
                else:
                    path_list[i][j] = min(path_list[i-1][j],path_list[i][j-1]) + grid[i][j]
        
        return path_list[-1][-1]

91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

1
2
3
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0
        dp = [1] * (len(s) + 1)
        print(dp)

        for i in range(1, len(s)):
            print('-',i)
            if s[i] == '0':
                if int(s[i - 1]) != 1 and int(s[i - 1]) != 2:
                    return 0
                else:
                    dp[i + 1] = dp[i - 1]
            else:
                if s[i - 1] != '0' and int(s[i - 1:i + 1]) <= 26:
                    dp[i + 1] = dp[i] + dp[i - 1]
                else:
                    dp[i + 1] = dp[i]
        print(dp)
        return dp[len(s)]

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def generateTrees(self, n):
        if n == 0:
            return []

        def generate_from_list(nums):
            if len(nums) == 0:
                return [None]
            if len(nums) == 1:
                return [TreeNode(nums[0])]
            
            roots = []
            for i in range(len(nums)):
                left_trees = generate_from_list(nums[: i])
                right_trees = generate_from_list(nums[i + 1:])

                for left_tree in left_trees:
                    for right_tree in right_trees:
                        root = TreeNode(nums[i])
                        root.left = left_tree
                        root.right = right_tree
                        roots.append(root)

            return roots

        return generate_from_list(list(range(1, n + 1)))