当前位置：首页 > article >正文

精选算法合集

article 2025/1/18 14:03:10

一、BFS相关

1.1 最小步骤

给定一个数组，从第一个开始，正好走到数组最后，所使用的最少步骤数。要求：

第一步从第一元素开始，第一步小于<len/2（len为数组的长度）。从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少, 如果目标不可达返回-1，输出最少的步骤数，不能往回走。

输入7 5 9 4 2 6 8 3 5 4 3 9输出2

输入1 2 3 7 1 5 9 3 2 1输出-1

package JDYL;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class MiniSteps {
    public int getMiniStep(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return 0;
        }

        int minStep = Integer.MAX_VALUE;
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[length];

        for (int i = 1; i < visited.length/2; i++) {
            visited[i] = true;
            queue.add(new int[]{i, 1});
        }

        visited[0] = true;

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int index = poll[0];
            int step = poll[1];

            if (index + arr[index] == length-1) {
                if (step+1 < minStep) {
                    minStep = step+1;
                }
            }

            if (index + arr[index] < length && !visited[index+arr[index]]) {
                queue.add(new int[]{index+arr[index], step+1});
                visited[index + arr[index]] = true;
            }

        }

        if (minStep == Integer.MAX_VALUE) {
            return -1;
        }

        return minStep;
    }

    public static void main(String[] args) {
        MiniSteps miniSteps = new MiniSteps();
        // 测试用例1
        int[] arr1 = {7, 5, 9, 4, 2, 6, 8, 3, 5, 4, 3, 9};
        System.out.println(miniSteps.getMiniStep(arr1)); // 输出 2

        // 测试用例2
        int[] arr2 = {1, 2, 3, 7, 1, 5, 9, 3, 2, 1};
        System.out.println(miniSteps.getMiniStep(arr2)); // 输出 -1
    }
}

暴力求解法

package org.example.jxsfhj;

public class MinStep {

    int res = Integer.MAX_VALUE;

    public int getMiniStep(int[] arr) {
        if (arr.length == 0) {
            return -1;
        }
        int len = arr.length / 2;

        for (int i = 0; i < len; i++) {
            getMini(arr, i, 1);
        }

        if (this.res == Integer.MAX_VALUE) {
            return -1;
        }

        int result = res;
        res = Integer.MAX_VALUE;

        return result;
    }

    public void getMini(int[] arr, int currStep, int step) {
        if (currStep == arr.length - 1) {
            if (step < res) {
                res = step;
            }
        } else if (currStep < arr.length-1) {
            int currElem = arr[currStep];
            if (currElem == 0) {
                return;
            }
            currStep = currStep + currElem;

            getMini(arr, currStep, step + 1);
        }
    }

    public static void main(String[] args) {
        MinStep minStep = new MinStep();

        int[] arr1 = {7, 5, 9, 4, 2, 6, 8, 3, 5, 4, 3, 9};
        System.out.println(minStep.getMiniStep(arr1));

        // 测试用例2
        int[] arr2 = {1, 2, 3, 7, 1, 5, 9, 3, 2, 1};
        System.out.println(minStep.getMiniStep(arr2));


    }
}

1.2 二维矩阵两点间所有的最短路径

package algo.backTrace2;

import java.util.*;

class Node<T> {
    Node<T> up;
    Node<T> down;
    Node<T> left;
    Node<T> right;
    T data;

    void setUp(Node<T> up) {
        this.up = up;
    }

    void setDown(Node<T> down) {
        this.down = down;
    }

    void setLeft(Node<T> left) {
        this.left = left;
    }

    void setRight(Node<T> right) {
        this.right = right;
    }

    void setData(T data) {
        this.data = data;
    }

    public Node<T> getUp() {
        return this.up;
    }

    public Node<T> getDown() {
        return this.down;
    }

    public Node<T> getLeft() {
        return this.left;
    }

    public Node<T> getRight() {
        return this.right;
    }

    public T getData() {
        return this.data;
    }

    @Override
    public String toString() {
        return " " + this.getData();
    }

