刷题记录合辑

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

162. 寻找峰值

思路

代码

题解

思路

尝试1 - 二分查找:

查看当前中间值，如果中间值处在一个上升区间: l = mid+1 下降区间r = mid-1

题解1 - 二分查找优化:

可以证明如果nums[i] < nums[i+1], 那么在[i+1, n-1]上一定存在峰值,否则是[0, i]
这里又一个重要的内容就是二分的时候我们是怎么确认是使用开区间，闭区间还是

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 左闭右闭
        n = len(nums)
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r)>>1
            if nums[mid] < nums[mid+1] or mid == n-1:
                l = mid+1
            else:
                r = mid 
        return l

```

{% endtabs %}

**总结**
我们需要重点关注是二分区间还是二分答案这一件事情
观察我们的l r 处于什么位置，他们如何影响我们的结果，画出图来方便我们查看 

---

## 13. Roman to Integer


{% tabs active:2 align:left %}
<!-- tab 思路 -->

**思路**  
尝试1 - 栈
* 这题看起来思路是栈
* 一个res, 一个current. 如果遇到比自己小的就进行结算。如果遇到比自己大的就进行反转 

题解1 - 实际上根本用不到栈:
* 使用python内置库的iterate_tools.pairwise()
* `for a, b in pairwise(data):`

<!-- tab 代码 -->

```python
class Solution:
    def romanToInt(self, s: str) -> int:
        dmap = {
            'I':1, 
            'V':5,
            'X':10,
            'L':50,
            'C':100,
            'D':500,
            'M':1000,
        }
        res = 0
        current = 0
        n = len(s)
        for i in range(0,n):
            if i == 0 or dmap[s[i]] > dmap[s[i-1]]:
                current = dmap[s[i]] - current
                res += current 
                current = 0
            else:
                current = dmap[s[i]]
        return res + current


ROMAN = {
    'I':1, 
    'V':5,
    'X':10,
    'L':50,
    'C':100,
    'D':500,
    'M':1000,
}
class Solution:
    def romanToInt(self, s: str) -> int:
        ans = 0
        for x, y in pairwise(s):
            x, y = ROMAN[x], ROMAN[y]
            ans += x if x >= y else -x
        return ans + ROMAN[s[-1]]

总结

pairwise(x)是iterate_tools里边的内容，可以按照0,1 1,2这样子的方式逐步枚举

58. 最后一个单词长度

思路
尝试1 - 内置函数: 通过

使用内置函数split(' ')将字符串拆分，然后找到最后一个不是’ ‘的元素

尝试2 - 内置函数: 通过

使用内置函数拆分，然后通过函数表达式将’ ‘筛掉

尝试3 - 内置函数: 通过

使用内置函数拆分，然后通过s = list(filter(None, s))将’ ‘筛掉

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.split(' ')
        # s = [word for word in s if word != '']
        idx = len(s)-1
        while s[idx] == ' ' or s[idx] == '':
            idx -= 1
        return len(s[idx])

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.split(' ')
        s = [word for word in s if word != '']
        idx = len(s)-1
        return len(s[idx])

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s.split(' ')
        s = [word for word in s if word != '']
        idx = len(s)-1
        return len(s[idx])

总结
filter函数用法如下

filter(function, iterable)这个返回的是一个迭代器，需要使用list或者for 才能看到
function是可以自定义的,他可以是固定的元素如

1
2
3

s = ['Hello', '', 'World', '', ' ']
result = list(filter(None, s))
# 输出: ['Hello', 'World', ' ']

也可以是一个函数表达式

def is_positive(n):
    return n > 0

nums = [-2, 0, 3, 5, -1]
result = list(filter(is_positive, nums))
# 输出: [3, 5]

380. O(1)时间插入,删除，随机返回

思路

代码

思路
题解 - 集合:

O(1)时间插入和删除就是只能是集合set

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.indices = {}

    def insert(self, val: int) -> bool:
        if val in self.indices:
            return False
        else: 
            self.indices[val] = len(self.nums)
            self.nums.append(val)
            return True
        
    def remove(self, val: int) -> bool:
        if val not in self.indices:
            return False
        else:
            idx = self.indices[val]
            self.nums[idx] = self.nums[-1]
            self.indices[self.nums[idx]] = idx
            self.nums.pop()
            del self.indices[val]
            return True

    def getRandom(self) -> int:
        return choice(self.nums)