LeetCode征途

为了捡回丢掉的数据结构和算法知识，也为了加强自己python编程的能力，LeetCode，Go！

应该想到的：

0、注意审题，题目给出限定条件了就不要去浪费时间了，题目给出了提示要记得挖掘

1、快慢指针破循环

2、顺序数组，二分查找

3、二叉搜索树，查找和更新都是logN，其中序遍历是顺序数组

4、注意看数字范围，巧用数组的下标做文章，还有装桶的操作

5、多个组合或者情形不能慌，可以准备列好，其实没啥变换，如题13

6、巧用栈、队列、堆、哈希表完成一些操作

征途地图：

How to effectively use LeetCode to prepare for interviews!!

Easy

13. Roman to Integer

虽然有很多组合的可能，但是注意审题发现，组合最多两个字母，那干脆把所有可能的组合都放到字典里，然后用get

其中唯一的trick就是c.get(a,b)的意思是，如果c中有a就返回a，否则返回b

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}
sum(d.get(s[i-1:i+1], d[n]) for i, n in enumerate(s))

20.Valid Parentheses

看到题目我还洋洋自得，这个我记得，用栈，然后就开始准备实现栈结构。。结果看了眼题解，发现太强了，虽然是用栈。。。但是用一个字典建立hash表，用左括号当key，对应的右括号为value，结合列表，就完成了匹配。。

基本思想就是，如果是左括号，那就一律入栈，如果是右括号，直接看当前栈顶的括号是否是对应的，如果不是就无法出栈，那就报错，否则就直接退栈，下一个

还有，可以用not stack判断列表是否为空。。。

def isValid(s: str) -> bool:
    dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
    stack = []
    for c in s:
        if c in dic:
            stack.append(c)
        elif dic[stack.pop()] != c :
            return False
    return len(stack) == 0

21. Merge Two Sorted List

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
        else:
            return l1 or l2

141. Linked List Cycle

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

哈希表解法：

def hasCycle(head):
    lookup = set()
    p = head
    while p:
        lookup.add(p)
        if p.next in lookup:
            return True
        p = p.next
    return False

快慢指针：

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head==None or head.next==None:
            return False
        slow,fast = head,head.next
        while fast and fast.next:
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

155. Min Stack

最小栈，一是实现栈，二是找出最小值。最简单就是开一个列表，一个数字记录栈顶，然后找最小就遍历，但是明显这个方法费时间，不中；

辅助栈

那就可以用另一个列表同步记下相应元素时的最小值，也就是同步辅助栈

当然辅助栈也可以不同步，即只在最小值发生变化的时候更新，然后出栈元素是最小值的时候就一起出栈，注意最小值栈在出现与最小值相等元素的时候也要入栈，因为出栈是一起的，入栈如果不入，就弹出去一个了

当然，不出意料嘛，看了题解，又整活了。。。

辅助栈的方法其实是用空间换时间，还是有方法只用一个栈就完成了的，其实记录最小值没问题，关键在于当最小值更新时，如何保存更新前的最小值，否则最小值出栈后就无法找到了，下面两个解法，其实就是想方设法记录下最小值的信息

older-最小值入栈

当最小值更新时，将之前的最小值入栈，保存现场！

入栈值减去最小值

把最小值的信息刻在每一个进栈元素的身体里！

当然还有一个，leetcode上觉得很厉害，但是其实一开始就很直接想到的，用链表呗，节点除了data和next，多定义一个min，头插法实现栈，再用min记录下最小值，其实这个类似于辅助栈啦，只不过双栈合一进化成了小链表而已~

详细的题解：
详细通俗的思路分析，多解法

169. Majority Element

寻找数组中过半的众数，一看到题目感觉就是用hash，就能保证O(n)，但是看了题解发现不仅一种思路。。

1.hash

首先是hash，虽然猜到了，但我想的是用字典，但是忘了可以用python的collection，不过不知道实际面试或者考试的时候是否让使用

另外，得到哈希表之后，如何找出具有最大values的键呢，可以通过max函数，max(counts.keys(), key=counts.get)即通过counts.keys()返回所有键，然后对这些键进行排序，排序的原则即由key=counts.get这句定义，即通过counts.get(key)得到的value进行排序，由此得出最大value的键

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)
# Real hash:
def majorityElement(nums):
    counts = {}
    for num in nums:
        if counts.get(num):
            counts[num] += 1
        else:
            counts[num] =1
    return max(counts.keys(), key=counts.get)

>>>majorityElement([3,2,3,2,2,3,4,4,4,4,4])
4

2.排序

