LeetCode (1)

Posted on Edited on In Views:
Symbols count in article: 13k Reading time ≈ 12 mins.

题目库: [455, 605, 122, 435, 665, 763, 452, 167, 88, 142, 633, 680, 524, 69, 34, 81, 350, 154, 53, 35, 374, 367, 744, 287, 1170, 1337, 153, 33, 154, 278]

Greedy

455 Easy

局部最优则全局最优, 将小的饼干满足胃口最小的孩子以此类推

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 findContentChildren(self, g: List[int], s: List[int]) -> int:

        g.sort()
        s.sort()
        num_people = 0
        curr_g = 0

        for i, v in enumerate(s):

            if curr_g >= len(g):

                break
            
            if v >= g[curr_g]:
                num_people += 1
                curr_g += 1
        
        return num_people

605 Easy

解法1： 一个一个遍历，判断左右有没有种植

解法2：

  1. 当遍历到index遇到1时，说明这个位置有花，那必然从index+2的位置才有可能种花，因此当碰到1时直接跳过下一格。
  2. 当遍历到index遇到0时，由于每次碰到1都是跳两格，因此前一格必定是0，此时只需要判断下一格是不是1即可得出index这一格能不能种花，如果能种则令n减一，然后这个位置就按照遇到1时处理，即跳两格；如果index的后一格是1，说明这个位置不能种花且之后两格也不可能种花（参照【1】），直接跳过3格。

解法3: 在解法1的基础上不需要添加头尾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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class Solution_1 :
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        left = 0

        for i, v in enumerate(flowerbed):

            if i < len(flowerbed) - 1:
                right = flowerbed[i + 1]
            
            else:
                right = 0

            if not left and not right:
                left = 1
                if not v:
                    n -= 1
            else:
                left = 0

            if n <= 0:

                return True
        
        return False

class Solution_2:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        i = 0

        while i < len(flowerbed):
            
            if flowerbed[i] == 0:
                
                if i == len(flowerbed) - 1:
                    n -= 1
                    i = i + 2

                else:

                    if flowerbed[i + 1] == 0:
                        n -= 1
                        i = i + 2
                        
                    else:
                        i = i + 1
            else:
                i = i + 2

            if n <= 0:

                return True
        
        return False

class Solution_3:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        tmp = [0]+ flowerbed + [0]

        for i in range(1, len(tmp)-1):
            if tmp[i-1] == 0 and tmp[i] == 0 and tmp[i+1] == 0:
                tmp[i] = 1  # 在 i 处栽上花
                n -= 1   
        return n <= 0   # n 小于等于 0 ，表示可以栽完花

122 Easy

假如说后一天和今天的差是正的就卖 不然就不卖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        if len(prices) > 1:

            i = 0

            while i < len(prices) - 1:
                
                if prices[i] < prices[i + 1]:
                    profit += prices[i + 1] - prices[i]

                i += 1

        return profit

435 Medium

首先我们需要将所有interval根据上限从大到小排列, 接着我们就可以通过对比上限和当前interval下限来塞入符合条件的interval， 同时如果塞入成功 则需要更新新的interval上限

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 eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        max_inter = 0

        intervals.sort(key=lambda x: x[1])
        curr_inter = intervals[0][1]

        for i in range(1, len(intervals)):
            
            if curr_inter > intervals[i][0]:
                max_inter += 1
            
            else:
                curr_inter = intervals[i][1]
            
            i += 1
        
        return max_inter


665 Easy

该题思路为在i的时候连续看3个数即i, i-1, i-2，假如出现 i < i - 1，那么则尽量修改小，既然要修改小的话就会出现2种情况:

  1. i < i - 1 但是 i > i - 2: 例子 2 5 3, i=3, 这样我们只需要将5改为3即可满足尽量修改小的原则
  2. i < i - 1 同时 i < i - 2：例子 4 5 3, i=3, 这样我们只能将3改为5否则则需要改2次

同时处理边角情况并记录修改次数

我们只需要在碰到情况2的时候做inplace修改 （nums[i] = nums[i - 1]）因为你在确认 i < i - 2 之前 你已经知道了 i < i -1 也就是说 counts += 1 不管结果如何，所以在碰到 情况1时不需要做任何修改只需要counts += 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        counts = 0
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                if i == 1:
                    pass
                else:
                    if nums[i] < nums[i - 2]:
                        nums[i] = nums[i - 1]

                counts += 1
                
            if counts > 1:
                return False
        
        return True


