【leetcode刷题之路】面试经典150题（1）——数组/字符串_力扣经典150

1 数组/字符串

1.1 【排序】合并两个有序数组

题目地址：https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

  直接将$num2$拼到$num1$后面排序即可。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[m+i] = nums2[i]
        nums1.sort()
1
2
3
4
5

1.2【双指针】移除元素

题目地址：https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

  将符合条件的$val$值全部移到数组的末尾，同时记录数组长度。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 0:
            return 0
        left = 0
        right = len(nums) - 1
        while left < right:
            while((left<right) and (nums[left]!=val)):
                left += 1
            while((left<right) and (nums[right]==val)):
                right -= 1
            nums[left], nums[right] = nums[right], nums[left]
        if(nums[left]==val):
            return left
        else:
            return left+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.3 【双指针】删除有序数组中的重复项

题目地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

  $left$记录当前遍历时未重复的元素，如果碰见重复的元素，则通过$right$进行交换赋值。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:  
        left = 0
        right = 1
        while(right < len(nums)):
            if nums[left]!=nums[right]:
                left += 1
                nums[left] = nums[right]
            right += 1
        return left+1
1
2
3
4
5
6
7
8
9
10

1.4 【双指针】删除有序数组中的重复项 II

题目地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

  按照上一题的思路，如果遇到重复的元素，比较其之后间隔两个$index$的元素即可。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left = 0
        for right in range(len(nums)):
            if(left<2 or nums[right]!=nums[left-2]):
                nums[left] = nums[right]
                left += 1
        return left
1
2
3
4
5
6
7
8

1.5 【数学】多数元素

题目地址：https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

  先对数组进行排序，因为多数元素是次数超过数组长度一半的元素，所以排序后数组的中间位置一定是多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]
1
2
3
4

1.6 【数组】轮转数组

题目地址：https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

  先对前$n-k$个元素进行翻转，在对后$k$个元素进行翻转，最后对整个数组进行翻转。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n
        def swap(l,r):
            while(l<r):
                nums[l], nums[r] = nums[r], nums[l]
                l = l+1
                r = r-1
        swap(0,n-k-1)
        swap(n-k,n-1)
        swap(0,n-1)
1
2
3
4
5
6
7
8
9
10
11
12

1.7 【动态规划】买卖股票的最佳时机

题目地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

$dp\_0$：表示第$i$天结束的时候，如果手里没有持有股票，最大的利润是多少。

$dp\_1$：表示第$i$天结束的时候，如果手里持有股票，最大的利润是多少。

在这里我们分别对上述两个进行计算：

• $dp\_0$：这个考虑到两种情况，一是第$i-1$天没有持有股票，所以与第$i-1$天未持有股票的利润一样，二是第$i-1$天持有股票，但是决定在第$i$天卖掉，所以利润为第$i-1$天持有股票的利润+第$i$天该股票的价格，两个取最大值即可。
• $dp\_1$：这个也考虑到两种情况，一是第$i-1$天持有股票，所以与第$i-1$天持有股票的利润一样，二是第$i-1$天未持有股票，但是决定在第$i$天买入，所以利润为负值，两个取最大值即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)==1:
            return 0
        dp_0 = 0
        dp_1 = -prices[0]
        i = 0
        while(i < len(prices)):
            dp_0 = max(dp_0, dp_1 + prices[i])
            dp_1 = max(dp_1, -prices[i])
            i += 1
        return dp_0
1
2
3
4
5
6
7
8
9
10
11
12

1.8 【贪心】买卖股票的最佳时机 II

题目地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150

  由局部最优解推到全局最优解，最大利润拆分到每天就是每两天之间进行股票交易，积累其为正数的利润，即为最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)==1:
            return 0
        ssum = 0
        i = 1
        while(i<len(prices)):
            if prices[i]-prices[i-1] > 0:
                ssum += prices[i]-prices[i-1]
            i += 1
        return ssum
1
2
3
4
5
6
7
8
9
10
11

1.9 【贪心】【动态规划】跳跃游戏