排序后在n/2地方的元素，道理显而易见，排序完，众数在一起，而个数有超过了n/2，所以n/2点的值必为众数

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

3.随机化抽取候选

随机抽取数值然后遍历看是否满足要求，需要分析具体的复杂度，一开始我想的为什么不按顺序选，这样避免了随机抽取有可能脸黑一直抽不到众数，但是一想，因为众数的个数较多，那么抽取的时候按照概率来说是更容易被抽到的，所以随机的方式更好（但是，真的认真想想，还是按顺序抽选好啊，因为数组的初始顺序也就是随机的啊，那按顺序也是更有可能提前找到的吧

import random
class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums)//2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

4.分治

哈，没想到吧。。是的，分治又出现了，其实回头总结反思一下，好多获取数组或者链表信息的题目都可以用到分治，比如找极值，就很典型，这个也是，其实如果能够找出子问题在全局和部分都适用，且能够进行方便的局部比较，分治就应该挺有效的，给自己提个醒。接下来继续讲解法，其实解法一目了然了，不断二分直到一个元素，合并的时候看左右众数是否相等，如果相等就保留，不同就选出现次数多的那个，然后一步步再回来

class Solution:
    def majorityElement(self, nums, lo=0, hi=None):
        def majority_element_rec(lo, hi):
            # base case; the only element in an array of size 1 is the majority
            # element.
            if lo == hi:
                return nums[lo]

            # recurse on left and right halves of this slice.
            mid = (hi-lo)//2 + lo
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid+1, hi)

            # if the two halves agree on the majority element, return it.
            if left == right:
                return left

            # otherwise, count each element and return the "winner".
            left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)

            return left if left_count > right_count else right

        return majority_element_rec(0, len(nums)-1)

5.Boyer-Moore 投票算法

嗯，这个当时考研的时候记得有，但很惭愧我果然忘了

简单理解，因为我们的众数的大于数组元素的1/2的，那么如果哪怕其他所有元素联合起来，和我众数硬碰硬，极限一换一，那么我还是留下至少一个的，基于这个朴素思想，操作开始了：

我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

如果 x 与 candidate 相等，那么计数器 count 的值增加 1；

如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

在遍历完成后，candidate 即为整个数组的众数。

我们举一个具体的例子，例如下面的这个数组：

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

在遍历到数组中的第一个元素以及每个在 | 之后的元素时，candidate 都会因为 count 的值变为 0 而发生改变。最后一次 candidate 的值从 5 变为 7，也就是这个数组中的众数。

当然，这个算法还有更详细的推导：

Boyer-Moore 算法的正确性较难证明，这里给出一种较为详细的用例子辅助证明的思路，供读者参考：

首先我们根据算法步骤中对 count 的定义，可以发现：在对整个数组进行遍历的过程中，count 的值一定非负。这是因为如果 count 的值为 0，那么在这一轮遍历的开始时刻，我们会将 x 的值赋予 candidate 并在接下来的一步中将 count 的值增加 1。因此 count 的值在遍历的过程中一直保持非负。

那么 count 本身除了计数器之外，还有什么更深层次的意义呢？我们还是以数组

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

作为例子，首先写下它在每一步遍历时 candidate 和 count 的值：

nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
candidate:  7  7  7  7  7  7   5  5   5  5  5  5   7  7  7  7
count:      1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4

我们再定义一个变量 value，它和真正的众数 maj 绑定。在每一步遍历时，如果当前的数 x 和 maj 相等，那么 value 的值加 1，否则减 1。value 的实际意义即为：到当前的这一步遍历为止，众数出现的次数比非众数多出了多少次。我们将 value 的值也写在下方：

nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
value:      1  2  1  2  1  0  -1  0  -1 -2 -1  0   1  2  3  4

有没有发现什么？我们将 count 和 value 放在一起：

nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
count:      1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4
value:      1  2  1  2  1  0  -1  0  -1 -2 -1  0   1  2  3  4

发现在每一步遍历中，count 和 value 要么相等，要么互为相反数！并且在候选众数 candidate 就是 maj 时，它们相等，candidate 是其它的数时，它们互为相反数！

为什么会有这么奇妙的性质呢？这并不难证明：我们将候选众数 candidate 保持不变的连续的遍历称为「一段」。在同一段中，count 的值是根据 candidate == x 的判断进行加减的。那么如果 candidate 恰好为 maj，那么在这一段中，count 和 value 的变化是同步的；如果 candidate 不为 maj，那么在这一段中 count 和 value 的变化是相反的。因此就有了这样一个奇妙的性质。

这样以来，由于：