    public Node<Integer>[][] getLinkeds(int n) {
        Node<Integer>[][] nodeArr = new Node[n][n];
        int m = 1;
        // 构造node二位数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Node<Integer> node = new Node<>();
                node.data = m;
                nodeArr[i][j] = node;
                m++;
            }
        }

        // 建立指针
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Node<Integer> current = nodeArr[i][j];
                // left
                if (j - 1 >= 0) {
                    Node<Integer> left = nodeArr[i][j - 1];
                    current.left = left;
                }
                // right
                if (j + 1 < n) {
                    Node<Integer> right = nodeArr[i][j + 1];
                    current.right = right;
                }
                // up
                if (i - 1 >= 0) {
                    Node<Integer> up = nodeArr[i - 1][j];
                    current.up = up;
                }
                // down
                if (i + 1 < n) {
                    Node<Integer> down = nodeArr[i + 1][j];
                    current.down = down;
                }
            }
        }

        return nodeArr;
    }

    public int allShortestPaths(Node<Integer> start, Node<Integer> target) {
        if (start == target) {
            System.out.println("start and targe are the same.");
            return -1;
        }

        // 定义变量
        Queue<Node<Integer>> queue = new LinkedList<>();
        Set<Node<Integer>> visited = new HashSet<>();
        Map<Node<Integer>, Integer> distance = new HashMap<>();
        Map<Node<Integer>, List<Node<Integer>>> parents = new HashMap<>();

        // 初始化变量
        queue.add(start);
        visited.add(start);
        distance.put(start, 0);
        parents.put(start, new ArrayList<>());

        // 逻辑处理
        while (!queue.isEmpty()) {
            Node<Integer> currNode = queue.poll();
            Node<Integer>[] direct = new Node[]{currNode.getUp(), currNode.getDown(), currNode.getLeft(), currNode.getRight()};
            for (int i = 0; i < direct.length; i++) {
                if (direct[i] != null) {
                    int newDistance = distance.get(currNode) + 1;
                    if (!visited.contains(direct[i])) {
                        queue.add(direct[i]);
                        visited.add(direct[i]);
                        distance.put(direct[i], newDistance);
                        parents.put(direct[i], new ArrayList<>());
                        parents.get(direct[i]).add(currNode);
                    } else {
                        if (distance.get(direct[i]) == newDistance) {
                            parents.get(direct[i]).add(currNode);
                        }
                    }
                }
            }
        }

        if (!visited.contains(target)) {
            System.out.println("Can not find the target.");
            return -2;
        }

        // 打印输出测试数据
        // System.out.println("parents : " + parents);

        //打印路径
        List<List<Node<Integer>>> results = new ArrayList<>();
        List<Node<Integer>> currList = new ArrayList<>();
        currList.add(target);

        this.printTraces(parents, target, currList, results);
        System.out.println("所有最短路径");
        for (List<Node<Integer>> result : results) {
            for (int i = result.size()-1; i >= 0; i--) {
                System.out.print(result.get(i) + " ");
            }
            System.out.println();
        }

        return 1;
    }

    public void printTraces(Map<Node<Integer>, List<Node<Integer>>> parents, Node<Integer> currNode, List<Node<Integer>> currList, List<List<Node<Integer>>> results) {

        List<Node<Integer>> nodes = parents.get(currNode);
        if (nodes.isEmpty()) {
            results.add(new ArrayList<>(currList));
            return;
        }

        for (Node<Integer> node : nodes) {
            currList.add(node);
            printTraces(parents, node, currList, results);
            currList.remove(currList.size()-1);
        }

    }

    public void getAllShortestPaths(Node<Integer> start, Node<Integer> target) {
        this.allShortestPaths(start, target);
    }
}

public class GetAllShortestPaths {
    public void main(String[] args) {
        int num = 4;
        Node<Integer> node = new Node<>();
        Node<Integer>[][] linkeds = node.getLinkeds(num);
        System.out.println("生成的二维矩阵：");
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                System.out.print(linkeds[i][j].data + " ");
            }
            System.out.println();
        }

        node.getAllShortestPaths(linkeds[0][0], linkeds[3][3]);
    }
}

1.3 BFS+回溯

贪吃蛇

现在有一个N*M(N，M=100)的方形矩形，在这个矩形的每一个方格上都放有一个随机值，一条可爱的小蛇从矩形的左上角开始出发，每次移动都只能移动一格，向右或向下，而每到达一格贪吃的小蛇都会吧该位置上的值吃个一干二净，直到到达右下角时停止。而贪吃的小蛇不怕撑死，它只想吃到最多，并输出路径。

package JDYL;

import java.util.*;

/**
 * 带权有向图
 */
public class Snake {

    static class Grap {
        Map<Integer, List<Edge>> grap;

        Grap() {
            grap = new HashMap<>();
        }

        public void addEdge(int from, Edge edge) {
            List<Edge> orDefault = this.grap.getOrDefault(from, new ArrayList<>());
            orDefault.add(edge);
            this.grap.put(from, orDefault);
        }

        public List<Edge> getAllEdgesByNode(int node) {
            return grap.get(node);
        }
    }

