算法理解（口语化）

前导

要学算法首先要熟悉 IO 模板这里先提前学 IO模板

提前告诉数据量的类型

import java.io.*;
import java.util.*;

public class Main{
    //这里注意要抛出异常
    public static void main(String[] args) throws IOException{
        //注意输入和输出流
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            ...
        }
        out.println(...);
    }
    out.flush();
    out.close();
}

不告诉数据量的类型

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while((line = in.readLine()) != null){
            String[] parts = line.split(" ");
            sum = 0;
            for(String num : parts){
                sum += Integer.valueOf(num);
            }
            out.println(sum);
        }
        out.flush();
        out.close();
    }
}

第一章数组

数组内存空间连续，数组的元素不能删除只能覆盖，下标从0开始

常见的是区间和和二分

二分

就是每次找中间，前提是有序数组，没有重复元素。

需要注意的是区间左边小于等于右边说明左边等于右边是有意义的

力扣二分查找题目连接

class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {//这里等于说明等于也在范围中
            if (nums[m] < target) {
                l = m + 1;
                m = l + (r - l) / 2;
            } else if (nums[m] > target) {
                r = m - 1;
                m = l + (r - l) / 2;
            } else {
                return m;
            }
        }
        return -1;
    }
}

区间和

区间和就是给一个数组和一个区间然后立刻获得和。

那么这个解决方法就是空间换时间，用一个新数组计算前缀和，然后就可以用前缀和得到区间和乐。

区间和题目链接

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        StreamTokenizer in = new StreamTokenizer(br);
        while( in.nextToken() != StreamTokenizer.TT_EOF){
            int n = (int)in.nval;
            int[] arr = new int[n];
            int[] sum = new int[n];
            for(int i = 0 ; i < n ;i++){
                in.nextToken();
                arr[i] = (int)in.nval;
            }
            sum[0] = arr[0];
            for(int i = 1 ;i < n ; i++){
                sum[i] = arr[i] + sum[i - 1];
            }
            String line ;
            String[] parts;
            while((line = br.readLine()) != null){
                parts = line.split(" ");
                
                int l = Integer.valueOf(parts[0]);
                int r = Integer.valueOf(parts[1]);
                if(l == 0){
                    out.println(sum[r]);
                }else{
                    out.println(sum[r] - sum[l - 1]);
                }
                
            }
        }
        out.flush();
        out.close();
    }
}

第二章链表

链表考验的就是操作。

删除节点

这里就是设置一个虚拟头结点，然后用一个cur从虚拟头结点开始，然后最后返回的时候返回虚拟头结点的下一个。

203. 移除链表元素 - 力扣（LeetCode）

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0 , head);
        ListNode cur = dummy;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

设计链表

在通常的acm类型的题目里由于需要读取数据所以一般要自己设计链表操作链表，所以重要的一环就是设计链表。

然后一个链表要初始化的是链表的大小和头结点。

其次记住这个head是个指针而已。

单链表

707. 设计链表 - 力扣（LeetCode）

class MyLinkedList {
    
    class Node {
        int val;
        Node next;
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    private int size;
    private Node head;

    public MyLinkedList() {
        this.size = 0;
        this.head = null;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size || head == null) {
            return -1;
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        head = new Node(val, head);
        size++;
    }
    
    public void addAtTail(int val) {
        Node newNode = new Node(val, null);
        if (head == null) {
            head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addAtHead(val);
            return;
        }
        Node dummy = new Node(0, head);
        Node cur = dummy;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = new Node(val, cur.next);
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size || head == null) {
            return;
        }
        Node dummy = new Node(0, head);
        Node cur = dummy;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        head = dummy.next; // 确保 head 更新（虽然通常不需要，但安全）
        size--;
    }
}

双链表也一样的，要注意细节了这个就。

第三章哈希表

哈希表就是通过哈希函数弄成的数组，也可以理解为数组+链表，通常的实现方式就是数组、集合set 、 map映射。

通常用来解决的问题就是快速判断一个元素是否出现在集合里

这种题的思路就是如果没有重复就放入集合，重复就返回

这里要记住hashmap的api，常用的就是put和containsKey和remove

set的话就是add和remove和contains

快乐数

202. 快乐数 - 力扣（LeetCode）

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。

class Solution {
    public static boolean isHappy(int n) {
        if(n == 1){
            return true;
        }
        Set<Integer> set = new HashSet<>();
        int sum = 0;
        set.add(n);
        while (true) {
        	sum = 0;
            while (n > 0) {
                int num = n % 10;
                n /= 10;
                sum += num * num;
            }
            n = sum;
            if(set.contains(n)){
                return false;
            }else if(n == 1){
                return true;
                
            }else{
                set.add(n);
            }
        }

    }
}

第四章字符串

字符串常用的就是双指针,kmp

然后这里需要记住操作字符串的api

StringBuilder sb = new StringBuileder();
sb.append();
String res = sb.toString();
res.toLowerCase();
res.toUpperCase();
res.substring(0,5);//左包含右不包含
res.contains();
res.replace();
res.charAt();//如果是唯一字符返回位置，如果是数字返回字符

反转字符串

344. 反转字符串 - 力扣（LeetCode）

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l <= r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode）

利用kmp，首先先构建next数组，然后在构建Next数组的时候首先要定义左边和右边，然后如果相等赋值为左边的如果不相等，然后左边不为0，回退到next[左边-1]如果左边为0，那么说明无法回退了，那么就设置next为0，然后主线就是获得next的最后一个元素然后用总长度减去最长公共前后缀，看看能不能让整个char数组的长度取模

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        char[] c = s.toCharArray();
        int len = c.length;
        int[] next = getNext(c,len);
        int minLen = len - next[len - 1];
        return next[len - 1] != 0 && len % minLen == 0 ? true : false;
    }
    public int[] getNext(char[] c,int len){
        int[] next = new int[len];
        int i = 0;
        int j = 1;
        while(j < len){
            if(c[i] == c[j]){
                i++;
                next[j] = i;
                j++;
            }else{
                if(i > 0){
                    i = next[i - 1];
                }else{
                    next[j] = 0;
                    j++;
                }
            }
        }
        return next;
    }
}

