Java常用算法技巧总结

// 向下取整
Math.floor()
// 向上取整
Math.ceil()
// 返回最接近参数的整数，如果有2个数同样接近，则会返回偶数的那个
Math.rint()
// 四舍五入
Math.round()

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}


public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

// 依次合并两个链表
public void mergeList(ListNode l1, ListNode l2) {
    ListNode l1_tmp;
    ListNode l2_tmp;
    while (l1 != null && l2 != null) {
        l1_tmp = l1.next;
        l2_tmp = l2.next;

        l1.next = l2;
        l1 = l1_tmp;

        l2.next = l1;
        l2 = l2_tmp;
    }
}

// 合并k个已排序的链表
public ListNode mergeKLists(ArrayList<ListNode> lists) {
    //小顶堆
    Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
    //遍历所有链表第一个元素
    for(int i = 0; i < lists.size(); i++){
        //不为空则加入小顶堆
        if(lists.get(i) != null)
            pq.add(lists.get(i));
    }
    //加一个表头
    ListNode res = new ListNode(-1);
    ListNode head = res;
    //直到小顶堆为空
    while(!pq.isEmpty()){
        //取出最小的元素
        ListNode temp = pq.poll();
        //连接
        head.next = temp;
        head = head.next;
        //每次取出链表的后一个元素加入小顶堆
        if(temp.next != null)
            pq.add(temp.next);
    }
    //去掉表头
    return res.next;
}

// 单链表排序
public ListNode sortInList (ListNode head) {
    // write code here
    if (head == null || head.next == null)
        return head;
    // 使用快慢指针寻找链表的中点
    ListNode fast = head.next, slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode tmp = slow.next;
    slow.next = null;
    // 递归左右两边进行排序
    ListNode left = sortInList(head);
    ListNode right = sortInList(tmp);
    // 创建新的链表
    ListNode h = new ListNode(0);
    ListNode res = h;
    // 合并 left right两个链表
    while (left != null && right != null) {
        // left  right链表循环对比
        if (left.val < right.val) {
            h.next = left;
            left = left.next;
        } else {
            h.next = right;
            right = right.next;
        }
        h = h.next;
    }
    // 最后添加未对比的链表部分判断左链表是否为空
    h.next = left != null ? left : right;
    return res.next;
}

// 删除有序链表中重复的元素
public ListNode deleteDuplicates (ListNode head) {
    //空链表
    if(head == null)
        return null;
    ListNode res = new ListNode(0);
    //在链表前加一个表头
    res.next = head;
    ListNode cur = res;
    while(cur.next != null && cur.next.next != null){
        //遇到相邻两个节点值相同
        if(cur.next.val == cur.next.next.val){
            int temp = cur.next.val;
            //将所有相同的都跳过
            while (cur.next != null && cur.next.val == temp)
                cur.next = cur.next.next;
        }
        else
            cur = cur.next;
    }
    //返回时去掉表头
    return res.next;
}

// 全排列
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        boolean[] used = new boolean[n];
        dfs(ans, nums, 0, n, used, new ArrayList<Integer>());
        return ans;
    }

    public void dfs(List<List<Integer>> ans, int[] nums, int index, int maxx, boolean[] used, ArrayList<Integer> temp) {
        if (index == maxx) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < maxx; i++) {
            if (used[i] == false) {
                temp.add(nums[i]);
                used[i] = true;
                dfs(ans, nums, index + 1, maxx, used, temp);
                used[i] = false;
                temp.remove(index);
            }
        }
    }
}

public static class UnionFind {
  private int[] parent;
  private int[] sizeMap;
  private int size;

  public UnionFind(int N) {
      size = N;
      parent = new int[N];
      sizeMap = new int[N];
      for (int i = 0; i < N; i++) {
          parent[i] = i;
          sizeMap[i] = 1;
      }
  }

  public int size() {
      return size;
  }

  private int find(int v) {
      if (v != parent[v]) {
          parent[v] = find(parent[v]);
      }
      return parent[v];
  }