    static class Edge {
        int des;
        int weight;

        Edge(int des, int weight) {
            this.des = des;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return this.des + "=" + this.weight;
        }
    }

    public void findMaxWeightSum(Grap grap, int start, int target) {
        Map<Integer, List<Integer>> prev = new HashMap<>();
        Map<Integer, Integer> disFromStart = new HashMap<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparing(a -> -a[1]));
        Map<Integer, Boolean> visited = new HashMap<>();
        grap.grap.forEach((k, edges) -> {
            visited.put(k, false);
        });


        // 初始化
        visited.put(start, true);
        queue.offer(new int[]{start, 0});
        disFromStart.put(start, 0);

        // BFS
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int currNode = poll[0];
            int currDisFromStart = poll[1];


            List<Edge> allEdgesByNode = grap.getAllEdgesByNode(currNode);
            for (Edge edge : allEdgesByNode) {
                int nextDes = edge.des;
                int weight = edge.weight;
                if (nextDes != -1) {
                    int newDisFromStart = currDisFromStart + weight;

                    if (!visited.get(nextDes)) {
                        queue.offer(new int[]{nextDes, newDisFromStart});
                        visited.put(nextDes, true);
                        disFromStart.put(nextDes, currDisFromStart + weight);
                        List<Integer> orDefault = prev.getOrDefault(nextDes, new ArrayList<>());
                        orDefault.add(currNode);
                        prev.put(nextDes, orDefault);
                    } else {
                        if (disFromStart.getOrDefault(nextDes, 0) < newDisFromStart) {
                            disFromStart.put(nextDes, newDisFromStart);
                            List<Integer> list = prev.get(nextDes);
                            list.clear();
                            list.add(currNode);
                            prev.put(nextDes, list);
                        } else if (disFromStart.getOrDefault(nextDes, 0) == newDisFromStart) {
                            List<Integer> list = prev.get(nextDes);
                            list.add(currNode);
                            prev.put(nextDes, list);
                        }
                    }
                }

            }
        }

        System.out.println("当前节点到开始节点的距离：" + disFromStart);
        System.out.println("前序节点：" + prev);

        if (!prev.keySet().contains(target)) {
            System.out.println("未找到路径");
        } else {
            List<List<Integer>> res = new ArrayList<>();
            this.printTrace(prev, start, target, new ArrayList<>(), res);
            System.out.println(res);
        }
    }

    public void printTrace(Map<Integer, List<Integer>> prev, int start, int target, List<Integer> currList, List<List<Integer>> result) {

        currList.add(target);
        List<Integer> list = prev.get(target);

        if (target == start) {
            System.out.println(currList);
            result.add(new ArrayList<>(currList));
            return;
        }

        for (Integer p : list) {
            printTrace(prev, start, p, currList, result);
            currList.remove(currList.size()-1);
        }

    }


    public static void main(String[] args) {

        Grap grap = new Grap();
        grap.addEdge(0, new Edge(1, 4));
        grap.addEdge(0, new Edge(2, 1));
        grap.addEdge(1, new Edge(3, 2));
        grap.addEdge(2, new Edge(3, 4));
        grap.addEdge(2, new Edge(4, 3));
        grap.addEdge(3, new Edge(5, 1));
        grap.addEdge(4, new Edge(5, 3));
        grap.addEdge(5, new Edge(-1, 0));


        grap.grap.forEach((k, v) -> {
            System.out.println(k + "=>" + v);
        });


        Snake snake = new Snake();
        snake.findMaxWeightSum(grap, 0, 5);
    }


}

二、回溯算法

2.1 能量消耗

给出一批用户，每个用户有3种选择A\B\C，但是价值不同，相临的用户不能选同一个，求出所有用户选择后总价值最大。

3个用户

30 8 4

50 20 9

11 7 6

输出65，因为选8 50 7

package JDYL;

import java.util.ArrayList;
import java.util.List;

public class BackTrace3 {

    Integer value = 0;
    List<Integer> trace = new ArrayList<>();

    public void router(int[][] arr) {
        core(arr, 0, 0, 0, new ArrayList<>());
    }

    public void core(int[][] arr, int row, int column, int currValue, List<Integer> currTrace) {
        if (row == arr.length) {
            if (currValue>this.value) {
                this.value = currValue;
                trace.clear();
                trace.addAll(currTrace);
            }
            return;
        }

        for (int currColum = 0; currColum < arr.length; currColum++) {
            if (currColum == column) {
                continue;
            }
            currTrace.add(arr[row][currColum]);
            core(arr, row+1, currColum, currValue+arr[row][currColum], currTrace);
            currTrace.remove(currTrace.size()-1);
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {30, 8, 4},
                {50, 20, 9},
                {11, 7, 6}
        };

        BackTrace3 trace3 = new BackTrace3();
        trace3.router(arr);

        System.out.println(trace3.value);
        System.out.println(trace3.trace);
    }
}

