62. 不同路径package hot100; public class lc62 { /*62. 不同路径 已解答 中等 相关标签 premium lock icon 相关企业 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径*/ public int uniquePaths(int m, int n) { int[][] dp new int[m][n]; dp[0][0] 1; for(int i 1; i m; i){ dp[i][0] 1; } for(int i 1; i n; i){ dp[0][i] 1; } for(int i 1 ; i m; i){ for(int j 1; j n; j){ dp[i][j] dp[i-1][j] dp[i][j-1]; } } return dp[m-1][n-1]; } public static void main(String[] args) { lc62 solution new lc62(); System.out.println(solution.uniquePaths(3,7)); } }最小路径和package hot100; public class lc64 { /*最小路径和 已解答 中等 相关标签 premium lock icon 相关企业 给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明每次只能向下或者向右移动一步。*/ public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[m][n]; dp[0][0] grid[0][0]; for(int i 1; i m; i){ dp[i][0] dp[i-1][0] grid[i][0]; } for(int i 1; i n; i){ dp[0][i] dp[0][i-1] grid[0][i]; } for(int i 1; i m; i){ for(int j 1; j n; j){ dp[i][j] Math.min(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } return dp[m-1][n-1]; } public static void main(String[] args) { lc64 solution new lc64(); // 测试用例13x3 矩阵预期结果 7 int[][] grid1 { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; System.out.println(最小路径和 (grid1) solution.minPathSum(grid1)); // 输出 7 // 测试用例21x1 矩阵预期结果 2 int[][] grid2 {{2}}; System.out.println(最小路径和 (grid2) solution.minPathSum(grid2)); // 输出 2 // 测试用例32x3 矩阵 int[][] grid3 { {1, 2, 3}, {4, 5, 6} }; System.out.println(最小路径和 (grid3) solution.minPathSum(grid3)); // 输出 12 (路径 1-2-3-6) } }最长回文子串package hot100; public class lc5 { /*5. 最长回文子串 已解答 中等 相关标签 premium lock icon 相关企业 提示 给你一个字符串 s找到 s 中最长的 回文 子串。 示例 1 输入s babad 输出bab 解释aba 同样是符合题意的答案。 示例 2 输入s cbbd 输出bb*/ public String longestPalindrome(String s) { if (s null || s.length() 0) return ; //动态规划 int n s.length(); boolean[][] dp new boolean[n][n]; int max 1; int start 0; for(int i 0; i n; i){ dp[i][i] true; max 1; start i; } for(int i 1; i n; i){ if(s.charAt(i-1) s.charAt(i)){ dp[i-1][i] true; max 2; //应该是i-1; start i-1; } } for(int len 3; len s.length(); len){ for(int i 0; ilen-1 s.length(); i ){ int j ilen-1; if(dp[i1][j-1] s.charAt(i) s.charAt(j)){ dp[i][j] true; if(len max){ max len; start i; } } } } return s.substring(start,startmax); } public static void main(String[] args) { lc5 solution new lc5(); System.out.println(solution.longestPalindrome(babad)); } }最长公共子序列package hot100; public class lc1143 { /*1143. 最长公共子序列 已解答 中等 相关标签 premium lock icon 相关企业 提示 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。 一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。 例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1 输入text1 abcde, text2 ace 输出3 解释最长公共子序列是 ace 它的长度为 3 。*/ public int longestCommonSubsequence(String text1, String text2) { int m text1.length(); int n text2.length(); //是一种技巧 int[][] dp new int[m1][n1]; for(int i 1; i m; i){ for(int j 1; j n; j){ if(text1.charAt(i-1) text2.charAt(j-1)){ dp[i][j] dp[i-1][j-1] 1; }else{ dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; } public static void main(String[] args) { lc1143 solution new lc1143(); System.out.println(solution.longestCommonSubsequence(abcde,ace)); } }编辑距离package hot100; public class lc72 { /*72. 编辑距离 已解答 中等 相关标签 premium lock icon 相关企业 给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符 删除一个字符 替换一个字符 示例 1 输入word1 horse, word2 ros 输出3 解释 horse - rorse (将 h 替换为 r) rorse - rose (删除 r) rose - ros (删除 e)*/ public int minDistance(String word1, String word2) { int n word1.length(); int m word2.length(); int[][] dp new int[n1][m1]; for(int i 0; i n; i){ dp[i][0] i; } for(int j 0; j m; j){ dp[0][j] j; } for(int i 1; i n; i){ for(int j 1; j m; j){ if(word1.charAt(i-1) word2.charAt(j-1)){ dp[i][j] dp[i-1][j-1]; }else{ dp[i][j] Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) 1; } } } return dp[n][m]; } public static void main(String[] args) { lc72 solution new lc72(); System.out.println(solution.minDistance(horse,ros)); } }只出现一次的数字package hot100; public class lc136 { /*136. 只出现一次的数字 已解答 简单 相关标签 premium lock icon 相关企业 提示 给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间*/ public int singleNumber(int[] nums) { int ans 0; for(int num : nums){ ans ^ num; } return ans; } public static void main(String[] args) { lc136 solution new lc136(); System.out.println(solution.singleNumber(new int[]{2,2,1})); } }多数元素package hot100; public class lc169 { /*169. 多数元素 已解答 简单 相关标签 premium lock icon 相关企业 给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的并且给定的数组总是存在多数元素。 示例 1 输入nums [3,2,3] 输出3 示例 2 输入nums [2,2,1,1,1,2,2] 输出2*/ public int majorityElement(int[] nums) { //选举计数 int count 1; int houxuanz nums[0]; for(int i 1; i nums.length; i){ if(count 0){ houxuanz nums[i]; } count (nums[i] houxuanz)? 1 : -1; } return houxuanz; } public static void main(String[] args) { lc169 soulution new lc169(); System.out.println(soulution.majorityElement(new int[]{3,2,3})); } }颜色分类package hot100; import java.util.Arrays; public class lc75 { /*75. 颜色分类 已解答 中等 相关标签 premium lock icon 相关企业 提示 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地 对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例 1 输入nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2] 示例 2 输入nums [2,0,1] 输出[0,1,2] */ public void sortColors(int[] nums) { //2, 1, 0,三轮 int p1 0; int p0 0; for(int i 0; i nums.length; i){ int temp nums[i]; nums[i] 2; if(temp 1){ nums[p1] 1; p1; } if(temp 0){ nums[p0] 0; p0; } } } public static void main(String[] args) { lc75 solution new lc75(); // 测试用例 1 int[] nums1 {2, 0, 2, 1, 1, 0}; solution.sortColors(nums1); System.out.println(排序后: Arrays.toString(nums1)); // 输出 [0, 0, 1, 1, 2, 2] // 测试用例 2 int[] nums2 {2, 0, 1}; solution.sortColors(nums2); System.out.println(排序后: Arrays.toString(nums2)); // 输出 [0, 1, 2] // 测试用例 3所有元素相同 int[] nums3 {1, 1, 1}; solution.sortColors(nums3); System.out.println(排序后: Arrays.toString(nums3)); // 输出 [1, 1, 1] } }下一个排列package hot100; import java.util.Arrays; public class lc31 { /*31. 下一个排列 已解答 中等 相关标签 premium lock icon 相关企业 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。 例如arr [1,2,3] 的下一个排列是 [1,3,2] 。 类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums 找出 nums 的下一个排列。 必须 原地 修改只允许使用额外常数空间。 示例 1 输入nums [1,2,3] 输出[1,3,2] 示例 2*/ public void nextPermutation(int[] nums) { int n nums.length; //i前面的数字都不能再改变了 int i n-2; while(i 0 nums[i] nums[i1]){ i--; } if(i 0){ //在i的右边找 int j n-1; while(nums[j] nums[i]){ j--; } swap(nums,i,j); } reverse(nums,i1, n-1); } private void swap(int[] nums, int i, int j){ int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void reverse(int[] nums, int left, int right){ while(left right){ swap(nums, left, right--); } } public static void main(String[] args) { lc31 solution new lc31(); // 测试用例 1输入 [1,2,3] - 预期 [1,3,2] int[] nums1 {1, 2, 3}; solution.nextPermutation(nums1); System.out.println(下一个排列 (1,2,3) - Arrays.toString(nums1)); // 测试用例 2输入 [3,2,1] - 预期 [1,2,3] 降序下一个为最小排列 int[] nums2 {3, 2, 1}; solution.nextPermutation(nums2); System.out.println(下一个排列 (3,2,1) - Arrays.toString(nums2)); // 测试用例 3输入 [1,1,5] - 预期 [1,5,1] int[] nums3 {1, 1, 5}; solution.nextPermutation(nums3); System.out.println(下一个排列 (1,1,5) - Arrays.toString(nums3)); // 测试用例 4输入 [1,3,2] - 预期 [2,1,3] int[] nums4 {1, 3, 2}; solution.nextPermutation(nums4); System.out.println(下一个排列 (1,3,2) - Arrays.toString(nums4)); } }寻找重复数package hot100; public class lc287 { /*287. 寻找重复数 已解答 中等 相关标签 premium lock icon 相关企业 给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 示例 1 输入nums [1,3,4,2,2] 输出2 示例 2 输入nums [3,1,3,4,2] 输出3 示例 3 : 输入nums [3,3,3,3,3] 输出3*/ public int findDuplicate(int[] nums) { int fast 0; int slow 0; while(true){ slow nums[slow]; fast nums[nums[fast]]; if(fast slow){ break; } } int head 0; while(slow ! head){ slow nums[slow]; head nums[head]; } return slow; } public static void main(String[] args) { lc287 solution new lc287(); // 测试用例 1 int[] nums1 {1, 3, 4, 2, 2}; System.out.println(重复数字 (nums1) solution.findDuplicate(nums1)); // 预期 2 // 测试用例 2 int[] nums2 {3, 1, 3, 4, 2}; System.out.println(重复数字 (nums2) solution.findDuplicate(nums2)); // 预期 3 // 测试用例 3 int[] nums3 {3, 3, 3, 3, 3}; System.out.println(重复数字 (nums3) solution.findDuplicate(nums3)); // 预期 3 // 额外测试n1 时数组为 [1,1] int[] nums4 {1, 1}; System.out.println(重复数字 (nums4) solution.findDuplicate(nums4)); // 预期 1 } }碎碎念后续会更新每天学习的八股和算法题开始准备秋招的第78/79/80天。努力连续更新100天以后每天就按秋招项目【java agent】科研必做项目算法八股锻炼身体来总结。总结加油吧1.hot100 【acm 】 100/100 完结撒花2.秋招项目【java 项目】继续【agent 项目 】继续3.科研。确定方向就搞就可以了4.实习6.背八股无7.锻炼身体无要点:接下来20天重点就是项目拷打和算法题容易错的题整理然后就开始投递简历准备秋招了希望一切顺利