第五章栈和队列

操作栈和队列最好就用一个类记起来比较方便

1	Deque<Integer> st = new ArrayDeque<>();

常用api就是addFirst()，addLast()，removeFirst(),removeLast()，peekFirst()，peekLast()，isEmpty

如果是要求只能使用单调队列那就用LinkedList实现队列，用Stack实现栈，记住队列的api是offer ，poll，peek，isEmpty，栈的api是push,pop,peek,empty()

题目一用两个队列实现栈，思路是一个用作备份，q1才是真正的栈，添加元素的时候先放到q2然后把q1的元素放到q2里然后最后把q2复制到q1，这时候q2是空,q1就是实现了栈了。

有效括号

20. 有效的括号 - 力扣（LeetCode）

class Solution {
    public boolean isValid(String s) {
        char[] c = s.toCharArray();
        Deque<Character> st = new ArrayDeque<>();
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '(' || c[i] == '{' || c[i] == '[') {
                st.addFirst(c[i]);
            } else if (c[i] == ')' || c[i] == '}' || c[i] == ']') {
                if (st.isEmpty()) {
                    return false;
                }
                char temp = st.peekFirst(); 
                if ((c[i] == ')' && temp != '(') ||
                    (c[i] == '}' && temp != '{') ||
                    (c[i] == ']' && temp != '[')) {
                    return false;
                } else {
                    st.removeFirst();
                }
            }
        }
        return st.isEmpty();
    }
}

滑动窗口

239. 滑动窗口最大值 - 力扣（LeetCode）

这里要使用 单调队列 就是队列里的元素单调递减或者单调递增的队列就是单调队列。

然后这里用双端队列，然后队列里存的都是下标，然后每次加入队列的元素如果比队尾元素大，那么队尾元素就能丢弃了，因为新加入的元素存活时间长又比队尾元素大，所以队尾元素可以丢弃，然后就首先移除过期元素，然后维护单调递减，然后再加入元素，然后记录结果。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> que = new ArrayDeque<>();
        int[] res = new int[nums.length - k + 1];
        int idx = 0;
        for(int i = 0 ; i < nums.length ; i++){
            if(!que.isEmpty() && que.peekFirst() <= i - k){
                que.removeFirst();
            }
            while(!que.isEmpty() && nums[que.peekLast()] < nums[i]){
                que.removeLast();
            }
            que.addLast(i);
            if (i >= k - 1) {
                res[idx++] = nums[que.peekFirst()];
            }
        }
        return res;
    }
}

前 K 个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

首先这种题需要统计频率又要排序还要找到前k个元素的问题。

用Map来统计，然后用优先队列来排序，优先队列实际上是一个完全二叉树来排序的，然后这里使用小顶堆，小顶堆就是最小的在根，因为小顶堆可以把最小的踢出去，然后每次维持k个元素就行。

这里要熟练使用map的api

常用的有put，get，getOrDefault(num, 0)，keySet，containsKey，containsValue，remove，isEmpty，entrySet

其次要熟练小根堆也就是优先队列的api PriorityQueue 这里的api跟队列一样，然后如果要大根堆需要在初始化的时候传入比较器

1	PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

注意这题是先把map维护好然后把map直接放入队列里排序维护

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计频率：key=数字，value=频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 2. 创建小顶堆：按频率升序
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));

        // 3. 维护大小为 k 的堆
        for (int num : map.keySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (map.get(num) > map.get(minHeap.peek())) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        // 4. 输出结果（题目不要求顺序）
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = minHeap.poll(); // 更规范的做法
        }
        return res;
    }
}

第六章二叉树

操作的时候通常用链式二叉树来表达，但是也可以用数组来存储二叉树如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树没别的多练了只能，层序遍历前中后序遍历，递归法迭代法，反转，路径总和，这个就只能多练了。

这里最重要的是递归法，写递归的时候来递归三部曲：

1、确定递归函数的参数和返回值

2、确定终止条件

3、确定单层递归逻辑

迭代的实现就是每次递归调用都会把函数的局部变量和参数值和返回值等压入调用栈中，所以我们写迭代函数的时候也是利用栈。

后序序列

给定前序 + 中序序列，输出后序

从前序取第一个字符作为根节点；
在中序中找到该根的位置，左边是左子树，右边是右子树；
递归处理左右子树；

代码思路就是首先读取前序字符串，后序字符串和传入一个result数组，然后读取前序的第一个字符就是最中间的根，然后在中序里找，中序就被分隔成左和右，然后记录中序的长度然后前序就根据长度也分成了左和右，然后递归从左，右，然后添加根的顺序添加到res里面即可。

import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		String line;
		while((line = in.readLine()) != null){
			int n = Integer.parseInt(line);
			while(n-- > 0){
				String pre = in.readLine();
				String mid = in.readLine();
				StringBuilder back = new StringBuilder();
				fun(pre,mid,back);
				out.println(back.toString());
			}
		}
		out.flush();
		out.close();
	}
	public static void fun(String pre,String mid,StringBuilder back){
		if(pre.isEmpty()){
			return;
		}
		
		char root = pre.charAt(0);
		int rootIndex = mid.indexOf(root);
		
		//midString
		String midSP = mid.substring(0,rootIndex);
		String midSM = mid.substring(rootIndex + 1);
		
		//preString
		String preSP = pre.substring(1,1 + rootIndex);
		String preSM = pre.substring(1 + rootIndex);
		
		//left , right , mid
		fun(preSP,midSP,back);
		fun(preSM,midSM,back);
		back.append(root);
	}
}

