刷题打卡，边自我督促边回顾整理

新人来打刷题卡
希望一边监督自己一边起到回顾整理的作用
求大米看帖子啦

bfs
1.serialize and deserialize binary tree
虐心题，每一步都要考虑好。 deserialize的时候，要注意：
slow_index和fast_index用处不同，slow_index 的作用是指向nodes中的每一点（nodes中的点自身都有值（因为下面有两个条件判断））并为这些点添加左右子节点的值； fast_index 的作用是遍历所有bfs_order，配合slow_index进行赋值
-------------------------------------------------------------
2. binary tree level order (traverse)
1).append(node.val)注意这个val
2).reversed(result)出来的结果必须加一个list()来把它变成一个list
--------------------------------------------------------------

今天主要刷的是二分法
Total Occurrence of Target
Rotate String
Search in a rotated array
Search for a range (找一个数出现的范围时采用两次二分，找出该数出现的第一个和最后一个位置，注意判断条件时 两次 中间位置的判断条件不同)
Search a 2d matrix
Find K closest elements(背向双指针）

今日持续二分法：
1.Search in rotated sorted array (无重复元素） 可以通过和第一个数或者最后一个数比将序列二分
2.Search in rotated sorted array (有重复元素） 无法二分 只能使用暴力解法 O(n)
3.Search in a 2D Matrix
二维矩阵：
可以采用逼近法，从左下角开始往上逼近
若等于target count+=1
若小于target 则这一列就可以划掉了（因为每一列的最下面一个数最大）
若大于target 则这一行就可以划掉了（因为每一行的最左边一个数最小）
4.Closest Number in Sorted Array

今天开始双指针啦
1.Valid Palindrome 回文串变形 有特殊符号和大小写：
对于空字符串和符号的处理没有考虑到 如果遇到应该跳过
自己写的时候对长度是奇数和偶数分类了但是实际上只要在start >= end的时候
s[start] == s[end]就可以统一判定
一定要时刻确保 检验时 start < end
但凡使用while循环一定不要陷入死循环！

2.valid palindrome 判断至多删掉一个字符是否能构成回文串
函数化思想 可以定义一个函数 isPalindrome() 在第一次判断出左边和右边不想等时，将分别删掉左右后的字符串 传入这一函数

3.Two sum:
如果有下标用hash table会更好 可以轻松建立下标和数之间的关系

4.Remove Duplicate numbers:
while j < len(nums):
            if nums[j] != nums[j - 1]:
                nums[i] = nums[j]
                i += 1
            j += 1     
        return i   
条件判断时， j< len(nums)
因为 下面比较的是 nums[j]   and nums[j-1]
所以不仅不会index超出 如果j< len(nums) -1 还会使得无法遍历到最后一个数

不是首尾两个指针比较 而是右边指针和自身位置前一个元素比较

今天时间比较多
再来几道
Two Sum (UNIQUE PAIRS)：
1.要unique 要保证找到一对以后left 和right 指针移动到和当前不同的位置上去
2.要时刻保证left < right 这个判定，内部判定的时候也是，不然会index超出

Three sums (Unique Pairs)：
先sort 然后对最小数做for 循环，可以转化为Two Sums 的问题
但是注意要对最小的数也避免重复

来打今天的卡
持续双指针：
1.Two sum 变形-- less than or equal to target:
-----------------------
本题可以循环其中一个数，从头开始，另外一个数每次最后开始向前，一旦右边的数<= target - nums[left] 那么right左边的数组均小于
注意的点：
1.不要忘记排序
2.一旦找到了一组值， 用break跳出循环，不然会无限循环
---------------------
2.Two Sum (Closest to target)
-------------------------
因为从左右逼近是差值有正有负，所以记下每一次的差值
当左右指针对应的数相加大于target时，左指针左移
反之右移，保证和离target更近
----------------------
3.Three sum (Closest to target)
----------------------
固定第一个数，第一个数的范围用range(len(numbers))即可，因为下一步会判断left < right 才执行
同样 记录sum
移动左右指针使得结果更逼近target
----------------------
4.Partition Array
----------------------
注意的点：
1.left <= right 每一次都要判断 一开始，判断于target的关于，以及交换位置前 都要换位置
2.注意left 和right指针的变动，避免造成无限循环
3.最后结束循环时left已经在right的右边了，所以返回的第一个值是left
----------------------

今日份刷题：
1.middle of linked list
用两个指针 slow = slow.next
fast = fast.next.next
当fast == None 的时候return slow 即可
----------------------------------
2.Move Zeroes
同向双指针，right走的快一些
如果right遇到不是0的数 进行交换 换到前面来
同时left += 1
如果遇到是0的数跳过。
-------------------------
3.Kth smallest numbers
1.可以写一个快速排序 然后直接取出第k-1个元素
注意快速排序的写法 先partition 然后左右递归
2.可以边partition 边比较
（1）第k小不在[start, right]和[left, end]这两个区间，说明pivot就是第k小并且其index为k，实际上你返回pivot或者nums[left - 1]或者nums[right + 1]也可以。
（2）因为你调用的还是原数组，原数组的index没有变，所以start = left, end = end, k = k
如果你new一个新的数组，start = 0, end = end - left, k就得等于k - 左边部分的数组长度了。
----------------------------
4.kth largest element
和smallest 相同的思路 做partition的时候把大的数字往左排即可
----------------------------
5.Partition Array by Odd and Even numbers
仍然是partition 问题 按照模板写即可

周末总结本周做题时间到了：
今天复习二分法题目：
while 循环的目的不是找到答案，而是将答案的范围缩小至两个数之间，再根据条件进行判断
相关题目
1. first position of target
2.last position of target
分别返回左指针 右指针

二分的核心不是数字而是将数据分为满足两个不同条件的subset，每次判断属于哪个subset
3. First bad version
4.find minimun in rotated array
找的这个数实际是小于等于最后一个数的第一个数 只有和数组的最后一个数比才能成功二分
5.maximum number in mountain sequence
二刷有惊喜，判断语句必须写nums[mid] > nums[mid + 1] 因为mid的值左偏，所以不会超出范围，如果以小于判断 会index 超出

持续周末总结：
今天是partition相关（震惊于居然前两天刷的题今天一点都想不起来了，所以果然是得二刷三刷四刷）
1.partition(基础题目）
2.kth smallest element
3.kth largest element
先进行partition，每次通过比较中点和k的位置，对范围进行缩小（二分mixpartition）
4.partition array by odd and even (标准partition）
5.interleaving positive and negative numbers
1)函数化编程， 写一个函数来做正数和负数的合并
2)巧妙的将数量大的list放在同一个位置

6. Sort colors
partition + recuision 很像quick sort，每一步使整体先有一个顺序，然后递归
7.sort colors 2 把需要排序的数抽象成了n ，是上面一道题的模板

同向双指针：
8.滑动窗口
注意left和right 的位置，不然会错一位
9.Remove duplicates
两种做法 用hashset的话注意hashset 不能用index取数 可以用pop
双指针的话要先sort O(nlogn)