devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

经典算法题汇总

作者：人工智能uu | 2024-07-24 18:37:06

赞

踩

经典算法题

目录

1. 动态规划 / 回溯

1.1 最长公共子序列（牛客版, leetcode 1143）

1.2 最长上升子序列（leetcode 300）

1.3 最长回文子串（牛客版，leetcode 5）

1.4 接雨水

1.5 重复数字的所有排列（回溯）

1.6 集合的所有子集 （牛客版，leetcode 78）

2. 树

2.1 判断一颗二叉树是否为二叉搜索树和完全二叉树

2. 2  二叉树的最近公共祖先（leetcode 236）

2.3 二叉搜索树的第k小节点（牛客版）

 2.4 二叉搜索树与双向链表（牛客版）

2.5 重建二叉树（剑指offer，leetcode版）

3. 数组

3.1 数组中的最长连续子序列（牛客版）

3.2 寻找第k大的数（牛客版）

3.3 旋转数组的最小数字

3.4 螺旋数组（牛客版）

4. 链表

4.1 链表中的节点每k个一组翻转（牛客版）

4.2 删除排序链表中的重复元素（牛客版，leetcode 82）

4.3 两个链表相加

4.4 合并k个升序链表（leetcode 23）

4.5 LRU

数学问题

1. 给定一个 0-4随机数生成器 如何生成0-6随机数（leetcode 470）

2. 求平方根

1. 动态规划 / 回溯

动态规划三要素：初始化状态，状态转移方程，边界

对于最长序列系列的问题（公共，上升，回文）的解决方案就是动态规划，采取填表的方式，定义dp[i][j]。

公共对应两个字符串str1和str2，i 和 j 分别对应str1的str2的位置，用于比较。

对于单个字符串dp[i][j]，指的是该字符串中第 i 位到第 j 位的运算。

1.1 最长公共子序列（牛客版, leetcode 1143）

题目：给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

输入： "1A2C3D4B56","B1D23CA45B6A"

输出："123456"

思路：设置二维数组dp[i][j]，其中 i 和 j 表示从str1的第 i 位到str2的第 j 位中的最长公共子序列

  1. import java.util.*;
  2.  
  3. public class Solution {
  4.     /**
  5.      * longest common subsequence
  6.      * @param s1 string字符串 the string
  7.      * @param s2 string字符串 the string
  8.      * @return string字符串
  9.      */
  10.     public String LCS (String s1, String s2) {
  11.         // write code here
  12.         int n1 = s1.length(), n2 = s2.length();
  13.         //默认赋值，[0][?],[?][0]默认两侧皆0,类似公式中0的场景
  14.         int[][] dp = new int[n1 + 1][n2 + 1];
  15.         
  16.         for(int i = 1; i <= n1; i++)
  17.             for(int j = 1; j <= n2; j++){
  18.                 if(s1.charAt(i - 1) == s2.charAt(j - 1)){
  19.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  20.                 }else{
  21.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  22.                 }
  23.             }
  24.         
  25.         //反推结果
  26.         int i = n1, j = n2;
  27.         StringBuffer sb = new StringBuffer();
  28.         while(i > 0 && j > 0){
  29.             //反推公式中不相等的场景
  30.             //根据之前的公式，知道两条字符串的下标都前进一位
  31.             if(s1.charAt(i - 1) == s2.charAt(j - 1)){
  32.                 sb.append(s1.charAt(i - 1));
  33.                 i--;
  34.                 j--;
  35.             }else {
  36.                 //对应公式中不相等的反推场景
  37.                 if(dp[i][j - 1] > dp[i - 1][j]){
  38.                     //找大的那个方向，此处是左边大于上面，则该处的结果是来自左边
  39.                     j--;
  40.                     j--;
  41.                 }else if(dp[i][j - 1] < dp[i - 1][j]){
  42.                     i--;
  43.                 }else if(dp[i][j - 1] == dp[i - 1][j]){
  44.                     j--;
  45.                 }
  46.             }
  47.         }
  48.         
  49.         //由于是从后往前加入字符的，需要反转才能得到正确结果
  50.         return sb.reverse().toString();
  51.     }
  52. }

1.2 最长上升子序列（leetcode 300）

题目：给定数组arr，设长度为n，输出arr的最长上升子序列的长度

输入：[2,1,5,3,6,4,8,9,7]

输出：5

