力扣爆刷第102天之hot100五连刷96-100
力扣爆刷第102天之hot100五连刷96-100
文章目录
- 力扣爆刷第102天之hot100五连刷96-100
- 一、136. 只出现一次的数字
- 二、169. 多数元素
- 三、75. 颜色分类
- 四、31. 下一个排列
- 五、287. 寻找重复数
一、136. 只出现一次的数字
题目链接：https://leetcode.cn/problems/single-number/description/?envType=study-plan-v2&envId=top-100-liked
思路：本题利用数学技巧，利用异或运算，一个数与0异或运算的结果还是它自身，此外，不同异或为1，相同为0，不同数异或会有一些大小变化，再进行相同数异或会减小掉变化。
class Solution {public int singleNumber(int[] nums) {int res = 0;for(int n : nums) {res ^= n;}return res;}
}
二、169. 多数元素
题目链接：https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-100-liked
思路：投票算法，当前数如果重复出现则加1，出现别的数则减1，为0换下一个数。
class Solution {public int majorityElement(int[] nums) {int count = 0, res = 0;for(int n : nums) {if(count == 0) {res = n;}count += n == res ? 1 : -1;}return res;}
}
三、75. 颜色分类
题目链接：https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
思路：3个数要排序，先0和1交换排序，然后再1和2交换排序。
class Solution {public void sortColors(int[] nums) {int zero = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] == 0) {int temp = nums[zero];nums[zero] = nums[i];nums[i] = temp;zero++;}}int one = zero;for(int i = zero; i < nums.length; i++) {if(nums[i] == 1) {int temp = nums[one];nums[one] = nums[i];nums[i] = temp;one++;}}}
}
四、31. 下一个排列
题目链接：https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked
思路：求下一个排列，是求下一个最小的大于它的值，基本原理从下图的5， 7， 6， 4处进行寻找，寻找最小的一个大于它的数，自然要从右边开始找，找第一个凹陷处，nums[i] < nums[i+1]，此时i= 5，然后再从右边找第一个大于5 的数，为6，也就是nums[j]>nums[i]，此刻这个6就是最小的一个大于它的数，然后交换，交换后[i, end]为单调递减，然后翻转即可。
class Solution {public void nextPermutation(int[] nums) {int i = nums.length - 2;while(i >= 0 && nums[i] >= nums[i+1]) {i--;}if(i >= 0) {for(int j = nums.length-1; j >= 0; j--) {if(nums[j] > nums[i]) {swap(nums, i, j);break;}}}reverse(nums, i+1, nums.length-1);}void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}void reverse(int[] nums, int i, int j) {while(i < j) {swap(nums, i, j);i++;j--;}}
}
五、287. 寻找重复数
题目链接：https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
思路：寻找重复数，给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）。这个是题目的描述，说明最大的数作为索引，也仅仅是数组结尾，所以可以把数组元素和索引建立联系，构建逻辑上的循环数组，和链表上的循环数组一样，使用快慢指针，慢的走一步，快的走两步，相遇就是环的入口，只不过此时拿到的是数组里的数，然后再有一个从起点出发，相遇即可拿到环的入口。
class Solution {public int findDuplicate(int[] nums) {int slow = 0, fast = 0;slow = nums[slow];fast = nums[nums[fast]];while(slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}int one = 0;while(one != slow) {one = nums[one];slow = nums[slow];}return one;}
}