Leetcode笔记

Posted on | Edited on | In ,

进度：

  • array部分差不多
  • string部分提高往后没有继续
  • math部分浅尝辄止
  • 开始搞树的部分

1 twoSum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1
2
3
4
5
6
7


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, item in enumerate(nums):
            if target - item in nums and nums.index(target - item) != i:
                return [i, nums.index(target - item)]

总结：

  • 刚开始用了直接for所有的元素的方法，忘记考虑当两个数字重复的时候需要怎么办，考虑了之后在非常大的数的情况下爆炸了
  • 标准答案说到了hash表，但是其实在python实现里面本身就是个hash（不然怎么从索引得到结果），不需要考虑这个问题
  • 然后考虑了把所有东西都放一个dict里面（毕竟hash？），但是遇到的问题是从value直接得到key会生一些问题。如果把数字作为key，索引作为value会发现数字有重复的，会覆盖key的值
  • 这时候突然发现，如果用数字作为索引的话其实dict和list没有本质区别，在list里面操作就行了，而且list的.index()可以直接返回这个值得坐标（找到的是第一个值！！）
  • 所以直接用enumerate把所有的index和item都列出来就可以解决了，神奇。

27 remove element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3, 2, 2, 3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn’t matter what you leave beyond the returned length.
Example 2:

Given nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn’t matter what values are set beyond the returned length.

1
2
3
4
5
6
7
8
9
10
11
12
13


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        remove_nums = 0
        ori_length = len(nums)
        for i in range(len(nums)):
            if nums[i] == val:
                remove_nums += 1
                nums[i] = float('inf')
        nums.sort()
        nums = nums[:ori_length - remove_nums]
        return len(nums)

总结：

  • 这道题的重点是需要in - place的处理，空间复杂度要求很高（然而我的空间结果很垃圾）。一个重点就是返回的list不需要按照原来的顺序排列
  • 从不需要原来的顺序得到的思路是：我把需要删除的东西的位置改成了inf，然后对所有部分进行排序，得到排序之后的结果再进行切片（这里刚开始的思路是删掉这个地方的东西然后再insert，后来发现直接替换就好了）
  • 其实也可以直接用交换位置的方法，不用切片，因为题目只需要前面的这些元素符合要求就可以了，没有说后面的怎么样。
  • 看了一些discussion都是memory只比5 % 的人少。。。但是差距都不大应该没问题！

看到了一个超级牛逼简要写法：

1
2
3
4
while val in nums:
    nums.remove(val)

return len(nums)

80

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1, 1, 1, 2, 2, 3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn’t matter what you leave beyond the returned length.

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 removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        while(True):
            if i >= len(nums) - 1:
                if len(nums) > 2 and nums[i] == nums[i - 2]:
                    nums = nums[:nums.index(nums[i]) + 2]
                    break
                else:
                    break
            if nums[i] == nums[i + 1]:
                i += 1
            else:
                next_num = nums[i + 1]
                start_index = nums.index(nums[i])
                next_index = nums.index(next_num)
                if next_index - start_index > 2:
                    for l in range(start_index + 2, next_index):
                        nums[l] = float('inf')
                i = next_index

        while float('inf') in nums:
            nums.remove(float('inf'))
        return len(nums)

总结：

  • 我深信我的方法虽然蠢但是没有问题，但是跑出来就是有问题，分明我return之前的数据还都是对的，但是return之后显示的东西就都有问题了
  • 主要思路是这样的
    • 因为in - place操作，所以就不能直接用remove去掉元素导致下标错乱
    • 本来是想和上面的思路一样，换成inf，然后再把有inf的部分删除掉（参考了 # 27的简易解法）
    • 怎么换成inf呢，我判断的方法是找到下一个值得index，然后计算这个index和上一个之间差多少个数，然后把富裕的数字都替换成inf
  • 忽略的问题：
    • 数数数错了很多问题
    • 最开始没有考虑到什么停止
    • 然后没有考虑到如果最后一个数字重复了两遍以上要怎么办的问题（这也是我用next_index的一个弊端）

然后看着大佬的代码哭出了声！！！

1
2
3
4
5
6
7
8
9
10


class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for n in nums:
            if i < 2 or n != nums[i - 2]:
                nums[i] = n
                i += 1
        return i

总结：

  • 哇这个思路真的牛逼！
  • 中心思想就是让n来增加但是i不增加，这里已经说了不在意前面项之后list里面的内容，也就是说前n项之后的东西都不用管了。既然如此的话与其用inf来替换这个位置的数字，不如直接用后面的项填在相对应的位置上，只有填成功了才会增加i
  • 这里需要先判断i的值是否小于2，然后再计算nums[i - 2]，否则会out of range
  • i跑的速度没有超过n跑的速度所以没有关系
  • 合理利用题里面的条件限制真的很重要！！

189 Rotate array

Given an array, rotate the array to the right by k steps, where k is non - negative.

Example 1:

Input: [1, 2, 3, 4, 5, 6, 7] and k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Explanation:
rotate 1 steps to the right: [7, 1, 2, 3, 4, 5, 6]
rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]
rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]

Example 2:

Input: [-1, -100, 3, 99] and k = 2
Output: [3, 99, -1, -100]
Explanation:
rotate 1 steps to the right: [99, -1, -100, 3]
rotate 2 steps to the right: [3, 99, -1, -100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

思路

  • 需不需要注意k = 0的时候
  • 如果k的个数特别大需不需要简化一下
1
2
3
4
5
6
7
8
9
10
11
12


class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        steps = k % len(nums)
        unchange_nums = nums[:len(nums) - steps]
        change_nums = nums[len(nums) - steps:]
        nums[:steps] = change_nums
        nums[steps:] = unchange_nums

总结：

  • 居然第一种就这么写出来了，实际上就是把后面的数字移动到前面去
  • 注意nums不能直接用change_nums + unchange_nums，大概是他认为这个不是in - place了吧

另一种方法：in-place

1
2
3
4
5
6
7
8
9
10
11
12
    k = k % len(nums)
    self.reverse_nums(nums, 0, len(nums) - 1)
    self.reverse_nums(nums, 0, k - 1)
    self.reverse_nums(nums, k, len(nums) - 1)

def reverse_nums(self,nums,start,end):
    while start < end:
        temp = nums[start]
        nums[start] = nums[end]
        nums[end] = temp
        start += 1
        end -= 1
  • 实际上，rotate的另外一种方法是先把整个list反向，然后把前面的k个反向，然后再把后面的(n-k)个反向（这里我是没想到的）
  • 把一个数组反向的算法就是从两头向中间逼近着交换（我该好好去看看基础的算法了。。）
  • 最后，还有一种方法是跳着设置值，也就是说k个之后的值就应该是现在这个位置的值

41 First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.

第一个思路：时间nlog(n)

1
2
3
4
5
6
7
8
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums.sort()
        target = 1
        for n in nums:
            if n == target:
                target += 1
        return target
  • 这个思路整体建立在先排序的基础上，但是排序的时间复杂度本身就已经是nlog(n)了
  • 排序 - 找到比0大的数字从这里开始 - 这个数字不符合的话找下一个
    • 但是我在找比0大的数字的时候还想着把list切片，切片就又需要考虑0啊，1啊，缺多少个数字的问题，空的list。其实根本不用这么麻烦
    • 本质上这个方法就是，找到miss的正数，那就从正数的第一个（1）开始找，如果找到了这个数就继续找下一个（target++），总是能找到的嘛，找到的就是缺的数字了

自己的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 1
        for i in range(len(nums)):
            target_num = i + 1
            if nums[i] == target_num:
                if i == len(nums) - 1:
                    return target_num + 1
                else:
                    continue
            if target_num in nums:
                temp = nums.index(target_num)
                nums[temp],nums[i] = nums[i], nums[temp]
            else:
                return target_num

  • 桶排序：要把对应的数字放在对应的位置上
    • 这道题里应该的样子就是nums[index] = index + 1
  • 大佬的思路 -> 首先判断边界条件！！(学到了学到了)
  • 看过了上面的提示写出来的第二版
    • 判断边界条件
    • 判断这个数字是不是摆在了正确的位置
      • 正确，判断是否是最后一个数字
        • 是，输出的是最后一个数字+1
        • 不是，这个位置的正确了，判断下一个位置
      • 没有，判断nums里面还有没有应该摆在这个位置的数字
        • 有，那就和这个位置交换
        • 没有，那没有的数字就是缺少的数字了
  • 因为每次都是把数字换到了正确的位置了，所以交换最多进行len(nums)次，时间复杂度是O(n)
1
2
3
4
5
6
7
8
9
def firstMissingPositive(self, nums):
    for i in xrange(len(nums)):
        while 0 <= nums[i]-1 < len(nums) and nums[nums[i]-1] != nums[i]:
            tmp = nums[i]-1
            nums[i], nums[tmp] = nums[tmp], nums[i]
    for i in xrange(len(nums)):
        if nums[i] != i+1:
            return i+1
    return len(nums)+1
  • 大佬的另一个方法，其实思路和上面的差不多，就是把数字换到正确的位置上，但是判断的条件和我的有一点不同，可能因为我的是基于python的功能
  • 其中，换到正确位置的数字就是在1到len(nums)之间的数字。nums[i]-1是这个数字应该的坐标位置，如果应该的位置和现在的位置的数字不一样，那就交换这两个数字
    • 注意这里需要用while换，要一直换到正确的位置才可以
  • 这样的结果就是大家都按正确的填好了，最后不对的那个位置的index+1就是需要的结果

299

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows.

Please note that both secret number and friend’s guess may contain duplicate digits.

Example 1:

Input: secret = “1807”, guess = “7810”

Output: “1A3B”

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.
Example 2:

Input: secret = “1123”, guess = “0111”

Output: “1A1B”

Explanation: The 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow.
Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

1
2
3
4
5
6
7
class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bull = sum(a == b for a,b in zip(secret,guess))
        cow = 0
        for x in set(guess):
            cow  += min(secret.count(x),guess.count(x))        
        return str(bull) + "A" + str(cow-bull) + "B"
  • 这里自己想了一些比较蠢的想法之后直接参考别人的了
    • 其一是比对他们两个位置和数字都相同的东西，想要转换成dict来比较，但是后来发现string就可以直接index了不用这么麻烦
    • 想过能不能按位做减法，未果
    • 其二是在得到了bull之后把bull的部分从原来的里面剔除出去然后再比较相似的数字
  • 遇到了主要问题是重复的数字怎么办以及如何剔除出去bull
  • 主要思路是这样的：
    • 其实cow的数量就是bull-cow都是的数量减去bull的数量，也就相当于维恩图里面，只有A的量是A的量 - 同时AB的量。这里是bull就相当于AB都有，两个里面所有重复的数量就相当于A的量
      • 这样可以做减法就解决了上面的从bull得到cow的问题！！
      • 所以说看问题还是要看本质
    • 面对重复的数字，居然可以直接把string转换成set
      • 这里复习一下set好吗！！！这个集合居然可以没有重复的元素，平常我忽视你了呀小可爱，转化成set就不会重复了哦，震惊！！
    • 这样问题就变成了：
      • 求bull：用zip把两个东西一一对应的打包起来（居然还有你小可爱！）直接对比
      • 求both：guess里面猜的次数就是总体的次数，secret里面的次数是真实的次数，对于每个在guess里面（set）的元素都看看分别在两个里面是多少个，然后小的那个就是both的大小
        • 这里介绍.count()小可爱，居然还可以数数！
      • 最后both-bull就是结果了

134 gas station

居然自己搞出来了一个看起来很蠢的

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 canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        if sum(gas) < sum(cost): return -1
        
        tank = 0
        current = 0
        counter = 0
        while(True):
            tank = tank + gas[current] - cost[current]
            if tank < 0:
                if current < len(gas):
                    current = current + 1
                    counter = 0
                    tank = 0
                    continue
                else:
                    return -1
            
            current += 1
            current = current % len(gas)
            counter += 1
            # print(current,counter)
            
            if counter == len(gas):
                return current % len(gas)

  • ~时间超过了百分之48的人，感觉可能还可以吧~时间都是骗人的又跑了一次居然超过了百分之86的！！
  • 重点
    • 一直按着顺序跑，不会跳着走
    • 如果gas的总量从一开始就小于cost的总量，那绝对不可能
  • 我的思路：
    • 从第一个点开始试着跑，一直到试着从最后一个点开始跑，找到了就直接返回
    • 增加一个计数的var，记一共跑了多远，因为是按着顺序跑的所以这个var等于gas的长度的时候就是跑完了
    • 避免out of range问题，需要求余数
  • 遇到问题：
    • 当tank小于0，更新完条件之后记得continue继续循环呀
    • 刚开始想用的判断条件是for或者while里面带条件，还想了一下要不要zip这两个数据，但是都是list实在是没有必要。但是感觉是想的实在是太多了
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: 
        if sum(gas) < sum(cost): return -1
        
        rest = start = 0
        for i in range(len(gas)):
            rest += gas[i] - cost[i]
            if rest < 0:
                start = i + 1
                rest = 0
        return start
  • 居然有这么简要的写法！！
  • 所以只要不是sum(gas) < sum(cost)就一定会有解诶，神奇。也就是说我上面有一个返回的-1是没有意义的
  • 而且用for的话就不用再考虑counter的问题了
  • 从哪里失败就从哪里的下一个爬起来

118 Pascal’s Triangle

Example:

Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        
        if numRows == 0:
            return []
        
        for row in range(numRows):
            now_row = []
            if row == 0:
                now_row = [1]
            elif row == 1:
                now_row = [1,1]
            else:
                now_row = [1]
                for member in range(1,row):
                    now_row.append(result[row-1][member-1] + result[row-1][member])
                
                now_row.append(1)
                
            result.append(now_row)
            
        return result
  • 总算是自己写出来一个东西了
  • 好简单，除了前两行是特定的，其他的可以归为一类
  • 求一个简单的数学关系就行了，数数别数错了！！注意数0
  • 唯一没有注意的点就是：事先不知道list的大小，所以初始化成空的之后需要用append添加元素

119 杨辉三角形2

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

Input: 3
Output: [1,3,3,1]

1
2
3
4
5
6
7
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        L = [1]
        while True:
            if len(L) == rowIndex + 1:
                return L
            L = [u+v for u,v in zip([0]+L,L+[0])]
  • 没想到杨辉三角形的代码也有简要的解法，这个是用L记录了上一行的信息，然后再把这行扩充两个0，相当于这个三角形的本质是两行错位相加！！
  • 注意最后的L得到的是一个list，list要有list的样子
  • 更加理解了一下zip和单行for的用法
  • index从0开始，结果开始没有注意到
  • while true 加上一个 if的效果等同于for的效果！！！越写越糊涂

169 Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]
  • 思路：这回想到了很多历遍的方法，但是感觉太蠢了，终于开始想怎么才能更好的实现了
  • 在写写画画的时候突然考虑到，如果有超过一半的数量都是这个数的话，把这个list排序之后最中间的那个数肯定是这个数
    • 极限情况就是两个元素差1，这时候是多一点的那个数的边界上
    • 其他的情况下就是在出现最多的那个数的中间
  • 本来想要用floor的，但是发现需要math包，所以用了 // 来求除之后的整数

229 Majority Element 2

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        major1,major2,count1,count2 = 0,1,0,0
        
        for n in nums:
            if major1 == n:
                count1 += 1
            elif major2 ==n:
                count2 += 1
            elif count1 ==0:
                major1 = n
                count1 = 1
            elif count2 == 0:
                major2 = n
                count2 =1
            else:
                count1 -= 1
                count2 -= 1
        
        return [n for n in (major1,major2) if nums.count(n) > len(nums) // 3]

  • 注意这道题说的是出现次数大于1/3的数字，所以结果只有只能是没有，1个或者两个，不存在结果是三个的情况！
  • 这个想了半天不会做，查了一下用的是Boyer-Moore Majority Vote algorithm
    • 这个算法的主要意思是如果两拨人打架，打架一对一抵消，然后看看剩下的部分哪个比较多
      • 记录剩下的东西的方法就是增加了一个额外的部分，包括major和count两部分，major记录的是有剩余的数是什么，count记录还有多少个
      • 如果count没有了，那么就从现在遇到的新的数开始记
      • 如果现在的数不是需要的，那么count - 1，如果是现在需要的那么count + 1
    • 最开始是用在一个数组里面找超过一半的数的，但是我上一道题用了其他方法所以没用到
    • 注意因为是求1/3的数字，所以虽然有剩下的，但是剩下的不一定都是符合要求的，需要再数一下个数对不对（这才有了return这一行里面的东西）
  • 人类的算法真是奇幻无穷

274 h-index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining
two with no more than 3 citations each, her h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        result = 0
        for h_cand in range(len(citations) + 1):
            h_more = 0
            for citation in citations:
                if citation >= h_cand:
                    h_more += 1
                if h_more >= h_cand:
                    result = max(result,h_cand)
        return result
  • 思路，非常直观的方法，直接iterate所有的元素，如果找到了更大的result的值就取最大的（根据题目要求）
  • 注意的点在需要 h_more >= h_cand而不是等于，因为给出的定义的意思是index-h是有h个的值大于等于h，h_more的个数会比h_cand多（但是因为取了下面的max，所以等于其实也是可以得）
  • 这个的速度真的好慢，尝试一下binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        bucket = [0 for n in range(len(citations)+1)]
        for nums in citations:
            if nums >= len(citations):
                bucket[len(citations)] += 1
            else:
                bucket[nums] += 1
        
        result = 0
        for nums in range(len(bucket)):
            nums = len(bucket) - nums -1
            result += bucket[nums]
            if result >= nums:
                return nums
        
        return  0
  • 用了桶排序的神奇方法
  • 还是取决于定义，如果一共有5个paper的话，可以选的h的值有6个，分别是0 1 2 3 4 5，把这留个值分成六个桶，每个里面放的就是比这桶的inde等于的paper的数量
    • 如果总数直接大于最大的桶数，就放在最后一个里面
    • 这是在第一个循环干的事情
  • 第二个循环里，把这些桶里面的值取出来就是比这个桶的index大于等于的paper的数量，从后往前数，如果这个paper的数量大于了现在的index，那就说明现在的index就是h！
  • 这里学到了一个创建固定长度列表的方法bucket = [0 for n in range(len(citations)+1)]
1
2
3
4
5
6
7
8
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse = True)
        result = 0
        for i,n in enumerate(citations):
            if n >= i+1:
                result = max(result,i+1)
        return result
  • 再另一种思路，用了排序
    • 如果把这个list按降序排序的话，index的数量加一就是目前数过的paper的数量，citation[index]就是这个数量上面对应的citation的数量，这两个值应该正好相等，或者citation更大一点，需要在排好序的内容里面找到这一项！
  • 这样速度比桶排序稍微慢一点但是还是蛮快的，起码比第一种要快很多了