763 Medium

  1. 解决方案一：

    • 遍历s，找到每个字母的区间放入一个dict
    • 将该dict变成list，并通过第一个位置排序
    • 这样该题目就被转化为了一个区间划分问题，只需要将重叠区间合并然后求出该区间长度就行

  2. 解决方案二:

    • 遍历s，找到每个字母的最后出现位置放入一个dict
    • 再遍历s，记录每个区间开始和结束，并更新区间最后出现位置
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
45
46
47
48
49
50
51
52
53
54
55
class Solution_1:
    def partitionLabels(self, s: str) -> List[int]:
        str_dict = {}
        output_lst = []
        for i, v in enumerate(s):
            if v in str_dict.keys():
                str_dict[v][1] = i

            else:
                str_dict[v] = [i, i]
        
        temp_lst = []
        for k, v in str_dict.items():
            temp_lst.append(v)

        temp_lst.sort(key=lambda x: x[0])
        curr_low = 0
        curr_max = temp_lst[0][1]

        for i in range(len(temp_lst) - 1):
            if curr_max < temp_lst[i + 1][0]:
                output_lst.append(curr_max - curr_low + 1)
                curr_low = temp_lst[i + 1][0]
                curr_max = temp_lst[i + 1][1]
            
            elif curr_max < temp_lst[i + 1][1]:
                curr_max = temp_lst[i + 1][1]
        
        output_lst.append(curr_max - curr_low + 1)
        
        return output_lst
    
class Solution_2:
    def partitionLabels(self, s: str) -> List[int]:
        str_dict = {}
        output_lst = []
        for i, v in enumerate(s):
            str_dict[v] = i

        start = 0
        end = str_dict[s[0]]
        for i in range(1, len(s)):
            if i > end:
                output_lst.append(end - start + 1)
                start = i
                end = str_dict[s[i]]
        
            if end < str_dict[s[i]]:
                end = str_dict[s[i]]

        output_lst.append(end - start + 1)
        return output_lst


452 Medium

先将区间根据第一个数从小到大排列，接着对比上限得到前后2个intervals相交的区间如果相交则更新上限，不需要更新下限因为右边下限永远比当前下限大，假如说不相交的话就会出现下限比上限大的情况， 这时就更新counts重制上限。

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

class Solution_1:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[0])
        counts = 1
        upper = points[0][1]
        for i in range(len(points) - 1):
            upper = min(upper, points[i + 1][1])
            if points[i + 1][0] > upper:
                counts += 1
                upper = points[i + 1][1]
        
        return counts

双指针

167 Easy

一个指针在前一个指针在后，后面指针负责缩小，前面指针负责放大

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        i = 0
        j = len(numbers) - 1     
        while i < j:
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
            elif numbers[i] + numbers[j] < target:
                i += 1
            else:
                j -= 1

88 Easy

从nums1 最后一个开始比较，插入n和m比较大的，直到n插入完毕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while n > 0:
            if m < 1:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
            elif nums2[n - 1] > nums1[m - 1]:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
            else:
                nums1[m + n -1] = nums1[m - 1]
                m -= 1

142 Medium

假设快指针和慢指针相遇的时间为f, 那么快指针走过的路程为 2s, 慢指针为s, 假设环起始位置到head距离为a, 环长度为b，那么 2s 即为快指针在b中走过的路程，2s - s = s = nb 即为慢指针走过的步数。这里n为整数因为相遇快的最少多走1圈 我们head开始一步一步每次走到环出口的步数为k = a + cb，假设c=n，而目前慢指针已经走了 nb这么多路了，我们只需要让另一个指针走a就可以到达出口。

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 singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow, very_slow = head, head, head
        while head and fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if fast == slow:
                
                while True:
                    if slow == very_slow:
                        return slow
                    
                    very_slow = very_slow.next
                    slow = slow.next

        return None

633 Medium

一道很简单的双指针问题

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

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        u = int(math.sqrt(c))
        i = 0
        while i <= u:
            if (i**2 + u**2) > c:
                u -= 1
            elif (i**2 + u**2) < c:
                i += 1
            else:
                return True
        
        return False