  public void union(int v1, int v2) {
      int f1 = find(v1);
      int f2 = find(v2);
      if (f1 != f2) {
          size--;
          int s1 = sizeMap[f1];
          int s2 = sizeMap[f2];
          if (s1 > s2) {
              parent[f2] = f1;
              sizeMap[f1] += s2;
          } else {
              parent[f1] = f2;
              sizeMap[f2] += s1;
          }
      }
  }
}

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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class BinaryTree {
    List<Integer> ans = new ArrayList<>();

    // 前序遍历
    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        ans.add(root.val); // 访问根节点
        preorder(root.left); // 遍历左子树
        preorder(root.right); // 遍历右子树
    }

    // 中序遍历
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left); // 遍历左子树
        ans.add(root.val); // 访问根节点
        inorder(root.right); // 遍历右子树
    }

    // 后序遍历
    public void postorder(TreeNode root) {
        if (root == null) {
            return;
        }
        postorder(root.left); // 遍历左子树
        postorder(root.right); // 遍历右子树
        ans.add(root.val); // 访问根节点
    }
}

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

class Solution {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

    public TreeNode helper(int in_left, int in_right) {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return null;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map.get(root_val);

        // 下标减一
        post_idx--;
        // 构造右子树
        root.right = helper(index + 1, in_right);
        // 构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        // 从后序遍历的最后一个元素开始
        post_idx = postorder.length - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (Integer val : inorder) {
            idx_map.put(val, idx++);
        }
        
        return helper(0, inorder.length - 1);
    }
}

import java.util.*;

public class TopologicalSort {
    public static List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
        // 创建一个数组来存储每个顶点的入度
        int[] inDegree = new int[numCourses];
        // 创建一个邻接表
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        // 填充邻接表并记录每个顶点的入度
        for (int[] prerequisite : prerequisites) {
            int dest = prerequisite[0];
            int src = prerequisite[1];
            adjList.get(src).add(dest);
            inDegree[dest]++;
        }
        // 使用队列找到所有入度为0的顶点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        // 进行拓扑排序
        List<Integer> topOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            topOrder.add(vertex);
            // 遍历每一个顶点的邻居
            for (int neighbor : adjList.get(vertex)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
        // 检查是否有环
        if (topOrder.size() != numCourses) {
            return new ArrayList<>(); // 如果排序后的顶点数不等于课程数，说明存在环
        }
        return topOrder;
    }

    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        List<Integer> order = topologicalSort(numCourses, prerequisites);
        System.out.println("Topological Order: " + order);
    }
}

import java.util.*;

public class DijkstraAlgorithm {
    private static final int NO_PARENT = -1;

    public static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
        int nVertices = adjacencyMatrix.length;
        int[] shortestDistances = new int[nVertices];
        boolean[] added = new boolean[nVertices];

        Arrays.fill(shortestDistances, Integer.MAX_VALUE);
        Arrays.fill(added, false);
        
        shortestDistances[startVertex] = 0;

        int[] parents = new int[nVertices];
        Arrays.fill(parents, NO_PARENT);

