LeetCode热题100——技巧
文章目录
- 1. 只出现一次的数字
- 1.1 题目链接
- 1.2 题目描述
- 1.3 解题代码
- 1.4 解题思路
- 2. 多数元素
- 2.1 题目链接
- 2.2 题目描述
- 2.3 解题代码
- 2.4 解题思路
- 3. 颜色分类
- 3.1 题目链接
- 3.2 题目描述
- 3.3 解题代码
- 3.4 解题思路
- 4. 下一个排列
- 4.1 题目链接
- 4.2 题目描述
- 4.3 解题代码
- 4.4 解题思路
- 5. 寻找重复数
- 5.1 题目链接
- 5.2 题目描述
- 5.3 解题代码
- 5.4 解题思路
1. 只出现一次的数字
1.1 题目链接
点击跳转到题目位置
1.2 题目描述
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
提示:
- 1 <= nums.length <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
- 除了某个元素只出现一次以外,其余每个元素均出现两次。
1.3 解题代码
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0; i < nums.length; ++i){
res ^= nums[i];
}
return res;
}
}
1.4 解题思路
- 亦或运算解决问题。
2. 多数元素
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
提示:
- n == nums.length
- 1 <= n <= 5 * 104
- -109 <= nums[i] <= 109
2.3 解题代码
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
2.4 解题思路
- 先对原来的数组进行排序。
- 输出数组的中位数即为次数 大于 ⌊ n/2 ⌋ 的元素。
3. 颜色分类
3.1 题目链接
点击跳转到题目位置
3.2 题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
提示:
- n == nums.length
- 1 <= n <= 300
- nums[i] 为 0、1 或 2
3.3 解题代码
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
for(int i = 0; i <= right; ++i){
while(i < right && nums[i] == 2){
nums[i] = nums[right];
nums[right] = 2;
--right;
}
if(nums[i] == 0){
nums[i] = nums[left];
nums[left] = 0;
++left;
}
}
}
}
3.4 解题思路
- 记录当前需要修改的数组左端为left,右端为right。
- 如果当前为2,那么就一直将当前的数字与右端的数字交换,每交换一次,右端-1,直到右端为当前的数字的下标。
- 如果当前为0,那么就将其与左端的数字交换,左端+1即可。
- 直到遍历的下标到达右端时候为止。此时保证0都在最左段,2都在最右端,1都在中间。
4. 下一个排列
4.1 题目链接
点击跳转到题目位置
4.2 题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。
例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。
必须 原地 修改,只允许使用额外常数空间。
提示:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
4.3 解题代码
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
int j = n - 1;
while(i >= 0){
if(nums[i] < nums[i + 1]){
while(j > i){
if(nums[j] > nums[i]){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
j--;
}
break;
}
i--;
}
int left = i + 1;
int right = n - 1;
while(left <= right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}
4.4 解题思路
- 对于 [1, 3, 2, 4],只需要将2,4对换位置即可。
- 对于 [4, 3, 2, 1],需要将整个数组对换位置。
- 对于 [1, 3, 4, 2],下一个数是[1, 4, 2, 3]。需要将3和4对换位置,然后将[2, 3]换位置。
- 所以设置双指针,数组长度为n,j为n - 1,i为 n - 2,只有当nums[i] < nums[i] + 1的情况下才有可能对当前后面的数进行操作。j开始自减,直到nums[i] < nums[j],此时将nums[i]和nums[j]对换位置,将[i + 1, n - 1]反转。
5. 寻找重复数
5.1 题目链接
点击跳转到题目位置
5.2 题目描述
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
提示:
- 1 <= n <= 105
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
5.3 解题代码
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while(slow != fast);
slow = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
5.4 解题思路
- 因为数组长度为n + 1,而数组中数字大小为[1, n],所以可以将数组看做是一个有向图,下标 i 指向 数组下标nums[i]。
- 因为存在相同的数,运用快慢指针,快指针每次在图中移动两次,慢指针移动一次,直到快慢指针接触,此时快指针已经在环中了。 下面所需要求的就是进环的那个节点。
- 之后将慢指针回归原点,两个指针都以一格速度向前。假设环的长度为L,从起点到进入环的节点长度设为a,从环中走b步到达相遇位置,再走c步到达环口。则第一次相遇一定是在环内的。则2 * (a + b) = (a + b) + k * L, k >= 2且为整数。则 a = k * L - b,即 a = (k - 1)* L + C。此时指针走a步到达环口,快指针相当于绕了k - 1 圈后走了c步也到达了环口。这个时候即为最终的答案。