题目地址：https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

  能走到最后一个位置，那么它前面的位置也能走到，所以只需要判断最远可以走到哪里，然后与数组的长度进行比较即可。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums)==1:
            return True
        if nums[0]==0:
            return False
        max_step = 0
        for i in range(len(nums)):
            if max_step>=i and i+nums[i]>max_step:
                max_step = i+nums[i]
        return max_step>=len(nums)-1
1
2
3
4
5
6
7
8
9
10
11

1.10 【贪心】【动态规划】跳跃游戏 II

题目地址：https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

  在上一题的基础上，记录步数即可，每次选择下一步时，要选择尽可能走到更远的下一步。

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_pos, end, step = 0, 0, 0
        for i in range(len(nums)-1):
            if max_pos >= i:
                max_pos = max(max_pos, i + nums[i])
                if i == end:
                    end = max_pos
                    step += 1
        return step
1
2
3
4
5
6
7
8
9
10

1.11 【二分】H 指数

题目地址：https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

  从$0$到$n$挨个遍历$h$指数，找到最高的那个$h$指数即可。

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        left, right = 0, len(citations)
        while(left<right):
            mid = (left+right+1)//2
            cnt = 0
            for cit in citations:
                if cit>=mid:
                    cnt += 1
            if cnt>=mid:
                left = mid
            else:
                right = mid-1
        return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.12 【模拟】时间插入、删除和获取随机元素

题目地址：https://leetcode.cn/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class RandomizedSet:

    def __init__(self):
        self.num = []

    def insert(self, val: int) -> bool:
        if val in self.num:
            return False
        else:
            self.num.append(val)
            return True

    def remove(self, val: int) -> bool:
        if val not in self.num:
            return False
        else:
            self.num.remove(val)
            return True

    def getRandom(self) -> int:
        i = random.randint(0, len(self.num)-1)
        return self.num[i]

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
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

1.13 【前缀和】除自身以外数组的乘积

题目地址：https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

  分别计算索引左边的数字乘积和索引右边的数字乘积，两者乘积结果即为该索引的乘积结果。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        left_ans, right_ans, answer = [0]*length, [0]*length, [0]*length

        left_ans[0] = 1
        for i in range(1,length):
            left_ans[i] = left_ans[i-1]*nums[i-1]
        
        right_ans[length-1] = 1
        for i in range(length-2,-1,-1):
            right_ans[i] = right_ans[i+1]*nums[i+1]
        
        for i in range(length):
            answer[i] = left_ans[i]*right_ans[i]
        
        return answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.14 【贪心】加油站

题目地址：https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

考虑两种情况：

• 情况一：如果总的油量剩余小于$0$，则从哪个加油站出发都不能走完一圈。
• 情况二：从加油站$n$到加油站$m$之间的油量剩余之和不能小于$0$，否则不能走完一圈，局部最优推到全局最优。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start, cur_res, total_res = 0, 0, 0
        for i in range(len(gas)):
            cur_res += gas[i] - cost[i]
            total_res += gas[i] - cost[i]
            if cur_res < 0:
                cur_res = 0
                start = i + 1
        if total_res < 0:
            return -1
        else:
            return start
1
2
3
4
5
6
7
8
9
10
11
12
13

1.15 【贪心】分发糖果

题目地址：https://leetcode.cn/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150

考虑两种情况：

• 情况一：从左往右数，首先每个学生发一颗糖果，如果学生$A$的$rating$大于学生$B$，则学生$A$的糖果数要比学生$B$多一颗，数量记在$left$中。
• 情况二：从右往左数，首先每个学生发一颗糖果，如果学生$B$的$rating$大于学生$A$，则学生$B$的糖果数要比学生$A$多一颗，数量记在$right$中。

最后结果为left和right中对应最大值之和。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        length = len(ratings)
        left, right, cnt = [1]*length, [1]*length, 0

        for i in range(1,length):
            if ratings[i] > ratings[i-1]:
                left[i] = left[i-1] + 1

        for i in range(length-2,-1,-1):
            if ratings[i] > ratings[i+1]:
                right[i] = right[i+1] + 1
            cnt += max(left[i],right[i])

        cnt += max(left[length-1],right[length-1])
        return cnt 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.16 【双指针】接雨水

