暂时搁置的代码

# 专题
- 相比于解析部分追求代码的绝对精简，本专题追求以高可读性呈现各大专题的常规思路。俩部分题目可能重复，但专题部分会有更详细的解析，且可能运用不同解法。为降低学习成本，🛫 每个方向会根据[C++篇](https://github.com/cy69855522/Clearest-LeetCode-Cpp-Solutions)收录少数优选的经典题目，若觉得不够请转[解析部分](#解析)，若想更改例题，欢迎 issue 提出您的建议或意见。
- 题型：[数组](#数组)、[哈希表](#哈希表)、[链表](#链表)、[数学](#数学)、[双指针](#双指针)、[字符串](#字符串)、[二分查找](#二分查找)、[分治算法](#分治算法)、[位运算](#位运算)
## 数组
### [238. Product of Array Except Self 双指针](https://leetcode.com/problems/product-of-array-except-self/)
```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        
        l = 1
        for i in range(n):
            res[i] *= l
            l *= nums[i]
        
        r = 1
        for j in range(n - 1, -1, -1):
            res[j] *= r
            r *= nums[j]
        
        return res
```
- 本题利用双指针，新数组每个位置上的值应该等于数组左边所有数字的乘积 × 数组右边所有数字的乘积
- 1.初始化一个新的数组res（result），包含n个1

  2.初始化变量l（left）代表左边的乘积，从左到右遍历数组，每次都让新数组的值乘以它左边数字的乘积l，然后更新l。此时新数组里的所有数字就代表了nums数组中对应位置左边所有数字的乘积
  
  3.再从右往左做一遍同样的操作，最终`res[i] = 1 * nums中i左边所有数字的乘积 * nums中i右边所有数字的乘积`
### [448. Find All Numbers Disappeared in an Array 逆遍历](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)
```python
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        r = [*range(1, len(nums) + 1)]
        for n in nums:
            r[n - 1] = 0
        for i in range(len(r) - 1, -1, -1):
            if not r[i]:
                r.pop(i)
        return r
```
- 应题目进阶要求，此解为 O(N) 时间效率，无额外空间（除了返回数组和中间变量）
- 初始化返回列表为数字 1 ~ n，值=索引+1
- 遍历nums，并把r中出现在nums中的值全部置0，这里实际上利用r为递增序列的特性，近似为一个哈希表
- 删除r中所有0元素
- 为什么不在遍历nums到时候直接删除r中的值？直接删除会影响后续索引的定位，因此需要逆遍历数组
## 哈希表
### [1. Two Sum 字典](https://leetcode.com/problems/two-sum/)
```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
	d = {}
	for i, n in enumerate(nums): 
	    if n in d: return [d[n], i]
	    d[target-n] = i
```
- 建立一个字典，每次遍历过一个值就记录与其匹配的值（设置d[匹配值]=当前索引），今后遇见匹配值即可直接返回结果
## 链表
### [206. Reverse Linked List 前后指针](https://leetcode.com/problems/reverse-linked-list/)
```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p = None
        while head:
            head.next, head, p = p, head.next, head
        return p
```
- 此处利用 python 多重赋值表达式的特性（例：`a, b = b, a`），python 中多变量同时赋值时，右手边的表达式在任何赋值发生之前就被求值了。右手边的表达式是从左到右被求值的
## 数学
### [268. Missing Number 等差数列](https://leetcode.com/problems/missing-number/)
```python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        s = sum(nums)
        n += 1
        return n * (n - 1) // 2 - s
```
- 缺失数字 = 0 加到 n+1 的总和 - 数组中所有数字的总和
- 计算 0 加到 n+1 的总和，可利用等差数列求和公式，此题可理解为`总和 = (元素个数 / 2) * (首尾两数字之和)`
## 双指针
### [344. Reverse String 双向指针](https://leetcode.com/problems/reverse-string/)
```python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
```
## 字符串
### [13. Roman to Integer 哈希表](https://leetcode.com/problems/roman-to-integer/)
```python
class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        r = d[s[0]]
        for i in range(1, len(s)):
            r += d.get(s[i-1:i+1], d[s[i]])
        return r
```
- 构建一个字典记录所有罗马数字子串，注意长度为2的子串记录的值是（实际值-子串内左边罗马数字代表的数值）
- dict.get(key, default)：判断字典中键key是否存在，存在返回对应的value否则返回default（预定义的值）
- 遍历整个s的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内，如果在就记录值，不在就说明当前位置不存在小数字在前面的情况，直接记录当前位置字符对应值。整个过程时间复杂度为O(N)
- 举个例子，遍历经过IV的时候先记录I的对应值1再往前移动一步记录IV的值3，加起来正好是IV的真实值4
## 二分查找
- :paperclip:【知识卡片】二分查找利用已排好序的数组，每一次查找都可以将查找范围减半。查找范围内只剩一个数据时查找结束。数据量为 n 的数组，将其长度减半 log2n 次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作 log2n 次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为 O(logn)
- :tophat:【套路】
	```python
	self.__class__.__getitem__ = lambda self, x: 向左搜索的条件
	寻找的索引 = bisect.bisect_left(self, True, 0, len(nums)) - 1
	```
	- python 中 bisect 模块针对的是 list, 如果直接构造 list，时间复杂度为 O(N)，因此我们修改当前类的魔法方法伪造 list
	- bisect.left(用于比较的数组，搜索的值，起始范围(包括)，终止范围(不包括))：返回应该插入的位置
### [162. Find Peak Element 二分查找](https://leetcode.com/problems/find-peak-element/)
```python
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        
        while l < r:
            m = (l + r) // 2
            if m > 0 and nums[m - 1] > nums[m]:
                r = m - 1
            elif m < len(nums) and nums[m + 1] > nums[m]:
                l = m + 1
            else:
                return m
        return l
```
- 初始化搜索范围为[0, len(nums)-1]，初始搜索位置为中间位置 m，如果 m 左边存在值比 nums[m] 大，说明[0, m-1]一定存在峰值，我们缩小搜索范围；否则如果 m 右边存在值比 nums[m] 大，说明[m+1, len(nums)-1]一定存在峰值，我们缩小范围；否则 m 就是峰值
- 自古真情留不住，唯有套路得人心，[2行题解](#162-Find-Peak-Element-2行)
## 分治算法
### [973. K Closest Points to Origin 快速选择](https://leetcode.com/problems/k-closest-points-to-origin/)
```python
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        dis = lambda x: x[0]**2 + x[1]**2
        p = dis(points[0])
        l = [x for x in points if dis(x) < p]
        m = [x for x in points if dis(x) == p]
        r = [x for x in points if dis(x) > p]
        
        if K <= len(l):
            return self.kClosest(l, K)
        elif K <= len(l) + len(m):
            return l + m[:K-len(l)]
        else:
            return l + m + self.kClosest(r, K-len(l)-len(m))
```
- 快速选择的一般流程，计算lmr，组合
## 位运算
### [461. Hamming Distance 异或](https://leetcode.com/problems/hamming-distance/)
```python
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')
```