1反转链表
2节点两两反转
3判断链表是否有环
1 0.5毫秒内是否出现Null
2 set中查重
3 快慢指针
4匹配左右括号
5实时判断第K大的元素
大顶堆 实时排序
6 乱序判断
法一：sort NlogN
return sorted(s)==sorted(t)
法二：数出现过个个数，用map计数
6两数之和 一个数组中两个数相加满足条件
sum==two of array[2,3,4,5]
7三数之和
a+b+c==D
法一：暴力法 三层循环嵌套
法二：c=-(a+b) -->放到一个set中
a b两层循环 每次查询set中 -(a+b)
法三： sort find
树代码
计算x的n次方，递归分治
def pow(self,x,n):
if not n:
return 1
if n<0:
return 1/self.pow(x,-n)
if n%2:
return x*self.pow(x,n-1)
return self.pow(x*x,n/2)
位运算非递归
class mypaw:
def mypaw(self,x,n):
if n<0:
x=1/x
n=-n
pow=1
while n:
if n&1 :
pow *=x
x *=x
n>>=1
return pow
求众数
排序； 暴力；分治
hashtable 同步 不允许NONE的k或v
hashset 基于map上省略value
hashmap 不同步，非线程有更好效率，允许一个none K 或者V
内排序：在内存中进行排序，不需要磁盘读写，一般假定所有用到的辅助空间也可以直接存在于内存中
外排序：需要磁盘访问，每次读入部分数据到内存进行排序
归并排序 merge sort 分治 nlogn 最坏 n**2
快排： quick sort 也是分治 随机选一个轴 再左右两部分 nlogn 平均N 额外空间logn
桶排序 bucket sort radix sort k*N
1.N皇后问题
N个皇后放在n*n棋盘山 使之不相互攻击
class Nqueen: def solveNQueen(self,n): if n <1 :return [] self.result =[] self.cols =set();self.pie=set();self.na=set() self.DFS(n,0,[]) return self._generate_result(n) def DFS(self,n,row,cur_state): if row>=n: self.result.append(cur_state) return for col in range(n): if col in self.cols or row+col in self.pie or row-col in self.na: continue self.cols.add(col) self.pie.add(row+col) self.na.add(row-col) self.DFS(n,row+1,cur_state+[col]) self.cols.remove(col) self.pie.remove(row+col) self.na.remove(row-col) def _generate_result(self,n): board=[] for res in self.result: for i in res: board.append("."*i+"Q"+"."*(n-1-n)) return [board[i:i+n] for i in range(0,len(board),n)]
class NQueen: def NQueen(self,n): def DFS(queens,pie,na): p = len(queens) if p==n: result.append(queens) return None for q in range(n): if q not in queens and p-q not in pie and p+q not in na: DFS(queens+[q],pie+[p-q],na+[p+q]) result=[] DFS=([],[],[]) return [ ["."*i+"Q"+"."*(n-i-1) for i in sol] for sol in result ]
2数独问题
9*9格子
行 列 只能1--9不能重复
每个3*3block不能重复
public class shudu { public void shudu(char[][] board){ if (board==null || board.length==0) return; solve(board); } public boolean solve(char[][] board){ for (int i=0;i<board.length;i++) for (int j=0;j<board[0].length;j++){ if (board[i][j]=='.'){ for (char c='1';c<='9';c++){ if (isValid(board,i,j,c)){ board[i][j]=c; if(solve(board)) return true; else board[i][j]='.'; } } return false; } } return true; } public boolean isValid(char[][] board,int row,int col,char c){ for(int i=0;i<9;i++){ if(board[i][col] !='.' &&board[i][col]==c) return false; if(board[row][i] !='.' &&board[row][i]==c) return false; if(board[3*(row/3)+i/3][3*(col/3)+i%3] !='.' && board[3*(row/3)+i/3][3*(col/3)+i%3] ==c) return false; } return true; } }
位运算
统计1的 个数
def ham(self,n)
res=0
mask=1
for i in range(32):
if n &mask:
res +=1
mask == mask <<1
return resC++
int ham(uint32_t n){
int res=0;
for (;n;n&=n-1)
++ res;
return resl
}
判断是否为2的N次方
bool isA(int n){
return n>0 && !(n&(n-1));
}或者
def isA(self,n):
return n>0 and not (n&n-1)
取一个数N，返回这个数0-N之间所有二进制1个数的数组
using namespace std;
vector<int> countBits(int num){
vector<int> bits(num+1,0); //填充num+1个 默认值为0
for(int i=1;i<=num;i++){
bits[i] +=bits[i&(i-1)] +1;
}
return bits;
}
N皇后问题
class weiNQueen:
def total(self,n):
if n<1:return []
self.count =0
self.DFS(n,0,0,0,0)
return self.count
def DFS(self,n,row,cols,pie,na):
if row >=n:
self.count +=1
return
bits= (~(cols|pie|na)& ((1<<n)-1)) #得到当前所有空位
while bits:
p=bits & -bits #-bits表示取反加1，~表示只取反，p 取到最低位的1
self.DFS(n,row+1,cols|p,(pie|p) <<1,(na|p)>>1)
bits=bits &(bits -1) #去掉最低位的1
A=weiNQueen()
print(A.total(4))