2.2 全排列

package algo.backtrace;

import java.util.ArrayList;
import java.util.List;


public class HSQanpailie {

    public List<List<Integer>> router(int[] arr) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        Boolean[] used = new Boolean[arr.length];
        for (int i = 0; i < used.length; i++) {
            used[i] = false;
        }
        this.qpl(arr, current, used, results);
        return results;
    }

    public void qpl(int[] arr, List<Integer> current, Boolean[] used, List<List<Integer>> results) {
        if (current.size() == arr.length) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (used[i]) {
                continue;
            }

            used[i] = true;
            current.add(arr[i]);

            qpl(arr, current, used, results);

            used[i] = false;
            current.remove(current.size()-1);
        }
    }

    public void main(String[] args) {
        int[] arr = {1,2,3};
        List<List<Integer>> router = this.router(arr);
        for (List<Integer> list : router) {
            System.out.println(list);
        }
    }
}

2.3 八皇后

package algo.backtrace;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 8*8矩阵，每一行放置一个皇后，要求满足如下条件：
 * 相邻两行的皇后不能在上下左右及对角线的位置。
 */
public class NQueen {
    public List<int[][]> slove8QueenRouter(int num) {
        List<int[][]> results = new ArrayList<>();
        int[][] current = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                current[i][j] = 0;
            }
        }
        this.slove8QueenCore(num, 0, current, results);
        return results;

    }

    public boolean isSafe(int[][] current, int row, int column, int num) {
        int left = 0;
        for (int i = row; i > 0 ; i--) {
            left++;
            // 左上对角线
            if (column-left>=0 && current[i-1][column-left] == 1) {
                return false;
            }
            // 上列
            if (current[i-1][column] == 1) {
                return false;
            }
            // 右对角线
            if (column+left<num && current[i-1][column+left] == 1) {
                return false;
            }
        }

        return true;
    }

    public int[][] copyArray(int[][] arr, int num) {
        int[][] result = new int[num][num];
        for (int i = 0; i < num ; i++) {
            for (int j = 0; j < num; j++) {
                result[i][j] = arr[i][j];
            }
        }
        return result;
    }

    public void slove8QueenCore(int num, int row, int[][] current, List<int[][]> results) {
        if (row == num) {
            results.add(copyArray(current, num));
            return;
        }

        for (int cloum = 0; cloum < num; cloum++) {
            if (isSafe(current, row, cloum, num)) {
                current[row][cloum] = 1;
                slove8QueenCore(num, row+1, current, results);
                current[row][cloum] = 0;
            }

        }
    }

    public void main(String[] args) {
        int num = 8;
        List<int[][]> results = this.slove8QueenRouter(num);
        System.out.println("results : ");
        for (int[][] result : results) {
            for (int i = 0; i < num; i++) {
                System.out.println(Arrays.toString(result[i]));
            }
            System.out.println();
        }
    }
}

2.4 Dijkstra 带权图最短路径（有难度）

package algo.backtrace.Dijkstra.weiwei;

import java.util.*;

public class Dijkstra {

    class Grap {

        // 带权重的无向图表示，邻接矩阵表示
        Map<Integer, List<Edag>> adjList;

        Grap() {
            adjList = new HashMap<>();
        }

        // 添加边
        public void addEdag(int start, int des, int weight) {
            adjList.putIfAbsent(start, new ArrayList<>());
            adjList.putIfAbsent(des, new ArrayList<>());
            adjList.get(start).add(new Edag(des, weight));
            adjList.get(des).add(new Edag(start, weight));
        }

        // 获取一个顶点的所有边
        public List<Edag> getEdags(int node) {
            return adjList.getOrDefault(node, new ArrayList<>());
        }

        // 获取所有顶点
        public Set<Integer> getAllNodes() {
            return adjList.keySet();
        }
    }

    // 描述边
    class Edag{
        int des;
        int weight;
        Edag(int des, int weight) {
            this.des = des;
            this.weight = weight;
        }
    }