题目地址：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150

  双指针解决，分别记录左边和右边的最大值，然后依次从两边往中间记录差值，最后差值的和即为接雨水量

class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        if length == 0:
            return 0
        
        ans = 0
        left, right = 0, length-1
        max_left, max_right = height[0], height[length-1]

        while left < right:
            max_left = max(max_left,height[left])
            max_right = max(max_right,height[right])
            if max_left < max_right:
                ans += max_left-height[left]
                left += 1
            else:
                ans += max_right-height[right]
                right -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.17 【哈希表】罗马数字转整数

题目地址：https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def romanToInt(self, s: str) -> int:
        Roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        ans = 0

        for i in range(len(s)-1):
            if Roman[s[i]] < Roman[s[i+1]]:
                ans -= Roman[s[i]]
            else:
                ans += Roman[s[i]]
        ans += Roman[s[-1]]

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

1.18 【哈希表】整数转罗马数字

题目地址：https://leetcode.cn/problems/integer-to-roman/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def intToRoman(self, num: int) -> str:
        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        ans = ''
        for key in hashmap:
            if num // key != 0:
                cnt = num // key
                ans += hashmap[key]*cnt
                num %= key
        return ans
1
2
3
4
5
6
7
8
9
10

1.19 【字符串】最后一个单词的长度

题目地址：https://leetcode.cn/problems/length-of-last-word/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        string_list = s.split(" ")
        ans = ""
        for i in range(len(string_list)-1,-1,-1):
            if string_list[i] == "":
                continue
            else:
                ans = string_list[i]
                break
        return len(ans)
1
2
3
4
5
6
7
8
9
10
11

1.20 【字符串】最长公共前缀

题目地址：https://leetcode.cn/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150

  纵向比较找出最长公共前缀。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        length = len(min(strs))
        ans = ""
        for i in range(0,length):
            for j in range(0,len(strs)-1):
                if strs[j][i] != strs[j+1][i]:
                    return ans
            ans += strs[0][i]
        return ans
1
2
3
4
5
6
7
8
9
10

1.21 【字符串】反转字符串中的单词

题目地址：https://leetcode.cn/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def reverseWords(self, s: str) -> str:
        string_list = s.split(" ")
        ans = ""
        for i in range(len(string_list)-1,-1,-1):
            if string_list[i] != "":
                ans += string_list[i] + " "
        if ans[-1] == " ":
            ans = ans[:-1]
        return ans
1
2
3
4
5
6
7
8
9
10

1.22 【字符串】Z字形变换

题目地址：https://leetcode.cn/problems/zigzag-conversion/description/?envType=study-plan-v2&envId=top-interview-150

  对字符串根据$numRows$进行分组，$flag$代表字符串$Z$字形方向。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows==1:
            return s
        
        ans = [""]*numRows
        i, flag = 0, -1
        for c in s:
            ans[i] += c
            if i == 0 or i == numRows-1:
                flag = -flag
            i += flag
        return "".join(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13

1.23 【字符串】找出字符串中第一个匹配项的下标

题目地址：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle not in haystack:
            return -1
        else:
            return haystack.index(needle)
1
2
3
4
5
6

1.24 【模拟】文本左右对齐

题目地址：https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res, line, str_num = [], [], 0
        for word in words:
            # line中所有单词加一起的长度 + line中单词(单词与单词之间原生需要1个空格)之间的间距数 + 当前需要判断的单词长度
            # 上述之和大于等于maxWidth时会溢出，为什么等于时也会溢出？因为若新加入Word，会新增加1个间距(即空格长度)
            if str_num + len(line)-1 + len(word) >= maxWidth:
                for i in range(maxWidth - str_num):
                    # 循环将每个空格依次加到每个单词之间的间距上
                    line[i%max(len(line)-1, 1)] += ' '
                res.append(''.join(line))
                line, str_num = [], 0
            line.append(word)
            str_num += len(word)
        return res + [' '.join(line).ljust(maxWidth)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15