我们证明了 count 的值一直为非负，在最后一步遍历结束后也是如此；

由于 value 的值与真正的众数 maj 绑定，并且它表示「众数出现的次数比非众数多出了多少次」，那么在最后一步遍历结束后，value 的值为正数；

在最后一步遍历结束后，count 非负，value 为正数，所以它们不可能互为相反数，只可能相等，即 count == value。因此在最后「一段」中，count 的 value 的变化是同步的，也就是说，candidate 中存储的候选众数就是真正的众数 maj。

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

复杂度分析

时间复杂度：O(n)O(n)。Boyer-Moore 算法只对数组进行了一次遍历。

空间复杂度：O(1)O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

题解：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/

229. Majority Element II

因为是n/3，且个数是0-2个，不确定，所以很多性质丢失了，上面的方法不一定全能用，比如排序、分治，主要还是推荐BM投票

202. Happy Number

快乐数，我真的是，快乐不起来了，一个是在做这个题的时候突然想起来了一个知识点，百度到了一个博客进去因为博客很漂亮又顺便看了看博客内容结果了发了好多的感慨妈的

还有一个就是，一开始我题目没看懂，然后看了题解，我人又傻了，日常跪真的是，这个竟然是用快慢指针做的。。。

快慢指针破循环，可太强了

而还有个大佬，用你妈的什么魔数，我真是人都傻了，那起止是魔数，就尼玛魔术。。。

正常人的-朴素的-集合

集合，得到一个往里放，如果集合中出现重复的，那必定循环。

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = {1}
        while n not in seen:
            seen.add(n)
            n = sum(int(i) ** 2 for i in str(n))
        return n == 1

虽然方法简单，但是这个题解，语法糖又太酷了。。。

快慢指针

https://leetcode-cn.com/problems/happy-number/solution/shi-yong-kuai-man-zhi-zhen-si-xiang-zhao-chu-xun-h/

魔数

https://leetcode-cn.com/problems/happy-number/solution/ni-ting-shuo-guo-mo-shu-ma-by-jemmyyu/.

还有离谱的递归解法

https://leetcode-cn.com/problems/happy-number/solution/python-1xing-by-knifezhu-9/

为什么说离谱呢，因为除了上面的魔数，就是和我一样不快乐的数最后都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中，而作者还分析出：已知规律：[1-4]中只有1是快乐数，[5~∞]的数字要么回归到1要么回归到4或3，因此可以递归使用判断，直到n小于4且不等于1，则不快乐，如果是1，那指定快乐啊

其中涉及到了尾递归，尾递归为啥能优化？

204. Count Primes

筛出范围内质数的个数，最朴素的想法，肯定是挨个找然后再挨个判断，那复杂度就是O(n^2)，再多想一点就是大一学C的时候就记过其实只要筛到sqrt(n)就够了，因为如果存在能整除的数，肯定一个小于等于sqrt(n)，一个大于等于sqrt(n)，那如果sqrt(n)内没找到，那这个数就是素数了。

接下来，真正的解法：埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，简单来讲就是逆思维，排除法，如果一个不是素数，存在能够整除的数，那么也就能通过整除的数经过相乘得到，那我们可以找到素数后，乘以1/2/3/4/5..直到<=n，那这些都不是素数。

那么，从实现上，就开一个等长数组，先全部置为素数，然后找到一个素数种子就开始乘1/2/3…，得到的结果置为非素数，最后再遍历数组据标记位统计素数个数。

接着，还是要优化哦，首先是筛选素数种子的时候，范围可以缩小为2-sqrt(n)+1，然后是得到素数种子开始种树的时候，这个比较明显，3x2的结果在之前2x3的时候就判断过啦，所以种子的播种范围不该是2，可以从i*i开始，然后接着ix(i++)，而体现出来的也就是等间隔往上加，那么如果就python就应该反映过来可以用列表的切片来当语法糖，so：

def countPrimes(n: int):
    if n<3:
        return 0
    count = [1]*n
    count[0],count[1] = 0,0
    for i in range(2,int(n**0.5+1)):
        if count[i]==1:
            count[i*i::i] = [0] * len(count[i*i::i])
        print(count)
    return sum(count)

这个算法的复杂度：

该算法的时间复杂度比较难算，显然时间跟这两个嵌套的 for 循环有关，其操作数应该是：

n/2 + n/3 + n/5 + n/7 + … = n × (1/2 + 1/3 + 1/5 + 1/7…)

括号中是素数的倒数。其最终结果是 O(N * loglogN)，有兴趣的读者可以查一下该算法的时间复杂度证明。