    public Map<Integer, Integer> dijkstra(Grap grap, Integer start) {
        // 定义工具
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
        Map<Integer, Integer> dist = new HashMap<>();
        Map<Integer, Integer> prev = new HashMap<>();

        // 初始化参数
        for (Integer node : grap.getAllNodes()) {
            dist.put(node, Integer.MAX_VALUE);
            prev.put(node, -1);
        }

        dist.put(start, 0);
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            int currNode = poll[0];
            int currWeight = poll[1];

            if (currWeight > dist.get(currNode)) {
                continue;
            }

            for (Edag edag : grap.getEdags(currNode)) {
                int newDist = currWeight + edag.weight;
                if (newDist < dist.get(edag.des)) {
                    dist.put(edag.des, newDist);
                    prev.put(edag.des, currNode);
                    pq.offer(new int[]{edag.des, newDist});
                }
            }
        }

        System.out.println("dist:" + dist);
        System.out.println("prev:" + prev);

        return prev;
    }

    public void printTrace(Map<Integer, Integer> prevMap, int traget, List<Integer> trace) {
        if (prevMap.get(traget) == -1) {
            return;
        }

        traget = prevMap.get(traget);
        printTrace(prevMap, traget, trace);
        trace.add(traget);
    }

    public void main(String[] args) {
        Grap grap = new Grap();
        grap.addEdag(0,1,4);
        grap.addEdag(0,2,1);
        grap.addEdag(1,3,2);
        grap.addEdag(2,3,8);
        grap.addEdag(2,4,3);
        grap.addEdag(4,5,2);
        grap.addEdag(3,5,1);

        Dijkstra dijkstra = new Dijkstra();
        Map<Integer, Integer> prevMap = dijkstra.dijkstra(grap, 0);
        List<Integer> list = new ArrayList<>();
        dijkstra.printTrace(prevMap, 5, list);
        System.out.println(list);
    }
}

2.5 动态规划

固定的容积，可以最多装多少？

例如：[5 3 4 6 1 2 9]，容积是15，输出为：5，说明是 3 4 1 2

package JDYL;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MaxWeight {

    int weight = Integer.MIN_VALUE;

    public List<Integer> router(int[] arr, int max) {
        List<Integer> result = new ArrayList<>();
        this.exec(arr, 0, 0, max, new ArrayList<>(), result);
        return result;
    }

    public void exec(int[] arr, int n, int currWeight, int max, List<Integer> currList, List<Integer> result) {
        if (currWeight>max || n >= arr.length) {
            return;
        }

        if (currWeight>this.weight) {
            this.weight = currWeight;
            result.clear();
            result.addAll(currList);
        }

        // 放进去
        currList.add(arr[n]);
        currWeight = currWeight+arr[n];
        n = n+1;
        exec(arr, n, currWeight, max, currList, result);
        n = n-1;
        currWeight = currWeight-arr[n];
        currList.remove(currList.size()-1);

        // 不放进去
        n = n+1;
        exec(arr, n, currWeight, max, currList, result);
        n = n-1;
    }


    public static void main(String[] args) {
        int max = 15;
        String s = "5 3 4 6 1 2 9";
        String[] split = s.split(" ");

        int[] arr = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();

        MaxWeight maxWeight = new MaxWeight();
        List<Integer> router = maxWeight.router(arr, max);
        System.out.println(router);
        System.out.println(maxWeight.weight);
    }
}


//[5, 3, 4, 1, 2]
//        15

三、字符串匹配

3.1 BF

package algo.stringMatch;

import java.util.Arrays;
import java.util.Objects;

public class BF {

    public int BF(String mainStr, String subStr) {
        String[] mainStrArr = mainStr.split("");
        String[] subStrArr = subStr.split("");


        for (int i = 0; i < mainStrArr.length - subStrArr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < subStrArr.length; j++) {
                if (!subStrArr[j].equals(mainStrArr[j+i])) {
                    flag = false;
                }
            }
            if (flag) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        String mainStr = "wejfhwohfjfdshfdskjhfs";
        String subStr = "dskj";

        BF bf = new BF();
        int index = bf.BF(mainStr, subStr);
        System.out.println(index);


    }


}

3.2 KMP

package algo.stringMatch;

import java.util.Arrays;

public class KMPAlgorithm {

    // 构建部分匹配表
    public static int[] computeLPSArray(String pat) {
        int M = pat.length();
        int[] lps = new int[M];
        int len = 0;

        lps[0] = 0; // lps[0] is always 0
        int i = 1;

        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    // KMP 字符串搜索
    public static void KMPSearch(String pat, String txt) {
        int N = txt.length();
        int M = pat.length();

        // 创建 lps 数组
        int[] lps = computeLPSArray(pat);

        int i = 0; // txt 的索引
        int j = 0; // pat 的索引

        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                i++;
                j++;
            }

            if (j == M) {
                j = lps[j - 1];
            }

            // 未匹配的情况
            if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i = i + 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        String txt = "ABABDABACDABABCABAB";
        String pat = "ABAC";
        KMPSearch(pat, txt);
    }
}

