Java算法总结

文章目录

• 一、链表相关
• • 1.1 从尾到头打印单链表[要求 方式1：反向遍历。方式2：Stack栈]
  • 1.2 josephu问题（使用带尾指针的循环链表）
• 二、动态规划
• • 2.1 斐波那契数列 2022.4.18
  • 2.2 青蛙上台阶 2022.4.18
• 三、位运算符
• • 3.1 二进制中1的个数 2022.4.18
• 四、回溯算法
• • 4.1 打印从1到最大的n位数 2022.4.18
• 五、双指针
• • 5.1 单链表反转 2022.4.18
  • 5.2 链表中倒数第k个节点 2022.4.18

一、链表相关

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 <= n
        int 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;
        }
        // 报数到m
        while (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指向pre
            out.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 value
    public 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);
            // 字符串转换为数字
            // 不保留数字0
            int 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.next
    public 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则返回null
            if(former == null) return null;
            former = former.next;
        }

        // 保持 former 与 laster的间距,使 former指向最后一个元素，则laster指向倒数第k个元素
        while(former.next!=null){
            former = former.next;
            laster = laster.next;
        }
        return laster;


    }
}