迭代遍历

首先迭代遍历的前序遍历相对简单，简而言之就是先处理当前节点然后再进入循环处理右再处理左，因为迭代要求的是中左右，所以入栈顺序是先右后左，而中间的是先处理的也就是根先入栈，然后根直接出栈然后加入到res里面然后再入右然后左。（前序遍历迭代法刚好可以中是匹配的，相对简单）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode temp = st.pop();
            res.add(temp.val);
            if (temp.right != null) {
                st.push(temp.right);
            }
            if (temp.left != null) {
                st.push(temp.left);
            }
        }
        return res;
    }
}

中序遍历的思路就不一样了

94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历的思路就是一路走到最左到底，然后到底之后再开始处理，处理完左边然后加入到res然后再把右边压入，然后循环条件是当前节点不为空或者栈不为空

“遍历结束”的标志是什么？我们要找的是：没有任何节点需要再处理了。

情况 1：当前 cur 不为 null

说明还有节点可以继续往左走（或者刚从右子树回来，要处理新子树）；
必须继续循环。

情况 2：当前 cur == null，但栈不为空

说明左边已经到底，但还有祖先节点没被访问（它们在栈里等着呢）；
下一步就要 pop() 访问它们；
必须继续循环。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !st.isEmpty()){
            if(cur != null){
                st.push(cur);
                cur = cur.left;
            }else{
                cur = st.pop();
                res.add(cur.val);
                cur =cur.right;
            }
        }
        return res;
    }
}

后序遍历 那么后序遍历迭代法其实就是把先序遍历的入栈顺序变成中右左然后再反转res数组就是后序遍历了。

第七章后序回溯算法

回溯算法解决的问题：组合问题、切割问题、子集问题、排列问题、棋盘问题。

回溯三部曲：

1、确定参数和返回值一般为void 参数不好确定可以边写边确定

2、回溯终止条件

3、回溯搜索的遍历过程

void backtracking(参数){
    if(终止条件){
        存放结果;
        return;
    }
    
    for(选择：本层集合中元素（树种节点孩子的数量就是集合的大小）){
        处理节点;
        backtracking(路径,选择列表);//递归
        回溯，撤销处理结果
    }
}

组合

77. 组合 - 力扣（LeetCode）

回溯三部曲

1、首先确定参数和返回值

首先有两个全局参数，一个是res存放arrayList，一个是单次路径答案path。

返回值是void，然后传入n 数量，k 要选个数，startIndex 确保不会重复的下标。

2、回溯终止条件

path的大小等于 k

3、回溯遍历过程

用一个for循环代表宽度，回溯相当于深度。

先把数字加入到path里面然后递归，然后撤销path里的一个数。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        int startIndex = 1;
        backtracking(n,k,startIndex);
        return res;
    }

    public void backtracking(int n , int k ,int startIndex){
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex ; i <= n ; i++){
            path.add(i);
            backtracking(n,k,i + 1);
            path.removeLast();
        }
    }
}

分隔回文串

131. 分割回文串 - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

1、确定参数和返回参数

首先初始化一个答案List res和一个List path用来记录一条路径的答案。

首先传输总长度，然后starIndex起始位置，然后StringBuilder

2、确定终止条件

当startIndex 大于等于整个字符长度。把path加入到res

3、确定单层递归逻辑

用For，然后遍历字符串，然后判断子串是不是回文，如果是就加入path

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if(s == null){
            return res;
        }

        backtracking(s,0,new StringBuilder());
        return res;
    }
    public void backtracking(String s,int startIndex,StringBuilder sb){
        if(startIndex >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex ; i < s.length() ; i++){
            sb.append(s.charAt(i));
            if(check(sb)){
                path.add(sb.toString());
                backtracking(s,i+1,new StringBuilder());
                path.removeLast();
            }
        }
    }

    public boolean check(StringBuilder sb){
        int l = 0 ;
        int r = sb.length() - 1;
        if(sb.length() == 1){
            return true;
        }else{
            while(l <= r){
                if(sb.charAt(l) == sb.charAt(r)){
                    r--;
                    l++;
                }else{
                    return false;
                }
            }
            
        }
        return true;
    }
}

子集

78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

子集问题是找树的所有节点。

1、参数和返回参数

首先一个全局的res 和 path

返回参数void，然后参数就是一个是数字n，然后一个k表示选的位置，然后一个startIndex

2、终止条件

当选完也就是startIndex 大于等于k

3、回溯逻辑

先把答案放入到res里面

先取一个然后放到path，然后回溯，然后path去除

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int startIndex = 0;
        int k = nums.length;
        backtracking(nums,k,startIndex);
        return res;
    }
    public void backtracking(int[] nums,int k , int startIndex){
        res.add(new ArrayList(path));//这个要放前面
        if(startIndex >= k){
            return;
        }
        
        for(int i = startIndex ; i < k ; i++){
            path.add(nums[i]);
            backtracking(nums,k,i + 1);
            path.removeLast();
        }
    }
}

全排列

46. 全排列 - 力扣（LeetCode）

1、参数和返回值

首先是void，然后参数需要传nums和一个标记是否使用的used数组，然后有一个全局变量path来存储一个答案，然后一个全局变量res存储最终答案

2、终止条件

path的大小等于 nums的长度。

3、回溯逻辑

