Java算法总结

一、链表相关

1.1 从尾到头打印单链表[要求 方式1：反向遍历。方式2：Stack栈]

// 上面的题的要求就是逆序打印单链表// 方式1：先将单链表进行反转操作，然后再遍历即可,这样做的问题就是会破坏原来的单链表的结构，不建议// * 方式2：可以利用栈这个数据结构，将各个结点压入栈中，然后利用栈的先进后出的特点，就实现了逆序打印public void printReverseLinkList() {if (head.next == null) return;Stack<T> stack = new Stack<>();// 遍历压栈Node<T> cur = head.next;while (cur != null) {stack.push(cur.getData());cur = cur.next;}// 出栈打印while (stack.size() > 0) {System.out.println(stack.pop());}}

1.2 josephu问题（使用带尾指针的循环链表）

package com.gyh.Link;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class SingleCircularLinkedListDemo {public static void main(String[] args) {SingleCircularLinkedList<Integer> integerSingleCircularLinkedList = new SingleCircularLinkedList<>();for (int i = 0; i < 10; i++) {integerSingleCircularLinkedList.add(i);}List<Integer> josephu = integerSingleCircularLinkedList.josephu(4, 6);josephu.forEach(System.out::println);}
}/*** 1. 创建尾结点* 2. 每次定位至数到 m 的结点的上一个结点位置（只有这样才可以更新信息）** @param <T>*/
class SingleCircularLinkedList<T> {// 不设置头结点(设置指向尾元素的指针)private Node<T> last;// 判断空public boolean isEmpty() {return last == null;}// 添加数据public void add(T d) {// 为空则直接创建if (isEmpty()) {last = new Node<>(d, null);last.setNext(last);return;}last.next = new Node<T>(d, last.next);last = last.next;}// 链表长度public int getLength() {// 为空则返回if (isEmpty()) return 0;int n = 1;Node<T> cur = last.next;while (cur != last) {n++;cur = cur.next;}return n;}// 约瑟夫问题public List<T> josephu(int k, final int m) {// 1 <= k <= nint n = getLength();assert k >= 1 && k <= n;if (n == 1) return Collections.singletonList(last.getData());// 循环出值List<T> out = new ArrayList<>();// pre初始为最后一个元素Node<T> pre = last;// 定位到 编号为 k 的前面一个人for (int i = 1; i < k; i++) {pre = pre.next;}// 报数到mwhile (true) {if (last.next == last) { // 只有一个元素out.add(last.getData());last = null;break;}// 获取数到m的结点的前面一个结点for (int i = 1; i < m; i++) {pre = pre.next;}// 从循环链表中删除该结点if (pre.next == last) last = pre; // 如果删除的是最后一个结点则将last指向preout.add(pre.next.getData()); // 将删除的结点值保存pre.next = pre.next.next;}return out;}
}

二、动态规划

2.1 斐波那契数列 2022.4.18

class Solution {// method1: 递归// public int fib(int n) {//     if(n==0){//         return 0;//     }//     if(n==1){//         return 1;//     }//     return fib(n-1)+fib(n-2);// }// method2: 记忆法// public static long[] fibs = new long[101];// static{//     fibs[0] = 0L;//     fibs[1] = 1L;// }// private static int curIndex = 1;// public int fib(int n) {//     if(n<=curIndex){//         return (int) fibs[n];//     }//     while(curIndex<n){//         curIndex++;//         fibs[curIndex] = (fibs[curIndex-1] + fibs[curIndex-2])% 1000000007;//     }//     return (int) fibs[n];// }// method3: 动态规划public int fib(int n) {if(n==0){return 0;}if(n==1){return 1;}int n1 = 0;int n2 = 1;int sum = 0;for(int i = 2;i<=n;i++){sum = (n1+n2)%1000000007;n1 = n2;n2 = sum;}return sum;}
}

2.2 青蛙上台阶 2022.4.18

