Hexo

深度优先1.定义深度优先遍历算法步骤 1)访问初始结点v，并标记结点v为已访问。 2)查找结点v的第一个邻接结点w。 3)若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。 4)若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。 5)查找结点v的w邻接结点的下一个邻接结点，转到步骤3。 2.个人理解先设置第一个点为已经访问过的再看这个点与其他拿几个点连接过，并且那些点没有访问过，那么久把这个点递归dfs（递归基停止是都访问过就直接跳回上一个 3.代码讲解首先设置为已经访问过的，在用for循环看邻接矩阵是否这两个相连并没有访问过，那么久把这个点用dfs在递归 12345678910public static void dfs(int i,int[][] arr,boolean[] visited){ visited[i]=true; System.out.print(i+"->"); for (int j = 0; j < arr.length; j++ ...

基数排序1.定义1)将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 2.个人理解首先获取最大值，看他有几位数就循环几次，首先构建10个队列，从0到9，首先看数组里元素的个位数，按个位数是i依次加入到为i的队列里，然后再把数组重新赋值，从队列0移除所有元素，一直到队列9，再从个位数j获取放到队列j里，直到循环结束 3.图示讲解 4.代码讲解找出最大值，看是几位就循环几次，然后依次获取个位数加入对应的队列再给arr赋值把队列清空，在获取十位，直到结束 1234567891011121314151617181920212223242526272829303132public static void main(String[] args) { int[] arr={53,63,542,748,14,214}; int max=arr[0]; for (int i = 0; i < arr.len ...

归并排序1.定义归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分**(divide)成一些小的问题然后递归求解，而治****(conquer)的阶段则将分的阶段得到的各答案“修补“在一起，即分而治之)**。 2.0个人理解先把数组一直分 分成n组直到每组只有一个元素，然后在对每两组元素进行合并（因为他就是两组两组的分的就是用middle来分），合并时就先狗一个空数组，同时设置l1，l2为每一组元素的开头，再比较arr【l1】yuarr【l2】的大小，晓得就假如新数组，并++，最后再把这个数组的元素拷贝到原数组里。 3.图示讲解 4.0代码讲解4.1不断分组的代码终止条件同样也是l》=r，否则就是取中间值middle，再划分两组，最后进行合并 12345678910public static void mergeSort(int left,int right,int[] arr){ if (left>=right){ r ...

快排1.0定义 快速排序（Quicksort）是对冒泡排序的一种改进。基本思想****是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 2.个人理解快排运用了分而治之的思想，先把数组分成两个区域，一个是小于value的区域，一个是大于value的区域，在对这两个区域里的进行分解，直到只有一个元素才停止，先用sort算法分成两个区域，并把value的下标取出，然后再分成左区域和右区域，再这里面进行找下标再区分，直到l>=r 3.图片讲解 4.0代码讲解首先要两个代码，一个是不断进行分左区域和区域，另一个就是分大于value和小于value，最后的出下标返回来进行左右划分 4.1不断划分左右区域条件终止是l》=r 123456789public static void quickSort2(int[] arr,int left,int right){ if (left>=right ...

希尔排序1.思路把整个数组先找出中间数mid=（length/2),用mid的个数分成5组，用插入排序，排每一组，再把mid=mid/2,再分成mid组，知道mid==0才停止。 1for (int i = arr.length/2; i >0; i/=2) {//分组 123456789for (int j = i; j <arr.length ; j++) {//选择排序，从mid开始数，找j-i来比较， int k=j-i; int tem=arr[j];//要插入的元素 while (k>=0&&tem<arr[k]){ arr[k+i]=arr[k]; k-=i; } arr[k+i]=tem; ...

八皇后问题1来源 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任****意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 2思路2.1构建思路构建一个int【8】的数组，i是x，arr【i】是y，这样就形成了坐标 2.2检测冲突直线就是arr【i】与arr【i-1】.。。arr【0】这些值是否相等，斜线就是x的变化值与y的变化值是否相等即i-j==arr【i】-arr【j】 123456789public static boolean check(int[] arr,int n){ //检测是否冲突 for (int i = 0; i < n; i++) { if (arr[n]==arr[i]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){ return false; ...

迷宫问题1定义定义走过通路为2，墙壁为1，未经过的是0，已经走过了的不是通路3，当终点为2时就是成功 2方法当终点是2直接返回成功，当为0时，我们先定义他是2，再走访他周围四个点，当周围有路可走就是通路返回true，如果周围都不是（1,3,2）已近走过了的和是墙，那就返回false 12345678910111213141516171819202122public static boolean setWay(int[][] map,int i, int j){ if (map[6][5]==2){ return true; }else if(map[i][j]==0){ map[i][j]=2;//先假设为通路 if (setWay(map,i+1,j)){ return true; }else if (setWay(map,i,j+1)){ ...

逆波兰算法1后缀表达式 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下**:** 1)从左至右扫描，将3和4压入堆栈； 2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3)将5入栈； 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5)将6入栈； 6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果 按照操作顺序来计算（所读取的是数字就加入，是符号就弹出，并进行求和 1234567891011121314151617181920212223String string="30 4 + 5 * 6 -"; String[] strings=s2.split(" ") ...

构建栈计算器1.思路一个个扫描每个字节看尸数字还是符号，分别加入不同的栈构建两个栈，一个数字栈，一个符号栈，符号栈威空直接压入或者要压的元素比栈顶的元素优先级高，就压入，否则就弹出两个数字和一个符号，计算结果，然后压入数字栈，再用那个符号与栈顶的符号比较，直到结束。 2.bug如果是多位数，会变成多个个位数不是百位数等解决方法，扫描是数字接着扫直到不是数字才停止 3.代码3.1分辨是符号还是数字1234public static boolean isoper(char ch){ return ch=='-'||ch=='+'||ch=='/'||ch=='*'; } 3.2符号优先级123456789public static int priority(int val){ if (val=='+'||val=='-'){ return 0; }el ...

反转链表解决 反转一个单链表。 示例: 12输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 解决思路：先构建一个虚拟头节点dummyhead，通过遍历获取每一个节点cur，插入在虚拟头节点那个树上了，具体是cur.next=dummyhead.next,dummyhead.next=cur，这句话是把cur指向dummyhead的下一个节点（前一个节点），然后dummyhead再指向cur，cur再遍历最后返回dummyhead。next就行 12345678910111213141516public ListNode re(ListNode head){ ListNode reverse=new ListNode(-1); ListNode cur=head.next; ListNode next; while (cur!=null){ next=cur.nex ...