首先for遍历所有Nums元素，然后先标记使用的元素，然后把元素加入path，然后回溯，然后去除path的最后一个，然后删除标记。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length];
        backtracking(nums , used);
        return res;
    }
    public void backtracking(int[] nums,int[] used){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        
        for(int i = 0 ; i < nums.length ; i++){
            if(used[i] == 1){
                continue;
            }
            used[i] = 1;
            path.add(nums[i]);
            backtracking(nums,used);
            path.removeLast();
            used[i] = 0;
        }
    }
}

第八章贪心

贪心算法一般分为4步

1、将问题分解为若干个子问题

2、找出适合的贪心策略

3、求解每一个子问题的最优解

4、将局部最优解堆叠成全局最优解

第九章动态规划

动态规划五部曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

斐波那契数列

509. 斐波那契数 - 力扣（LeetCode）

1、确定dp数组以及下标的含义

dp i 的含义，第 i 个数的斐波那契数是dp i

2、确定递推公式

题目已经把递推公式直接给我们了，dp[i] = dp[i - 1] + dp[i - 2]

3、dp数组如何初始化

题目中也把如何初始化给我们了

1 2	dp[0] = 0; dp[1] = 1;

4、确定遍历顺序

从递归公式中可以看出dp[i]是依赖前一个dp和前一个的前一个来决定的，那么遍历顺序一定是从前到后遍历的。

5、举例子推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

class Solution {
    public int fib(int n) {
        if(n <= 1){
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n ; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1、确定数组dp下标的意义

dp下标表示爬到该层花费最小的费用

2、确定递推公式

第三层=min(一层2个，两层1个)

dp[i] = dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);3、初始化

3、初始化

dp[0] = 0，dp[1] = 0

4、遍历顺序

遍历顺序就是从前往后

5、举例子

cost【10，15,20】

minCost【10，15，15】

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        for(int i = 2 ; i <= cost.length ; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

不同路径

62. 不同路径 - 力扣（LeetCode）

1、确定dp数组下标和意义

dp[i] = 到达的不同路径数

2、确定递推公式

dp [ i ] [ j ] =从上和从左 = dp [ i - 1] [ j ] + dp [ i ] [ j - 1 ]

3、初始化

第一行和第一列

第一行全部1，第一列也是1.

4、遍历顺序

从上到下从左到右一层一层刷

5、举例

m = 3，n = 7

自己画图

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1 ; i < m + 1; i++){
            dp[i][1] = 1;
        }
        for(int j = 1 ; j < n +1 ; j++){
            dp[1][j] = 1;
        }
        for(int i = 2 ; i < m + 1 ; i++){
            for(int j = 2 ; j < n +1 ; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

01背包

01背包就是物品数量只有1个，然后提供物品价值和物品重量还有背包容量。

1、确定下标含义

i 表示物品，j 表示背包容量 dp[i] [j] 表示最大能装的价值

2、确定递推公式

dp【1：0和1两个物品选择】【4容量】=

1、要么不放物品1 那么最大价值就是dp[0] [4]

2、放物品1 那么就是需要空出物品1的大小，也就是4容量 - 3重量，那么还剩1重量也就是 dp[0] [1] + 物品1价值然后取最大值

dp[i] [j] = Math.max(dp[i - 1] [j] , dp[i - 1] [j - w[i] + v[i]])

3、确定初始化

初始化就是把第一行，初始化了，如果大于物品0就放入不大于就是0，然后第一列都是0

4、遍历顺序就是一行一行刷

5、举例

自己画图

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        String line ;
        while((line = br.readLine()) != null){
            String[] s = line.trim().split(" ");
            int m = Integer.parseInt(s[0]);
            int n = Integer.parseInt(s[1]);
            line = br.readLine();
            s = line.trim().split(" ");
            int[] w = new int[s.length];
            for(int i = 0 ; i < s.length ; i++){
                w[i] = Integer.parseInt(s[i]);
            }
            line = br.readLine();
            s = line.trim().split(" "); 
            int[] v = new int[s.length];
            for(int i = 0 ; i < s.length ; i++){
                v[i] = Integer.parseInt(s[i]);
            }
            out.println(fun(m,n,w,v));
        }
        out.flush();
        out.close();
    }

    public static int fun(int m,int n,int[] w,int[] v){
        int[][] dp = new int[m][n + 1];
        for(int i = 0 ; i < n + 1 ; i++){
            if(i >= w[0]){
                dp[0][i] = v[0];
            }else{
                dp[0][i] = 0;
            }
        }

        for(int i = 1 ; i < m ; i++){
            for(int j = 1 ; j < n+1 ; j++){
                if(j >= w[i]){
                    dp[i][j] = Math.max(dp[i - 1][j] , dp[i- 1][j - w[i]] + v[i]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[m - 1][n];
    }
}

滚动数组

上面那题使用二维的数组，现在用一维的数组，实际上是因为可以

把 i - 1 层的答案拷贝到 i 层以此来实现重复利用，不用二维数组存储了。

然后现在开始

1、定义下标

j 就是背包大小，然后dp[j] 就是背包容量最大的价值

2、确定递推公式

dp[j] = Math.max(dp[j] , dp[j - w[i]] + v[i])

3、确定初始化

就只能初始化容量为0的时候了，那么就是0就好了

4、确定顺序

顺序要 i 的时候从物品0 到 N ，然后背包容量要从大到小

因为如果从小到大容易加两次。（因为假设dp 1 能放那么dp1会加一次，然后dp 2 也能放这时候dp 2 会加dp 1这就加两次了）

5、举例

自己画图

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        String line;
        while((line = br.readLine()) != null){
            String[] s = line.trim().split(" ");
            int m = Integer.parseInt(s[0]);
            int n = Integer.parseInt(s[1]);
            line = br.readLine();
            s = line.trim().split(" ");
            int[] w = new int[s.length];
            for(int i = 0 ; i < s.length ; i++){
                w[i] = Integer.parseInt(s[i]);
            }
            line = br.readLine();
            s = line.trim().split(" ");
            int[] v = new int[s.length];
            for(int i = 0 ; i < s.length ; i++){
                v[i] = Integer.parseInt(s[i]);
            }

            out.println(fun(n,m,w,v));

        }
        out.flush();
        out.close();
    }

    public static int fun(int n,int m ,int[] w,int[] v){
        int[] dp = new int[n + 1];
        for(int i = 0 ; i < m ; i++){
            for(int j = n ; j > 0 ; j--){
                if(j >= w[i]){
                    dp[j] = Math.max(dp[j],dp[j - w[i]] + v[i]);
                }
            }
        }
        return dp[n];
    }
}

完全背包

完全背包就是物品数量无数个。

1、确定dp数组以及下标的含义

dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

2、确定递推公式

也是选和不选两种，不选的情况一样，但是选的时候

01背包，背包先空流出物品1的容量，此时容量为1，只考虑放物品0的最大价值是dp[0][1]，因为01背包每个物品只有一个，既然空出物品1，那么背包中也不会再有物品1。

但是在完全背包中，物品是可以放无限个，所以即使空出物品1空间容量，那背包中也可能还有物品1，所以此时我们依然考虑放物品1和物品0的最大价值dp[1][1]而不是dp[0][1]

所以放物品1 的时候 = dp[1][1] + 物品1的价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

3、dp数组初始化

也是第一行和第一列

4、遍历顺序

一行一行刷，先物品后背包

5、举例

自己画图

零钱兑换

518. 零钱兑换 II - 力扣（LeetCode）

1、确定dp数组以及下标的含义

这里用dp[i] [j]二维数组，然后i表示物品，j表示背包大小，然后dp[i] [j] 表示用物品i装满 j 有几种方法

2、递推公式

dp[i] [j] 表示用物品0 到 i - 1装满容量 j 的背包有几种方法。

用物品i - 1和不用物品 i - 1

不用物品i - 1就是dp[i - 1] [j]

用物品1 就是 dp[i] [j - coins[i]]（这个表示至少用了一个物品 i ，那么这个就表示了用了物品1的方法量了）

所以递推公式

if j >= coins[i]:
	dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]]
else:
    dp[i][j] = dp[i-1][j]

3、初始化

首先想行和列，首先是第0列，就是背包容量为0的话，用物品装满的方法为1，就是不装，然后行用物品0装满容量的方法，如果容量取模物品0为0就为1否则就是0

4、顺序

一行一行

5、举例

自己画图

class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];
        for(int i = 0 ; i < coins.length ; i++){
            dp[i][0] = 1;
        }
        for(int j = 1 ; j <= amount ; j++){
            if(j>=coins[0] && j % coins[0] == 0){
                dp[0][j] = 1;
            }
        }