上述题解参考：
https://leetcode-cn.com/problems/count-primes/solution/ru-he-gao-xiao-pan-ding-shai-xuan-su-shu-by-labula/
和
https://leetcode-cn.com/problems/count-primes/solution/pythonzui-you-jie-fa-mei-you-zhi-yi-liao-ba-by-bru/

事实上，这类题目是一个小领域，叫做素数筛法，有更快的筛法，看有大神提到线性的欧拉筛和亚线性的Atkin筛、Wheel筛，希望以后有机会学习吧。

242. Valid Anagram

有效的字母异位词，看到就想到了，哈希，如果限定了是字母，那就直接开26个空间，对比一下；有一个trick是，不需要开两个26空间然后比对，可以开一个，然后字符串1出现的字母++，字符串2出现的字母—，最后看是否归零；

哈希表之单数组

def isAnagram(s,t):
    if len(s) != len(t):
        return False
    alpha = [0]*26
    for i in range(len(s)):
        alpha[ord(s[i]) - ord('a')] += 1
        alpha[ord(t[i]) - ord('a')] -= 1
    for chars in alpha:
        if chars:
            return False
    return True

哈希表之集合

def isAnagram(s,t):
    if len(s) != len(t):
        return False
    set_s,set_t = set(s),set(t)
    if set_s == set_t:
        for x in set_s:
            if s.count(x) != t.count(x):
                return False
        return True
    else:
        return False

哈希表之collection

from collections import Counter
def isAnagram(s,t):
    return Counter(s) == Counter(t)

另外，看了题解也可以先对字符串字母排序，排序完比对，感觉也挺快的；

排序后比对

def isAnagram(s,t):
    return sorted(s)==sorted(t)

371. Sum of Two Integers

题目很简单，简单到我傻眼，当然，我的傻眼是指他妈这题咋做啊，求和，然后不能用加减法

好吧，改为二进制通过位运算算出结果

def getSum(a, b):
    if not a:
        return b
    while b != 0:
        temp = a^b
        b = ( a&b ) << 1
        a = temp 
    return a

上述是单纯版，其他语言类似逻辑就搞定了，但是在python里不行，因为：

Python太厉害了，嗯，他的int不是32位的，他的位数是动态增长的（可以下看面代码）

sys.getsizeof(0)
sys.getsizeof(1)
sys.getsizeof(-1)
sys.getsizeof(999999)
sys.getsizeof(999999999999)
sys.getsizeof(999999999999999999999)
output:
24
28
28
28
32
36

也就是说咱们左移的话不是溢出的，而是增加位数的，这就需要我们手动对 Python 中的整数进行处理，手动模拟 32 位 INT 整型。

具体做法是将整数对 0x100000000 取模，保证该数从 32 位开始到最高位都是 0。

所以需要深思熟虑版：

def getSum(a, b):
    # 2^32
    MASK = 0x100000000
    while b != 0:
        # 计算进位
        carry = (a & b) << 1 
        # 取余范围限制在 [0, 2^32-1] 范围内
        a = (a ^ b) % MASK
        b = carry % MASK
    # 整型最大值
    MAX_INT = 0x7FFFFFFF
    MIN_INT = MAX_INT + 1
    print(MAX_INT,MIN_INT,MASK)
    return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)   
or
def getSum(a, b):
    # 2^32
    MASK = 0x100000000
    while b:
        carry = ( (a&b) << 1) % MASK 
        a = ( a^b ) % MASK
        b = carry
    return a if a < MASK/2 else ~( a ^ (MASK-1) )

题解：位运算详解以及在 Python 中需要的特殊处理

Python 位运算一些坑

原码、反码、补码知识详细讲解（此作者是我找到的讲的最细最明白的一个）

好沉重，好难，所以，

还有滑稽版

def getSum(self, a, b):
    return sum([a, b])

。。。。。。

88. Merge Sorted Array

合并两个排序的字序列

合并后排序

可以直接合到一个序列里再排序，时间复杂度O( (m+n) lg(m+n) )

双指针合并——边插入边排序

就和归并排序里的合并两个序列一样，只不过这里因为是直接修改nums1，所以需要额外开个空间，
所以基本思路：双指针合并，需要O(n)个空间，时间复杂度就是m+n

但是看了题解有一个不需要额外空间的高级版：

双指针倒序合并，不需要额外空间

就是倒着插入，因为第一个子序列的末尾都是0，所以先插入这些，就不会占用空间了