# if no import 
class Solution_2:
    def judgeSquareSum(self, c: int) -> bool:
        i = 0
        u = 0
        while u ** 2 < c:
           u += 1
            
        while i <= u:
            if (i**2 + u**2) > c:
                u -= 1
            elif (i**2 + u**2) < c:
                i += 1
            else:
                return True
        
        return False

680 Easy

双指针，判断s[i] != s[j]， 这时我们有2种选择，删掉i，或者删掉j，假如说删掉i，i+1 不等于j则说明不能删i同样apply to j。接着我们判断删掉之后的东西是不是为一个回文字符串就可以了。 当出现i和j都可以被删除的情况只要判断删掉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

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1

        def check(s, i, j):
            while i < j:
                if s[i] != s[j]:
                    return False

                i += 1
                j -= 1

            return True
        
        while i < j:
            if s[i] != s[j]:
                if s[i + 1] == s[j] and s[j - 1] == s[i]:
                    return check(s, i + 1, j) or check(s, i, j - 1)
                elif s[i + 1] == s[j]:
                    return check(s, i + 1, j)
                elif s[j - 1] == s[i]:
                    return check(s, i, j - 1)
                else:
                    return False
                    
            i += 1
            j -= 1

        return True

524 Medium

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
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        curr_word = ''

        def find_in_s(word):
            i = 0
            j = 0
            while i < len(s):
                if word[j] == s[i]:
                    j += 1
                
                if j >= len(word):
                    return True

                i += 1

            return False

        dictionary.sort(key=lambda x: (len(x), x))
        # for word in dictionary:
        #     word_in_dict = find_in_s(word)
        #     if (len(word) > len(curr_word)) and word_in_dict:
        #         curr_word = word
        #     elif (len(word) == len(curr_word)) and (word < curr_word) and word_in_dict:
        #         curr_word = word

        for word in dictionary:
            if (len(word) > len(curr_word)) and find_in_s(word):
                curr_word = word

        return curr_word

287 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        s, f = nums[0], nums[nums[0]]
        while f < len(nums):
            if s == f:
                f = 0
                while f != s:
                    s = nums[s]
                    f = nums[f]

                return f

            s = nums[s]
            f = nums[nums[f]]

        return nums[0]

Binary Search

69 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x

        if x == 1:
            left = 1
            
        while (right - left) > 1:
            mid_point = int((right + left) / 2)
            if x / mid_point == mid_point:
                return mid_point
            elif x / mid_point < mid_point:
                right = mid_point
            else:
                left = mid_point

        return left

278 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l <= r:
            mid = l + (r - l) // 2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1

        if l > n:
            return l - 1
        
        return l

34 Medium