四、递归

4.1 获取所有台阶走法

package JDYL;

public class GetTotleSteps {

    int res = 0;

    public void getPath(int n) {
        core(n, 0);
    }

    public void core(int n, int currIndex) {
        if (currIndex == n) {
            res++;
            return;
        }

        if (currIndex < n) {
            // 走1个台阶
            core(n, currIndex+1);

            // 走2个台阶
            core(n, currIndex+2);
        }
    }


    public static void main(String[] args) {
        int n = 2;

        GetTotleSteps getTotleSteps = new GetTotleSteps();
        getTotleSteps.getPath(n);
        System.out.println(getTotleSteps.res);
    }
}

4.2 兔子繁殖

3个月兔子长大，然后每个月都会生产一只小兔，问N天后，一共有多少只小兔。

package JDYL;

public class RabbitsCount {
    public int getRabbits(int days) {
        int months = (days + 29) / 30;
        int[] rabbits = new int[months+1];

        rabbits[1] = 1;
        rabbits[2] = 1;
        rabbits[3] = 1;

        for (int i = 4; i < months+1; i++) {
            rabbits[months] = rabbits[months-1]+rabbits[months-3];
        }

        return rabbits[months];
    }

    public static void main(String[] args) {
        int n = 70;

        RabbitsCount rabbitsCount = new RabbitsCount();
        int rabbits = rabbitsCount.getRabbits(n);
        System.out.println(rabbits);
    }
}

五、边界处理

5.1 喊7的次数重排

喊7是一个传统的聚会游戏，N个人围成一圈，按顺时针从1到N编号。编号为1的人从1开始喊数，下一个人喊的数字为上一个人的数字加1，但是当数字是7的倍数或者数字本身含有7的话，要喊"过"。现给定一个长度为N的数组，存储了打乱顺序的每个人喊"过"的次数，请把它还原成正确的顺序，即数组的第i个元素存储编号i的人喊"过"的次数。

输入为一行，为空格分隔的喊"过"的次数，

示例1

输入

0 1 0

输出

1 0 0

说明

一共只有一次喊"过"，那只会发生在需要喊7时，按顺序，编号为1的人会遇到7，故输出1 0 0。注意，结束时的K不一定是7，也可以是8、9等，喊过的次数都是1 0 0。

示例2

输入

0 0 0 2 1

输出

0 2 0 1 0

说明

一共有三次喊"过"，发生在7 14 17，按顺序，编号为2的人会遇到7 17，编号为4的人会遇到14，故输出0 2 0 1 0。

package JDYL;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ContionsSevle {

    public boolean isContions7(int n) {
        return n%7 == 0 || String.valueOf(n).contains("7");
    }

    public int[] exec(int[] arr) {
        int[] res = new int[arr.length];

        // 一共几个人
        int people = arr.length;
        // 一共叫过几次
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        int tmpCount = 0;
        int n = 1;
        while (tmpCount < sum) {
            if (isContions7(n)) {
                res[n%people-1]++;
                tmpCount++;
            }
            n++;
        }

        return res;
    }


    public static void main(String[] args) {
        int[] arr = {0,0,0,2,1};

        ContionsSevle contionsSevle = new ContionsSevle();
        int[] exec = contionsSevle.exec(arr);
        System.out.println(Arrays.toString(exec));
    }
}

六、循环数组

循环数组解题技巧：

i%n 来模拟循环。
循环2次，来比较最后一个元素和第一个元素。
借助栈来解题，与当前元素距离最近，其实栈弹出后是个倒序。

例题：

找出比自己大的数

给一个数组，收尾相连，按照顺序找到比自己大的第一个数，找不到的存-1。

例如[35,25,48,37] ->输出[48,48,-1,48]

package JDYL;

import java.util.Stack;

public class NextGreaterElement {

    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        // 初始化结果数组，默认值为 -1
        for (int i = 0; i < n; i++) {
            result[i] = -1;
        }