        for(int i = 1 ; i < coins.length ; i++){
            for(int j = 1 ; j <= amount ; j++){
                if(j >= coins[i]){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[coins.length - 1][amount];
    }
}

多重背包

56. 携带矿石资源（第八期模拟笔试）

这里就是多个物品数量所以是多重背包

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题。

例如：

背包最大重量为10。

物品为：

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

问背包能背的物品最大价值是多少？

和如下情况有区别么？

	重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

主要区别是循环的时候需要枚举个数了

 // 枚举拿 k 个第 i 种物品
for (int k = 1; k <= nums[i]; k++) {
    if (j >= k * weight[i]) {
        dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
    } else {
        break; // 容量不够，跳出
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int c = (int) in.nval; // 背包容量
            in.nextToken();
            int n = (int) in.nval; // 物品种类数

            int[] weight = new int[n];
            int[] value = new int[n];
            int[] nums = new int[n];

            // 读取重量
            for (int j = 0; j < n; j++) {
                in.nextToken();
                weight[j] = (int) in.nval;
            }
            // 读取价值
            for (int j = 0; j < n; j++) {
                in.nextToken();
                value[j] = (int) in.nval;
            }
            // 读取数量
            for (int j = 0; j < n; j++) {
                in.nextToken();
                nums[j] = (int) in.nval;
            }

            int result = solveMultipleKnapsack(c, n, weight, value, nums);
            out.println(result);
        }

        out.flush();
        out.close();
    }

    public static int solveMultipleKnapsack(int c, int n, int[] weight, int[] value, int[] nums) {
        int[] dp = new int[c + 1];

        for(int i = 0 ; i < n ; i++){
            for(int j = c ; j > 0 ; j--){
                for(int k = 1 ; k <= nums[i] ;k++){
                    if(j >= k * weight[i]){
                        dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                    }else{
                        break;
                    }
                }
            }
        }
        return dp[c];
    }
}

第十章单调栈

那有同学就问了，我怎么能想到用单调栈呢？什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈重要的是单调，而不是栈，重要的是维护多一个单调的结构

每日温度

739. 每日温度 - 力扣（LeetCode）

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

单调栈的本质就是空间换时间，因为在便利的过过程中需要用一个栈来记录右边第一个比当前元素高的元素。优点是整个数组只需要遍历一次。

在使用单调栈的时候首先要明确如下几点：

1、单调栈里存放的元素是什么？

2、单调栈里元素是递增呢？还是递减呢？

使用单调栈主要有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

那么这题开始思考

1 2	输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

1、单调栈里放元素的下标

2、从头到底递增

因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

即：如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

3、把案例过一遍处理好三个判断条件

如果比他大，那就知道要放的下标就是栈内下标，然后经过天数就是新入栈的下标 - 栈内下标，然后栈内pop然后新入栈，一路pop到没比他大的。然后最后因为res数组默认为0所以到最后没有大的了就默认为0了

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> st = new Stack<>();
        
