0.1 数组/字符串

[88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150)
```python
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.
        """
        i,j,k = m-1,n-1,m+n-1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
```
[27. 移除元素](https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        i = j = 0
        while j < n:
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
                j += 1
            else:
                j += 1
        return i
```
[26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        s = 0
        for f in range(1,n):
            if nums[f] != nums[s]:
                s += 1
                nums[s] = nums[f]
        return s + 1
```
[80. 删除有序数组中的重复项 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        i = 1
        for j in range(2,n):
            if nums[j] != nums[i] or nums[j] != nums[i-1]:
                i += 1
                nums[i] = nums[j]
        return i + 1
```
[169. 多数元素](https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            if count == 0:
                candidate = nums[i]
                count += 1
            else:
                if candidate == nums[i]:
                    count += 1
                else:
                    count -= 1
        return candidate
```
[189. 轮转数组](https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def revert(nums, left, right):
            while left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        n = len(nums)
        k = k % n
        revert(nums, 0, n-1)
        revert(nums, 0, k-1)
        revert(nums, k, n-1)
```
[121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = -inf
        sell = 0
        for p in prices:
            buy = max(buy, -p)
            sell = max(sell, p + buy)
        return sell
```
[122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        n = len(prices)
        if n <= 1:
            return 0
        for i in range(1, n):
            if prices[i] > prices[i - 1]:
                res += prices[i] - prices[i - 1]
        return res

```
[55. 跳跃游戏](https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        far = 0
        n = len(nums)
        for i in range(n):
            if i > far:
                return False
            far = max(far, i + nums[i])
            if far >= n - 1:
                return True
```
[45. 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def jump(self, nums: List[int]) -> int:
        cur_far = 0
        far = 0
        n = len(nums)
        res = 0
        for i in range(n):
            if cur_far >= n - 1:
                return res
            far = max(far, nums[i] + i)
            if i == cur_far:
                res += 1
                cur_far = far

```
[274. H 指数](https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        for i in range(len(citations)):
            # 第 i+1篇论文的引用次数是否小于 i+1。
            if citations[i] < i + 1:
                return i
        return len(citations)

```
[380. O(1) 时间插入、删除和获取随机元素](https://leetcode.cn/problems/insert-delete-getrandom-o1/submissions/658076908/?envType=study-plan-v2&envId=top-interview-150)
```python
class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.nums_idx = {}

def insert(self, val: int) -> bool:
        if val in self.nums_idx:
            return False
        self.nums_idx[val] = len(self.nums)
        self.nums.append(val)
        return True

def remove(self, val: int) -> bool:
        if val not in self.nums_idx:
            return False
        remove_idx = self.nums_idx[val]
        last_num = self.nums[-1]
        self.nums[remove_idx] = last_num
        self.nums_idx[last_num] = remove_idx
        self.nums.pop()
        del self.nums_idx[val]
        return True

def getRandom(self) -> int:
        return random.choice(self.nums)
```
[238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        for i in range(1, n):
            res[i] = res[i - 1] * nums[i - 1]
        temp = 1
        for i in range(n - 2, -1, -1):
            temp *= nums[i + 1]
            res[i] = res[i] * temp
        return res
```
[134. 加油站](https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        total = 0
        start = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            if total < 0:
                start = i + 1
                total = 0
        return start
```
[135. 分发糖果](https://leetcode.cn/problems/candy/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        res = [1] * n
        for i in range(1,n):
            if ratings[i] > ratings[i-1]:
                res[i] = res[i-1] + 1
        for i in range(n-2,-1,-1):
            if ratings[i] > ratings[i+1]:
                res[i] = max(res[i], res[i+1] + 1)
        return sum(res)
```
[42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left, right = 0, n - 1
        max_left = max_right = 0
        res = 0
        while left < right:
            max_left = max(max_left, height[left])
            max_right = max(max_right, height[right])
            res += max_left - height[left] + max_right - height[right]
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return res
```
[13. 罗马数字转整数](https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_int = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        res = 0
        prev = 0
        for c in s:
            cur = roman_int[c]
            if cur > prev:
                res += cur - 2 * prev
            else:
                res += cur
            prev = cur
        return res

```
[12. 整数转罗马数字](https://leetcode.cn/problems/integer-to-roman/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def intToRoman(self, num: int) -> str:
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        val = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        string = ""
        for i in range(len(nums)):
            while num >= nums[i]:
                num -= nums[i]
                string += val[i]
        return string
```
[58. 最后一个单词的长度](https://leetcode.cn/problems/length-of-last-word/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        n = len(s)
        right = n-1
        while right >= 0 and s[right] == ' ':
            right -= 1
        left = right
        while left >= 0 and s[left] != ' ':
            left -= 1
        return right - left
```
[14. 最长公共前缀](https://leetcode.cn/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        s0 = strs[0]
        for j, c in enumerate(s0):
            for s in strs:
                if j == len(s) or s[j] != c:
                    return s0[:j]
        return s0

```
[151. 反转字符串中的单词](https://leetcode.cn/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip().split()
        s.reverse()
        return ' '.join(s)
```
[6. Z 字形变换](https://leetcode.cn/problems/zigzag-conversion/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2:
            return s
        res = ["" for _ in range(numRows)]
        i = 0
        flag = -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1:
                flag = -flag
            i += flag
        return "".join(res)

```
[28. 找出字符串中第一个匹配项的下标](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150)
```python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:  
            return 0
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            if haystack[i:i+n] == needle:
                return i
        return -1
```
[]()
```python

```
[]()
```python

```