        // 遍历数组两遍，模拟循环
        for (int i = 0; i < 2 * n; i++) {
            int currentIndex = i % n;  // 取模操作，模拟循环
            // 如果栈不为空且当前元素大于栈顶元素，则找到下一个比栈顶元素大的数
            while (!stack.isEmpty() && nums[stack.peek()] < nums[currentIndex]) {
                int idx = stack.pop();
                result[idx] = nums[currentIndex];
            }
            // 仅将元素索引压入栈
            if (i < n) {  // 只在第一次遍历时压入索引
                stack.push(currentIndex);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {35, 25, 48, 37};
        int[] result = nextGreaterElements(nums);

        // 输出结果
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

七、排序算法

思想设计的巧妙和边界问题尤为需要注意的当属归并排序和快速排序两个排序算法，且对应的算法时间复杂度都是O(nlogn)，相比冒泡，插入等排序算法的O(N^2)复杂度要低，更加常用。

要重点体会“思想的巧妙”和“边界的处理”。

7.1 归并排序

package org.example.JDAL;

import java.util.Arrays;

public class MergeSort {

    // 测试归并排序
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前数组:" + Arrays.toString(arr));

        MergeSort mergeSort = new MergeSort();

        mergeSort.mergeSort(arr);

        System.out.println("排序后数组:" + Arrays.toString(arr));
    }

    private void mergeSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }

        int mid = length/2;

        int[] left = new int[mid];
        int[] right = new int[length-mid];


        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }
        for (int i = mid; i < length; i++) {
            right[i-mid] = arr[i];
        }

        this.mergeSort(left);
        this.mergeSort(right);

        this.merge(arr, left, right);
    }

    private void merge(int[] arr, int[] left, int[] right) {

        int i=0;
        int j=0;
        int k=0;

        while (i<left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        if (i<left.length) {
            for (int l = i; l < left.length; l++) {
                arr[k] = left[l];
                k++;
            }
        }

        if (j<right.length) {
            for (int l = j; l < right.length; l++) {
                arr[k] = right[l];
                k++;
            }
        }
    }
}

7.2 快速排序

package org.example.JDAL;

import java.util.Arrays;

public class QuickSortTest {

    public void quickSort(int[] arr, int s, int e) {
        if (s>=e) {
            return;
        }

        int p = partition(arr,s,e);
        this.quickSort(arr, s, p-1);
        this.quickSort(arr, p+1, e);
    }

    public int partition(int[] arr, int s, int e) {
        int p = arr[e];
        int m=s;

        for (int i = s; i < e; i++) {
            if (arr[i] <= p) {
                int tmp = arr[i];
                arr[i] = arr[m];
                arr[m] = tmp;

                m++;
            }
        }

        int tmp = arr[e];
        arr[e] = arr[m];
        arr[m] = tmp;

        return m;
    }


    public static void main(String[] args) {
        int[] arr = {7,5,1,2,3,4,8,9};
        QuickSortTest quickSortTest = new QuickSortTest();
        quickSortTest.quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

八、双指针

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

package JDYL;

import java.util.Arrays;

class RemoveDuplicates2 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2,2,2, 2, 3};
        int newLength = removeDuplicates(nums);

        // 输出新数组的长度和修改后的数组
        System.out.println("New length: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int slow = 1;  // slow 指针从第二个元素开始
        int count = 1; // count 用于记录当前元素出现的次数

        // 遍历数组，从第二个元素开始
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] == nums[fast - 1]) {
                count++;
            } else {
                count = 1; // 如果遇到不同的元素，重置 count
            }

            // 如果 count <= 2，说明当前元素可以保留
            if (count <= 2) {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        System.out.println(Arrays.toString(nums));

        return slow; // slow 即为新数组的长度
    }
}

九、数组操作(TODO)

获取指定数组的子数组
合并两个子数组为一个大数组

十、字符串操作(TODO)

获取指定字符串的子串
合并多个字符串

十一、跳跃游戏（贪心思想）

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

package org.example.JDAL;

public class JumpGame {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 0, 4};
        boolean b = jumpCore(nums);
        System.out.println(b);
    }

    private static boolean jumpCore(int[] nums) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i>maxLen) {
                return false;
            }
            maxLen = Math.max(i+nums[i], maxLen);
        }

        return true;
    }
}

十二、跳跃游戏2（贪心思想）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

package org.example.JDAL;

public class MinSteps2 {
    public static int jump(int[] nums) {
        int n = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < n - 1; i++) {
            // 计算能到达的最远距离
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {2, 3, 0, 1, 4};
        System.out.println(jump(nums1));
        System.out.println(jump(nums2));
    }
}00片；【

十三、数据结构与算法复杂度

O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

package org.example.JDAL;

import java.util.*;

// O(1) 时间插入、删除和获取随机元素
public class RandomizedSet {