275 h-index 2

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        l, r = 0, n-1
        while l <= r:
            mid = (l+r)//2
            if citations[mid] >= n-mid:
                r = mid - 1
            else:
                l = mid + 1
        return n-l
  • 可以依然沿用上面的方法，但是可能是因为数据量上去的原因，所以速度变慢了
  • 这里可以加入二分法搜索取代上面的直接iterate
    • while的条件是因为移动一位，所以会出现l>r的情况，在这种情况下就可以停下来了
    • 二分法就是这么写的！

217 contains duplicate

1
2
3
4
5
6
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for n in nums:
            if nums.count(n) >= 2:
                return True
        return False
1
2
3
4
5
6
7
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        setNums = set(nums)
        if len(setNums) == len(nums):
            return False
        else:
            return True
  • 消耗时间太长了！！
  • 说明这个count的时间还是不可以
  • 想到了用set但是没相当怎么用set
    • set可以把有重复内容的变成没有重复内容的！！
    • 所以set和list的长度是不一样的

219 contains duplicate2

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if len(set(nums)) >= len(nums):
            return False
        extra = {}
        for i,n in enumerate(nums):
            if n in extra and i-extra[n] <= k:
                return True
            extra[n] = i
        
        return False
  • 注意这里需要找到的差的绝对值是最大是k，所以找到一个比k小的很容易！！只要找到就能返回
  • 判断边界条件
  • 把元素作为key放进extra里面，val是这个元素的index，因为key是唯一的所以可以一直找到离得最近的index，这样就越来越能确保满足条件，一旦满足条件就返回，如果所有的都不满足就false