        for (int i = 0; i < temperatures.length; i++) {
            // 注意：这里不需要 if-else 分支！直接用 while 处理
            while (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {
                int index = st.pop();
                res[index] = i - index;
            }
            st.push(i); // 当前索引只 push 一次
        }
        
        return res;
    }
}

最后一章图论

图论分为五大模块：

1、深搜和广搜

2、并查集

3、最小生成树

4、拖布排序

5、最短路算法

输出细节

最后一行不要有空格

想要做图论题目首先对图有概念

二维坐标中，两个点可以连成线，多个点连成的线就构成了图。

当然图也可以就一个几点，甚至没有节点（空图）

图的种类

整体上一般分为有向图和无向图

有向图是指图中边是有方向的：

无向图是指图中边没有方向：

加权有向图，就是图中边是有权值的，例如：

加权无向图也是同理。

度

无向图中有几条边连接该节点，该节点就有几度。

例如，该无向图中，节点4的度为5，节点6的度为3.

在有向图中，每个节点有出度和入度。

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

例如，该有向图中，节点3的入度为2，出度为1，节点1的入度为0，出度为2。

连通性

在图中表示节点的联通情况，我们称之为连通性。

连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图。

如图：

如果有节点不能到达其他节点，则为非连通图，如图：

节点1 不能到达节点4。

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为强连通图。

这个跟连通图有什么区别

我们来看这个有向图：

这个图是强连通图吗？

初步一看，好像这节点都连着呢，但这不是强连通图，节点1 可以到节点5，但节点5 不能到节点1 。

强连通图是在有向图中任何两个节点是可以相互到达

下面这个有向图才是强连通图：

图的构造

我们如何用代码来表示一个图呢？

一般使用邻接表、邻接矩阵或者用类来表示。

主要是朴素存储、邻接表和邻接矩阵。

关于朴素存储，这是自创的名字，因为这种存储方式，就是将所有边存下来。

图的存储方式

朴素存储

例如图：

图中有8条边，我们就定义 8 2的数组，即有n条边就申请n 2，这么大的数组：

数组第一行：6 7，就表示节点6 指向节点7，以此类推。

当然可以不用数组，用map，或者用类到可以表示出这种边的关系。

这种表示方式的好处就是直观，把节点与节点之间关系很容易展现出来。

但如果我们想知道节点1 和节点6 是否相连，我们就需要把存储空间都枚举一遍才行。

这是明显的缺点，同时，我们在深搜和广搜的时候，都不会使用这种存储方式。

因为搜索中，需要知道节点与其他节点的链接情况，而这种朴素存储，都需要全部枚举才知道链接情况。

邻接矩阵

邻接矩阵使用二维数组表示图结构，有多少节点就申请多大的二维数组。

假设要表示节点2和节点5为有向图，那么就创建grid[ 2 ] [ 5 ] = 6,说明节点2指向节点5 边的权值为6