思路：设置并计算dp[i]，i 表示从 0 到 i 中当前最长上升数值的个数

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         if(nums == null || nums.length == 0)
  4.             return 0;
  5.         
  6.         int[] dp = new int[nums.length];
  7.         dp[0] = 1;
  8.         int res = 1;
  9.         for(int i = 1; i < dp.length; i++){
  10.             int maxval = 0;
  11.             for(int j = 0; j < i; j++){
  12.                 if(nums[i] > nums[j]){
  13.                     maxval = Math.max(maxval, dp[j]);
  14.                 }
  15.             }
  16.             dp[i] = maxval + 1;
  17.             res = Math.max(dp[i], res);
  18.         }
  19.  
  20.         return res;
  21.     }
  22. }

1.3 最长回文子串（牛客版，leetcode 5）

题目：给定字符串A以及它的长度n，请返回最长回文子串的长度。

输入："abc1234321ab",12

输出：7

思路：设置二维数组dp[i][j], 表示第 i 个字符到第 j 个字符是否是回文串

  1. import java.util.*;
  2.  
  3. public class Palindrome {
  4.     public int getLongestPalindrome(String A, int n) {
  5.         // write code here
  6.         if(A == null || n <= 0) return 0;
  7.         
  8.         // 第 i 个字符到第 j 个字符是否是回文串
  9.         boolean[][] dp = new boolean[n][n];
  10.         int maxLen = 0;
  11.         
  12.         // 字符串收尾字母长度差 len = j - i
  13.         for(int len = 0; len < n; len++){
  14.             // 字符串起始位置 i
  15.             for(int i = 0; i + len < n; i++){
  16.                 // 字符串终止位置 j
  17.                 int j = i + len;
  18.                 if(len == 0){
  19.                     dp[i][j] = true;
  20.                 }else if(len == 1){
  21.                     dp[i][j] = A.charAt(i) == A.charAt(j);
  22.                 }else{
  23.                     dp[i][j] = (A.charAt(i) == A.charAt(j) && dp[i + 1][j - 1]);
  24.                 }
  25.                 
  26.                 if(dp[i][j] && j - i + 1 > maxLen){
  27.                     maxLen = j - i + 1;
  28.                 }
  29.             }
  30.         }
  31.         
  32.         return maxLen;
  33.     }
  34. }

1.4 接雨水

对于每一列来说，他能存的雨水量是他 左边最高墙和右边最高墙中较低的那堵墙的高度减去自身墙的高度 。所以可以用数组记录每列左右最高墙的高度，然后计算每一列可以存的雨水量。

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int sum = 0;
  4.         int[] max_left = new int[height.length];
  5.         int[] max_right = new int[height.length];
  6.  
  7.         for(int i = 1; i < height.length - 1; i++){
  8.             max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
  9.         }
  10.  
  11.         for(int i = height.length - 2; i >= 0; i--){
  12.             max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
  13.         }
  14.  
  15.         for(int i = 1; i < height.length - 1; i++){
  16.             int min = Math.min(max_left[i], max_right[i]);
  17.             if(min > height[i]){
  18.                 sum += min - height[i];
  19.             }
  20.         }
  21.  
  22.         return sum;
  23.     }
  24. }

1.5 重复数字的所有排列（回溯）

题目：给出一组数字，返回该组数字的所有排列

示例：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].

回溯核心思想：采用递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

1、路径：已经做出的选择

2、选择列表：当前可以做的选择

3、结束条件：到达决策树底层，无法再做选择的条件

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. public class Solution {
  4.     ArrayList<ArrayList<Integer>> res;
  5.     
  6.     public ArrayList<ArrayList<Integer>> permute(int[] num) {
  7.         res = new ArrayList<ArrayList<Integer>>();
  8.         if(num == null || num.length == 0) return res;
  9.         //对数组元素进行从小到大排序
  10.         Arrays.sort(num);
  11.         ArrayList<Integer> list = new ArrayList<Integer>();
  12.         
  13.         solve(list, num);
  14.         return res;
  15.     }
  16.     
  17.     private void solve(ArrayList<Integer> list, int[] num){
  18.         if(list.size() == num.length){
  19.             res.add(new ArrayList<Integer>(list));
  20.             return;
  21.         }
  22.         for(int i = 0; i < num.length; i++){
  23.             if(!list.contains(num[i])){
  24.                 list.add(num[i]);
  25.                 solve(list, num);
  26.                 list.remove(list.size() - 1);
  27.             }
  28.         }
  29.     }
  30. }

