wap网站 劣势,给中小企业提供网站建设服务,刚刚好痛,wordpress购物模板一、BFS相关
1.1 最小步骤
给定一个数组#xff0c;从第一个开始#xff0c;正好走到数组最后#xff0c;所使用的最少步骤数。要求#xff1a;
第一步从第一元素开始#xff0c;第一步小于len/2#xff08;len为数组的长度#xff09;。从第二步开始#xff0c…一、BFS相关
1.1 最小步骤
给定一个数组从第一个开始正好走到数组最后所使用的最少步骤数。要求
第一步从第一元素开始第一步小于len/2len为数组的长度。从第二步开始只能以所在成员的数字走相应的步数不能多也不能少, 如果目标不可达返回-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;Queueint[] 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 (step1 minStep) {minStep step1;}}if (index arr[index] length !visited[indexarr[index]]) {queue.add(new int[]{indexarr[index], step1});visited[index arr[index]] true;}}if (minStep Integer.MAX_VALUE) {return -1;}return minStep;}public static void main(String[] args) {MiniSteps miniSteps new MiniSteps();// 测试用例1int[] arr1 {7, 5, 9, 4, 2, 6, 8, 3, 5, 4, 3, 9};System.out.println(miniSteps.getMiniStep(arr1)); // 输出 2// 测试用例2int[] 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));// 测试用例2int[] 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 NodeT {NodeT up;NodeT down;NodeT left;NodeT right;T data;void setUp(NodeT up) {this.up up;}void setDown(NodeT down) {this.down down;}void setLeft(NodeT left) {this.left left;}void setRight(NodeT right) {this.right right;}void setData(T data) {this.data data;}public NodeT getUp() {return this.up;}public NodeT getDown() {return this.down;}public NodeT getLeft() {return this.left;}public NodeT getRight() {return this.right;}public T getData() {return this.data;}Overridepublic String toString() {return this.getData();}public NodeInteger[][] getLinkeds(int n) {NodeInteger[][] nodeArr new Node[n][n];int m 1;// 构造node二位数组for (int i 0; i n; i) {for (int j 0; j n; j) {NodeInteger 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) {NodeInteger current nodeArr[i][j];// leftif (j - 1 0) {NodeInteger left nodeArr[i][j - 1];current.left left;}// rightif (j 1 n) {NodeInteger right nodeArr[i][j 1];current.right right;}// upif (i - 1 0) {NodeInteger up nodeArr[i - 1][j];current.up up;}// downif (i 1 n) {NodeInteger down nodeArr[i 1][j];current.down down;}}}return nodeArr;}public int allShortestPaths(NodeInteger start, NodeInteger target) {if (start target) {System.out.println(start and targe are the same.);return -1;}// 定义变量QueueNodeInteger queue new LinkedList();SetNodeInteger visited new HashSet();MapNodeInteger, Integer distance new HashMap();MapNodeInteger, ListNodeInteger parents new HashMap();// 初始化变量queue.add(start);visited.add(start);distance.put(start, 0);parents.put(start, new ArrayList());// 逻辑处理while (!queue.isEmpty()) {NodeInteger currNode queue.poll();NodeInteger[] 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);//打印路径ListListNodeInteger results new ArrayList();ListNodeInteger currList new ArrayList();currList.add(target);this.printTraces(parents, target, currList, results);System.out.println(所有最短路径);for (ListNodeInteger 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(MapNodeInteger, ListNodeInteger parents, NodeInteger currNode, ListNodeInteger currList, ListListNodeInteger results) {ListNodeInteger nodes parents.get(currNode);if (nodes.isEmpty()) {results.add(new ArrayList(currList));return;}for (NodeInteger node : nodes) {currList.add(node);printTraces(parents, node, currList, results);currList.remove(currList.size()-1);}}public void getAllShortestPaths(NodeInteger start, NodeInteger target) {this.allShortestPaths(start, target);}
}public class GetAllShortestPaths {public void main(String[] args) {int num 4;NodeInteger node new Node();NodeInteger[][] 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(NM100)的方形矩形在这个矩形的每一个方格上都放有一个随机值一条可爱的小蛇从矩形的 左上角开始出发每次移动都只能移动一格向右或向下而每到达一格贪吃的小蛇都会吧该位置上的值吃个一干二净直到到达右下角时停止。而贪吃的小蛇不怕撑死它只想吃到最多并输出路径。
package JDYL;import java.util.*;/*** 带权有向图*/
public class Snake {static class Grap {MapInteger, ListEdge grap;Grap() {grap new HashMap();}public void addEdge(int from, Edge edge) {ListEdge orDefault this.grap.getOrDefault(from, new ArrayList());orDefault.add(edge);this.grap.put(from, orDefault);}public ListEdge 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;}Overridepublic String toString() {return this.des this.weight;}}public void findMaxWeightSum(Grap grap, int start, int target) {MapInteger, ListInteger prev new HashMap();MapInteger, Integer disFromStart new HashMap();PriorityQueueint[] queue new PriorityQueue(Comparator.comparing(a - -a[1]));MapInteger, 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);// BFSwhile (!queue.isEmpty()) {int[] poll queue.poll();int currNode poll[0];int currDisFromStart poll[1];ListEdge 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);ListInteger orDefault prev.getOrDefault(nextDes, new ArrayList());orDefault.add(currNode);prev.put(nextDes, orDefault);} else {if (disFromStart.getOrDefault(nextDes, 0) newDisFromStart) {disFromStart.put(nextDes, newDisFromStart);ListInteger list prev.get(nextDes);list.clear();list.add(currNode);prev.put(nextDes, list);} else if (disFromStart.getOrDefault(nextDes, 0) newDisFromStart) {ListInteger 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 {ListListInteger res new ArrayList();this.printTrace(prev, start, target, new ArrayList(), res);System.out.println(res);}}public void printTrace(MapInteger, ListInteger prev, int start, int target, ListInteger currList, ListListInteger result) {currList.add(target);ListInteger 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;ListInteger 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, ListInteger currTrace) {if (row arr.length) {if (currValuethis.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, row1, currColum, currValuearr[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 ListListInteger router(int[] arr) {ListListInteger results new ArrayList();ListInteger 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, ListInteger current, Boolean[] used, ListListInteger 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};ListListInteger router this.router(arr);for (ListInteger 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 Listint[][] slove8QueenRouter(int num) {Listint[][] 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-left0 current[i-1][column-left] 1) {return false;}// 上列if (current[i-1][column] 1) {return false;}// 右对角线if (columnleftnum current[i-1][columnleft] 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, Listint[][] 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, row1, current, results);current[row][cloum] 0;}}}public void main(String[] args) {int num 8;Listint[][] 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 {// 带权重的无向图表示邻接矩阵表示MapInteger, ListEdag 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 ListEdag getEdags(int node) {return adjList.getOrDefault(node, new ArrayList());}// 获取所有顶点public SetInteger getAllNodes() {return adjList.keySet();}}// 描述边class Edag{int des;int weight;Edag(int des, int weight) {this.des des;this.weight weight;}}public MapInteger, Integer dijkstra(Grap grap, Integer start) {// 定义工具PriorityQueueint[] pq new PriorityQueue(Comparator.comparing(a - a[1]));MapInteger, Integer dist new HashMap();MapInteger, 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(MapInteger, Integer prevMap, int traget, ListInteger 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();MapInteger, Integer prevMap dijkstra.dijkstra(grap, 0);ListInteger 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 ListInteger router(int[] arr, int max) {ListInteger 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, ListInteger currList, ListInteger result) {if (currWeightmax || n arr.length) {return;}if (currWeightthis.weight) {this.weight currWeight;result.clear();result.addAll(currList);}// 放进去currList.add(arr[n]);currWeight currWeightarr[n];n n1;exec(arr, n, currWeight, max, currList, result);n n-1;currWeight currWeight-arr[n];currList.remove(currList.size()-1);// 不放进去n n1;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();ListInteger 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[ji])) {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 0int 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, currIndex1);// 走2个台阶core(n, currIndex2);}}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[months1];rabbits[1] 1;rabbits[2] 1;rabbits[3] 1;for (int i 4; i months1; 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];StackInteger stack new Stack();// 初始化结果数组默认值为 -1for (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 i0;int j0;int k0;while (ileft.length j right.length) {if (left[i] right[j]) {arr[k] left[i];i;} else {arr[k] right[j];j;}k;}if (ileft.length) {for (int l i; l left.length; l) {arr[k] left[l];k;}}if (jright.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 (se) {return;}int p partition(arr,s,e);this.quickSort(arr, s, p-1);this.quickSort(arr, p1, e);}public int partition(int[] arr, int s, int e) {int p arr[e];int ms;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 (imaxLen) {return false;}maxLen Math.max(inums[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 1040 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 {MapInteger, Integer map;ListInteger list;Random random;public RandomizedSet() {// 查询 O1的有Array HashMap// 插入 list hashMap// 删除 list hashMapmap new HashMap();list new ArrayList();random new Random();}public boolean insert(int val) {if (this.map.containsKey(val)) {return false;}// insertthis.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;}// removeInteger 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[i1]*nums[i1];}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;}Overridepublic 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 listNode node8 new Node(8);Node node4 new Node(4);Node node5 new Node(5);node8.next node4;node4.next node5;// A listNode headA new Node(4);Node nodeA1 new Node(1);headA.next nodeA1;nodeA1.next node8;// B ListNode 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; // 91int max 91; // 91Knapsack knapsack new Knapsack();ListInteger res knapsack.getMaxW(weight, max);System.out.println(maxW : knapsack.maxW res : res);}private ListInteger getMaxW(int[] weight, int max) {ListInteger res new ArrayList();int currIdx 0;int currW 0;ListInteger currList new ArrayList();this.exec(weight, max, currIdx, currW, currList, res);return res;}private void exec(int[] weight, int max, int currIdx, int currW, ListInteger currList, ListInteger 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);}}多背包
