leetcode必刷100道题 （三），46 全排列、49 字母异位词分组、53 最大子序和、55 跳跃游戏、56 合并区间、62 不同路径、64 最小路径和、72 编辑距离70 爬楼梯、

46 全排列 flag [ ]、index == nums.length48 旋转图像 （未完成）49 字母异位词分组，53 最大子序和，dp想法，curNum变量替换，maxNum比对55 跳跃游戏 n=1;从后往前遍历数组，如果遇到的元素可以到达最后一行，则截断后边的元素。56 合并区间 自定义第一个数字排序，for循环，加入list62 不同路径 ，dp[j] +=dp[j-1]64 最小路径和 二维 ，一维 ：1.i是边界 j是1. i是边界 j是 2. i不是 j是 3. i是 j不是 4. i不是 j不70 爬楼梯，p1、p2 指针 10.72 编辑距离 先处理边界，若字母相等,dp[i][j] = dp[i-1][j-1]; 否则，三者取最小 +1；

lee46 全排列

7.3 重新写的

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); boolean[] flag = new boolean[nums.length]; helper(nums, res, 0, new ArrayList<>(), flag); return res; } private static void helper(int[] nums, List<List<Integer>> res, int index, ArrayList<Integer> list, boolean[] flag) { if (index == nums.length) { res.add(new ArrayList<>(list)); return; } for (int i = 0; i < nums.length; i++) { if (flag[i] == false) { flag[i] = true; list.add(nums[i]); helper(nums, res, index + 1, list, flag); list.remove(list.size() - 1); flag[i] = false; } } } }

lee49 字母异位词分组

class Solution { public List<List<String>> groupAnagrams(String[] strs) { if(strs==null || strs.length==0) return new ArrayList(); Map<String,List> map = new HashMap<>(); for(String s :strs){ char[] cur = s.toCharArray(); Arrays.sort(cur); String key = String.valueOf(cur); if(! map.containsKey(key)){ map.put(key,new ArrayList()); } map.get(key).add(s); } return new ArrayList(map.values()); } }

在美版leetcode上看到大神的思路，用质数表示26个字母，把字符串的各个字母相乘，这样可保证字母异位词的乘积必定是相等的。其余步骤就是用map存储，和别人的一致了。（这个用质数表示真的很骚啊！！!）

lee53 最大自序和

这道题，一看子序列和，想动态规划，dp【】，这个考虑的就是dp[ i ] = Math.max(dp[i-1]+nums[i],nums[i]),然后因为dp[n] 存的不一定就是最长区间，因为最长区间可能在中间，所以需要一个max每次对比一下，还有dp其实只存了前一个值，所以替换成一个变量就可。

class Solution { public static int maxSubArray(int[] nums) { if(nums == null || nums.length==0) return 0; int maxNum = nums[0]; int curmax = 0; for(int i=0;i<nums.length;i++){ curmax = Math.max(curmax+nums[i],nums[i]); maxNum = Math.max(maxNum,curmax); } return maxNum; } }

lee55 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2:

输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

solution

从后往前遍历数组，如果遇到的元素可以到达最后一行，则截断后边的元素。否则继续往前，弱最后剩下的元素大于1个，则可以判断为假。否则就是真，时间复杂度O(n)就可以，不知道有没有大佬可以继续优化。

class Solution { public boolean canJump(int[] nums) { if(nums==null || nums.length == 0) return false; int n = 1; for(int i = nums.length-2;i>=0;i--){ if(nums[i] >= n){ n=1; } else{ n++; } if(i==0 && n>1){ return false; } } return true; } }

lee56 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

for (int i = 0; i < res.length; i++) { System.out.println(Arrays.toString(res[i])); }

自定义排序：

Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return a[0] - b[0]; } });

list转int【】【】 你你