1.6 集合的所有子集 （牛客版，leetcode 78）

 

2. 树

2.1 判断一颗二叉树是否为二叉搜索树和完全二叉树

  • 二叉搜索树：每个节点左边节点小于右边节点，左子树的最大值一定小于根节点，小于右子树的最大值；通过中序遍历，严格递增。
  • 完全二叉树：层序遍历，除了最后的一层，每层都是满的。采用层序遍历，一旦出现null，则队列中剩余的节点必须为叶子节点。
  1. import java.util.*;
  2.  
  3. /*
  4.  * public class TreeNode {
  5.  *   int val = 0;
  6.  *   TreeNode left = null;
  7.  *   TreeNode right = null;
  8.  * }
  9.  */
  10.  
  11. public class Solution {
  12.     /**
  13.      * 
  14.      * @param root TreeNode类 the root
  15.      * @return bool布尔型一维数组
  16.      */
  17.     public boolean[] judgeIt (TreeNode root) {
  18.         // write code here
  19.         // 两个情况分别判断：
  20.         // 二叉搜索树：每个节点左边节点小于右边节点，左子树的最大值一定小于根节点，小于右子树的最大值；通过中序遍历，严格递增
  21.         // 完全二叉树：层序遍历，除了最后的一层，每层都是满的
  22.         if(root == null) return new boolean[]{false, false};
  23.         boolean b1 = isBST(root);
  24.         boolean b2 = isCBT(root);
  25.         return new boolean[]{b1, b2};
  26.     }
  27.     
  28.     private boolean isBST(TreeNode root){
  29.         List<Integer> list = new ArrayList<>();
  30.         midSearch(root, list);
  31.         for(int i = 0; i < list.size() - 1; i++){
  32.             if(list.get(i) > list.get(i + 1))
  33.                 return false;
  34.         }
  35.         
  36.         return true;
  37.     }
  38.     
  39.     private void midSearch(TreeNode root, List<Integer> list){
  40.         if(root == null) return;
  41.         midSearch(root.left, list);
  42.         list.add(root.val);
  43.         midSearch(root.right, list);
  44.     }
  45.     
  46.     private boolean isCBT(TreeNode root){
  47.         // 判断一棵树是否为完全二叉树，层序遍历，一旦出现null，则队列中剩余的节点必须为叶子节点
  48.         Queue<TreeNode> queue = new LinkedList<>();
  49.         queue.add(root);
  50.         while(!queue.isEmpty()){
  51.             TreeNode cur = queue.remove();
  52.             if(cur.left == null){
  53.                 if(cur.right != null) return false;
  54.                 while(!queue.isEmpty()){
  55.                     TreeNode node = queue.remove();
  56.                     if(node.left != null ||node.right != null) return false;
  57.                 }
  58.             }else{
  59.                 queue.add(cur.left);
  60.             }
  61.             
  62.             if(cur.right == null){
  63.                 while(!queue.isEmpty()){
  64.                     TreeNode node = queue.remove();
  65.                     if(node.left != null ||node.right != null) return false;
  66.                 }
  67.             }else{
  68.                 queue.add(cur.right);
  69.             }
  70.         }
  71.         
  72.         return true;
  73.     }
  74.  
  75. }

2. 2  二叉树的最近公共祖先（leetcode 236）

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root == null) return null;
  4.         if(root == p || root == q) return root;
  5.         TreeNode left = lowestCommonAncestor(root.left,p,q);
  6.         TreeNode right = lowestCommonAncestor(root.right,p,q);
  7.         if(left == null) return right;
  8.         if(right == null) return left;
  9.         if(right != null && left != null) return root;
  10.         return null;
  11.     }
  12. }