        for (int i = 1; i < nVertices; i++) {
            int nearestVertex = -1;
            int shortestDistance = Integer.MAX_VALUE;
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
                    nearestVertex = vertexIndex;
                    shortestDistance = shortestDistances[vertexIndex];
                }
            }

            added[nearestVertex] = true;

            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];
                
                if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
                    parents[vertexIndex] = nearestVertex;
                    shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
                }
            }
        }

        printSolution(startVertex, shortestDistances, parents);
    }

    private static void printSolution(int startVertex, int[] distances, int[] parents) {
        System.out.println("Vertex\t Distance\tPath");
        
        for (int vertexIndex = 0; vertexIndex < distances.length; vertexIndex++) {
            if (vertexIndex != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(vertexIndex + " \t\t ");
                System.out.print(distances[vertexIndex] + "\t\t");
                printPath(vertexIndex, parents);
            }
        }
    }

    private static void printPath(int currentVertex, int[] parents) {
        if (currentVertex == NO_PARENT) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    public static void main(String[] args) {
        int[][] adjacencyMatrix = {
            { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
            { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
            { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
            { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
            { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
            { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
            { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
            { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
            { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
        };
        dijkstra(adjacencyMatrix, 0);
    }
}

public class FloydWarshallAlgorithm {
    final static int INF = 99999, V = 4;

    public static void floydWarshall(int graph[][]) {
        int dist[][] = new int[V][V];
        int i, j, k;

        for (i = 0; i < V; i++)
            for (j = 0; j < V; j++)
                dist[i][j] = graph[i][j];

        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

        printSolution(dist);
    }

    public static void printSolution(int dist[][]) {
        System.out.println("The following matrix shows the shortest distances between every pair of vertices");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int graph[][] = { {0, 5, INF, 10},
                          {INF, 0, 3, INF},
                          {INF, INF, 0, 1},
                          {INF, INF, INF, 0}
                        };
        floydWarshall(graph);
    }
}

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] == target) {
                return mid; // 目标值在数组中的索引
            } else if (array[mid] < target) {
                left = mid + 1; // 搜索右半区间
            } else {
                right = mid - 1; // 搜索左半区间
            }
        }
        return -1; // 如果未找到目标值，返回 -1
    }

    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 9;
        int result = binarySearch(numbers, target);
        System.out.println("Index of target is: " + result);
    }
}

import java.util.*;

public class Main {
    
    public static String mulNums(String a, String b) {
        // Create an array to store multiplication results
        int[] res = new int[a.length() + b.length() - 1];
        // Populate the result array with products of digits
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                res[i + j] += (a.charAt(i) - '0') * (b.charAt(j) - '0');
            }
        }
        
        // Convert the result array into the final result string
        StringBuilder ret = new StringBuilder();
        int carry = 0;
        for (int i = res.length - 1; i >= 0; i--) {
            int num = res[i] + carry;
            ret.insert(0, (char) (num % 10 + '0'));
            carry = num / 10;
        }
        // Add remaining carry if present
        if (carry > 0)
            ret.insert(0, (char) (carry + '0'));
        return ret.toString();
    }

    public static void main(String[] args) {
        System.out.println(mulNums("12345", "67890111"));
    }
}

import java.math.BigInteger;

public class HighPrecisionDivision {

    public static String divideNumbers(String dividend, String divisor) {
        // Convert strings to BigInteger for handling large numbers
        BigInteger bigDividend = new BigInteger(dividend);
        BigInteger bigDivisor = new BigInteger(divisor);
        
        // Perform division and get the quotient
        BigInteger quotient = bigDividend.divide(bigDivisor);
        
        // Return the quotient as a string
        return quotient.toString();
    }

    public static void main(String[] args) {
        String dividend = "12345678901234567890";
        String divisor = "12345";
        System.out.println("Quotient: " + divideNumbers(dividend, divisor));
    }
}

public class SlidingWindowTemplate {

    /**
     * Finds the minimum length of a subarray with a sum at least equal to the given target.
     * @param nums Array of integers.
     * @param target Sum target for the subarray.
     * @return Minimum length of the subarray with sum at least target, or 0 if no such subarray exists.
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;  // Set to a large number initially.
        int start = 0;                      // Start index of the sliding window.
        int sum = 0;                        // Current sum of the sliding window.

        for (int end = 0; end < n; end++) {
            sum += nums[end];  // Expand the window by including the current element.

            // Once we have a window with sum >= target, we try to shrink it from the left.
            while (sum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                sum -= nums[start];  // Shrink the window from the start.
                start++;             // Move the start index to the right.
            }
        }

        // If minLength was updated, return its value, otherwise return 0 for no valid subarray.
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        int result = minSubArrayLen(target, nums);
        System.out.println("Minimum length of subarray: " + result);  // Output should be 2, for the subarray [4, 3]
    }
}