class Solution {public int numWays(int n) {// 动态规划（等价于斐波拉切）if(n == 0){return 1;}if(n == 1){return 1;}int n1 = 1;int n2 = 1;int sum = 0;for(int i = 2; i <= n; i++){sum = (n1+n2) % 1000000007;n1 = n2;n2 = sum;}return sum;}
}

三、位运算符

3.1 二进制中1的个数 2022.4.18

https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {// method1: 从二进制的最右一位逐位判断1// int hw = 0;// while(n!=0){//     hw += n&1;//     n>>>=1; // 无符号右移// }// return hw;// method2: 利用 n&(n-1)int hw = 0;while(n!=0){hw++;n&=n-1; // 会将二进制最右侧的一去除}return hw;}
}

四、回溯算法

4.1 打印从1到最大的n位数 2022.4.18

// class Solution {
//     public int[] printNumbers(int n) {
//         // method1: 非大数打印
//         int end = (int)Math.pow(10, n) - 1;
//         int[] res = new int[end];
//         for(int i = 0; i < end; i++)
//             res[i] = i + 1;
//         return res;//     }
// }class Solution {// method2: 大数打印int[] res;char[] chars = {'0','1','2','3','4','5','6','7','8','9'};char[] nums;int n,count=0;public int[] printNumbers(int n) {this.n = n; // 最大的位数// 创建输出结果的int数组res = new int[(int)Math.pow(10,n)-1];nums = new char[n]; // nums为与最大位数个数相同的字符数组，用于保存每个数dfs(0);return res;}/**基于深度优先的字符打印*/private void dfs(int x){if(x == n){// 字符数组转换为字符串String nStr = String.valueOf(nums);// 字符串转换为数字// 不保留数字0int m;if((m=Integer.parseInt(nStr))!=0){res[count++] = m;}return;}for(char p:chars){nums[x] = p;dfs(x+1);}}}

五、双指针

5.1 单链表反转 2022.4.18

// 基于迭代
// 单链表的反转// 先定义一个结点 reverseHead=new Node// 从头到尾遍历原来的链表，每遍历一个结点，就将其取出，并放在新的链表的最前端(头插法)// 原来的链表的 head.next = reverseHead.nextpublic void reverseLink() {// 1. 没有数据或只有一个数据，就不操作if (head.next == null || head.next.next == null) return;// 设置反转链表的头结点Node<T> reverseHead = new Node<>(null, null);Node<T> cur = head.next;// 指向当前的结点Node<T> next; // 指向当前结点[cur]的下一个结点while (cur != null) {// 暂时保存当前结点的下一个结点next = cur.next;// 头插法cur.next = reverseHead.next;reverseHead.next = cur;// 更新当前结点位置cur = next;}head.next = reverseHead.next;}

package com.gyh.reverselinkedlist;/*** @author Gao YongHao* @version 1.0*/
public class ReverseList {public static void main(String[] args) {ListNode node5 = new ListNode(5, null);ListNode node4 = new ListNode(4, node5);ListNode node3 = new ListNode(3, node4);ListNode node2 = new ListNode(2, node3);ListNode node1 = new ListNode(1, node2);ListNode prev = recursion(node1);while (prev != null) {System.out.println(prev.val);prev = prev.next;}}public static ListNode iterate(ListNode node) {return null;}// 递归public static ListNode recursion(ListNode head) {// 如果头结点为null或找到尾元素则返回if (head == null || head.next == null) {return head;}// 递归返回最后一个结点的ListNode new_head = recursion(head.next);head.next.next = head;head.next = null;return new_head;}}class ListNode {Integer val;ListNode next;public ListNode(Integer val, ListNode next) {this.val = val;this.next = next;}
}

5.2 链表中倒数第k个节点 2022.4.18

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode getKthFromEnd(ListNode head, int k) {// int length = 0;// ListNode curr = head;// method1: 求全长+遍历// // 求链表长度// while(curr!=null){//     length++;//     curr = curr.next;// }// // 迭代获取倒数第k个结点// curr = head;// for(int i = 0;i<length-k;i++){//     curr = curr.next;// }// return curr;// method2: 基于快慢指针ListNode former=head, laster=head;// 让 former 先走 k 步for(int i = 0;i < k-1;i++){// 如果链表长度小于k则返回nullif(former == null) return null;former = former.next;}// 保持 former 与 laster的间距,使 former指向最后一个元素，则laster指向倒数第k个元素while(former.next!=null){former = former.next;laster = laster.next;}return laster;}
}