2.3 二叉搜索树的第k小节点（牛客版）

  1. public class Solution {
  2.     TreeNode res;
  3.     int k;
  4.     TreeNode KthNode(TreeNode pRoot, int k)
  5.     {
  6.         if(pRoot == null || k <= 0) return null;
  7.         this.k = k;
  8.         postOrder(pRoot);
  9.         return res;
  10.     }
  11.     
  12.     private void postOrder(TreeNode pRoot){
  13.         if(pRoot == null) return;
  14.         
  15.         postOrder(pRoot.left);
  16.         if(k == 0) return;
  17.         if(--k == 0) res = pRoot;
  18.         postOrder(pRoot.right);
  19.     }
  20.  
  21. }

 2.4 二叉搜索树与双向链表（牛客版）

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

  1. public class Solution
  2. {
  3.     public TreeNode Convert(TreeNode root)
  4.     {
  5.          
  6.         if(root==null)return null;
  7.         if(root.left==null&&root.right==null)return root;
  8.         TreeNode left=Convert(root.left);
  9.         TreeNode p=left;
  10.         while(p!=null&&p.right!=null)
  11.         {
  12.             p=p.right;
  13.         }
  14.         if(left!=null)
  15.         {
  16.          p.right=root;
  17.           root.left=p;
  18.         }
  19.        TreeNode right=Convert(root.right);
  20.         if(right!=null)
  21.          {
  22.             root.right=right;
  23.             right.left=root;
  24.         }
  25.          
  26.       return  left!=null?left:root; 
  27.     }
  28. }

2.5 重建二叉树（剑指offer，leetcode版）

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

  1. class Solution {
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.         if (preorder == null || preorder.length == 0) {
  4.             return null;
  5.         }
  6.         Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
  7.         int length = preorder.length;
  8.         for (int i = 0; i < length; i++) {
  9.             indexMap.put(inorder[i], i);
  10.         }
  11.         TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
  12.         return root;
  13.     }
  14.  
  15.     public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
  16.         if (preorderStart > preorderEnd) {
  17.             return null;
  18.         }
  19.         int rootVal = preorder[preorderStart];
  20.         TreeNode root = new TreeNode(rootVal);
  21.         if (preorderStart == preorderEnd) {
  22.             return root;
  23.         } else {
  24.             int rootIndex = indexMap.get(rootVal);
  25.             int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
  26.             TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
  27.             TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
  28.             root.left = leftSubtree;
  29.             root.right = rightSubtree;
  30.             return root;
  31.         }
  32.     }
  33. }

3. 数组

3.1 数组中的最长连续子序列（牛客版）

题：给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

例：输入：[100,4,200,1,3,2]     输出：4

  • 方法一：排序，然后再遍历一遍找最长连续递增数列，时间复杂度O(NlogN)
  • 方法二：使用HashMap或者HashSet，将数组元素存入set中，然后遍历set，先找到每个序列的开头元素
  1. import java.util.*;
  2.  
  3. public class Solution {
  4.     public int MLS (int[] arr) {
  5.         // write code here
  6.         if(arr == null || arr.length == 0) return 0;
  7.         HashSet<Integer> set = new HashSet<>();
  8.         int maxLen = 0;
  9.         
  10.         for(int value : arr){
  11.             set.add(value);
  12.         }
  13.         
  14.         for(int num : set){
  15.             if(!set.contains(num - 1)){
  16.                 int currentNum = num;
  17.                 int currentLen = 1;
  18.                 while(set.contains(currentNum + 1)){
  19.                     currentNum += 1;
  20.                     currentLen++;
  21.                 }
  22.                 
  23.                 maxLen = Math.max(maxLen, currentLen);
  24.             }
  25.         }
  26.         
  27.         return maxLen;
  28.     }
  29. }

3.2 寻找第k大的数（牛客版）

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数

输入：[1,3,5,2,2],5,3

输出：2

思路：快速排序 + 递归（注意第 k 大是从后往前数，第 k 小是从小往大）

  1. import java.util.*;
  2.  
  3. public class Finder {
  4.     public int findKth(int[] a, int n, int K) {
  5.         // write code here
  6.         return findK(a, 0, n - 1, K);
  7.     }
  8.     
  9.     private int findK(int[] arr, int left, int right, int k){
  10.         if(left <= right){
  11.             int temp = quickSort(arr, left, right);
  12.             
  13.             if(temp == arr.length - k){
  14.                 return arr[temp];
  15.             }else if(temp > arr.length - k){
  16.                 return findK(arr, left, temp - 1, k);
  17.             }else{
  18.                 return findK(arr, temp + 1, right, k);
  19.             }
  20.         }
  21.  
  22.         return -1;
  23.     }
  24.     
  25.     private int quickSort(int[] a, int left, int right){
  26.         int key = a[left];
  27.         while(left < right){
  28.             while(left < right && a[right] >= key){
  29.                 right--;
  30.             }
  31.             
  32.             a[left] = a[right];
  33.             
  34.             while(left < right && a[left] <= key){
  35.                 left++;
  36.             }
  37.             
  38.             a[right] = a[left];
  39.         }
  40.         
  41.         a[left] = key;
  42.         
  43.         return left;
  44.     }
  45. }

