南山做网站哪家好,深圳外贸商城网站建设,一键识图找原图,深圳工程建设信息网算法是码农的基本功#xff0c;也是各个大厂必考察的重点#xff0c;让我们一起坚持写题吧。
遇事不决#xff0c;可问春风#xff0c;春风不语#xff0c;即是本心。
我们在我们能力范围内#xff0c;做好我们该做的事#xff0c;然后相信一切都事最好的安排就可以啦…
算法是码农的基本功也是各个大厂必考察的重点让我们一起坚持写题吧。
遇事不决可问春风春风不语即是本心。
我们在我们能力范围内做好我们该做的事然后相信一切都事最好的安排就可以啦慢慢来会很快向前走别回头。
目录
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 ListListInteger permute(int[] nums) {ListListInteger res new ArrayList() ;ListInteger tmp new ArrayList() ;boolean [] vis new boolean[nums.length] ;dfs(nums, 0, res, tmp, vis) ;return res ;}public void dfs(int [] nums, int k, ListListInteger res, ListInteger tmp, boolean [] vis){if(k nums.length){res.add(new ArrayList(tmp)) ;}for(int i0; inums.length; i){if(vis[i]){continue ;}vis[i] true ;tmp.add(nums[i]) ;//k标记有几个元素dfs(nums, k1, res, tmp, vis) ;tmp.remove(k) ;vis[i] false ;}}
}
方法2交换法每次全排列之前需要先交换元素然后再进行全排列全排列完成之后交换回来。
class Solution {public ListListInteger permute(int[] nums) {ListListInteger res new ArrayList() ;ListInteger tmp new ArrayList() ;boolean [] vis new boolean[nums.length] ;dfs(nums, 0, res, tmp) ;return res ;}public void dfs(int [] nums, int k, ListListInteger res, ListInteger tmp){if(k nums.length){for(int i0; inums.length; i){tmp.add(nums[i]) ;}res.add(new ArrayList(tmp)) ;tmp.clear() ;}for(int ik; inums.length; i){swap(nums, i, k) ;dfs(nums, k1, 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 ListListInteger permuteUnique(int[] nums) {ListListInteger res new ArrayList() ;ListInteger 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, ListListInteger res, ListInteger tmp, boolean [] vis){if(k nums.length){res.add(new ArrayList(tmp)) ;}for(int i0; inums.length; i){if(vis[i] || (i0 vis[i-1] nums[i-1]nums[i])){continue ;}vis[i] true ;tmp.add(nums[i]) ;dfs(nums, k1, 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 in-1; i0; i--){for(int j0; jn; j){res[j][n-i-1] matrix[i][j] ;}}for(int i0; in; i){for(int j0; jn; j){matrix[i][j] res[i][j] ;}}}
}
方法2原地旋转数组不需要额外的开辟存储空间先水平翻转然后沿着主对角线翻转。
class Solution {public void rotate(int[][] matrix) {int n matrix.length;// 先水平翻转for(int i0; in/2; i){for(int j0; jn; j){int tmp matrix[i][j] ;matrix[i][j] matrix[n-i-1][j] ;matrix[n-i-1][j] tmp ;}}// 沿着主对角线翻转for(int i0; in; i){for(int j0; ji; 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 ListListString groupAnagrams(String[] strs) {ListListString res new ArrayList() ;MapString, ListString map new HashMapString,ListString() ;for(int i0; istrs.length; i){char [] c strs[i].toCharArray() ;Arrays.sort(c) ;String str new String(c) ;ListString list map.getOrDefault(str, new ArrayListString()) ;list.add(strs[i]) ;map.put(str, list) ;}for(ListString 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) ;}
}
