我的刷题笔记

遍历

程序有顺序，判断，循环三种结构，而循环正是程序的精髓，电脑能够取代人力，最主要的就是因为程序能够做一些重复的事情，而这一切都离不开循环结构。

在做算法题时，不管我们准备对数据执行哪些操作，通常要先对数据进行遍历 ,而不同的数据结构又有不同的遍历方式，熟练掌握遍历是开始编程的第一步。以下总结了几种数据结构的遍历方式：

对数组进行遍历

java

1
2
3

//对数组进行遍历一般会给一个数组nums
for(int i=0;i
}

对链表进行遍历

java

//对链表进行遍历一般会给一个链表的头head(其实就相当于数组遍历中的nums)
Node idx = head;
//循环结束的条件
while(idx!=null){
    //循环的索引变更
    idx=idx.next;
}

对树进行遍历

java

TreeNode idx=root;
void DFS(idx){
    //循环结束的条件
    if(idx==null){
        return;
    }
    //如果idx!=null:循环的索引变更
    DFS(idx.left);
    DFS(idx.right);
}
//对树的遍历和对链表和数组遍历的最大的不同，就在于对数的遍历的路径是分叉的，在每一轮的循环中索引都要增加且分叉，循环结束的路径也不是一个，而是在多条路径处都要结束

对数字的位进行遍历

java

while(num!=0){//遍历结构,这里写的是遍历到头，其实可以改条件达到半路截胡的效果
    whatwewant=num%10;//我们想要的每一位
    num=num/10;//遍历结构
}///遍历结构

对数字的比特位进行遍历

java

while(num!=0){//遍历结构
    whatwewant=num&1;//我们想要的每一比特位
    num=num>>1;///遍历结构
}//遍历结构

对列表进行遍历

java

1
2
3

for (int i=0; i
     whatwewant = list.get(i);     
}

if……else……的简略写法

java

//原始写法(一般在函数的最后，通过一个判断来返回值时可以简写成三目运算的形式)
if(A==B){
    return true;
}
else{
    return false;
}
//三目运算符写法（当三目运算的结果是boolean类型时，三目运算可以进一步化简）
return A==B ? true : false;
//最简写法
return A==B;

判断奇数偶数的两种方式

java

num%2==1;//奇数
num%2==0;//偶数
num&1==1;//奇数
num&1==0;//偶数

摩尔投票法

摩尔投票法的核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

树相关知识点

java

1 2	//判断是否是叶结点 if(root.left==null&&root.right==null)

java

1	//树的遍历中一个重要的信息是看是否越过叶子节点

比特运算相关知识点

java

n&(n-1) 可以将最后一位1变成0;
举例： n=1000; n-1=0111; 相&之后变成 0000;
n&(-n) 可以得到最后一位1；
举例： n=10100;-n=01100; 相&之后变成00100;

String相关知识点

java

//String和int相互转换
Integer.parseInt(str);
String.valueOf(int);   string = ""+int;
//String转char[]
char[] array = string.toCharArray();
//动态构建String
StringBuilder sb = new StringBuilder();
sb.append("something");
String res = sb.toString();

数组相关知识点

java

//List转Array方法1：toArray()返回一个Object[] 数组，之后需要进行强制类型转换
List list = List.of("apple", "pear", "banana");
Object[] array = list.toArray();
//List转Array方法2：toArray()中传入泛型参数，就不用强制类型转换了
List list = List.of(12, 34, 56);
Integer[] array = list.toArray(new Integer[3]);
//数组转换成List :  List.of();
Integer[] array = {1,2,3};
List list = List.of(array);
//数组排序
int[] var= new int[n];
Arrays.sort(var);

compare() 和 compareTo() 方法

java

// compare
compare(a,b){
    //返回-1(负数)，a在前b在后
    //返回1(正数),b在前a在后
}
//compareTo 方法用于字符串，对象之间的比较，且返回值是正数，负数或者0，分别表示a比b大，小或者相等
a.compareTo(b)
//所以compare中一般包含一个compareTo，compareTo负责大小，compare负责前后。两者合作可以实现按大小排序

动态规划

状态转移：

多对多：即一个状态可以转变成多种状态，同理一个状态也可以由多个状态转移而来，这在dp数组的每一维度都有可能发生，一般在最后一个维度
一对一：一个状态只能由一种状态转移而来，这种比较简单

回溯法

回溯法中最重要的就是记录进行到了哪一步，如果这个能记录的比较清楚，回溯法就会很简单。回溯法函数中的参数就是专门做这个的。所以，回溯法的函数参数必须要体现两点，一个是已经做了哪些选择，一个是还可以做哪些选择。

例如在数组中做选择，一般dfs的参数只需要一个索引”i” 就够了。这个i可以代表当前已经做了多少i个选择，还有length-i个选择没做。

归并排序

leetcode 第315、327、493题