3.3 旋转数组的最小数字

题目：输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例子：数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。建议使用O(logn)时间复杂度

思想：二分查找的变种，注意旋转后的边界

  1. import java.util.ArrayList;
  2. public class Solution {
  3.     public int minNumberInRotateArray(int [] array) {
  4.         if(array.length == 0 || array == null)
  5.             return 0;
  6.         
  7.         int left = 0;
  8.         int right = array.length - 1;
  9.         int mid = left;
  10.         
  11.         while(array[left] >= array[right]){
  12.             // 二分查找的边界
  13.             if(right - left == 1){
  14.                 mid = right;
  15.                 break;
  16.             }
  17.             
  18.             mid = (left + right) / 2;
  19.             if(array[mid] >= array[left])
  20.                 left = mid;
  21.             else if(array[mid] <= array[right])
  22.                 right = mid;
  23.         }
  24.         
  25.         return array[mid];
  26.     }
  27. }

3.4 螺旋数组（牛客版）

题目：给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

例如：

  1. [
  2.     [ 1, 2, 3 ],
  3.     [ 4, 5, 6 ],
  4.     [ 7, 8, 9 ]
  5. ]

返回：[1,2,3,6,9,8,7,4,5]

  1. import java.util.ArrayList;
  2. public class Solution {
  3.     public ArrayList<Integer> spiralOrder(int[][] matrix) {
  4.         ArrayList<Integer> res = new ArrayList<Integer>();
  5.         
  6.         if(matrix.length == 0) return res;
  7.         
  8.         int rowBegin = 0;
  9.         int rowEnd = matrix.length - 1;
  10.         int colBegin = 0;
  11.         int colEnd = matrix[0].length - 1;
  12.         
  13.         while(rowBegin <= rowEnd && colBegin <= colEnd){
  14.             for(int j = colBegin; j <= colEnd; j++){
  15.                 res.add(matrix[rowBegin][j]);
  16.             }
  17.             
  18.             rowBegin++;
  19.             for(int i = rowBegin; i <= rowEnd; i++){
  20.                 res.add(matrix[i][colEnd]);
  21.             }
  22.             
  23.             colEnd--;
  24.             
  25.             if(rowBegin <= rowEnd){
  26.                 for(int j = colEnd; j >= colBegin; j--){
  27.                     res.add(matrix[rowEnd][j]);
  28.                 }
  29.             }
  30.             
  31.             rowEnd--;
  32.             
  33.             if(colBegin <= colEnd){
  34.                 for(int i = rowEnd; i >= rowBegin; i--){
  35.                     res.add(matrix[i][colBegin]);
  36.                 }
  37.             }
  38.             colBegin++;
  39.         }
  40.         return res;
  41.     }
  42. }

3.5 字符串最长无重复子串（牛客版，leetcode 48）

题目：给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

解法：使用hashmap来保存重复字符的位置。

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     public int maxLength (int[] arr) {
  6.         // write code here
  7.         HashMap<Integer, Integer> map = new HashMap<>();
  8.         int max = 1;
  9.         for(int start = 0, end = 0; end < arr.length; end++){
  10.             if(map.containsKey(arr[end])){
  11.                 start = Math.max(start, map.get(arr[end]) + 1);
  12.             }
  13.             max = Math.max(max, end - start + 1);
  14.             map.put(arr[end], end);
  15.         }
  16.         
  17.         return max;
  18.     }
  19. }

4. 链表

