leetcode刷题(46-50)

算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写题吧。

遇事不决，可问春风，春风不语，即是本心。

我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

目录

1.全排列

2.全排列II

3.旋转图像

4.字母异位词分组

5.Pow(x,n)

---

1.全排列

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/permutations/description/

思路：该题的数组默认没有重复的，所以不需要考虑数字重复的问题。

方法1:标记回溯法，使用vis数组标记元素是否访问过，使用数字k标记访问了多少个元素，vis数组避免重复访问同一个元素，当访问的元素k等于数组的长度，则存入结果集合。

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>() ;List<Integer> tmp = new ArrayList<>() ;boolean [] vis = new boolean[nums.length] ;dfs(nums, 0, res, tmp, vis) ;return res ;}public void dfs(int [] nums, int k, List<List<Integer>> res, List<Integer> tmp, boolean [] vis){if(k == nums.length){res.add(new ArrayList<>(tmp)) ;}for(int i=0; i<nums.length; i++){if(vis[i]){continue ;}vis[i] = true ;tmp.add(nums[i]) ;//k标记有几个元素dfs(nums, k+1, res, tmp, vis) ;tmp.remove(k) ;vis[i] = false ;}}
}

方法2：交换法，每次全排列之前需要先交换元素，然后再进行全排列，全排列完成之后交换回来。

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>() ;List<Integer> tmp = new ArrayList<>() ;boolean [] vis = new boolean[nums.length] ;dfs(nums, 0, res, tmp) ;return res ;}public void dfs(int [] nums, int k, List<List<Integer>> res, List<Integer> tmp){if(k == nums.length){for(int i=0; i<nums.length; i++){tmp.add(nums[i]) ;}res.add(new ArrayList<>(tmp)) ;tmp.clear() ;}for(int i=k; i<nums.length; i++){swap(nums, i, k) ;dfs(nums, k+1, res, tmp) ;swap(nums,i,k) ;}}public void swap(int [] nums, int x, int y){int tmp = nums[x] ;nums[x] = nums[y] ;nums[y] = tmp ;}
}

2.全排列II

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/permutations-ii/description/

思路：因为含有重复元素，首先需要对数组元素按照升序排序，然后使用标记回溯法，进行标记，除了访问过的元素不访问，也要避免元素的重复访问。

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> res = new ArrayList<>() ;List<Integer> tmp = new ArrayList<>() ;boolean [] vis = new boolean [nums.length] ;Arrays.sort(nums) ;dfs(nums,0,res,tmp,vis) ;return res ;}public void dfs(int [] nums, int k, List<List<Integer>> res, List<Integer> tmp, boolean [] vis){if(k == nums.length){res.add(new ArrayList<>(tmp)) ;}for(int i=0; i<nums.length; i++){if(vis[i] || (i>0 && vis[i-1] && nums[i-1]==nums[i])){continue ;}vis[i] = true ;tmp.add(nums[i]) ;dfs(nums, k+1, res, tmp, vis) ;tmp.remove(k) ;vis[i] = false ;}}
}

3.旋转图像

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/rotate-image/description/

思路：

方法1：开辟一个新的二维数组来存储元素，当然题目要求不让使用这种方法。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;int [][] res = new int [n][n] ;for(int i=n-1; i>=0; i--){for(int j=0; j<n; j++){res[j][n-i-1] = matrix[i][j] ;}}for(int i=0; i<n; i++){for(int j=0; j<n; j++){matrix[i][j] = res[i][j] ;}}}
}

方法2：原地旋转数组，不需要额外的开辟存储空间，先水平翻转，然后沿着主对角线翻转。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 先水平翻转for(int i=0; i<n/2; i++){for(int j=0; j<n; j++){int tmp = matrix[i][j] ;matrix[i][j] = matrix[n-i-1][j] ;matrix[n-i-1][j] = tmp ;}}// 沿着主对角线翻转for(int i=0; i<n; i++){for(int j=0; j<i; j++){int tmp = matrix[i][j] ;matrix[i][j] = matrix[j][i] ;matrix[j][i] = tmp ;}}}
}

4.字母异位词分组

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/group-anagrams/

思路：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>() ;Map<String, List<String>> map = new HashMap<String,List<String>>() ;for(int i=0; i<strs.length; i++){char [] c = strs[i].toCharArray() ;Arrays.sort(c) ;String str = new String(c) ;List<String> list = map.getOrDefault(str, new ArrayList<String>()) ;list.add(strs[i]) ;map.put(str, list) ;}for(List<String> values : map.values()){res.add(values) ;}return res ;}
}

5.Pow(x,n)

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/powx-n/

思路：题解说是什么快速幂+递归/迭代，直接调api不香吗。

class Solution {public double myPow(double x, int n) {return Math.pow(x,n) ;}
}