    Map<Integer, Integer> map;
    List<Integer> list;
    Random random;

    public RandomizedSet() {
        // 查询 O（1）的有：Array ｜ HashMap
        // 插入 list ｜ hashMap
        // 删除 list ｜ hashMap

        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (this.map.containsKey(val)) {
            return false;
        }

        // insert
        this.list.add(val);
        int size = this.list.size();
        this.map.put(val, size);
        return true;
    }

    public boolean remove(int val) {
        if (!this.map.containsKey(val)) {
            return false;
        }

        // remove
        Integer index = this.map.get(val);
        int last = list.get(list.size()-1);
        list.set(index, last);
        map.put(last, index);
        list.remove(list.size()-1);
        map.remove(val);

        return true;
    }

    public int getRandom() {
        int i = this.random.nextInt(this.list.size());
        return this.map.get(i);
    }

    public static void main(String[] args) {

    }

}

十三、正向思维与逆向思维

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

package org.example.JDAL;

import java.util.Arrays;

public class ProductExceptSelf2 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};

        ProductExceptSelf2 exceptSelf2 = new ProductExceptSelf2();
        int[] res = exceptSelf2.route(nums);
        System.out.println(Arrays.toString(res));
    }

    private int[] route(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] res = new int[length];


        L[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            L[i] = L[i-1]*nums[i-1];
        }

        R[length-1] = 1;
        for (int i = length-2; i >= 0; i--) {
            R[i] = R[i+1]*nums[i+1];
        }

        for (int i = 0; i < res.length; i++) {
            res[i] = L[i]*R[i];
        }

        System.out.println(Arrays.toString(L));
        System.out.println(Arrays.toString(R));

        return res;

    }

}

十四、YangQG 面试题汇总

YangQG 面试题汇总-CSDN博客

14.1 交叉链表

解题思想：

双指针思想

package org.example.YangQianGuan;

class Node {
    int data;
    Node next;

    Node(int val) {
        this.data = val;
        this.next = null;
    }

    @Override
    public String toString() {
        return " {data: " + this.data + " next: " + this.next + "} ";
    }
}

public class IntersectionNode {
    public Node getStartInter(Node headA, Node headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Node pA = headA;
        Node pB = headB;

        while (pA!= pB) {
            pA = pA == null? headB : pA.next;
            pB = pB == null? headA : pB.next;
        }
        return pA;
    }


    public static void main(String[] args) {
        // node list
        Node node8 = new Node(8);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node8.next = node4;
        node4.next = node5;

        // A list
        Node headA = new Node(4);
        Node nodeA1 = new Node(1);
        headA.next = nodeA1;
        nodeA1.next = node8;

        // B List
        Node headB = new Node(5);
        Node nodeB1 = new Node(6);
        Node nodeB2 = new Node(1);
        headB.next = nodeB1;
        nodeB1.next = nodeB2;
        nodeB2.next = node8;

        IntersectionNode intersectionNode = new IntersectionNode();
        Node startInter = intersectionNode.getStartInter(headA, headB);
        System.out.println(startInter);
    }
}

十五、背包问题

背包问题是经典的算法问题，其变种多背包算法在实际项目中也有应用，这次让我们一起来搞懂背包算法。

背包

0-1背包

package org.example;

import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    int maxW = 0;

    public static void main(String[] args) {
        int[] weight = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//        int max = 31; // 91
        int max = 91; // 91

        Knapsack knapsack = new Knapsack();

        List<Integer> res = knapsack.getMaxW(weight, max);
        System.out.println("maxW :" + knapsack.maxW + " res : " + res);
    }

    private List<Integer> getMaxW(int[] weight, int max) {
        List<Integer> res = new ArrayList<>();
        int currIdx = 0;
        int currW = 0;
        List<Integer> currList = new ArrayList<>();

        this.exec(weight, max, currIdx, currW, currList, res);

        return res;
    }

    private void exec(int[] weight, int max, int currIdx, int currW, List<Integer> currList, List<Integer> res) {
        if (currW == max || currIdx == weight.length) {
            if (currW > this.maxW) {
                this.maxW = currW;
                res.clear();
                res.addAll(currList);
            }
            return;
        }

        // 当前物品放进背包
        if (currW + weight[currIdx] <= max) {
            currW += weight[currIdx];
            currList.add(weight[currIdx]);
            this.exec(weight, max, currIdx + 1, currW, currList, res);
            currList.remove(currList.size() - 1);
            currW -= weight[currIdx];
        }

        // 当前物品不放进背包
        this.exec(weight, max, currIdx + 1, currW, currList, res);
    }

}