找到左边界，再找到右边界，重点是boundary的判定

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums) - 1

        def find_left(left, right):
            res = -1
            while (right - left) >= 0:
                mid = (right + left) // 2
                if nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    right = mid - 1
                    res = mid               
                else:
                    left = mid + 1

            return res

        def find_right(left, right):
            res = -1
            while (right - left) >= 0:
                mid = (right + left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    left = mid + 1
                    res = mid
                else:
                    right = mid - 1

            return res

        out_left = find_left(left, right)
        out_right = find_right(left, right)
            
        return [out_left, out_right]

81 Medium

350 Easy

先把他们放到一个dict 然后在找共同就行

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:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result_lst = []

        def get_len(array):
            out_dict = {}
            for i in range(len(array)):
                if array[i] in out_dict.keys():
                    out_dict[array[i]] += 1
                else:
                    out_dict[array[i]] = 1

            return out_dict
        
        num1_dict = get_len(nums1)
        num2_dict = get_len(nums2)

        if len(num1_dict) > len(num2_dict):
            for k, v in num2_dict.items():
                if k in num1_dict.keys():
                    if v > num1_dict[k]:
                        result_lst = result_lst + [k] * num1_dict[k]
                    else:
                        result_lst = result_lst + [k] * v
        else:
            for k, v in num1_dict.items():
                if k in num2_dict.keys():
                    if v > num2_dict[k]:
                        result_lst = result_lst + [k] * num2_dict[k]
                    else:
                        result_lst = result_lst + [k] * v
        
        return result_lst

154 Easy

class Solution: def minArray(self, numbers: List[int]) -> int: for i in range(len(numbers) - 1): if numbers[i] > numbers[i + 1]: return numbers[i + 1]

    return numbers[0]

35 Easy

不需要最后的l边界判断

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2 # prevent overflow
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
                
        return l

374 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 1, n
        while l <= r:
            mid = l + (r - l) // 2
            if guess(mid) == 0:
                return mid
            elif guess(mid) < 0:
                r = mid - 1
            elif guess(mid) > 0:
                l = mid + 1

744 Easy

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

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        l, r = 0, len(letters) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if letters[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        
        if (r < 0) or (l > len(letters) - 1):
            return letters[0]
        else:
            return letters[l]

1170 Medium

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

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(s):
            s = sorted(s)
            counts = 1
            target = s[0]
            while counts < len(s):
                if target != s[counts]:
                    return counts

                counts += 1

            return len(s)

        for j, w in enumerate(words):
            words[j] = f(w)

        words.sort()
        for i, q in enumerate(map(f, queries)):
            # counts = 0
            # for f_w in words:
            #     if f_w <= q:
            #         break

            #     counts += 1

            l, r = 0, len(words) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if words[mid] <= q:
                    l = mid + 1
                elif words[mid] > q:
                    r = mid - 1
            
            if l >= len(words):
                queries[i] = 0
            else:
                queries[i] = len(words) - l

        return queries

1337 Easy

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 kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def count_soilder(row):
            n = len(row)
            l, r = 0, n - 1
            while l <= r:
                mid = l + (r - l) // 2
                if row[mid] == 1:
                    l = mid + 1
                else:
                    r = mid - 1

            return l
        
        for i, r in enumerate(map(count_soilder, mat)):
            mat[i] = (i, r)
        
        mat.sort(key=lambda x: x[1])

        return list(map(lambda x: x[0],  mat[:k]))

378 Medium

153 Medium

应该比较最右边，将最小情况变为 【5， 1】 或者 【1， 5】这种情况

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] <= nums[r]:
                r = mid
            elif nums[mid] > nums[r]:
                l = mid + 1

        return nums[l]

33 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution_1:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[l]:
                if (target < nums[mid]) and (target >= nums[l]):
                    r = mid - 1
                else:
                    l = mid + 1
            
            elif nums[mid] < nums[l]:
                if (target > nums[mid]) and (target <= nums[r]):
                    l = mid + 1
                else:
                    r = mid - 1 
        
        return -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
34
35
class Solution_2:
    def search(self, nums: List[int], target: int) -> int:

        # find smallest
        def find_smallest():
            l, r = 0, len(nums) - 1
            while l < r:
                mid = l + (r - l) // 2
                if nums[mid] > nums[r]:
                    l = mid + 1
                else:
                    r = mid
                
            return l
        
        def binary_search(l, r):
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    r = mid - 1
                elif nums[mid] < target:
                    l = mid + 1

            return -1

        smallest_idx = find_smallest()
        
        if smallest_idx == 0:
            return binary_search(0, len(nums) - 1)
        elif target >= nums[0]:
            return binary_search(0, smallest_idx - 1)
        else:
            return binary_search(smallest_idx, len(nums) - 1)

81 Medium

similar to 33, but we check back and front, if they equal, we move front one spot to convert this problem to #33

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 search(self, nums: List[int], target: int) -> bool:
        
        # find smallest
        def find_smallest():
            l, r = 0, len(nums) - 1
            while l < r:
                if nums[l] == nums[-1]:
                    l += 1
                else:
                    mid = l + (r - l) // 2
                    if nums[mid] > nums[r]:
                        l = mid + 1
                    else:
                        r = mid
                
            return l
        
        def binary_search(l, r):
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    return True
                elif nums[mid] > target:
                    r = mid - 1
                elif nums[mid] < target:
                    l = mid + 1

            return False

        smallest_idx = find_smallest()
        
        if smallest_idx == 0:
            return binary_search(0, len(nums) - 1)
        elif target >= nums[0]:
            return binary_search(0, smallest_idx - 1)
        else:
            return binary_search(smallest_idx, len(nums) - 1)

154 Hard

153 的重复版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findMin(self, nums: List[int]) -> int:
        # find smallest
        l, r = 0, len(nums) - 1
        while l < r:
            if nums[l] == nums[-1]:
                l += 1
            else:
                mid = l + (r - l) // 2
                if nums[mid] > nums[r]:
                    l = mid + 1
                else:
                    r = mid
            
        return nums[l]
Related Posts