def merge(nums1, m, nums2, n):
    p1 = m-1
    p2 = n-1
    p = (m+n)-1
    while p1>=0 and p2>=0:
        if nums1[p1]>=nums2[p2]:
            nums1[p]=nums1[p1]
            p1 -= 1
        else:
            nums1[p]=nums2[p2]
            p2 -= 1
        p -= 1
    if p2>=0:
        nums1[:p2+1] = nums2[:p2+1]
    print(nums1)

108. 将有序数组转换为二叉搜索树

中序遍历二叉搜索树出来的就是排序好的数组，所以用中序遍历的方式对数组进行建树就好

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def sortedArrayToBST(self, nums) -> TreeNode:
        if nums:
            m = len(nums) // 2
            r = TreeNode(nums[m])
            r.left, r.right = map(self.sortedArrayToBST, [nums[:m], nums[m+1:]])
            return r

189. Rotate Array

字符串平移，可以切片，可以通过反转

切片

def rotate(nums,k) -> None:
    k = k % len(nums)
    if k == 0:
        return
    nums[:-k], nums[-k:] = nums[-k:], nums[:-k]
    # 或者
    #nums[:] = nums[-k:] + nums[:-k]
    print(nums)

字符串反转

def rotate(nums,k) -> None:
    def reverse(nums,start,end):
        while start < end :
            nums[start],nums[end] = nums[end],nums[start]
            start +=1
            end -=1
    l = len(nums)
    k = k%(l)
    reverse(nums,0,l-1)
    reverse(nums,0,k-1)
    reverse(nums,k,l-1)

辅助变量

要么把一部分变量取出，之后放回，要么直接找个新的数组存值

下面是明明输出对了，但是一直提示num没修改，我他妈百思不得其解为啥。。。

from copy import deepcopy
def rotate(nums,k) -> None:
    l = len(nums)
    a = [0]*l
    for i,num in enumerate(nums):
        a[(i+k)%(l)] = num 
    nums = deepcopy(a)
    print(a,nums)

205. Isomorphic Strings

首先想到的就是隐射，利用字典的一一对应和集合的排除重复项：

def isIsomorphic(s,t) -> bool:
    if len(s)!=len(t):
        return False
    stot_dict = {}
    t_used = set()
    for ss,tt in zip(s,t):
        if ss not in stot_dict:
            if tt not in t_used:
                stot_dict[ss]=tt
                t_used.add(tt)
            else:
                return False
        elif stot_dict[ss]!=tt: 
            return False
    return True

226. 翻转二叉树

左右交换，递归调用就好

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.right, root.left = root.left, root.right
        self.invertTree(root.right)
        self.invertTree(root.left)
        return root

448. 找到所有数组中消失的数字

简单的就类似桶排序，有的就进去消掉，但是空间复杂度是O(n)

厉害的就是不使用额外的空间复杂度，有一个题解说的很好，首先要从题目中挖掘条件，比如说数组是小于n的，那么就联想到用下标，所以就是在第一轮遍历的时候对出现过的数字所对应的下标做一些小标记，同时又不影响遍历，然后第二次遍历就可以没出现过的挑出来了

https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-de-shu-zi-2/576154

能用方法2解答必定是有限制条件,比如前面说了1到n,然后在限制条件上做文章 套路是 在首次遍历的时候做点小动作,但是不影响首次遍历. 在第二次遍历的时候根据第一次遍历的小动作就能区别出某些元素是否符合题意. 你可以看下这个,我加了点注释,这个和官方用 * -1 是一样的

public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList();
        int n = nums.length;
        for(int i = 0; i < n; i++){
            // 以出现过元素为下标,使该下标所在元素 + n,用于后续区分是否出现过
            // 由于对 n 取模,所以即使+n也不影响第一次for循环,结果为所有出现过元素的所在下标的值都会+n
            nums[(nums[i] - 1) % n] += n;
        }
        for(int i = 0; i < n; i++){
            // 如果该元素 <= n,说明没有出现过
            if(nums[i] <= n)
                res.add(i + 1);
        }

572. 另一个树的子树

首先定义一个函数，判断两棵树是否相同，其条件就是根相同，左右俩儿子相同，即取 and

