刷题记录合辑

标题不含题号，题号写在正文与 description 中。

167. 两数之和

思路

代码

二分查找

思路
尝试1 - 通过: 双指针模板题

已经非递减，那么指针向右移动会让和变大，指针向左移动会让和变小
每次更新都是将快慢指针一起更新然后往回退slow,配合剪枝减少比较数量
复杂度O(n^2)

题解1: 正统双指针

双指针出初始化为0和len(numbers)-1
这个的正确性我没搞懂，我现在搞懂了，需要复习

题解2: 二分

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        slow, fast = 0, 1
        size = len(numbers)
        while fast < size:
            num = numbers[slow] + numbers[fast]
            if num < target:
                fast = fast + 1
                slow = fast - 1
                continue
            else:
                targetSlow = target - numbers[fast]
                while numbers[slow] > targetSlow and slow >= 0:
                    slow = slow - 1
                if slow = -1:
                    fast = fast + 1
                    slow = fast - 1
                else if numbers[slow] == targetSlow:
                    res = []
                    res.append(slow)
                    res.append(fast)
                    return res

```


<!-- tab 题解 -->
```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1
        while left < right:
            num = numbers[left] + numbers[right]
            if num < target:
                left = left+1
            elif num > target:
                right = right - 1
            else:
                res = []
                res.append(left+1)
                res.append(right+1)
                return res

总结

392. 判断子序列

思路

代码

二分查找

思路
尝试与题解: 双指针
进阶题思路: 预处理每个点下一个字母出现

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        slow, fast = 0, 0
        size1 = len(s)
        size2 = len(t)
        while slow < size1 and fast < size2:
            if s[slow] == t[fast]:
                slow = slow + 1
            fast = fast+1
        return slow == size1

```


<!-- tab 题解 -->
```python

总结

134. 加油站

思路

代码

二分查找

思路
尝试1: 贪心算法，一旦出现当前点不足的情况直接结束，从结束点重新开始

只要能走够size步说明成功绕一圈
如果start再次到0说明没法走了

主要的问题是我没法快速判断如果sum(gas) > sum(cost)就一定存在解

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        size = len(gas)
        net = []
        for i in range(0, size):
            net.append(gas[i]-cost[i])

        start = 0
        while start < size:
            current = 0
            for i in range(0,size):
                current = current + net[(start+i)%size]
                if current < 0:
                    break
                if i == size-1:
                    return start
            start = start + i + 1
        return -1

```

<!-- tab 题解 -->
```python

总结

135. 分发糖果

思路

代码

不同解法

思路

尝试1: 统计上升序列，错误因为只保证了右边的数量符合要求，左边的没有保证
尝试2: 每次找到最小的然后将所有减掉最小的，然后删掉的左右两边都加一，但是这样的复杂度太差了
尝试3: 用dp，但是dp要保证后边的状态是由前边的状态推导得到

题解 - 贪心:，统计上升序列然后选择较大的来实现即可

class Solution:
    def candy(self, ratings: List[int]) -> int:
        size = len(ratings)
        left = [0] * size
        left[0] = 1 
        for i in range(1, size):
            if ratings[i] > ratings[i-1]:
                left[i] = left[i-1] +1
                #elif ratings[i] == ratings[i-1]:
                # left[i] = left[i-1]
            else:
                left[i] = 1
        right = [0] * size
        right[size-1] = 1 
        for i in range(size-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                right[i] = right[i+1] + 1
                #elif ratings[i] == ratings[i+1]:
                # right[i] = right[i+1]
            else:
                right[i] = 1
        res = 0
        for i in range(0, size):
            res = res + max(left[i], right[i])
        return res

```


<!-- tab 题解 -->
```python

总结

知识点小结

模板

思路

代码

二分查找

思路

```

<!-- tab 题解 -->
```python

总结

刷题记录4

刷题记录合辑

167. 两数之和

392. 判断子序列

134. 加油站

135. 分发糖果

相关题目

知识点小结