LeetCode 26 - 30 记录

26

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

简单的题目。

from typing import List
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        index = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                index = index + 1
                nums[index] = nums[i]
        return index + 1

if __name__ == '__main__':
    solu = Solution()
    Input = [0,0,1,1,1,2,2,3,3,4]
    Output = solu.removeDuplicates(Input)
    print(Input)
    print(Output)

27

https://leetcode.com/problems/remove-element/

和上一题类似。

from typing import List

from singly_list_utils import print_linked_list
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for num in nums:
            if num != val:
                nums[index] = num
                index += 1
        return index

if __name__ == '__main__':
    solu = Solution()
    nums = [3, 2, 2, 3]
    val = 3
    Output = solu.removeElement(nums, val)
    print(Output)
    for i in range(Output):
        print(nums[i], end=' ')
    print()

28

https://leetcode.com/problems/implement-strstr/

真是让人生气的一题。看到 downvotes 就比 upvotes 差一点点，我就应该知道这道题是什么情况了。

本来是想直接使用遍历的，不用 Python 的切片。那个超时的用例给我整懵了。算了，就用切片好了。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == '':
            return 0
        res = -1
        for i in range(len(haystack)):
            if haystack[i] == needle[0]:
                if haystack[i:i + len(needle)] ==needle:
                    res = i
            if res != -1:
                break
        return res

if __name__ == '__main__':
    solu = Solution()
    haystack = 'hello'
    needle = 'll'
    Output = solu.strStr(haystack, needle)
    print(Output)

29

https://leetcode.com/problems/divide-two-integers/

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2 ** 31 - 1
        INT_MIN = -2 ** 31
        # dividend is INT_MIN
        if dividend == INT_MIN:
            if divisor == 1:
                return dividend
            elif divisor == -1:
                return INT_MAX
        # ddivisor is INT_MIN
        if divisor == INT_MIN:
            if dividend == INT_MIN:
                return 1
            else:
                return 0
        if divisor == 1:
            return dividend
        if divisor == -1:
            return -dividend
        if dividend == 0:
            return 0
        
        # normal situation
        # recursive method, this is the core method
        def recurse_div(dividend: int, divisor: int):
            if dividend < divisor:
                return 0
            cur_min = 1
            util_num = divisor
            while util_num <= dividend - util_num: # the fisrt clause to detect overflow
                cur_min += cur_min
                util_num += util_num # equals to multiply by 2
            return cur_min + recurse_div(dividend - util_num, divisor)
        
        flag = 0
        if (dividend >= 0 and divisor > 0) or (dividend < 0 and divisor < 0):
            flag = 1

        if dividend == INT_MIN:
            if divisor < 0:
                ans = 1 + recurse_div(abs(dividend - divisor), abs(divisor))
            if divisor > 0:
                ans = 1 + recurse_div(abs(dividend + divisor), divisor)

        else:
            ans = recurse_div(abs(dividend), abs(divisor))
        return ans if flag == 1 else -ans

if __name__ == '__main__':
    solu = Solution()
    Output = solu.divide(-2147483648, -2)
    print(Output)

代码写得不好，题目本身的限制有点烦。好在终于 AC 了。

我看很多人的题解都没有考虑 32 位数的限制。

我这里本来是这样来判断的：

把

util_num + uitl_num <= INT_MAX

转化成减法即可：

util_num <= INT_MAX - util_num

后来发现其实把 while

util_num + util_num <= dividend

转化成

util_num <= dividend - util_num

就行了。

另外，边界处理是真的烦人。我这里对 -2147483648 的处理是先将其剪掉一个 divisor，然后在用核心代码来处理。即：

if dividend == INT_MIN:
    if divisor < 0:
        ans = 1 + recurse_div(abs(dividend - divisor), abs(divisor))
    if divisor > 0:
        ans = 1 + recurse_div(abs(dividend + divisor), divisor)

30

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

from typing import List

# 先用效率低一点的遍历方式来遍历试一下
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        from collections import Counter
        words_counter = Counter(words)
        single_word_len = len(words[0])
        word_num = len(words)
        all_word_len = word_num * single_word_len
        s_len = len(s)
        for index in range(0, s_len - all_word_len + 1):
            sub_string = s[index:index + all_word_len]
            flag = True
            words_counter_copy = Counter(words_counter)
            for index2 in range(0, all_word_len - single_word_len + 1, single_word_len):
                each_word = sub_string[index2:index2+single_word_len]
                words_counter_copy[each_word] -= 1
                if words_counter_copy[each_word] < 0:
                    flag = False
                    break
            if flag == True:
                res.append(index)
        return res

if __name__ == '__main__':
    solu = Solution()
    # Input
    s = "barfoothefoobarman"
    words = ["foo","bar"]
    # s = "barfoofoobarthefoobarman"
    # words = ["bar","foo","the"]
    s = "wordgoodgoodgoodbestword"
    words = ["word","good","best","good"]
    Output = solu.findSubstring(s, words)
    print(Output)

这里用了简单的遍历，对每一个子串利用字典进行判断是否符合条件。这个字典其实就是 hash 表，但我感觉，这个和我学过的 hash 是不一样的。

注意题目的条件，给定的字符串数组中的每一个字符串的长度是一样的。

还有，关于 Python 的字符统计，有一个库函数 Counter，具体使用的方法可以参见：https://www.guru99.com/python-counter-collections-example.html

按：有例子的讲述最容易理解了。

这道题目可以用滑动窗口来优化，暂时搁置。