再定义一个函数，寻找是否存在这样的子树与待匹配树相同，那就通过遍历，然后取 or

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSametree(self,s,t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.isSametree(s.left,t.left) and self.isSametree(s.right,t.right)
    
    def isSubtree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

当然还有好玩的办法啦，一个就是还想到过的，一个遍历把树和待匹配子树都变成字符串，然后比对待匹配树的字符串是否为当前树的子串，这里需要注意两个点，第一个trick是，一个树的先序遍历即DFS的输出中子树就是连续的，第二个trick是，还需要额外的判断，因为存在空节点，如假设 s由两个点组成，1是根，22 是1的左孩子；t也由两个点组成，1是根，2是1的右孩子。这样一来s和t的 DFS 序相同，可是t并不是s的某一棵子树，所以可以通过lnull和rnull来标记左右两空孩子，再来遍历

转换完后就是字符串匹配了，那可以暴力或者仍有印象的kmp了

还有一种是树哈希

题解地址：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/

557.Reverse Words in a String III

句子中的单词分别倒序，一想到就可以通过python切片的[::-1]的特性，但从数据结构的角度，这种逆序输出，应该马上想到栈，是的可以把单词压入栈然后出栈，实现单词的逆序，但是要注意出栈的条件即单词结束的标志

def reverseWords(s) -> str:
    # 分割完倒序直接放进
    return ' '.join( [ss[::-1] for ss in s.split(' ')] )
    # 两次倒序
    return ' '.join( s.split(' ')[::-1] )[::-1]

589. N叉树的前序遍历

递归遍历比较简单嘛，就是自己，然后儿砸，要注意的是，不是一个个吐，要开一个list存

迭代那也类似，

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if root is None:
            return []
        stack, output = [root], []
        while stack:
            root = stack.pop()
            output.append(root.val)
            stack.extend(root.children[::-1])
        return output

605. Can Place Flowers

def canPlaceFlowers(flowerbed,n) -> bool:
    count = 0
    for i in range(len(flowerbed)):
        if flowerbed[i]==0 and ( i==0 or flowerbed[i-1]==0 ) and ( i+1==len(flowerbed) or flowerbed[i+1]==0 ):
            flowerbed[i] = 1
            count += 1
        if count>=n:
            return True
    return False

直接判断自身和上一个、下一个的数值

也可以你通过前后补零的方式，使得头尾统一

617. 合并二叉树

递归或者是迭代的

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        # 递归
        # if not ( t1 and t2 ):
        #     return t1 if t1 else t2
        # t1.val += t2.val
        # t1.left = self.mergeTrees(t1.left,t2.left)
        # t1.right = self.mergeTrees(t1.right,t2.right)
        # return t1

        # 迭代
        if not (t1 and t2):
            return t1 if t1 else t2
        queue = [(t1,t2)]
        while queue:
            r1,r2 = queue.pop(0)
            r1.val += r2.val
            if r1.left and r2.left:
                queue.append( (r1.left, r2.left) )
            elif not r1.left:
                r1.left = r2.left
            if r1.right and r2.right:
                queue.append( (r1.right,r2.right) )
            elif not r1.right:
                r1.right = r2.right    
        return t1

665. 非递减数列

是很简单，但是要注意特殊情况！ 首先比较的时候都是比较num[i]与num[i-1]，那么可以把自己变大和前面一个一样大，也可以把前面的变小和自己一样大，所以是有两种可能，都要去尝试，而如果这两种不行，哪怕只有一个数字出现了这个问题，但是怎么试都没用的，所以注意count计数底下的外加判断

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        for i in range(1,len(nums)):
            if nums[i] < nums[i-1]:
                count += 1
                if i+1 < len(nums) and i-2 >= 0:
                    if nums[i+1] < nums[i-1] and nums[i-2] > nums[i]:
                        return False
            if count > 1:
                return False
        return True

作者：han-han-a-gou
链接：https://leetcode-cn.com/problems/non-decreasing-array/solution/python3xiang-jie-bu-gai-bian-shu-zu-yuan-su-zhi-ch/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

669. 修剪二叉搜索树

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

资料：二叉查找树与平衡二叉树

关键点：二叉搜索树的删除节点：

• 如果删除的是叶节点，可以直接删除；
• 如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
• 如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除

题解：题解其实提示了，可能需要修改根节点，那先判断根节点的值，如果根节点大于R，那根节点和其右边的子树都没了，那就先把左子树作为根节点，如果根节点<L，那就根节点和左边的子树的都没了，先把右子树作为根节点，如果L<=root<=R，那就先保留根节点，然后继续遍历左右子树。大框架上呢，其实还是按照往常关于树的问题，每一颗子树也是一棵树，那么就可以递归地去做，也就是递归的地判断当前的根节点是否合适

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        def dfs(root, L, R):
            if root is None:
                return 
            if root.val > R:
                return dfs(root.left,L,R)
            elif root.val < L:
                return dfs(root.right,L,R)
            else:
                root.left = dfs(root.left,L,R)
                root.right = dfs(root.right,L,R)
                return root
        return dfs(root,low,high)
作者：Jiang_Kun
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/solution/669-xiu-jian-er-cha-sou-suo-shu-di-gui-by-jiang_ku/

674. 最长连续递增子序列

挨个向前比较，如果大那就继续+1，并且存下当前最长的，如果不递增了，置1

def findLengthOfLCIS(nums) -> int:
    if len(nums)<=1:
        return len(nums)
    max_str = count = 1
    for i in range(len(nums)):
        if i and nums[i]>nums[i-1]:
            count += 1
            max_str = max(max_str,count)
        else:
            count = 1
    return max_str

记录最长子序列的下标anchor，计算差值 i- anchor +1

def findLengthOfLCIS(nums) -> int:
    ans = anchor = 0
    for i in range(len(nums)):
        if i and nums[i-1]>=nums[i]:
            anchor = i
        else:
            ans = max( ans, i-anchor+1 )
    return ans

703. 数据流中的第K大元素

排序，或者利用python的小顶堆

import heapq
class KthLargest(object):
    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.data = nums
        print(self.data,type(self.data))
        heapq.heapify(self.data)
        print(self.data,type(self.data))
        while len(self.data)>k:
            heapq.heappop(self.data)
        
    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.data) < self.k:
            heapq.heappush(self.data, val)
        elif self.data[0] < val:
            heapq.heapreplace(self.data,val)
            
        return self.data[0]