4.1 链表中的节点每k个一组翻转（牛客版）

  1. public class Solution {
  2.     /**
  3.      * 
  4.      * @param head ListNode类 
  5.      * @param k int整型 
  6.      * @return ListNode类
  7.      */
  8.     public ListNode reverseKGroup (ListNode head, int k) {
  9.         // write code here
  10.         
  11.         if(head == null || head.next == null || k < 2)
  12.             return head;
  13.         
  14.         ListNode res = new ListNode(-1);
  15.         res.next = head;
  16.         ListNode pre = res;
  17.         ListNode end = res;
  18.         
  19.         while(end != null){
  20.             for(int i = 0; i < k && end != null; i++){
  21.                 end = end.next;
  22.             }
  23.             
  24.             if(end == null) break;
  25.             
  26.             ListNode start = pre.next;
  27.             ListNode next = end.next;
  28.             end.next = null;
  29.             pre.next = reverseList(start);
  30.             start.next = next;
  31.             pre = start;
  32.             end = pre;
  33.         }
  34.         
  35.         return res.next;
  36.     }
  37.     
  38.     private ListNode reverseList(ListNode head){
  39.         ListNode preNode = null, pNode = head;
  40.         while(pNode != null){
  41.             ListNode pNext = pNode.next;
  42.             pNode.next = preNode;
  43.             preNode = pNode;
  44.             pNode = pNext;
  45.         }
  46.         
  47.         return preNode;
  48.     }
  49. }

4.2 删除排序链表中的重复元素（牛客版，leetcode 82）

题目：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

给出的链表为1→2→3→3→4→4→5, 返回 1→2→5.
给出的链表为1→1→1→2→3, 返回 2→3.

  1. import java.util.*;
  2.  
  3. public class Solution {
  4.     public ListNode deleteDuplicates (ListNode head) {
  5.         // write code here
  6.         if(head == null || head.next == null)
  7.             return head;
  8.         
  9.         ListNode res = new ListNode(-1);
  10.         res.next = head;
  11.         ListNode preNode = res;
  12.         ListNode pNode = head;
  13.         
  14.         while(pNode != null && pNode.next != null){
  15.             if(preNode.next.val != pNode.next.val){
  16.                 preNode = preNode.next;
  17.                 pNode = pNode.next;
  18.             }else{
  19.                 while(pNode != null && pNode.next != null && preNode.next.val == pNode.next.val){
  20.                     pNode = pNode.next;
  21.                 }
  22.                 
  23.                 preNode.next = pNode.next;
  24.                 pNode = pNode.next;
  25.             }
  26.         }
  27.         
  28.         return res.next;
  29.         
  30.     }
  31. }

4.3 两个链表相加

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

思路：先反转，再相加，注意进位以及最后一次相加（String类型的大数加法思路一致）

  1. import java.util.*;
  2.  
  3.  
  4. public class Solution {
  5.     public ListNode addInList (ListNode head1, ListNode head2) {
  6.         // write code here
  7.         if(head1 == null) return head2;
  8.         if(head2 == null) return head1;
  9.         
  10.         ListNode l1 = reverseList(head1);
  11.         ListNode l2 = reverseList(head2);
  12.         int carry = 0;
  13.         ListNode res = new ListNode(-1);
  14.         ListNode curNode = res;
  15.         
  16.         while(l1 != null || l2 != null){
  17.             int num1 = l1 == null ? 0 : l1.val;
  18.             int num2 = l2 == null ? 0 : l2.val;
  19.             
  20.             int val = (num1 + num2 + carry) % 10;
  21.             carry = (num1 + num2 + carry) / 10;
  22.             
  23.             curNode.next = new ListNode(val);
  24.             if(l1 != null) 
  25.                 l1 = l1.next;
  26.             if(l2 != null)
  27.                 l2 = l2.next;
  28.             
  29.             curNode = curNode.next;
  30.         }
  31.         
  32.         return reverseList(res.next);
  33.     }
  34.     
  35.     public ListNode reverseList(ListNode head){
  36.         ListNode preNode = null;
  37.         ListNode curNode = head;
  38.         
  39.         while(curNode != null){
  40.             ListNode nextNode = curNode.next;
  41.             curNode.next = preNode;
  42.             preNode = curNode;
  43.             curNode = nextNode;
  44.         }
  45.         
  46.         return preNode;
  47.     }
  48. }

4.4 合并k个升序链表（leetcode 23）

题目：合并 k 个已排序的链表并将其作为一个已排序的链表返回。