如果想表示无向图，即：`grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。

如图：

在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。

图中有一条双向边，即：grid[2][5] = 6，grid[5][2]= 6

适合稠密图

邻接表

邻接表使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。

邻接表的构造如图：

这里表达的图是：

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4指向节点1

有多少边邻接表才会申请多少个对应的链表节点。

适合稀疏图

图的遍历方式

1、深搜 dfs

2、广搜 bfs

所有可达路径

98. 可达路径

常用的存储图的数据结构，好好审题，节点编号从1到 n 的

1、邻接矩阵

首先做这种题先存储好，图，那么这里先用邻接矩阵，题目先提供节点数和边然后就可以建立相对应的二维数组的大小了。

那么存好图之后开始深搜三部曲

1、函数的返回值，参数

首先是void返回值，然后有一个全局的res答案和一个存储路径的path，然后函数要传入图，当前遍历节点 x，终点 n

2、确认终止条件

什么时候我们找到一条路径了

当目前遍历的节点为最后一个节点n 的时候就找到了终点了。

3、处理当前节点的逻辑

首先是遍历节点x连接的所有节点，如果找到x连接的点，然后加入路径然后到下一层递归，然后回溯。

import java.io.*;
import java.util.*;

public class Main{
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer in = new StreamTokenizer(br);
        
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            int N = (int)in.nval;
            in.nextToken();
            int M = (int)in.nval;
            int[][] grid = new int[N + 1][N + 1];
            for(int i = 1 ; i < M + 1 ; i++){
                in.nextToken();
                int s = (int)in.nval;
                in.nextToken();
                int e = (int)in.nval;
                grid[s][e] = 1;
            }
            res.clear(); 
            path.clear(); 
            path.add(1);
            dfs(1,N,grid);
            if (res.isEmpty()) {
                out.println(-1);
            } else {
                for (List<Integer> pa : res) {
                    for (int i = 0; i < pa.size() - 1; i++) {
                        out.print(pa.get(i) + " ");
                    }
                    out.println(pa.get(pa.size() - 1));
                }
            }
        }
        out.flush();
        out.close(); 
    }

    public static void dfs(int cur,int n,int[][] grid){
        if(cur == n){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 2 ; i < n + 1 ; i++){
            if(grid[cur][i] == 1){
                path.add(i);
                dfs(i,n,grid);
                path.remove(path.size() - 1);
            }
        }
    }
}

2、邻接表

邻接表使用数组 + 链表的方式来表示。注意这里只是存储图的时候用数组 + 链表，但是存储path和res等其他思路没变。

import java.io.*;
import java.util.*;

public class Main {
    // 将 res 和 path 保留在类级别是可以的，但必须在每组数据前清空
    public static List<List<Integer>> res = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);

        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval; // n个节点
            in.nextToken();
            int m = (int) in.nval; // m条边

            // ======== 关键：重置全局状态 ========
            res.clear(); // 清空上一轮的结果
            path.clear(); // 清空上一轮的路径
            // ================================

            // 存储图
            List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
            for(int i = 0 ; i <= n ; i++){
                graph.add(new LinkedList<>());
            }
            while (m-- > 0) {
                in.nextToken();
                int s = (int) in.nval;
                in.nextToken();
                int t = (int) in.nval;
                 // 使用邻接表表示 s -> t 是相连的
                graph.get(s).add(t);
            }

            path.add(1); // 从节点1开始 (现在 path 是空的)
            dfs(graph, 1, n); // 开始遍历

            // 输出结果
            if (res.isEmpty()) {
                out.println(-1);
            } else {
                for (List<Integer> pa : res) {
                    for (int i = 0; i < pa.size() - 1; i++) {
                        out.print(pa.get(i) + " ");
                    }
                    out.println(pa.get(pa.size() - 1));
                }
            }
        }
        out.flush();
        out.close(); 
    }

    public static void dfs(List<LinkedList<Integer>> graph, int x, int n) {
        if (x == n) {
            res.add(new ArrayList<>(path)); // 添加路径的副本
            return;
        }
        for (int i : graph.get(x)) { // 找到 x指向的节点
            path.add(i); // 遍历到的节点加入到路径中来
            dfs(graph, i, n); // 进入下一层递归
            path.remove(path.size() - 1); // 回溯，撤销本节点
        }
    }
}

广搜

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

BFS是一圈一圈的搜索过程，但具体是怎么一圈一圈来搜？

我们用一个方格地图，假如每次搜索的方向为上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。

如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：

我们从图中可以看出，从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。

正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。

而且地图还可以有障碍，如图所示：

在第五步，第六步我只把关键的节点染色了，其他方向周边没有去染色，大家只要关注关键地方染色的逻辑就可以。

从图中可以看出，如果添加了障碍，我们是第六步才能走到end终点。

只要BFS只要搜到终点一定是一条最短路径，大家可以参考上面的图，自己再去模拟一下。

代码框架

这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。

其实我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么勇队列，还是用栈，甚至用数组，都是可以的

用队列的话，就是保证灭一圈都是一个方向去赚，例如同意顺时针或者逆时针。

因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈又顺时针遍历

因为栈是先进后厨，加入元素和弹出元素的顺序改变了。

那么广搜需要注意转圈搜索的顺序吗？不需要

所以用队列，还是用栈都是可以的，但大家习惯用队列了，所以下面还是用队列来讲，但是并不是非要用队列。

/-import java.util.*;

/**
 * 广度优先搜索 (BFS) 模板
 * 用于在二维网格（地图）上进行遍历
 * 
 * @param grid     二维字符数组，表示地图
 * @param visited  二维布尔数组，用于标记已访问的格子，防止重复访问
 * @param x        起始搜索位置的行索引
 * @param y        起始搜索位置的列索引
 */
public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
    // 方向数组：定义了上下左右四个移动方向
    // dir[0] = {0, 1}  -> 右 (行不变，列+1)
    // dir[1] = {1, 0}  -> 下 (行+1，列不变)
    // dir[2] = {-1, 0} -> 上 (行-1，列不变)
    // dir[3] = {0, -1} -> 左 (行不变，列-1)
    int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    // 创建一个队列，用于存储待探索的格子坐标
    // Java 中使用 LinkedList 作为 Queue 的实现
    Queue<int[]> queue = new LinkedList<>();

    // 将起始位置 (x, y) 加入队列
    queue.offer(new int[]{x, y});

    // 标记起始位置为已访问，避免重复入队
    visited[x][y] = true;

    // 当队列不为空时，继续搜索
    while (!queue.isEmpty()) {
        // 从队列头部取出当前要探索的格子
/*      int[] current = queue.poll();        
	    int curX = current[0]; // 当前格子的行坐标
        int curY = current[1]; // 当前格子的列坐标

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            // 计算下一个要探索的格子的坐标
            int nextX = curX + dir[i][0];
            int nextY = curY + dir[i][1];

            // 边界检查：判断新坐标是否超出网格范围
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue; // 越界，跳过这个方向
            }

            // 检查该格子是否已经被访问过
            if (!visited[nextX][nextY]) {
                // 如果未访问，则将其加入队列，准备后续探索
                queue.offer(new int[]{nextX, nextY});
                // 立即标记为已访问，这是防止重复入队的关键！
                visited[nextX][nextY] = true;
            }
        }
    }
    // 当队列为空时，说明从起始点 (x, y) 出发所有能到达的格子都已探索完毕
}

孤岛计数

99. 计数孤岛

首先广搜的策略就是，在visited，如果遇到1那就把visited的都标记了，然后开始广搜，遇到0就跳过，然后用一个res计岛屿数量。

import java.util.*;
import java.io.*;

public class Main {
    static int[][] dir = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };

    static class Pair {
        int x;
        int y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval; // 行数
            in.nextToken();
            int m = (int) in.nval; // 列数

            // 创建 (n+1) x (m+1) 网格，使用 [1..n][1..m]
            int[][] grid = new int[n + 1][m + 1];
            boolean[][] visited = new boolean[n + 1][m + 1];

            // 读入网格数据
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    in.nextToken();
                    grid[i][j] = (int) in.nval;
                }
            }

            int res = 0;

            // 遍历每个格子
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    // 如果是陆地（1）且未访问过，启动 BFS
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        res++;
                        bfs(grid, visited, i, j, n, m);
                    }
                }
            }

            out.println(res);
        }

        out.flush();
        out.close();
    }

    public static void bfs(int[][] grid, boolean[][] visited, int startX, int startY, int n, int m) {
        Queue<Pair> que = new LinkedList<>();
        que.offer(new Pair(startX, startY));
        visited[startX][startY] = true;

        while (!que.isEmpty()) {
            Pair cur = que.poll();
            int curX = cur.x;
            int curY = cur.y;

            // 探索四个方向
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];

                // 边界检查：必须在 [1, n] 和 [1, m] 范围内
                if (nextX < 1 || nextX > n || nextY < 1 || nextY > m) {
                    continue;
                }

                // 如果是陆地且未访问过，则加入队列
                if (grid[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                    visited[nextX][nextY] = true;
                    que.offer(new Pair(nextX, nextY));
                }
            }
        }
    }
}

如果是深搜

import java.util.*;
import java.io.*;

public class Main {
    static int[][] dir = {
        {-1, 0}, // 上
        {0, 1},  // 右
        {1, 0},  // 下
        {0, -1}  // 左
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval; // 行数
            in.nextToken();
            int m = (int) in.nval; // 列数

            int[][] grid = new int[n + 1][m + 1];
            boolean[][] visited = new boolean[n + 1][m + 1];

            // 读入网格（1-indexed）
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    in.nextToken();
                    grid[i][j] = (int) in.nval;
                }
            }

            int res = 0;

            // 遍历每个格子
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        res++; // 发现新岛屿
                        dfs(grid, visited, i, j, n, m);
                    }
                }
            }

            out.println(res);
        }

        out.flush();
        out.close();
    }

    // 深度优先搜索：将当前岛屿所有陆地标记为已访问
    public static void dfs(int[][] grid, boolean[][] visited, int x, int y, int n, int m) {
        // 标记当前点为已访问
        visited[x][y] = true;

        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            // 边界检查：必须在 [1, n] 和 [1, m] 范围内
            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }

            // 如果是陆地且未访问，继续 DFS
            if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                dfs(grid, visited, nx, ny, n, m);
            }
        }
    }
}

BFS 版本（关键片段）

Queue<Pair> que = new LinkedList<>();
que.offer(new Pair(startX, startY));
visited[startX][startY] = true;

while (!que.isEmpty()) {
    Pair cur = que.poll(); // ← 从队列头取出
    for (四个方向) {
        if (合法 && 是陆地 && 未访问) {
            visited[...] = true;
            que.offer(new Pair(...)); // ← 加入队列尾
        }
    }
}

DFS 版本（关键片段）

public static void dfs(...) {
    visited[x][y] = true;
    for (四个方向) {
        if (合法 && 是陆地 && 未访问) {
            dfs(grid, visited, nx, ny, n, m); // ← 直接递归调用
        }
    }
}

看出深搜和广搜的区别了。

并查集

并查集解决连通性问题。

并查集功能：将两个元素添加到一个集合中，判断两个元素在不在同一个集合。

那么为什么需要并查集，用set或者map不就可以了吗？

因为操作效率不同，在优化后的并查集中，合并两个集合只需要O（1）的复杂度就能完成，如果用现成的Set或者map需要遍历一个集合并加入到另一个，就慢了。

那么并查集是如何判断两个元素在一个集合内？

举例有A,B,C三个元素，然后A指向B，B指向C，C指向自己C，那么这时候判断A和B是否在同一个集合内，这时候由于A和B的根节点都是C，所以判断都在同一个集合内。

这就是并查集大体的工作过程。

void init(){
    for(int i ; i < n ;i++){
        father[i] = i;//默认自己指向自己
    }
}
void join(int a ,int b){
	a = find(a);
    b = find(b);
    if(a == b){//判断是否原本就是同一个集合了
        return;
    }
    father[a] = b;//这里其实就是将a的根节点和b的根节点连在一起
}
boolean isSame(int a,int b){
    //找根节点的函数实现
    a = find(a);
    b = find(b);
    if(a == b){
        return true;
    }else{
        return false;
    }
}
int find(int u){
    if( u == father[u]){
        return u;
    }
    int father = find(father[u]);
    return father;
}
//只有最深层的递归（满足 u == father[u] 的那层）
//所有上层递归都必须执行到最后的 return，把结果一层层传回去

在find里面还能进行性能优化

路径压缩

假设find里面非常的深，每次find都要一层一层递归才找到根节点，递归是特别耗时的。优化就是把所有层变成两层，扁平化，只需要递归一次就能找到根节点，那么如何压缩呢？在find里面修改

int find(int u){
    if(u == father[u]){
        return u;
    }
    father[u] = find(father[u]);
    return father[u];
}

那么这样就实现了路径压缩了。

算法理解（口语化）

前导

第一章 数组

二分

区间和

第二章 链表

删除节点

设计链表

第三章 哈希表

快乐数

第四章 字符串

反转字符串

重复的子字符串

第五章 栈和队列

有效括号

滑动窗口

前 K 个高频元素

第六章 二叉树

后序序列

迭代遍历

第七章后序 回溯算法

组合

分隔回文串

子集

全排列

第八章 贪心

第九章 动态规划

斐波那契数列

爬楼梯

不同路径

01背包

滚动数组

完全背包

零钱兑换

多重背包

第十章 单调栈

每日温度

最后一章 图论

输出细节

图的种类

度

连通性

连通图

强连通图

图的构造

图的存储方式

朴素存储

邻接矩阵

邻接表

图的遍历方式

所有可达路径

1、邻接矩阵

2、邻接表

广搜

代码框架

孤岛计数

并查集

第一章数组

第二章链表

第三章哈希表

第四章字符串

第五章栈和队列

第六章二叉树

第七章后序回溯算法

第八章贪心

第九章动态规划

第十章单调栈

最后一章图论