test：

nums = [4,5,8,2]
kl = KthLargest(3,nums)

kl.add(3)
kl.add(5)
kl.add(10)
kl.add(9)

Output：
4
5
5
8

705. 设计哈希集合

1、单独链接法

按照hash的求模，分桶，然后桶里面可以用列表，但是列表的插入删除是O(N)，所以建议采用链表，这样插入删除的复杂度就是O(1)了

先在hashset里定义合适的桶，合适的定义是较大且最好为质数，如题解建议的769，然后定义题目要求的函数操作

在底下定义好桶的数据结构，定义其基本操作，然后再定义单个节点的链表结构，即地址与值（其实应该是反过来）

可以改进的：虽然插入删除的复杂度是O(1)，但是查找的时间复杂度是O(N)，而查找速度快的结构可能更新速度慢，如排序列表，所以查找的复杂度和更新的复杂度都需要考虑，可以采用查找，删除，插入操作时间复杂度都为O(logN) 的二叉搜索树（二叉查找树）

题解参考：设计哈希集合

852. 山脉数组的峰顶索引

注意审题，确定是山脉的数组，所以最简单就是顺序查找最大的

改进方案是二分查找，应该要想到在已经排序的数组里，最快的肯定是二分

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l,h = 0, len(arr)-1
        while l < h:
            m = l + (h-l)//2
            if arr[m-1] < arr[m]:
                l = m
            else:
                h = m+1
        return m

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        low=0
        high=len(arr)-1
        while low<high:
            mid = ( low+high ) // 2
            if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
                return mid
            elif arr[mid]>arr[mid+1]:
                high = mid+1
            else:
                low = mid
        return mid

题解：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/solution/shan-mai-shu-zu-de-feng-ding-suo-yin-by-leetcode/

1160. 拼写单词

python自带的collections模块的Counter函数，或者通过26字母打表，注意ord为取char字符ascii码的函数，

import collections
class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        # 利用集合collection
        # c_chars = collections.Counter(chars)
        # result = 0
        # for word in words:
        #     c_word = collections.Counter(word)
        #     if all( c_word[char] <= c_chars[char] for char in c_word ):
        #         result += len(word)
        # return result

        # 26字母打表
        def alpha_colleciton(word:str):
            word = list(word)
            word_count = [0]*26
            for char in word:
                word_count[ ord(char)-ord('a') ] += 1 
            return word_count

        c_chars = alpha_colleciton(chars)
        result = 0
        for word in words:
            c_word = alpha_colleciton(word)
            if all( c_word[i] <= c_chars[i] for i in range(26) ):
                result += len(word)
        return result

二叉树模板

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 递归
# 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
# 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn)

# 递归1：二叉树遍历最易理解和实现版本
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        # 前序递归
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
        # # 中序递归 
        # return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
        # # 后序递归
        # return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

# 递归2：通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(cur):
            if not cur:
                return      
            # 前序递归
            res.append(cur.val)
            dfs(cur.left)
            dfs(cur.right) 
            # # 中序递归
            # dfs(cur.left)
            # res.append(cur.val)
            # dfs(cur.right)
            # # 后序递归
            # dfs(cur.left)
            # dfs(cur.right)
            # res.append(cur.val)      
        res = []
        dfs(root)
        return res



