1 求list中从位置i到j的累计和问题
思路：比如求和,$ a[i:j]=a[0:j] - a[o:i] $，然后弄一个list保存0到i之间的累计，大幅节省空间，速度也快
尝试过用2层list保存所有的可能i-j之间的累计和，但是内存爆了
2 数组是有序的
这时要首先考虑二分法
3 (n-1)&n能将n的二进制表示最右边的1变为0
位运算用的多
4 中位数问题
解法3种：
- 统计出现次数
- 排序后中间那个：排序后中间那个，用快排的partition思想（需最后验证是否出现次数过一半）
- 抵消法：把两个不同的数抵消，最后留下的那个就是（需最后验证是否出现次数过一半）
5 链表的精妙操作
快慢指针：可以解决找链表中间节点问题。就是一个指针一次走多步，一个指针一次走一步双指针：可以找倒数第k个节点。一个指针先走k步，然后两个指针每次走相同步数
6 最长回文串问题
回文串就是左右对称的字符串
暴力法，遍历所有子串复杂度$ O(n^3) $动态规划法：算法复杂$ O(n^2) $中心扩展法：算法复杂度$ O(n^2) $Manacher算法（别称马拉车算法）：算法复杂度$ O(n^2) $,博客链接 先利用最右边界的已经匹配过的信息，赋予一个初值，再看看边界还能不能再往外扩展一下
python版本代码
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s = "#" + "#".join(s) + "#"
length = len(s)
ls = [0] * length
rightIndex, centerIndex = 0, 0
answer, index = 0, 0#当前最长回文串半径，中心点
for i in range(length):
if i < rightIndex:
ls[i] = min(rightIndex - i, ls[2 * centerIndex - i])
else:
ls[i] = 1
while i - ls[i] >= 0 and i + ls[i] < length and s[i-ls[i]] == s[i + ls[i]]:
ls[i] += 1
if i + ls[i] > rightIndex:
rightIndex = i + ls[i]
centerIndex = i
if ls[i] > answer:
answer = ls[i]
index = i
return s[index - answer + 1:index + answer].replace("#", "")
7 编辑距离
编辑距离（Edit Distance），又称Levenshtein距离
动态规划:博客地址 用矩阵保存当前距离，三种编辑操作(向右走、向下走、对角线)对应对矩阵的不同操作
8 数组中当前位置要比相邻的数大/小
例题如LeetCode 135
当前点要比左边大，还要比右边大，所以可以分两个for，一次从左到右，一次从右到左，分别考虑两个方向上的大小关系，
9 最长公共子序列 VS 最长公共子串
区别：前者得到的子序列在原始字符串中可以是不连续的，而子串是原字符串中连续的一部分。所以动态规划的公式有点不一样
前者：https://www.cnblogs.com/wkfvawl/p/9362287.html
后者：https://blog.csdn.net/ten_sory/article/details/79857531
10 字符串匹配KMP
基本KMP：https://blog.csdn.net/your_answer/article/details/79619406
改进KMP：http://data.biancheng.net/view/13.html
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
next = self.get_next(needle)
n, m = len(haystack), len(needle)
i, j = 0, 0
while i < n and j < m:
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
else:
j = next[j]
if j == m:
return i - j
else:
return -1
def get_next(self, nums):
j, length = 0, len(nums)
next = [-1] * length#初始化为-1
i = 1
while i < length - 1:
if j == -1 or nums[i] == nums[j]:#因为这里j要加1，所以next初始化为-1
j += 1
i += 1
next[i] = j if nums[i] != nums[j] else next[j]#多跳一步，
else:
j = next[j]
return next
11 滑动窗口
可以解决好几种字符串匹配问题
- 最小覆盖子串：在 S(source) 中找到包含 T(target) 中全部字母的一个子串，顺序无所谓，但这个子串一定是所有可能子串中最短的。[LeetCode ]
- 找到字符串中所有字母异位词
- 无重复字符的最长子串：寻找最长的没有重复字符的子串
思想：设置窗口的左右边界left、right，然后根据规则，不停调整right和left，在遍历过程中保存最佳答案，网址
最小覆盖子串：
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
length = len(s)
start, minLen = 0,length + 1
left, right = 0, 0
match = 0#已经满足计数的字符
window = {}
needs = {}
for c in t:
needs[c] = needs.get(c, 0) + 1
while right < length:
#拓展右边
c = s[right]
if c in needs:
window[c] = window.get(c, 0) + 1
if window[c] == needs[c]:
match += 1
right += 1
#缩左边
while match == len(needs):
if right - left < minLen:
minLen = right - left
start = left
c = s[left]
if c in needs:
window[c] -= 1
if window[c] < needs[c]:
match -= 1
left += 1
return s[start: start + minLen] if minLen < length + 1 else ''
12 Python字符串不能更改问题
在python中字符串是不可改变对象（Immutable），所以无法更改字符串某一位字符。
方法：
- 转为
list：s = list(s) - 转回字符串：
s=''.join(s)
13 牛客网输入问题
在LeetCode上刷题的时候，只需要写处理函数，输入已以函数参数的形式给出，而大多数公司笔试都在牛客网上，或类似网站上，需要写全部代码，包括输入输出
- 一行输入一个数
import sys n = int(sys.stdin.readline().strip()) - 一行输入多个数，每个数以空格隔开
import sys nums = [int(i) for i in sys.stdin.readline().strip().split()]
