前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.只出现一次的数字
题目链接:136. 只出现一次的数字 - 力扣(LeetCode)
题面:
基本分析:用异或,当两数相同时,异或结果是0,而0和A异或答案是A,由此线性遍历数组,记录异或结果,最终结果则为出现一次的元素
代码:
class Solution {public int singleNumber(int[] nums) {Arrays.sort(nums);int l = 1;int ans = 0;int n = nums.length;if(n==0)return 0;if(n==1)return nums[0];while(l<n){if(nums[l]!=nums[l-1]){ans = nums[l-1];break;}l+=2;}if(nums[n-1]!=nums[n-2])ans = nums[n-1];return ans;}
}
2.多数元素
题目链接:169. 多数元素 - 力扣(LeetCode)
题面:
基本分析:可以采用哈希表,也可以排序后取索引为n/2的元素,还可以采用摩尔投票,详细可以看力扣的大佬题解
代码:
class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();int n = nums.length;int flag = n/2;int ans = 0;for(int a:nums){map.put(a,map.getOrDefault(a,0)+1);if(map.get(a)>flag){ans = a;break;}}return ans;}
}
3.颜色分类
题目链接:75. 颜色分类 - 力扣(LeetCode)
题面:
基本分析:可以采用双指针前后遍历进行排序,我采取的是一个稍微复杂点的双指针
代码:
class Solution {public void sortColors(int[] nums) {int n = nums.length;int[] ans = new int[n];Arrays.fill(ans,1);int l = 0;int r = n-1;for(int i = 0;i<n;i++){if(nums[i]==1)continue;if(nums[i]==0)ans[l++] = 0;else if(nums[i]==2)ans[r--]=2;}for(int i =0;i<n;i++)nums[i]=ans[i];}
}
4.下一个排列
题目链接:31. 下一个排列 - 力扣(LeetCode)
题面:
基本分析:想找到下一个排列,可以从后往前遍历,找到第一个小于最后一个元素的数,记其索引为k,然后交换,由于最后一个数更大,他被调到高位后整个排列就更大了,为了让这个排序尽可能小,就把k之后的数从小到大排序
代码:
class Solution {public void nextPermutation(int[] nums) {int n = nums.length, k = n - 1;while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;if (k == 0) {reverse(nums, 0, n - 1);} else {int u = k;while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;swap(nums, k - 1, u);reverse(nums, k, n - 1);}}void reverse(int[] nums, int a, int b) {int l = a, r = b;while (l < r) swap(nums, l++, r--);}void swap(int[] nums, int a, int b) {int c = nums[a];nums[a] = nums[b];nums[b] = c;}
}
5.寻找重复数
题目链接:287. 寻找重复数 - 力扣(LeetCode)
题面:
基本分析:采用循环链表,详细看大佬题解,非常巧妙
代码:
class Solution {public int findDuplicate(int[] nums) {int slow = nums[0];int fast = nums[nums[0]];while(slow!=fast){slow = nums[slow];fast = nums[nums[fast]];}int flag = 0;while(flag!=slow){flag = nums[flag];slow = nums[slow];}return slow;}
}
后言
上面是力扣Hot100的技巧专题,下一篇会有专题,希望有所帮助,一同进步,共勉!