# 迭代
# 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
# 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)

# 迭代1：前序遍历最常用模板（后序同样可以用）
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []        
        res = []
        stack = [root]
        # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res
        
        # # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
        # while stack:
        #     cur = stack.pop()
        #     if cur.left:
        #         stack.append(cur.left)
        #     if cur.right:
        #         stack.append(cur.right)
        #     res.append(cur.val)
        # return res[::-1]

# 迭代1：层序遍历最常用模板
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        cur, res = [root], []
        while cur:
            lay, layval = [], []
            for node in cur:
                layval.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            cur = lay
            res.append(layval)
        return res

        
        
# 迭代2：前、中、后序遍历通用模板（只需一个栈的空间）
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]: 
        res = []
        stack = []
        cur = root
        # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res
        
        # # 前序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.left
        #     cur = stack.pop()
        #     cur = cur.right
        # return res
        
        # # 后序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.right
        #     cur = stack.pop()
        #     cur = cur.left
        # return res[::-1]
        


# 迭代3：标记法迭代（需要双倍的空间来存储访问状态）：
# 前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
# 而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [(0, root)]
        while stack:
            flag, cur = stack.pop()
            if not cur: continue
            if flag == 0:
                # 前序，标记法
                stack.append((0, cur.right))
                stack.append((0, cur.left))
                stack.append((1, cur))
                
                # # 后序，标记法
                # stack.append((1, cur))
                # stack.append((0, cur.right))
                # stack.append((0, cur.left))
                
                # # 中序，标记法
                # stack.append((0, cur.right))
                # stack.append((1, cur))
                # stack.append((0, cur.left))  
            else:
                res.append(cur.val)  
        return res
        
        # # 层序，标记法
        # res = []
        # queue = [(0, root)]
        # while queue:
        #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
        #     if not cur: continue
        #     if flag == 0:
                  # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
        #         queue.append((1, cur))
        #         queue.append((0, cur.left))
        #         queue.append((0, cur.right))
        #     else:
        #         res.append(cur.val)
        # return res



# 莫里斯遍历
# 时间复杂度：O(n)，n为节点数，看似超过O(n)，有的节点可能要访问两次，实际分析还是O(n)，具体参考大佬博客的分析。
# 空间复杂度：O(1)，如果在遍历过程中就输出节点值，则只需常数空间就能得到中序遍历结果，空间只需两个指针。
# 如果将结果储存最后输出，则空间复杂度还是O(n)。

# PS：莫里斯遍历实际上是在原有二叉树的结构基础上，构造了线索二叉树，
# 线索二叉树定义为：原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点
# emmmm，好像大学教材学过，还考过

# 此处只给出中序遍历，前序遍历只需修改输出顺序即可
# 而后序遍历，由于遍历是从根开始的，而线索二叉树是将为空的左右子节点连接到相应的顺序上，使其能够按照相应准则输出
# 但是后序遍历的根节点却已经没有额外的空间来标记自己下一个应该访问的节点，
# 所以这里需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
# 具体参考大佬博客

# 莫里斯遍历，借助线索二叉树中序遍历（附前序遍历）
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        # cur = pre = TreeNode(None)
        cur = root

        while cur:
            if not cur.left:
                res.append(cur.val)
                # print(cur.val)
                cur = cur.right
            else:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right
                if not pre.right:
                    # print(cur.val) 这里是前序遍历的代码，前序与中序的唯一差别，只是输出顺序不同
                    pre.right = cur
                    cur = cur.left
                else:
                    pre.right = None
                    res.append(cur.val)
                    # print(cur.val)
                    cur = cur.right
        return res



# N叉树遍历
# 时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。
# 空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。
# 将根节点推出栈后，需要将这些节点都放入栈，共有 M−1个节点，因此栈的大小为 O(M)。


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

# N叉树简洁递归
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root: return []
        res = [root.val]
        for node in root.children:
            res.extend(self.preorder(node))
        return res

# N叉树通用递归模板
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        def helper(root):
            if not root:
                return
            res.append(root.val)
            for child in root.children:
                helper(child)
        helper(root)
        return res

# N叉树迭代方法
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        s = [root]
        # s.append(root)
        res = []
        while s:
            node = s.pop()
            res.append(node.val)
            # for child in node.children[::-1]:
            #     s.append(child)
            s.extend(node.children[::-1])
        return res
作者：821218213
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/python3-er-cha-shu-suo-you-bian-li-mo-ban-ji-zhi-s/