leetcode hot100特殊题型

1️⃣4️⃣ 技巧（特殊题型、数学、位运算等）

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

题解:

• 涉及数字的要求线性时间的, 一般尝试能不能用位运算实现

• 只出现一次的数字, 多个数字异或, 两个相同的数字异或为0, 那么最终剩下的就是只出现一次的数字

• class Solution {public int singleNumber(int[] nums) {int n = nums.length;if(n==1){return nums[0];}int res = nums[0];for(int i=1;i<n;i++){res = res^nums[i];}return res;}
  }
  

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

题解:

• 第一种, 使用哈希表存储每个元素出现的个数, 超过n/2的即为多数元素, 多数元素只可能有一个, 所以找到即可return

• 第二种, 由于多数元素总是>n/2的, 因此排序后索引值n/2处必定是多数元素.

• class Solution {public int majorityElement(int[] nums) {// int n = nums.length;// int cnt=0;// Map<Integer,Integer> map = new HashMap<>();// for(int i=0;i<n;i++){//     map.put(nums[i],map.getOrDefault(nums[i],0)+1);//     if(map.getOrDefault(nums[i],0)>(n>>1)){//         return nums[i];//     }// }// return cnt;Arrays.sort(nums);return nums[nums.length/2];}
  }
  

75. 颜色分类荷兰国旗问题

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

题解:

• 只有三个元素, 那么遇到红色插入0后, 遇到蓝色插入2前即可

• class Solution {public void sortColors(int[] nums) {int n = nums.length;int l=0,r=n-1;int idx=0;while(idx<n&&idx<=r){if(nums[idx]==0){int temp = nums[l];nums[l] = nums[idx];nums[idx] = temp;l++;idx++;}else if(nums[idx]==2){int temp = nums[r];nums[r] = nums[idx];nums[idx] = temp;r--;//遇到蓝色索引不能增加, 因为现在还未处理交换而来的尾部的新数据}else{idx++;}}}
  }
  

31. 下一个排列

题目太长了,简单来说就是给定一个整型数组, 找出当前排列代表数字的下一个大于它的最小数组.例: [1,2,3] 下一个就是[1,3,2], 如果当前即为数组能代表的最大数字, 那么返回最小排列,例: [3,2,1], 下一个就是[1,2,3]

题解:

• 数组排列, 寻找移动的规律:

  • 从后至前找到第一个小于当前数字的数字, 比如1,3,4,5,2,1, 找到的就是4
  • 然后在尾部的降序数组中找到最小的能够刚好大于当前数字的数字, 上述找到的就是5,
  • 交换两个数字,变为1,3,5,4,2,1 然后反转尾部降序的数组即可
  • 变为1,3,5,1,2,4

• class Solution {public static int findMinLarge(int[] nums,int start, int end,int target){int res = Integer.MAX_VALUE;int idx=0;for(int i=start;i<=end;i++){if(nums[i] > target){if(nums[i]<=res){res = nums[i];idx = i;}}}return  idx;}public static void swap(int[] nums,int tag1,int tag2){int temp = nums[tag1];nums[tag1] = nums[tag2];nums[tag2] = temp;}public static void reverse(int[] nums, int start,int end){while(start <= end){int temp = nums[start];nums[start++] = nums[end];nums[end--] = temp;}}public void nextPermutation(int[] nums) {int n = nums.length;// int flag = 0;for(int i=n-1;i>=1;i--){if(nums[i-1]<nums[i]){int idx = findMinLarge(nums,i,n-1,nums[i-1]);swap(nums,i-1,idx);reverse(nums,i,n-1);// flag=1;return;}}// if(flag==0){reverse(nums,0,n-1);// }}}
  

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

题解:

• 对于0-n的索引的值, 都会指向1-n, 那么必然会有存在0~n有两个或者多个索引的值是重复的, 由于值不会是0, 那么0必然会作为一个外部指向内部的指针, 内部就是1~n的循环指向

• 那么既然这是一个环, 重复元素肯定是环的入口, 使用快慢指针即可得到快慢指针相遇点

• 经由前面快慢指针的题可以知道, slow到入口的长度=0索引到入口的长度,二者相遇点即为环的入口就是重复值

• class Solution {public int findDuplicate(int[] nums) {int fast=0,slow=0;while(true){fast = nums[nums[fast]];slow = nums[slow];if(slow==fast){fast=0;while(nums[slow] != nums[fast]){fast = nums[fast];slow = nums[slow];}return nums[slow];}}}
  }