思路：归并排序法 + 两个链表合并法

  1. class Solution {
  2.     public ListNode mergeKLists(ListNode[] lists) {
  3.         if(lists == null || lists.length == 0) return null;
  4.  
  5.         return merge(lists, 0, lists.length - 1);
  6.     }
  7.  
  8.     private ListNode merge(ListNode[] lists, int left, int right){
  9.         if(left == right) return lists[left];
  10.  
  11.         int mid = left + (right - left) / 2;
  12.         ListNode l1 = merge(lists, left, mid);
  13.         ListNode l2 = merge(lists, mid + 1, right);
  14.         return mergeTwoLists(l1, l2);
  15.     }
  16.  
  17.     private ListNode mergeTwoLists(ListNode l1, ListNode l2){
  18.         ListNode res = new ListNode(-1);
  19.         ListNode pNode = res;
  20.  
  21.         while(l1 != null && l2 != null){
  22.             if(l1.val <= l2.val){
  23.                 pNode.next = l1;
  24.                 l1 = l1.next;
  25.             }else{
  26.                 pNode.next = l2;
  27.                 l2 = l2.next;
  28.             }
  29.             pNode = pNode.next;
  30.         }
  31.  
  32.         pNode.next = l1 == null ? l2 : l1;
  33.         return res.next;
  34.     }
  35. }

4.5 LRU

  1. class LRUCache {
  2.     class Node {
  3.         public int key, val;
  4.         public Node prev, next;
  5.         public Node(int key, int val){
  6.             this.key = key;
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     class DoubleList{
  12.         private Node head, tail;
  13.         private int size;
  14.  
  15.         public DoubleList(){
  16.             head = new Node(0, 0);
  17.             tail = new Node(0, 0);
  18.             head.next = tail;
  19.             tail.prev = head;
  20.             size = 0;
  21.         }
  22.  
  23.         public void addFirst(Node x){
  24.             x.next = head.next;
  25.             x.prev = head;
  26.             head.next.prev = x;
  27.             head.next = x;
  28.             size++;
  29.         }
  30.  
  31.         public void remove(Node x){
  32.             x.prev.next = x.next;
  33.             x.next.prev = x.prev;
  34.             size--;
  35.         }
  36.  
  37.         public Node removeLast(){
  38.             if(tail.prev == head){
  39.                 return null;
  40.             }
  41.             Node last = tail.prev;
  42.             remove(last);
  43.             return last;
  44.         }
  45.  
  46.         public int size(){
  47.             return this.size;
  48.         }
  49.  
  50.     }
  51.  
  52.     public HashMap<Integer, Node> map;
  53.     private DoubleList cache;
  54.     private int cap;
  55.     
  56.     public LRUCache(int capacity) {
  57.         map = new HashMap<>();
  58.         cache = new DoubleList();
  59.         this.cap = capacity;
  60.     }
  61.     
  62.     public int get(int key) {
  63.         if(!map.containsKey(key)){
  64.             return -1;
  65.         }
  66.  
  67.         int val = map.get(key).val;
  68.         put(key, val);
  69.  
  70.         return val;
  71.     }
  72.     
  73.     public void put(int key, int value) {
  74.         Node x = new Node(key, value);
  75.  
  76.         if(map.containsKey(key)){
  77.             cache.remove(map.get(key));
  78.             cache.addFirst(x);
  79.             map.put(key, x);
  80.         }else{
  81.             if(cache.size == cap){
  82.                 Node last = cache.removeLast();
  83.                 map.remove(last.key);
  84.             }
  85.  
  86.             cache.addFirst(x);
  87.             map.put(key, x);
  88.         }
  89.     }
  90. }

 

数学问题

1. 给定一个 0-4随机数生成器 如何生成0-6随机数（leetcode 470）

定理：已知 rand_N() 可以等概率的生成[1, N]范围的随机数。那么：

(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数，即实现了 rand_XY()

例：(rand9() - 1) × 7 + rand7() = rand63();

  1. class Solution extends SolBase {
  2.     public int rand10() {
  3.         while(true) {
  4.             int a = rand7();
  5.             int b = rand7();
  6.             int num = (a-1)*7 + b; // rand 49
  7.             if(num <= 40) return num % 10 + 1; // 拒绝采样
  8.             
  9.             a = num - 40; // rand 9
  10.             b = rand7();
  11.             num = (a-1)*7 + b; // rand 63
  12.             if(num <= 60) return num % 10 + 1;
  13.             
  14.             a = num - 60; // rand 3
  15.             b = rand7();
  16.             num = (a-1)*7 + b; // rand 21
  17.             if(num <= 20) return num % 10 + 1;
  18.         }
  19.     }
  20. }

2. 求平方根

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/876227
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号