return list.toArray(new int[list.size()][]); public class merge56 { public static void main(String[] args) { int[][] nums = {{1, 3}, {2, 6}, {8, 10}, {15, 18}}; int[][] res = merge(nums); for (int i = 0; i < res.length; i++) { System.out.println(Arrays.toString(res[i])); } } public static int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0 || intervals[0].length==0) return new int[0][0]; Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return a[0] - b[0]; } }); List<int[]> list = new ArrayList<>(); list.add(intervals[0]); for (int i = 1; i < intervals.length; i++) { int[] curNum = intervals[i]; int[] peek = list.get(list.size() - 1); if (curNum[0] > peek[1]) { list.add(curNum); } else { peek[1] = Math.max(peek[1], curNum[1]); } } return list.toArray(new int[list.size()][]); } }

lee62 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？

7.4 自己写的

class Solution { public int uniquePaths(int m, int n) { if(m<=0 || n<=0) return 0; int[][] dp=new int[m][n]; for(int i=0;i<n;i++) dp[0][i]=1; for(int i=0;i<m;i++) dp[i][0]=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]; } }

**一维数组dp【】 **想法：

class Solution { public int uniquePaths(int m, int n) { if(m<=0 || n<=0) return 0; int[] dp=new int[n]; Arrays.fill(dp, 1); for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[j]+=dp[j-1]; } } return dp[n-1]; } }

如果有障碍呢？lee63 如果碰到1就dp[ ]=0;

lee64 最小路径和

分为四种情况 ：

7.4

public class minPathSum64 { public static void main(String[] args) { int[][] grid = { {1,3,1}, {1,5,1}, {4,2,1} }; int res = minPathSum(grid); System.out.println(res); } public static int minPathSum(int[][] grid) { int m = grid.length,n=grid[0].length; if(grid==null || m==0 || n==0) return 0; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for(int i=1;i<m;i++){ dp[i][0]=grid[i][0]+dp[i-1][0]; } for(int i=1;i<n;i++){ dp[0][i]=grid[0][i]+dp[0][i-1]; } 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]; } }

同理 一维数组

class Solution { public int minPathSum(int[][] grid) { if(grid.length==0|| grid==null) return 0; int[] dp=new int[grid[0].length]; for(int i=grid.length-1;i>=0;i--){ for(int j=grid[0].length-1; j>=0; j--){ if( j != grid[0].length-1 && i!=grid.length-1){ dp[j]= Math.min( dp[j], dp[j+1] ) + grid[i][j]; } else if(i==grid.length-1 && j!=grid[0].length-1){ dp[j]=grid[i][j]+dp[j+1]; } else if(i!=grid.length-1 && j==grid[0].length-1){ dp[j]=grid[i][j]+dp[j]; } else dp[j]=grid[i][j]; } } return dp[0]; } }

lee70 爬楼梯

class Solution { public int climbStairs(int n) { if(n<=0) return 0; if(n == 1) return 1; if(n == 2) return 2; int p1 = 1,p2 = 2; int p3=0; for(int i=3;i<=n;i++){ p3 = p1+p2; p1=p2; p2=p3; } return p3; } }

lee72 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

示例 1： 输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’) 示例 2： 7.4

public class minDistance72 { public static void main(String[] args) { String word1 = "horse", word2 = "ros"; int res = minDistance(word1, word2); System.out.println(res); } public static int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); if (m == 0) return n; if (n == 0) return m; int[][] dp = new int[m+1][n+1]; // 先收拾边界 for(int i=0;i<=m;i++){// 注意这里要有=m dp[i][0] = i; } for(int i = 0;i<=n;i++){ dp[0][i] = i; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(word1.charAt(i-1) == word2.charAt(j-1)){// 注意这里是i-1 dp[i][j] = dp[i-1][j-1]; } // 别忘最后+1 else dp[i][j] = minhelper(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])+1; } } return dp[m][n]; } private static int minhelper(int i, int i1, int i2) { return Math.min(i,Math.min(i1,i2)); } }