二叉树是否是其子结构
从根节点开始，不是，看左节点，再看有节点
链表合并
翻转链表
链表找入口
链表蛇形打印
数组中重复的数字
二维数组找target
替换空格
两个指针 一个指向末尾，一个指向替换后的字符串的末尾
逆序输出链表
栈，加递归
构建乘积数组，遍历两次，从头然后从尾部
不用运算法则做加法
求 1+...+n
&&的短路原理
股票的最大利润，找到当前最小值，和当前最大差值，进行替换
圆圈中最后剩下的数字
扑克牌中的顺子，判断是否连续，中间差不要大于王的个数，或者直接小于四
n个骰子的点数
递归
反轉句子中单词的顺序
队列的最大值（窗口）
两个列表，一个缓存窗口，一个缓存最终最大值的变量，窗口需要满足是一个两端的队列，最大值在0，如果超过size大小，则pop 0，如果新来的比原有缓存窗口的值大，在pop，
和为s的两个数字之乘积最小
遍历两次，拿到所有组合放到ls中，取ls[0]
搜索旋转排序数组 logn 就是二分的思想
数组不存在重复数字
举例子观察left和right取等号不？，先找第一遍分界点，logn，再二分查找，logn
（数组是否是重复的）
找到中间位置
考虑元素重复 加边界条件 如下
数组中数字出现的次数
顺时针打印矩阵
行列大于2倍的start
二叉树的深度
递归调用函数也需要加self
平衡二叉树
二叉搜索树k大的节点
二叉搜索树中左节点小于根节点，右节点大于根节点，通过中序遍历即可排序，再取第k
大的节点
排序数组中查找数字出现次数
classSolution:
defGetNumberOfK(self, data, k):
# write code here
count =len(data)
i =0
forj inrange(count):
ifdata[j] ==k:
i +=1
returni
排序数组，想到二分查找，先找到第一个存在的k，在找到最后一个存在的k，找到中间位置，若等于该数字，判断前一个是不是该数字，是的话，再继续二分查找，直到找到等于该数字，且前一个不是该数字的位置。
递增排序数组中缺失的数字，log（n）的解决方案，遍历用总和减去目前的和
log（n）考虑转换题目为找出第一个值与下标不相等的元素
num[middle] != middle
链表找环，
思路一 两个链表接起来，找到相同的点
思路二，先遍历一遍，确定两个链表的长度，然后求出差值，长的链表先走差值的歩数
数组中的逆序对
mergesort
逆序对
public class Solution {
public int InversePairs(int [] array) {
if(array==null||array.length==0)
{
return 0;
}
int[] copy = new int[array.length];
for(int i=0;i<array.length;i++)
{
copy[i] = array[i];
}
int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
return count;
}
private int InversePairsCore(int[] array,int[] copy,int low,int high)
{
if(low==high)
{
return 0;
}
int mid = (low+high)>>1;
int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
int count = 0;
int i=mid;
int j=high;
int locCopy = high;
while(i>=low&&j>mid)
{
if(array[i]>array[j])
{
count += j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007)//数值过大求余
{
count%=1000000007;
}
}
else
{
copy[locCopy--] = array[j--];
}
}
for(;i>=low;i--)
{
copy[locCopy--]=array[i];
}
for(;j>mid;j--)
{
copy[locCopy--]=array[j];
}
for(int s=low;s<=high;s++)
{
array[s] = copy[s];
}
return (leftCount+rightCount+count)%1000000007;
}
}
字符串中第一个只出现一次的字符，python采用count
hash 第一遍求出出现的次数，第二遍挑出等于1的
classSolution:
defFirstNotRepeatingChar(self, s):
# write code here
index =0
iflen(s) ==0:
return-1
else:
forx ins:
ifs.count(x) ==1:
returnindex
index +=1
字符流中第一个不重复的数字，是一个不断迭代不断更新的过程，通过两个函数方法实现，一个更新s和dict， 一个检查
寻找丑数
第一种写一个判断是不是丑数的函数
% 2,3,5=0 则整除2.3,5最终为1则为丑数，挑出第1500个每个数字都需要计算
第二种通过增加辅助数组减少换取时间上的效率
三个指针开始移动乘以2,3,5 取最小
最长不含重复字符的子字符串
class Solution:
def lengthOfLongestSubstring(self, s):
""" :type s: str
:rtype: int
""" start=0
maxLength=0
usedChar={}
foriin range(len(s)):
ifs[i]inusedCharandstart<=usedChar[s[i]]:
start=usedChar[s[i]]+1else:
maxLength=max(maxLength,i-start+1)
usedChar[s[i]]=i
return maxLength
动态规划的思路
通过一个trcik 定义一个26长度的数组，初始-1，来记录上一次出现该字符的位置
如果没出现过或者上次出现过的距离大于当前最大长度
则当前长度++
否则上次出现过的最大距离等于当前长度再与最大长度作对比进行替换
礼物的最大价值
动态规划，python版本，基于递归的思路用大量重复计算，采用循环则代码效率会高很多，为了缓存中间结果需要辅助数组。
def getMaxValue1(self,array,rows,cols):
# write code hereifarray==[]orrows<=0orcols<=0:
return 0
maxValues=[[0foriinrange(cols)]forjin range(rows)]
foriin range(rows):
forjin range(cols):
left=0
up=0
ifi>0:
#如果行号大于0，说明它上面有数字up=maxValues[i-1][j]
ifj>0:
#如果列号大于0，说明它左边有数字left=maxValues[i][j-1]
maxValues[i][j]=max(up,left)+array[i*cols+j]
returnmaxValues[rows-1][cols-1]
通过规律可以发现只添加一个长度等于列的数组即可
def getMaxValue2(self, array, rows, cols):
# write code hereifarray == []orrows <= 0orcols <= 0:
return 0
maxValues=[0foriin range(cols)]
foriin range(rows):
forjin range(cols):
up=0
left=0
ifi>0:
#如果行号大于0，说明它上面有数字。up仍为当前列的maxValueup=maxValues[j]
ifj>0:
#如果列号大于0，说明它左边有数字。left=maxValues[j-1]
maxValues[j]=max(up,left)+array[i*cols+j]
returnmaxValues[cols-1]
把数字都翻译成字符串
采用动态规划的思路，从最小的开始计算
通过归纳定义一个函数fi＝fi＋1 ＋g＊fi+2，如果第i位置和i+1位置的和在10-25以内的时候，g＝1否则为零
把数组排成最小的数
先把数字转换成字符串，然后在函数中定义比较规则，在采用qsort，最终的复杂度等于qsort 为O（nlogn）比拼接所有组合的n！要小
sorted(iterable, cmp=None, key=None, reverse=False)
iterable -- 可迭代对象。 cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。 key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。 reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）
数字序列中的某一位数字
找到规律发现对应的数字是什么，判断对应的数字是哪个区间内呢，10， 180，2700，在找到这个区域开始的位置，0,10,100然后取得该位置for i <biginnumer, numbers/10
1~n中1出现的次数
暴力解法
连续子数组的最大和
当前最大和的初始值应为一个负数 greatSum=float('-inf')
数据流中的中位数
一遍排序，一遍取中位数
偶数的时候一个为下标，一个为下标-1
最小的k个数
可以最大堆，或者快排
快排的partion
数组中出现一半的数字
快排取中位数
字符串的排列
python itertools
combinations方法重点在组合，permutations方法重在排列。
combinations和permutations返回的是对象地址，原因是在python3里面，返回值已经不再是list,而是iterators（迭代器）, 所以想要使用，只用将iterator 转换成list 即可
java或者cpp采用递归的思路，分成两部分，一部分是第一个字符，另一部分是后边所有字符，第一个字符和后边所有字符来替换
写java 包的引用与熟练,采用java 用下标ij作为指针。
重建二叉树
要求节点不能重复，先序遍历，加中序遍历
找到根节点，然后知道左右两颗子树通过递归实现
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int length=pre.length;
if(length==0){
return null;
}
if(length==1){
TreeNode flag = new TreeNode(pre[0]);
//flag.val=pre[0];
return flag;
}else{
TreeNode flag = new TreeNode(pre[0]);
int gen=0 ;
for(int i=0;i<in.length;i++)
{
if(in[i]==pre[0])
{
gen=i;
break;
}
}
int[] pre_left=new int[gen];
int[] pre_right=new int[length-gen-1];
int[] in_left=new int[gen];
int[] in_right=new int[length-gen-1];
for(int i=0;i<gen;i++)
{
in_left[i]=in[i];
pre_left[i]=pre[i+1];
}
for(int i=gen+1;i<length;i++)
{
in_right[i-gen-1]=in[i];
pre_right[i-gen-1]=pre[i];
}
flag.left=reConstructBinaryTree(pre_left,in_left);
flag.right=reConstructBinaryTree(pre_right,in_right);
return flag;
}
}
python 采用index函数找到下标
序列化二叉树
从先序遍历开始 ，采用递归的思路，序列化是拼接成字符串
defSerialize(self, root):
s =""
s =self.recursionSerialize(root, s)
returns
defrecursionSerialize(self, root, s):
if(root isNone):
s ='$,'
returns
s =str(root.val) +','
left =self.recursionSerialize(root.left, s)
right =self.recursionSerialize(root.right, s)
s +=left +right
returns
解码的时候，python先用split拿到现在的所有字符，cpp可以做成流式处理
root需要通过TreeNode来生成
二叉搜索树与双向链表
思路1加一个O（n）的数组来存储中序遍历的值，然后转成双向排序链表
self.attr[:-1]
思路二：递归，将特定节点的左指针指向其左子树中的最后子节点，将其右指针指向其右子树中的最左子节点，依次递归，调整好全部节点的指针指向。拿到phead为最小值，其他节点的指针调整为递归思路。即根节点指向左子树的最大值，右子树最小值
二叉树的镜像
左右子节点依次交换顺序
对称的二叉树
需要把空指针考虑进来
对比节点的左右子节点是否一致
顺时针打印矩阵
循环的条件是start*2小于column和row
出发的点是相同的start。第一步总是有的，第二步的前提条件是终止行号大于起始行号，第三部的条件是，终止行号大于起始行号，且终止列号大于起始列号，第四部是终止行号比截止行号大2，且列号大于终止列号
包含min函数的栈
java peek 不弹出，
思路定义一个存最小值的栈
栈的压入与弹出
判断弹出的顺序是不是压栈的序列，建立辅助栈，情况如下，如直接相同，则为压入立即弹出，如果辅助栈栈顶存在的与要pop的相同，则弹出，否则判断压入栈时候还有值，有的话加入辅助栈，直到所有的值压入，判断是否是其弹出的序列。
从上到下打印二叉树
不分行的时候
分行打印
采用广度优先遍历一棵树的时候，采用队列
分行打印返回一个二维列表
之字形打印
分词奇数和偶数的列表进行存储
二叉搜索树的后序遍历序列
想到递归，特征为 左子树小于根节点，右子树大于根节点
二叉树和为某一值的路径
从根节点到子节点为一个路径，采用递归，，如果子节点没有左右节点且值等于，则返回，否则为none，
复杂链表的复制
方法1、通过空间换时间，通过一个hash表，记录配对信息放在hash表
方法2、分成三步骤，1、复制每个节点对应的下一个节点，然后复制其指向的节点，然后将奇数位置的节点连接起来。
class Solution:
# 返回 RandomListNodedef Clone(self, pHead):
# write code hereifpHead==None:
return None
self.CloneNodes(pHead)
self.ConnectRandomNodes(pHead)
return self.ReconnectNodes(pHead)
def CloneNodes(self,pHead):
''' 复制原始链表的每个结点, 将复制的结点链接在其原始结点的后面
''' pNode=pHead
while pNode:
pCloned=RandomListNode(0)
pCloned.label=pNode.label
pCloned.next=pNode.next
pNode.next=pCloned
pNode=pCloned.next
def ConnectRandomNodes(self,pHead):
''' 将复制后的链表中的克隆结点的random指针链接到被克隆结点random指针的后一个结点
''' pNode=pHead
while pNode:
pCloned=pNode.next
ifpNode.random!=None:
pCloned.random=pNode.random.next
pNode=pCloned.next
def ReconnectNodes(self,pHead):
''' 拆分链表：将原始链表的结点组成新的链表, 复制结点组成复制后的链表
''' pNode=pHead
pClonedHead=pClonedNode=pNode.next
pNode.next = pClonedNode.next
pNode=pNode.next
while pNode:
pClonedNode.next=pNode.next
pClonedNode=pClonedNode.next
pNode.next=pClonedNode.next
pNode=pNode.next
returnpClonedHead
方法3、递归法