220

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0: return False
        buckets = {}
        for i in range(len(nums)):
            bucket = nums[i] // (t+1)
            if bucket in buckets:
                return True
            elif bucket - 1 in buckets and nums[i] - buckets[bucket-1] <= t:
                return True
            elif bucket + 1 in buckets and buckets[bucket+1] - nums[i] <=t:
                return True
            buckets[bucket] = nums[i]
            
            if i >= k:
                del bucket[nums[i-k] // (t+1)]
        return False
  • 运用的是桶排序的思路，每个nums[i]会放在一个桶里，这个桶的宽度是这两个数字的差
    • 如果想要这两个数值的差值小于等于t，那么需要这两个数字在一个桶里或者在相邻的桶里（因为后面增加了k的判断条件，所以不用考虑k）

  • 思路

    • 首先考虑了一下k，如果i大于k的时候，就可以直接扔掉i-k之前的数据了，只考虑中间的k+1个数据，这样的话空间复杂度很低。这里的扔掉指的是把bucket里面的值直接扔掉，这样就避免了找到在相同的桶里面却i和j的差值超过k的问题
    • 首先iterate整个nums，把不同的数字放在不同的桶里，注意桶的个数是t+1
    • 然后如果在放之前这个桶有东西，或者相邻的桶的值和现在的值的差是小于等于t的，那么就存在，返回true
    • 如果都不存在的话，把现在的数字放到对应的桶里面

  • 另外一个思路考虑的是二叉树的数据结构，用这个结构可以很快的搜索到离这个数最近的数据并且判断这个数据和这个数的差是不是小于t！

55 Jump game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if nums is []: return False
        if len(nums) == 1: return True
        current = len(nums) - 1
        while current >= 0:
            flag = False
            for i in range(0,current):
                if current - i <= nums[i] and current >= i:
                    flag = True
                    current = i
                    if current == 0:
                        return True
            if flag == False:
                return False
  • 虽然超时了但是写的还不错的iterate
  • =。=算了这就是一坨屎！！！
1
2
3
4
5
6
7
8
9
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        current = len(nums) - 1
        for i in range(len(nums))[::-1]:
            if current - i <= nums[i]:
                current = i
                if current == 0:
                    return True
        return False
  • 我的方法其实思路是没有问题的，主要在于太啰嗦了而且循环太多了，其实直接从后往前找就行了！！！从后往前找不用考虑怎么让他循环起来呀，直接一个一个往前推就可以了
  • 前面那个的问题在于多叠了一个while，于是时间瞬间爆炸，写前面的那个的时候也在想着如何找回循环里面去，结果还是用了个蠢办法
1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        j = 0
        for i,n in enumerate(nums):
            if j < i: return False
            j = max(i+n,j) 
        return True
  • i+n就是从这步开始可以移动的最大距离，j是上一步可以移动的最大距离，这两个哪个大就走哪个
  • 如果这个距离还赶不上i，那就说明走不到最后了，告辞

45 Jump game 2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1: return 0
        start, end = 0, 0
        step,maxend = 0,0
        while True:
            step += 1
            for i in range(start, end+1):
                if i+nums[i] >= len(nums) -1: return step
                maxend = max(maxend, i + nums[i])
            start = end + 1
            end = maxend
  • 实际上来说用的是BFS的思想，但是不是每次都把东西从queue里面拿出来，而是确定了每次寻找的开始的阀内
  • start和end分别代表现在可以开始寻找的开始和结束，如果在这个范围里面找到了符合要求的结果，那么直接返回这个步数，如果没找到的话就从下一个范围开始找，下一个范围是上一个范围的end+1 到目前能到的最大的范围
  • 注意符合的要求是大于等于n-1而不是正好走到这个点
  • 求maxend和之前的一样

121 Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minBuy = float('inf')
        maxProfit = 0
        for i in prices:
            if i < minBuy:
                minBuy = i
            elif i - minBuy > maxProfit:
                maxProfit = i - minBuy
        return maxProfit
  • 用brute的算法会time limit，这里用的方法是用两个变量分别记录最低的价钱和最高的利润，这样的话只需要对数组遍历一次就能得到最终的结果
  • 因为判断这个价钱低了的话，求这个东西的最大利润也就只能用这个最低价钱之后的东西求了，所以不会冲突

122

  • 现在可以进行多次交易了，但是每次之间不能重叠
  • 其实只要后一次比前一次贵，这个profit就可以一直累计，分为一直上涨或者中间掉下来一下再重新买的感觉
1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                maxProfit += prices[i] - prices[i-1]
        return maxProfit

123

  • 现在最多进行两次交易,找到最大的利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost_1 = float('inf')
        profit_1 = 0
        cost_2 = float('inf')
        profit_2 = 0
        
        for price in prices:
            cost_1 = min(cost_1,price)
            profit_1 = max(profit_1, price - cost_1)
            cost_2 = min(cost_2,price - profit_1)
            profit_2 = max(profit_2, price - cost_2)
        
        return profit_2
  • 其中，下标带1的是第一次交易之后的结果，下标带2的是第二次交易之后的结果
  • 从总体上来看，第二次买入之后花掉的钱实际上是第二次买入的实际花费 - 第一次交易之后挣的钱（可以是负数）。而第二次卖出之后的总的收益为 第二次卖出的钱 - 第二次买入之后的实际花费
  • 所以，如果需要利润最大，需要第二次买入的实际花费最小，需要第一次的利润最大，需要第一次买入的花费最小，最终形成了这个代码

188

  • 现在需要进行最多k次交易，把profit弄到最大
  • 这部分好像大家都用到了DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n < 2: return 0
        if k >= n/2:
            return sum(i-j for i, j in zip(prices[1:],prices[: -1]) if i > j)
        profits = [0] * n
        for _ in range(k):
            preprofit = 0
            for i in range(1,n):
                profit = prices[i] - prices[i-1]
                preprofit = max(preprofit + profit, profits[i])
                profits[i] = max(preprofit, profits[i-1])
        return profits[-1]
  • 首先考虑边界条件，如果k的数量已经比n/2大了，那么可以直接认为可以进行无限次交易了，就和上面的第二题一样
  • 主要思路就是现在定义了两个变量，一个变量表示在前i天完成的交易，已经得到的最大利润。另一个变量定义了在第i天卖出的话，这时候得到的最大利润。这两个变量的都是在在第j次交易里。
  • 用一个长n的list profits来记录这个天数之后获得的利益。在k次交易中一直更新这个profits里面的最大值。所以实际上关于k的变量不需要考虑
  • 首先分析在第i天得到的利润，就是这一天的价格减去前一天的价格。更新之前i天里面的总利润，就是把最开始的preprfit再加上这一天获得的利润，和本来的preprofit来比大小，更新preprofit
  • 更新实际上第i天的利润，对比实际上前一天的利润和前i天的利润哪个大

309 中间带冷却的买股票

  • 每次卖出去之后必须要cooldown一轮
  • 用了dp和state machine来表示，一共会有三种状态
    • s0(reset) -sell-> s1 -cool-> s2(reset) -buy-> s0
    • 用一个数组来记录在每天在这个状态里面的最大利润，然后再从最后一天的最大利润里面挑出来一个
  • 注意考虑边界条件
  • 学会了一个新的初始化list的方法
  • 感觉自己终于理解了dp呢（并没有）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            n = len(prices)
            if n < 2:
                return 0
            s0,s1,s2 = [0]*n,[0]*n,[0]*n
            s0[0] = -prices[0]
            s1[0] = float('-inf')
            s2[0] = 0
            for i in range(1,n):
                price = prices[i]
                s0[i] = max(s0[i-1],s2[i-1] - price)
                s1[i] = s0[i-1] + price
                s2[i] = max(s1[i-1],s2[i-1])
            
            return max(s0[n-1],s1[n-1],s2[n-1])

11 装水

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        start, end  = 0, n-1
        maxArea = 0
        while start < end:
            if height[start] >= height[end]:
                maxArea = max(maxArea,height[end] * (end-start))
                end -= 1
            else:
                maxArea = max(maxArea,height[start] * (end-start))
                start += 1
        return maxArea
  • 这道题的重点在这个装水的大小是由比较短的那条边决定的。而且肯定是底边越长越牛逼，所以从底边最长的两边开始找，然后在两个高度里面取比较大的继续找下一个
  • 需要用一个变量来储存 max area的大小（这个我想到了）
  • 然后比较快的方法是从两遍开始逼近，这样的话只遍历了这个list一次，时间复杂度是n，好像有个排序算法和这个的想法也差不多
  • 注意while的判断条件其实就是这个

42 装水

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n < 2:
            return 0
        left_max,right_max = [0]*n,[0]*n
        left_max[0],right_max[-1] = height[0],height[-1]
        maxTrap = 0
        for i in range(1,n):
            left_max[i] = max(left_max[i-1],height[i])
        for i in reversed(range(0,n-1)):
            right_max[i] = max(right_max[i+1],height[i])
        for i in range(n):
            maxTrap += min(left_max[i],right_max[i]) - height[i]
        
        return maxTrap
  • 用dp解决的这个问题
  • 核心思想在竖着（按列）数每个格子，这个格子可不可以装水和左右两边的最高点有关，这个格子能装多少水和1.最短的高点和2.这个格子本身的高度有关
  • 所以可以用三个循环搞定这个问题，用空间换时间，在list里面记录下来每个列对应的左边的最高点和右边的最高点，然后再数每个列的容量，大小是（左右最高中间短的那个） - （这个列对应的高度）

334 升序的三个数字

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        first = float('inf')
        second = float('inf')
        third = None
        for i,num in enumerate(nums):
            if num <= first:
                first = num
            elif num > first and num <= second:
                second = num
            else: third = num
        
        return (third != None)
  • 我最初的思路没有错，需要有变量来保存这三个升序的东西
  • 其实核心的思路在于，如果现在这个数比第一个升序的数字小，那么这个数字完全就可以成为新的第一个数字，比如 3 2 4 5，那么345和245没有什么本质的区别，而一旦third有了取值，那么就说明肯定已经有了一个结果

128

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 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
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
#         if nums == []: return 0
#         max_num = max(nums)
#         min_num = min(nums)
#         if max_num > len(nums) or -max
#         if min_num < 0:
#             max_num -= min_num
#         ass_list = [None] * (max_num + 1)
#         for i,num in enumerate(nums):
# #             确保都是正数
#             if min_num < 0:
#                 num = num-min_num
#             ass_list[num] = 1
        
#         max_length = 0
#         prev_length = 0
#         for i in range(len(ass_list)):
#             if ass_list[i] != None:
#                 max_length += 1
#             else:
#                 prev_length = max(max_length,prev_length)
#                 max_length = 0
#         return max(max_length,prev_length)
        if nums == []: return 0
        current_length,prev_length = 1,1
        num_set = set(nums)
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                while current_num+1 in num_set:
                    current_num += 1
                    current_length += 1
                prev_length = max(prev_length,current_length)
                current_length = 1
        return max(current_length, prev_length)
  • 这个问题一开始的思路是错的，已经comment掉了，但是感觉这个想法其实就是更具体化的hash表而已，第一个思路是把所有的数字平均的放在一个list里面，然后每个数字的本身就对应的是他的index，这样的话就可以直接知道有哪些数字是连续的了。但是这种方法在数字特别大的时候空间上就爆炸了，空间复杂度也是和数字大小有关
  • 这时候又要拿出来快乐的hash表了，记住python自己自带hash表
  • 每遇到一个数字，需要判断这个数字的下一个数字在不在这个nums里面，如果在的话更新数字和长度，如果不再的话刷新计数器并且开始下一个数字
  • 但是直接这样算还是会时间爆炸（比如一堆连续的只有一个是跳开的），所以又加进去了一个新的判断条件，这个条件的精髓在于，如果这个数之前的数字在nums里面，那么这个数在算他前面那个数的时候就应该被算上了，所以这部分就可以跳过这个数了，只有当前一个数字不在的时候才需要数长度

164

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
(3,6) or (6,9) has the maximum difference 3.
Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        nums.sort()
        max_gap = 0
        
        if len(nums) < 2: return 0
        
        for i in range(1,len(nums)):
            gap = nums[i] - nums[i-1]
            max_gap = max(max_gap, gap)
        
        return max_gap
  • 直接用python自带的排序速度不一定很慢，虽然只超过了百分了20的人但是最后还是跑出来了
  • 这个方法非常直接了
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
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2: return 0
        max_num, min_num = max(nums), min(nums)
        if max_num == min_num: return 0
        
        wide = max((max_num - min_num) // (n-1),1)
        num_b = (max_num - min_num) // wide + 1
        
        maxGap = 0
        # prev_bucket = float('-inf')
        max_b = [0]* num_b
        min_b = [float('inf')]* num_b
        
        for i, num in enumerate(nums):
            idx = (num-min_num) // wide
            max_b[idx] = max(max_b[idx],num)
            min_b[idx] = min(min_b[idx],num)
        
        
        prev_max = max_b[0]
        for i in range(1,num_b):
            if max_b[i] == 0:
                continue
            maxGap = max(maxGap,min_b[i] - prev_max)
            prev_max = max_b[i]
        return maxGap
  • 这个桶排序终于写出来了，基本思路是上面的截图，需要注意的有几点
    • 第一，python不导入math的话没办法求ceiling，但是可以用 -（-a // b）来求
    • 第二，在求bucket的个数的时候，需要多加上一个bucket，因为一个bucket里面最后的数字是放在下一个bucket里面最前面的
    • 第三，可能会有空的bucket，所以不能直接用这个的min减去上一个的max，必须要留一个变量保存上一个的max
    • 第四，当所有数字都相同的时候会变得很麻烦，最后加上去一个条件过滤掉这个部分

28 implement strStr（）

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:

Input: haystack = “aaaaa”, needle = “bba”
Output: -1

1
2
3
4
5
6
7
8
9
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "": return 0
        
        for i, ch in enumerate(haystack):
            if ch == needle[0]:
                if needle == haystack[i:i+len(needle)]:
                    return i
        return -1
  • 刚开始特别快乐的暴力破解了，真是万万没想到
  • 感觉python处理起来字符串是真的开心
  • 但是这个的时间不是很快乐
  • 关于字符串匹配有另外两个算法KMP和BM（BM更快一点）

14

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:

Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0: return ""
        if len(strs) == 1: return strs[0]
        LCP = self.compare(strs[0],strs[1])
        for i in range(2,len(strs)):
            LCP = self.compare(LCP,strs[i])
        
        return LCP
    def compare(self,a,b):
        i = j = 0
        counter = 0
        while i < len(a) and j < len(b):
            if a[i] == b[i]:
                counter += 1
            else: break
            i += 1
            j += 1
        if counter == 0: 
            return ""
        else: return a[:counter]

  • 思路：平行比较，先找出来前两个里面的prefix，然后再用这个prefix和第三个东西比较
  • 注意输入的长度是1的时候，需要输出整个字符串
  • 注意如果比较失败了的话，要直接停止比较！

58

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: “Hello World”
Output: 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        if len(s) == 0: return 0
        while s[-1] == " ": 
            s = s[:-1]
            if len(s) == 0: return 0
        new_str = s.split(" ")
        # return new_str
        print(new_str)
        return len(new_str[-1])
        # cnt = 0
        # for v in reversed(s):
        #     if v.isspace():
        #         if cnt: break
        #     else: cnt += 1
        # return cnt

  • 原来运行时间也很玄学
  • 但是还是别人的代码看起来厉害一点！

387

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = collections.Counter(s)
        
        index = 0
        for ch in s:
            if count[ch] == 1:
                return index
            else:
                index += 1
        return -1

  • 居然有这么个东西叫做counter，感到震惊！！！

383

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

  • 这个题目也太写意了吧，意思就是我需要写一个勒索信，然后要从杂志上面找单词，看看能不能用杂志上面的东西拼凑出来这个单词

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
        def canConstruct(self, ransomNote: str, magazine: str) -> bool:
            alphabet = [0]*26
            for ch in magazine:
                index = ord(ch) - ord('a')
                alphabet[index] += 1
            for ch in ransomNote:
                index = ord(ch) - ord('a')
                alphabet[index] -= 1
                if alphabet[index] < 0: return False
            return True

  • 看到了一个清奇的思路然后自己实现了一下

    • 统计magazine里面每个字母的数量，和需要的字母数量对比，如果不够的话就不行
    • 我在写的时候多iteration了一次26个字母，但是其实在ransomNote里面直接对比和0的大小就可以了
    • 感觉字母和数字最大的区别就在于字母有限而数字无限

344

reverse一个list，要求in-place而且占用o1的空间

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        length = len(s)
        for i in range(length // 2):
            temp = s[i]
            s[i] = s[length - 1 - i]
            s[length - 1 - i] = temp

  • 其实可以不用temp的，直接用 s[i]，s[length - 1 - i] = s[length - 1 - i], s[i]就可以了

151

reverse一个string，让这句话倒过来，主要会有多个空格

1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.split()[::-1])

  • python真的是很作弊了
  • split不加参数就可以直接分开所有大小的空格

70 爬楼梯 DP

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        elif n ==0: return 0
        elif n == 2: return 2
        f = (n+1)*[0]#走n节的时候可以有的方法数量
        f[1] = 1
        f[2] = 2
        for i in range(3,n+1):
            f[i] = f[i-1] + f[i-2]
        
        return f[n]
  • 其实就相当于斐波那契数列，第i种的可能的方法是从i-2走一个2，以及从i-1走一个1的和

345

把一个string里面的原因反序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = "AEIOUaeiou"
        index = []
        for i, j in enumerate(s):
            if j in vowels:
                index.append(i)
        s = list(s)
        i,j = 0,len(index)-1
        while i<j:
            s[index[i]],s[index[j]] = s[index[j]],s[index[i]] 
            i += 1
            j -= 1
        return "".join(s)
  • 首先判断哪个是原因
  • 然后把元音的部分倒过来
  • .join把list转回string

205 Isomorphic Strings

Easy

767

217

Favorite

Share
Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = “egg”, t = “add”
Output: true

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        n = len(s)
        sub_1,sub_2 = [0]*256,[0]*256
        for i in range(n):
            a,b = s[i],t[i]
            if sub_1[ord(a)] != sub_2[ord(b)]:
                return False
            sub_1[ord(a)] = i + 1
            sub_2[ord(b)] = i + 1
        return True

  • 注意这里面的mapping不一定是字母，也可以是数字
  • ascii码一共是256个，所以是不会超出这个范围的
  • 主要思路就是这样的，两个数组分别记录的是对应位置的ascii码的mapping的位数，如果这两个位数不一样的话，就说明这两个的mapping方式有问题，所以return False，不然的话return True

290 word pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = “abba”, str = “dog cat cat dog”
Output: true

1
2
3
4
5
class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        pattern = list(pattern)
        string = str.split(" ")
        return len(set(zip(pattern,string))) == len(set(string)) == len(set(pattern)) and len(pattern) == len(string)

  • 又到了活用zip的时候，返回的是一个个对应的东西，也就是说返回的是
    • a-dog,b-cat,b-cat,a-dog
    • 这时候把他们转化成set，得到的就是不带重复的东西的长度
  • 如果匹配上的长度和原先的长度全都相同（去掉重复的元素），那么就证明匹配上了

49 变位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # for i,item in enumerate(strs):
        #     item = list(item)
        #     item.sort()
        #     item = "".join(item)
        #     temp[i],temp_sort = item,item
        # temp_sort.sort()
        # print(temp,strs)
        
        d = {}
        for word in strs:
            key = "".join(sorted(word))
            if key in d:
                d.get(key).append(word)
            else:
                d[key] = [word]
            # d[key] = d.get(key,[]) + [word]
        return d.values()
  • 核心思想 -> 排序，排序之后的变位词就都一样了
  • leetcode 242,49
    • 这个题的核心思路就是，每个单词按字母顺序排序之后的答案就是这个单词的key，如果两个单词的key一样的话这两个单词就是变位词，如果不一样的话就是新的词
    • 在python里面直接用字典可以很好的储存变位词

56 merge intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

1
2
3
4
5
6
7
8
9
10
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x : x[0])
        output = []
        for i in intervals:
            if output and i[0] <= output[-1][1]:
                output[-1][1] = max(output[-1][1], i[1])
            else:
                output.append(i)
        return output
  • 注意点：
    • 给的数据输入并不一定是排好序的，所以需要先排好序。这里用到了排序的key的功能。lambda是定义任意函数 g(x)= x[0]
    • 需要输出的格式是list套list，所以需要append
  • 思路错了的一个方向是，其实每个i不应该和隔壁的i比大小，而是应该和output里面的最终结果比大小，因为需要考虑到好几个内容都可以合并的情况

57插入

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
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        out = []
        adding = False
        if len(intervals) == 0: return [newInterval]
        if newInterval[1] < intervals[0][0]:
            out.append(newInterval)
            adding = True
        for i in intervals:
            if adding is False:
                if newInterval[0] > i[1]:
                    out.append(i)
                elif newInterval[1] < i[0]:
                    out.append(newInterval)
                    adding = True
                else:
                    after_insert = [min(i[0],newInterval[0]),max(i[1],newInterval[1])]
                    out.append(after_insert)
                    adding = True
                # print("adding")
            if adding is True:
                if i[0] > out[-1][1]:
                    out.append(i)
                else:
                    out[-1][1] = max(out[-1][1],i[1])
        if adding is False:
            out.append(newInterval)
        return out
  • 自己苦思冥想了一个多小时的答案
  • 有点繁琐，debug的时候主要是情况考虑的不够明确，包括没有考虑空的情况，在最后插入的情况，在最前插入的情况
  • 但是最后总结的想，应该对插入的前后一视同仁，因为状况其实是差不多的，而我把前面分成了好多种状况，后面倒是写成了一种情况
1
2
3
4
5
6
7
8
9
10
11
12
13
left = []
right = []
s,e = newInterval[0],newInterval[1]

for i in intervals:
    if i[1] < s:
        left.append(i)
    elif i[0] > e:
        right.append(i)
    else:
        s = min(i[0],s)
        e = max(i[1],e)
return left + [[s,e]] + right
  • 这是discussion里面的一种简要的解法，思路的不同就是他是每次都merge到new里面了（也就是s和e），而我是merge到out里面了
  • 其实我的代码本身的也有merge到new的意思，但是被我分出了太多种太复杂的情况

101对称树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        now = []
        if root:
            now.append(root)
        while now:
            vals = []
            for i in now:
                if i:
                    vals.append(i.val)
                else:
                    vals.append(None)
            if list(reversed(vals)) != vals: return False
            else:
                now = [j for i in now if i for j in (i.left, i.right)]
        return True
  • 遍历的方法，最后一个now的表达式值得学习
  • 注意root是node，而这个node实际的值在vals里面，因为好久没处理node了所以忘记了这一点
1
2
3
4
5
6
7
8
9
10
def isSymmetric(self, root: TreeNode) -> bool:
    
    def Symm(L,R):
        if L and R:
            return L.val == R.val and Symm(L.left,R.right) and Symm(L.right,R.left) 
        else:
            return L == R
            # return L is None and R is None #同等意义
    return Symm(root, root)
    # 没有关于空的树的判断条件，所以需要从root开始
  • 这个方法过于优雅，我要哭出来了

87 Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great

/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat

/ \
rg eat
/ \ / \
r g e at
/ \
a t

  • 思路：
    • 首先，如果我这个单词的substring满足这个要求的话，上面一层的单词就满足这个要求，也就是说可以recursive的完成这个工作，对于不同的substring call这个函数来检验是否满足要求
    • 边界条件：
      • 如果string的长度小于等于2，那么怎么换其实都是满足的
      • 如果两个string直接相等，那么也是满足的
    • 先决条件：
      • 如果这两个string的长度都不一样，那么肯定也不一样
      • 如果这两个string里面字母的sort之后都不一样，那么肯定不一样
    • 判断条件：
      • 对于一个string，如果从k位置来分的话，有两种不同的结果。or关系
        • 结果1：s1的前k个和s2的前k个一样 and s1的后n-k个和s2的后n-k个一样
        • 结果2：s1的前k个和s2的后k个一样 and s1的前n-k个和s2的前n-k个一样
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n1,n2 = len(s1),len(s2)
        if n1 != n2 or sorted(s1) != sorted(s2): return False
        if n1 <= 2 or s1 == s2: return True
        f = self.isScramble
        for i in range(1,n1):
            if (f(s1[0:i], s2[0:i]) and f(s1[i:],s2[i:])) or \
            f(s1[0:i], s2[n2-i:]) and f(s1[i:],s2[0:n2-i]):
                return True
        return False

38 count and say

The count-and-say sequence is the sequence of integers with the first five terms as following:

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
    1 is read off as “one 1” or 11.
    11 is read off as “two 1s” or 21.
    21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

自己的智障解法

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
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1: return "1"
        
        result = [1]
        for i in range(2,n+1):
            result = self.Say(result)
        return result
            
    
    def Say(self,num):
        n = len(num)
        counter = 1
        counters = ""
        nums = str(num[0])
        for i in range(1,n):
            if num[i] == num[i-1]:
                counter += 1
            else:
                counters += str(counter)
                counter = 1
                nums += str(num[i])
        counters += str(counter)
        result = ""
        for i in range(len(counters)):
            result += counters[i]
            result += nums[i]
        return result

  • 注意，如果要把list接成string，需要先把里面的所有项都转成string
  • 感觉自己还是很不擅长recursive

#316 remove deplicate letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: “bcabc”
Output: “abc”
Example 2:

Input: “cbacdcbc”
Output: “acdb”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # s = sorted(s)
        # i = 0
        # for n in s:
        #     # print(n,i,s[i-1])
        #     if i < 1 or n != s[i-1]:
        #         s[i] = n
        #         i += 1
        # return "".join(s[:i])
        s = list(s)
        result = []
        last_occurrence = {c: i for i, c in enumerate(s)}
        for i,n in enumerate(s):
            if n not in result:
                while result and n < result[-1] and result[-1] in s[i:]:
                    result.pop()
                result.append(n)
        return "".join(result)
  • 这道题里面的重点在lexicographical order
    • 也就是说，在操作的时候，如果这个字母在后面的位置上出现了，但是放在前面的位置上会导致前面变大，那么就取后面的那个结果
  • 本来我想的是可以先把没出现过的放进去，然后再刷新。但是直接放最好的应该更好一些
  • 几种情况：
    • 如果已经出现了：那么直接跳过
    • 如果没出现：
      • 如果比之前的小，并且前面的那个在后面还有，就得往前顶。还要考虑顶没了的情况，也就是result不为空
      • 这里注意这三个条件是并列的，需要同时and。我刚开始把在后面出现放到循环里面去了，所以死循环了
      • 在上面顶完之后，再把最新的加到最后

168 excel column title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def convertToTitle(self, n: int) -> str:
        result = []
        while n > 0:
            letter = n % 26
            n = n // 26
            if letter == 0:
                letter = 26
                n = n-1
            result.append(letter)
        result = result[::-1]
        for i,item in enumerate(result):
            item += 64
            item = str(chr(item))
            result[i] = item
        # print(result)
            
        return "".join(result)
  • 自己的傻逼方法：
    • 最先得到的余数应该是最后的字母的值，所以这里出来的result需要翻转一下
    • 翻转list最快的方法是 [::-1]
    • str(chr(n))把数字转成char，ord把char转成数字，大写A是65，小写a是97
1
return "" if num == 0 else self.convertToTitle((num - 1) / 26) + chr((num - 1) % 26 + ord('A'))
  • 大佬的一行
  • 忘记了这种str的连接方法
  • 直接减-1计算更方便

171 Excel Sheet Column Number

1
2
3
4
5
6
7
class Solution:
    def titleToNumber(self, s: str) -> int:
        # s = s[::-1]
        # result = 0
        # for i,item in enumerate(s):
        #     result += 26^(i) + (ord(item) - ord("A"))
        return 0 if s == "" else self.titleToNumber(s[:-1]) * 26 + ord(s[-1]) - ord("A") + 1
  • 上面那道题的友情题，模拟大佬写出了解法
  • 注意list的上限，到-1的话是到-2不包括-1

13 roman to integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def romanToInt(self, s: str) -> int:
        trans = {
            "I":1,
            "V":5,
            "X":10,
            "L":50,
            "C":100,
            "D":500,
            "M":1000
        }
        
        s = s.replace("IV","IIII").replace("IX","VIIII")
        s = s.replace("XL","XXXX").replace("XC","LXXXX")
        s = s.replace("CD","CCCC").replace("CM","DCCCC")
        
        result = 0
        for c in s:
            result += trans[c]
        return result

  • 比较典型的用dict解决的例子，善用string里面的replace方法

12 int to roman

上面的友情题

  • 虽然可以穷举实现，但是我骄傲的自己写出来了recursive的方法
  • 需要注意字母的替换顺序，不然会换错
    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
    class Solution:
        def intToRoman(self, num: int) -> str:
            space = ["M", "D", "C", "L", "X", "V", "I"]
            trans = {
                "I": 1,
                "V": 5,
                "X": 10,
                "L": 50,
                "C": 100,
                "D": 500,
                "M": 1000
            }
            s = self.find_raw(num, 0, space, trans)

            s = s.replace("DCCCC", "CM").replace("CCCC", "CD")
            s = s.replace("LXXXX", "XC").replace("XXXX", "XL")
            s = s.replace("VIIII", "IX").replace("IIII", "IV")

            return s

        def find_raw(self, num, name, space, trans):
            if num < 5:
                return num * "I"
            else:
                temp = (num // trans[space[name]]) * space[name]
                after = self.find_raw(
                    num % trans[space[name]], name + 1, space, trans)
                return temp + after


    s = Solution()
    print(s.intToRoman(9))

273 int to english

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 numberToWords(self, num: int) -> str:
        t0to19 = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven",
                  "Twelve", "Thirteen", "Fourteen",
                  "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["Twenty", "Thirty", "Forty", "Fifty",
                "Sixty", "Seventy", "Eighty", "Ninety"]

        def word(num, i = 0):
            if num == 0:
                return [""]
            if num < 20:
                return [t0to19[num]]
            if num < 100:
                return [tens[num // 10 - 2]] + word(num % 10)
            if num < 1000:
                return [t0to19[num // 100]] + ["Hundred"] + word(num % 100)
            else:
                trans = {"Billion": int(1e9), "Million": int(
                    1e6), "Thousand": int(1e3)}
                part = ["Billion", "Million", "Thousand"][i]
                if num // trans[part] == 0:
                    return word(num % trans[part], i + 1)
                else:
                    return word(num // trans[part]) + [part] + word(num % trans[part], i + 1)
        s = word(num, 0)
        while "" in s:
            s.remove("")
        return " ".join(s) or "Zero"
  • 注意移除空项的时候，需要用while而不是if
  • 因为最后需要空格连接，所以最好先扔到list里面再出来
  • 这题也太傻比了=。=无论怎么样都要自己手打这么多东西

# 68 text justification

需要把这一行字左右对齐

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
39
40
41
42
43
44
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        # 每一行填满，如果填不满的时候，词的中间的空格尽量平均
        # 最后一行右边加空格
        
        # 每读一个单词后面需要加一行
        space = 0
        line = [0] # 每一行开头的单词的坐标
        for i, word in enumerate(words):
            if space + len(word) < maxWidth:
                space += len(word) + 1
            elif space + len(word) == maxWidth and i != len(words) - 1:
                space = 0
                line.append(i + 1)
            elif space + len(word) > maxWidth:
                space = len(word) + 1 #注意这里的长度变化了
                line.append(i)
        output = []
        for i in range(len(line)):
            if i < len(line) - 1:
                s = ""
                this_line = words[line[i]:line[i+1]]
                length = -1 # 最后一个单词不带空格
                for w in this_line:
                    length += len(w) + 1
                if len(this_line) == 1:
                    s = this_line[0] + (maxWidth - len(this_line[0])) * " "
                else:
                    space_len = (maxWidth - length) // (len(this_line) - 1)
                    extra_space = (maxWidth - length) % (len(this_line) - 1)
                    for i,w in enumerate(this_line):
                        if i < len(this_line) - 1:
                            s = s + w + " " + space_len*" "
                            if i <= extra_space - 1:
                                s = s + " "
                        else:
                            s = s + w
                output.append(s)
            else:
                this_line = words[line[i]:]
                s = " ".join(this_line)
                s = s + " "*(maxWidth-len(s))
                output.append(s)
        return output

  • 思路
    • 先分开单词
    • 再往里插空格

6

把整数转过来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def reverse(self, x: int) -> int:
        Positive = True
        x2 = []
        if str(x)[0] == "-":
            Positive = False
            x = int(x - x * 2)
        while x >= 10:
            num = x % 10
            x = x // 10
            x2.append(str(num))
        x2.append(str(x))
        output = "".join(x2)
        output = int(output)
        if Positive:
            output = int(output)
        else:
            output = int(output) - 2 * int(output)
        if output > 2**31 - 1 or output < -2**31:
            return 0
        else:
            return output

  • 注意啊2的31次方不是2e31啊啊我在干什么

165. Compare Version Numbers

  • 比较两个版本号，需要忽略里面的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
    35
    36
    class Solution:
        def compareVersion(self, version1: str, version2: str) -> int:
            v1 = version1.split(".")
            v2 = version2.split(".")
            v1 = [int(x) for x in v1]
            v2 = [int(x) for x in v2]
            # 可以简化为两行
            # versions1 = [int(v) for v in version1.split(".")]
            # versions2 = [int(v) for v in version2.split(".")]
            if len(v1) > len(v2):
                length = len(v2)
            else:
                length = len(v1)
            
            for i in range(length):
                c1,c2 = v1[i],v2[i]
                if c1 > c2:
                    return 1
                elif c1 < c2:
                    return -1
                end = i
            
            rest1,rest2 = v1[i+1:],v2[i+1:]
            if sum(rest1) == sum(rest2): return 0
            elif sum(rest1) > sum(rest2): return 1
            elif sum(rest1) < sum(rest2): return -1

            # 另一种方法，更简洁
            # for i in range(max(len(versions1),len(versions2))):
            #     v1 = versions1[i] if i < len(versions1) else 0
            #     v2 = versions2[i] if i < len(versions2) else 0
            #     if v1 > v2:
            #         return 1
            #     elif v1 < v2:
            #         return -1;
            # return 0;

  • 需要考虑的主要就是长度不一样的情况和塞0的情况，我的想法是取比较小的总长度，然后再比较剩余的

  • 大佬的情况是比较的所有的长度，如果超过了现在的长度就直接设置为0，这样不会影响比较。最后都比完都没差就是0

66

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n-1,-1,-1):
            digits[i] += 1
            if digits[i] < 10: return digits
            digits[i] = 0
        if digits[0] == 0:
            digits.append(0)
            for j in range(n,0,-1):
                digits[j] = digits[j-1]
            digits[0] = 1
        return digits
  • 没啥好多说的，所有情况都考虑了就行了
  • 但是其实，如果会产生进位，只有可能是因为最后一位是9，所以我这个判断条件稍微有一点没想清楚的感觉
  • 下面这个写出来更加优雅
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def plusOne(self, digits):
            """
            :type digits: List[int]
            :rtype: List[int]
            """
            if len(digits) == 1 and digits[0] == 9:
                return [1, 0]

            if digits[-1] != 9:
                digits[-1] += 1
                return digits
            else:
                digits[-1] = 0
                digits[:-1] = self.plusOne(digits[:-1])
                return digits

258 一个数字的逐位相加，直到小于9

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def addDigits(self, num: int) -> int:
        if num < 10:
            return num
        Sum = 0
        for i in str(num):
            Sum += int(i)
        return self.addDigits(Sum)
    
        # if num == 0 : return 0
        # else:return (num - 1) % 9 + 1
  • 上面那种方法是我写的，复杂度是n
  • 下面的方法是数学规律，复杂度是1

144 Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]

  • 注意审题：这道题并不是按左小右大的顺序排列的，而且preorder traversal指的就是先访问root，再从左到右访问root的子节点
  • 需要注意输入为空的情况
  • recursive和iterate都可以完成
  • 在recursive里面，因为需要把内容储存在list里面，所以需要新建一个函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
        def preorderTraversal(self, root: TreeNode) -> List[int]:
            result = []
            if root:
                self.preorder(root,result)
            return result
            
        def preorder(self,root,result):
            if root: result.append(root.val)
            if root.left: 
                self.preorder(root.left,result)
            if root.right: 
                self.preorder(root.right,result)
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        result = []
        while stack:
            current = stack.pop()
            if current:
                result.append(current.val)
                stack.append(current.right)
                stack.append(current.left)
        return result
  • 注意因为是把内容放在stack里面，所以要先放right才能让他后出来
  • 需要判断current是不是为空
  • pop默认的就是最后一位

145 Binary Tree Postorder Traversal

  • 和上一道题反序
  • 注意虽然是post，但是还是需要先访问左child，再访问右child
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if root:
            self.post(root,res)
        return res
        
        
    def post(self,root,res):
        if root.left:
            self.post(root.left,res)
        if root.right:
            self.post(root.right,res)
        if root: res.append(root.val)
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        res = []
        while stack:
            current = stack.pop()
            if current:
                res.append(current.val)
                stack.append(current.left)
                stack.append(current.right)
        return res[::-1]
  • iterative的方法可以采用先处理右边的点，再处理左边的点。因为右边的后放进stack所以先出来先进res里面
  • 最后再把结果倒序（牛逼）

102

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
#         self.levels = []
#         self.find(root,0)
#         return self.levels
        
#     def find(self,node, level):
#         if node:
#             if len(self.levels) <= level:
#                 self.levels += [[node.val]]
#             else:
#                 self.levels[level] += [node.val]
#             self.find(node.left, level + 1)
#             self.find(node.right,level + 1)
        if not root: return []
        stack, queue, nCount, res = [root],[],1,[[root.val]]
        while stack:
            temp = stack.pop(0)
            if temp.left: stack.append(temp.left)
            if temp.right: stack.append(temp.right)
            nCount -= 1
            if nCount == 0:
                queue = [x.val for x in stack]
                if queue:
                    res += [queue]
                nCount = len(stack) #得到的是下一层的个数
        return res
  • 两种方法，重点是找到如何重新计数level的层级，第一种方法不是顺着一步一步写进结果里的，是跳着写进去的。第二个方法是直接写进去的

103 把树按层zigzag排列

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        levels = []
        self.Find(root,0,levels)
        return levels
        
        
    def Find(self, node, level, levels):
        if node:
            if len(levels) <= level:
                levels.append([node.val])
            elif level%2:
                levels[level].insert(0,node.val)
            elif not level%2:
                levels[level].append(node.val)
            
            self.Find(node.left,level+1,levels)
            self.Find(node.right,level+1,levels)

  • 直接判断层数就可以实现，如果用一个flag表示没法在一整层的层面上实现
  • list是可以两端插入的

100 判断两个tree是不是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # if (not p and q) or (not q and p):
        #     return False
        # if p and q:
        #     if p.val != q.val: return False
        #     else:
        #         return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        # return p == q
        
        
        # if p and q:
        #     return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        # return p == q
        
        if p and q:
            if p.val != q.val: return False
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return p == q
  • 感觉自己写recursive总是有点问题，需要判断好终极条件

226 把一个二叉树对称变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 不需要变换树的val，可以直接变换node

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # def invert(L,R):
        #     if L and R:
        #         L.val, R.val = R.val, L.val
        #         invert(L.left,R.right)
        #         invert(L.right,R.left)
                
                
        if root: 
            invert = self.invertTree
            root.right, root.left = invert(root.left), invert(root.right)
        return root
  • 需要换node而不是换val

257

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

1
/ \
2 3
\
5

Output: [“1->2->5”, “1->3”]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if not root: return []
        
        stack = [(root,"")]
        result = []
        while stack:
            current,ls = stack.pop()
            if not current.left and not current.right:
                result.append(ls+str(current.val))
            if current.right:
                stack.append((current.right,ls+str(current.val)+"->"))
            if current.left:
                stack.append((current.left,ls+str(current.val)+"->"))
            
        return result

  • dfs的方法，终止条件是现在的点没有任何child了。自己搞错的地方主要是需要string跟着stack一起走，而不是两个分别判断。
  • 同样的到底可以写出来第112题，本质上是一样的，就是把求路径换成了这个路径的和
  • 同理写出来113，在tuple里面再加上路径的计算就可以了
  • 129也同理！但是129可以直接在每次recursion里面把上一位数乘10，然后加上这一位数，这样会比得到所有路径再计算的速度快很多

111 找出这个tree的最小depth

  • 可以用BFS也可以用DFS，但是注意的是两个return的东西的条件是不一样的。DFS的时候必须把左右树比大小
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
        def minDepth(self, root: TreeNode) -> int:
            if not root: return 0
            # stack = [(root,1)]
            # while stack:
            #     current,depth = stack.pop(0)
            #     if not current.left and not current.right:
            #         return depth
            #     if current.left:
            #         stack.append((current.left,depth+1))
            #     if current.right:
            #         stack.append((current.right,depth+1))
            
    #         dfs
            if root.left is None or root.right is None:
                return max(self.minDepth(root.left),self.minDepth(root.right))+1
            else:
                return min(self.minDepth(root.left),self.minDepth(root.right))+1

104

  • 寻找最深的层
  • 不用判断条件，直接dfs每次加一就可以实现了
    1
    2
    3
    4
    5
    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root: return 0
            # if not root.left and not root.right:
            return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

110 判断是不是平衡树

  • recursion的方法，注意的是每次返回的时候连带着子树是否平衡一起返回的，整体思路和之前的带着深度一起返回的感觉差不多
  • 或者也可以直接设置一个函数，计算出各个部分的height，然后再放到isBalance里面从上到下计算
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            return self.dfs(root)[1]
        
        def dfs(self,root):
            if not root: return (0, True) #depth, if_balance
            l_depth, l_balance = self.dfs(root.left)
            r_depth, r_balance = self.dfs(root.right)
            return max(l_depth,r_depth)+1, l_balance and r_balance and abs(l_depth-r_depth) <= 1

337/213

都是贼偷东西，不能连着偷两家。简单的动态规划问题。
这个问题的主要思路如下：

  • 对于每一家，其实都有两种情况：偷这家和不偷这家情况下得到的钱
    • 偷这家的时候，偷到的钱等于：这家的钱+前一家（childnode）不偷时候得到的钱
    • 不偷这家的时候，偷到得钱等于：max（偷前一家，不偷前一家）
      • 注意这种情况下，前一家可以偷可以不偷，取决于有多少钱
        三个题如下：
  • 最简单的情况是数组
  • 中等情况是一个环，即数组的收尾不能连着偷。在这种情况下其实就是计算两次，一次不偷第一家，一次不偷最后一家，看哪种情况多
  • 最后的情况是二叉树的情况，这种情况下可以给每个点都规定一个tuple分别表示偷了和没偷的结果
1
2
3
4
5
6
7
8
9
10
11
class Solution: #第二种情况下
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        return max(self.simple_rob(nums[1:]),self.simple_rob(nums[:-1]))
        
    def simple_rob(self,nums):
        rob,not_rob = 0,0
        for n in nums:
            rob,not_rob = not_rob+n, max(not_rob,rob)
        return max(rob,not_rob)
1
2
3
4
5
6
7
8
9
10
class Solution: #第三种情况下
    def rob(self, root: TreeNode) -> int:
        return max(self.dfs(root))
    
    def dfs(self,root):
        if not root:
            return (0,0) # [0]steal this node, [1] don't steal this node
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        return (root.val + left[1] + right[1],max(left[0],left[1]) + max(right[0],right[1]))

235 Lowest Common Ancestor of a Binary Search Tree

  • 找到给的两个点的最低的公共的祖先（parent）
  • 其实需要注意这个思路，思路就是当这两个点都比现在的root小的时候，那这个公共点在root的左边，如果都小的时候就在右边。
  • 因为这里要找的是最low的公共点，也就是离root最远的点
1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or not p or not q:
            return None
        if max(p.val,q.val) < root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if min(p.val,q.val) > root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root

236

  • 依然是找公共祖先，但是不是在BST里面找而是普通的二叉树里面找了，所以也就是不能用BST的性质了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if root is None or root==p or root ==q:
                return root
            left = self.lowestCommonAncestor(root.left,p,q)
            right = self.lowestCommonAncestor(root.right,p,q)
            if left and right:
                return root
            return left or right

108

Convert Sorted Array to Binary Search Tree

  • 注意，已经给了排好序的array了，而且需要的结果是height-balance的，这里可以直接取这个array最中间的作为root，然后左右分别recursion
  • 如果用平常的插入方法，插入进来的树不一定是平衡的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
        def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
            if not nums: return None
            mid = len(nums) // 2
            root = TreeNode(nums[mid])
            
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid+1:])
            
            return root

77 回溯法，列举所有组合

  • 回溯法需要注意三个阶段
    • 可以选择的条件是什么（需要在这些条件里迭代)
    • 对条件的限制是什么。比如在这个例子里面，如果一个数字用过了就不能再用了。不能实现或者已经实现的条件需要弹出
    • 目标：需要得到一个base case。比如这个题里面，字符串的长度到了k，就需要输入了
  • 用于问题种类：计算或者列举全部的可能
  • 这道题的python的问题，在list里面append之后pop明显会出现一些问题
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
        def combine(self, n: int, k: int) -> List[List[int]]:
            all_res = []
            self.search(1,n,k,[],all_res)
            return all_res
        
        def search(self,index,n,k,res,all_res): #start, n, choose num, all result
            if len(res) == k: 
                all_res.append(res)
                # print(all_res)
                return

            for i in range(index,n+1):
                # res.append(i)
                # print("before",res)
                # print(i+1,res,all_res)
                self.search(i+1,n,k,res+[i],all_res)
                # del(res[-1])
                # print("after",res)
            return

39 所有能到target数字的组合 回溯

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        def solver(nums,target,index,path,res):
            if target < 0:
                return
            if target == 0:
                # path.sort()
                # if path not in res:
                res.append(path)
                return
            for i in range(index,len(nums)):
                solver(nums,target-nums[i],i,path+[nums[i]],res)
        
        
        res = []
        solver(candidates,target,0,[],res)
        return res

  • 注意这里需要每次从i开始进行下一轮，也就是如果第一个2可以加进去，第二次还是从2开始往里试着加。要是2加不进去了，就只会往2后面的index走（也就是默认给你的list已经是排好序的了）
  • 整体思路和前面几道题差不多。重点就是确认停止的条件，然后每次先判断停止条件，如果不符合再进行recursion。注意recursion的每轮的条件判定

40

  • 数字不是按顺序排好的了，数字会重复出现了

  • 我选择的方法是在每次加入新的path之前，排序，然后比对这个是否在已经算出来的结果里面（虽然好像不快）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            
            def solver(nums,target,index,path,res):
                if target < 0:
                    return
                if target == 0:
                    path.sort()
                    if path not in res:
                        res.append(path)
                for i in range(index,len(nums)):
                    solver(nums,target-nums[i],i+1,path+[nums[i]],res)
            res = []
            solver(candidates,target,0,[],res)
            return res

  • 别人的方法主要增加了两个新的判断，第一个是如果在for里面，现在的数字已经比需要的target大了，那么就不需要继续搜索后面所有的部分了（？）。因为现在所有的数字都是positive的

  • 最重要的是，如果这个数字不是第一个放进去的数字，并且这个数字和之前的数字相同，那么这个数字应该直接被ignore

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution:
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            
            def solver(nums,target,index,path,res):
                if target < 0:
                    return
                if target == 0:
                    print(path)
                    res.append(path)
                for i in range(index,len(nums)):
                    if i > index and nums[i]==nums[i-1]:
                        continue
                    if nums[i] > target:
                        break
                    solver(nums,target-nums[i],i+1,path+[nums[i]],res)
            res = []
            candidates.sort()
            solver(candidates,target,0,[],res)
            return res

  • 以 1，1，2，5，6，7，10凑8为例子

    • 当取第一个1的时候，能组出来116，125，17，三个结果。这时候这三个结果都在第一层的i=0的时候的出来的结果。当这一层所有的结果取过之后，就会从第一个1退出来，进到第二个1.
    • 但是如果直接算第2个1，也能组粗125和17，从结果上说这两个1是重复的，所以代码在这部分直接continue了，没有计算第二个1，而是直接跳到了第三个数字2
    • 这样计算重复的方法比我再sort一次然后search一次消耗的时间少很多

216 回溯

  • 从1-9里选k个数字组合，得到目标数字
  • 很简单，没啥可搞的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
        def combinationSum3(self, k: int, n: int) -> List[List[int]]:
            
            def Solver(nums,k,n,index,path,res):
                if len(path) == k:
                    if n <0:
                        return
                    if n == 0:
                        res.append(path)
                        return
                for i in range(index,9):
                    if i > n:
                        break
                    Solver(nums,k,n-nums[i],i+1,path+[nums[i]],res)
                    
            
            nums = [i for i in range(1,10)]
            res = []
            Solver(nums,k,n,0,[],res)
            return res

377 虽然放在上面的系列里了但是是DP

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

1
2
3
4
5
6
7
8
9
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        com = [1] + [0]*target
        for i in range(target+1):
            for num in nums:
                if num > i: break
                com[i] += com[i-num]
        return com[target]

46 找出所有的排列组合

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

  • 这里每个数字不止用一次，所以需要一个方法来记录已经visit的数字，或者把nums的大小改变（比如每一次新输入的nums都跳过现在使用的数字）
  • 注意这里面没有重复的数字
  • 我这个方法也可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        def Solver(nums,index,path,res):
            
            if len(path) == len(nums):
                res.append(path)
                return
            
            for i in nums:
                if i not in path:
                    Solver(nums,i+1,path+[i],res)
        
        res = []
        Solver(nums,0,[],res)
        return res

47在上面的基础上有了重复的数字

  • 首先保证了数组必须要是sort的，这样才能确定相同的数字挨在一起
  • 核心思想就是，每次取出一个数字的时候，把原来nums的这个数直接去掉，下次再从0开始找，这样就能得到所有的数据了
  • 在recursion判断条件上，因为已经确定了数组有序，所有每次记录一个temp，来表示上一个数字，只有当这个数字 第一次被拿出来（index==0）or这个数字和上一个数字不相等or上一个还没有数字的时候，才能进入recursion
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            def Solver(nums,temp,path,res):
                if len(nums) == 0:
                    res.append(path)
                    return
                
                for i in range(0,len(nums)):
                    if temp is None or nums[i] != temp or i == 0:
                        temp = nums[i]
                        Solver(nums[:i]+nums[i+1:],temp,path+[nums[i]],res)
            
            nums.sort()
            res = []
            Solver(nums,None,[],res)
            return res

60

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

  • 时间太长了，不能用backtracking来做
  • 思路，前（n-1）！个数字的开头是1，然后n-1！个是2，然后是3，以此类推一直到最后。因为一共n个数字，n-1！xn也就是n！了
  • 在确定第一个数字之后，第二个数字的前n-2！个是2，然后是3，然后以此类推