图
每个节点有2种状态,不要boolean[] isVisited, boolean[] isEnd两个数组
直接int[] status,用2种数字来表示状态
dfs
递归的思想有2种:
- 对自己进行条件判断,对下面的小弟无脑入
- 不必判断自己,对下面的小弟进行条件判断后,筛选进入
dfs或者递归的思路是从f(n)推向f(n+1)的各种情况
即:发散
dp
动态规划就是总结有哪些f(n-1)的情况会导致f(n+1)
即:归纳
注意在使用dfs或者dp时,尽量用“状态”而非“操作”
因为:由于某个“操作”导致某个“状态”,所以只要把最后的状态保留即可
数组
数组链表
数组nums的长度为n
但是里面的数字范围为1-n,其中n表示末尾(因为nums[n]就超出了)
这种情况下,这个链表是没有“环”的
什么情况下会有环?
数字范围1 ~ (n-1) ,
因为如果有数字等于n的话,就跳出去了
int[] nums = {1,2,3,4,5}; //没有环 int[] nums2 = {1,4,5,2,3}; //没有环 int[] nums3 = {1,4,3,2,2}; //有环 i = 0; while(i != nums.length) { i = nums[i]; }
排序
快排
partition流程:
-
选一个标兵p
-
i从左往右找到比p大的
-
j从右往左找到比p小的
-
swap(i,j),回到步骤2
-
上述的流程保证了i之前的元素(不包括i)都是小于等于p的
而j之后的元素(不包括j)都是大于等于p的
-
最后j在i左边,把标兵和i-1的位置上的元素交换一下
import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] data = {10, 3, 15, 5, 18}; // int[] data = {10}; // partition(data,0,data.length-1); qsort(data, 0, data.length - 1); System.out.println(Arrays.toString(data)); } public static void qsort(int[] data, int left, int right) { if(left>=right){ return; } int i = partition(data, left, right); qsort(data, left, i - 1); qsort(data, i + 1, right); } public static int partition(int[] data, int left, int right) { int p = data[left]; int i = left; int j = right; while (i <= j) { while (i <= j && data[i] <= p) { i++; } while (i <= j && data[j] >= p) { j--; } if (i < j) { swap(data, i, j); ++i; ++j; } } swap(data, left, i - 1); return i - 1; } public static void swap(int[] data, int i, int j) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }
插入排序
public static void insertSort(int[] a){
for(int i=1;i<a.length;++i){
int tmp = a[i];
int j=i-1;
for(;j>=0&&a[j]>tmp;--j){
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
希尔排序
public static void shellSort(int[] a){
for(int gap=a.length/2;gap>=1;gap/=2){
for(int i=gap;i<a.length;++i){
int tmp = a[i];
int j = i-gap;
for(;j>=0&&a[j]>tmp;j-=gap){
a[j+gap] = a[j];
}
a[j+gap] = tmp;
}
}
}
排序技巧
场景:
背包问题
有一个代表物品价值的数组
int[] values;
有一个代表物品重量的数组
int[] weights;
现在我建造想让这两个数组按照**单位价值(value/weight)**排序
写法1: 放到一个类里面
// 放到一个类里面
class Thing{
int value;
int weight;
double density;
Thing(int value, int weight, double density){
this.value = value;
this.weight = weight;
this.density = density;
}
}
int limit = 15;
int[] values = {4,5,23,7};
int[] weights = {3,7,10,3};
Thing[] things = new Thing[valus.length];
for(int i=0;i<things.length;++i){
things[i] = new Thing(values[i],weight[i], values[i]/(double)weight[i]);
}
Arrays.sort(things, Comparator.compareDouble(a->a.density));
// 这样写一般是可以的
// 唯一的缺点是: 我不知道原来的下标跟现在的下标的对应关系
// 比如说:我想用一个向量表示物品被选取了多少
double[] res = new double[values.length];
// 现在下标乱掉了, 对应不起来
写法2: 对下标进行排序
int limit = 15;
int[] values = {4,5,23,7};
int[] weights = {3,7,10,3};
Integer[] idx = new Integer[values.length]; //每个物品的下标
for(int i=0;i<idx.length;++i){
idx[i] = i;
}
// 对下标进行排序, ok
Arrays.sort(idx, Comparator.comparingDouble(i->values[i]/(double)weights[i]));
// 答案下标
double[] res = new double[values.length];
for(int i : idx){
if(weight[i] < limit){
limit -= weight[i];
res[i] = 1;
}else{
limit = 0;
res[i] = limit/(double)weight[i];
break;
}
}
System.out.println(Arrays.toStrig(res));
最长回文子串
贪心算法
通常需要进行排序
特点:
-
最优子结构性质: 整体最优包含子结构最优
-
贪心选择性质: 一步步贪心选择可以达到最优解
动态规划
特点:
- 最优子结构性质: 整体最优包含子结构最优
- 子机构重叠&子结构空间小(所以可以遍历所有子结构来得到总体最优)
回溯 – dfs
全排列
给出平面上的n个点,现在需要你求出,在这n个点里选3个点能构成一个三角形的方案有几种。
输入描述:
第一行包含一个正整数n,表示平面上有n个点(n <= 100)
第2行到第n + 1行,每行有两个整数,表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100,且保证所有坐标不同)
输出描述:
输出一个数,表示能构成三角形的方案数。
输入例子1:
4
0 0
0 1
1 0
1 1
输出例子1:
4
例子说明1:
4个点中任意选择3个都能构成三角形
// 也就是说, 要从一堆点中拿出3个点
// 相当于C(3,n)
// 可以用dfs, 比如先拿第1个位置, 再在后面拿剩下的2个
public class Main{
public static Point[] points; // 解空间(可以选的分支)
public static ArrayList<Point> container = new ArrayList<>(); // 记录当前的搜索路径
public static int count = 0; // 可行路径的个数
// k: 还要拿几个点
// next_loc: 下一次从哪个位置开始拿
public static void dfs(int k, int next_loc){
// 终止条件
if(k==0){
if(isTriangle(container.get(0),container.get(1),container.get(2))){
count++;//答案数量++
}
}
// 剪枝: 要拿的点的数量超过了剩下的点的数量
if( k > (points.length - next_loc)) return;
// dfs
for (int i = next_loc; i < points.length; i++) {
container.add(points[i]); //扩展搜索路径
dfs(k-1, i+1);
container.remove(container.size()-1); //回溯
}
}
}
图的最短路径(dijkstra)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
System.out.println(f());
}
public static HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>(); //用hash来存图, int[0]表示终点 int[1]表示边的权值
public static int[] distance; // 每个节点距离源点的距离
public static boolean[] is_select; // 是否已经被选入集合
public static ArrayList<Integer> group = new ArrayList<>(); // 每次只考虑新加入集合的节点带来的影响(list中的最后一个)
public static int f(){
Scanner sc = new Scanner(System.in);
int n_factory = sc.nextInt(); // 节点的数量
int src = sc.nextInt(); // 源点
int item = sc.nextInt(); //边的数量
distance = new int[n_factory+1];
is_select = new boolean[n_factory+1];
for(int i=1;i<=n_factory;++i){
is_select[i] = false;
distance[i] = -1; // -1 代表无穷大, 这是一个坑, 最好用一个大数, 不然后面每次都要考虑特殊情况
}
for (int i = 0; i < item; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
int time = sc.nextInt(); // 边的权值
if(!graph.containsKey(start)){
ArrayList<int[]> list_ = new ArrayList<>();
int[] ints = {end, time};
list_.add(ints);
graph.put(start, list_);
}else{
int[] ints = {end, time};
graph.get(start).add(ints);
}
}
dfs(src);
for (int i=1;i<=n_factory;++i) {
if(!is_select[i]) return -1; //表示有的边到不了
}
// 题目中就是要求边的最大权值
int _max = -1;
for (int d : distance) {
_max = Math.max(_max,d);
}
return _max;
}
// 关键代码
public static void dfs(int src){
group.add(src);
distance[src] = 0;
is_select[src] = true;
while(true){
// 更新distance向量
int fresh = group.get(group.size()-1);
ArrayList<int[]> ints = graph.get(fresh);
if(ints!=null){ // 注意如果这个节点没有出边的话, hash表中存的就是null
for(int[] int_ : ints){
if(distance[int_[0]]==-1 || distance[fresh] + int_[1] < distance[int_[0]]){
distance[int_[0]] = distance[fresh