力扣-《剑指offer》-哈希表-刷题笔记
目录
第一题：03.数组中重复的数字
第二题：39.数组中出现次数超过一半的数字
第三题：50.第一个只出现一次的字符
第四题：53. （0-n-1）中缺失的数字
第一题：03.数组中重复的数字
我的答案：
法一：普通数组
class Solution {public int findRepeatNumber(int[] nums) {int len=nums.length;//数组长度int num=-1;//暂存重复值，用于返回int[] nums2=new int[len];//创建一个新数组，长度与旧数组一样for(int i=0;i<len;i++){//新数组的下标为旧数组的元素值，新数组的元素值即为对应的下标值在旧数组中出现的次数nums2[nums[i]]++;}for(int i=0;i<len;i++){//遍历新数组，如果出现元素值大于1，即为其下标值在旧数组中重复出现if(nums2[i]>1) {num=i;break;}}return num;}
}
法二：哈希表
class Solution {public int findRepeatNumber(int[] nums) {Map<Integer,Integer> count=new HashMap<>();//新建一个哈希表int num=-1;//用于存储重复出现的元素for(int i=0;i<nums.length;i++){//重点在于如何让哈希表键值对的值实现自增Integer n=count.get(nums[i]);//因为n可能为null，所以类型设为Integer，而不是intif(n==null){//如果n为null，证明这次的元素是第一次出现count.put(nums[i],1);}else{//如果n不为null，则由键取到它原来的旧值，在旧值上加1count.put(nums[i],n+1);}}for(Map.Entry<Integer,Integer> e:count.entrySet()){//遍历哈希表if(e.getValue()>1){num=e.getKey();break;//找到一个重复的元素后，直接结束循环，然后返回num}}return num;}
}
官方答案：
法一：哈希集合
class Solution {public int findRepeatNumber(int[] nums) {Set<Integer> set = new HashSet<Integer>();//新建一个哈希集合int repeat = -1;for (int num : nums) {//遍历数组if (!set.add(num)) {//Hashset不允许有重复项，所以如果num已经被加进过set里，那后面再遇到时，就加不进set里面了//此时set.add(num)返回false，取反！后就为true，返回此时的numrepeat = num;break;}}return repeat;}
}第二题：39.数组中出现次数超过一半的数字
我的答案：
法一：排序函数sort()
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);int len=nums.length;return nums[(int)Math.floor(len/2)];//Math.floor(len/2)向下取整，得到数组中间位置的值//但此时是double值，所以要强转为int值}
}
//len/2已经是取整了，不必再写前面的数学函数了
法二：哈希表
class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> count=new HashMap<>();int n=(int)Math.floor(nums.length/2);int num=0;for(int i=0;i<nums.length;i++){Integer m=count.get(nums[i]);if(m==null){count.put(nums[i],1);}else{count.put(nums[i],m+1);}if(count.get(nums[i])>n){num=nums[i];}}return num;}
}
官方答案：
法一：哈希表
class Solution {private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();//新建一个哈希表for (int num : nums) {//遍历数组if (!counts.containsKey(num)) {//如果哈希表中不包含数组中的元素num，则把它添加进去//元素的值为键，出现的次数为值counts.put(num, 1);} else {//此时的num已经被加进过哈希表了，所以这里的值实现自增counts.put(num, counts.get(num) + 1);}}return counts;}public int majorityElement(int[] nums) {Map<Integer, Integer> counts = countNums(nums);//Map.Entry<Integer, Integer> majorityEntry = null;//用打擂台的方式去维护一个最大值for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {//遍历哈希表//entry是对象名//Map.Entry是对象类型//<Integer, Integer>分别是键、值的数据类型//counts.entrySet()该方法返回的是键值对的集合if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {//majorityEntry是用来记录值最大的键majorityEntry = entry;//变更最大值}}return majorityEntry.getKey();}
}法二：排序
将数组
nums中的所有元素按照单调递增或单调递减的顺序排序，那么下标为n/2的元素（下标从0开始）一定是众数。
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}法三：随机化
因为超过n/2的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。
class Solution {private int randRange(Random rand, int min, int max) {//取随机数做下标return rand.nextInt(max - min) + min;}private int countOccurences(int[] nums, int num) {//验证该数是否是众数int count = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] == num) {count++;}}return count;}public int majorityElement(int[] nums) {Random rand = new Random();int majorityCount = nums.length / 2;while (true) {int candidate = nums[randRange(rand, 0, nums.length)];if (countOccurences(nums, candidate) > majorityCount) {//验证return candidate;}}}
}
法四：分治
分治算法：
分：递归地求解更小的问题，直到再也分割不了
治：子问题的解决方案形成了原问题的解决方案
class Solution {private int countInRange(int[] nums, int num, int lo, int hi) {//统计元素num在数组nums下标为[lo,hi]范围内出现的次数int count = 0;for (int i = lo; i <= hi; i++) {if (nums[i] == num) {count++;}}return count;}private int majorityElementRec(int[] nums, int lo, int hi) {// 长度为 1 的子数组中唯一的数显然是该子数组的众数，直接返回即可if (lo == hi) {return nums[lo];}// 递归对半分割数组，直到所有的子问题都是长度为 1 的数组int mid = (hi - lo) / 2 + lo;int left = majorityElementRec(nums, lo, mid);int right = majorityElementRec(nums, mid + 1, hi);// if (left == right) {return left;}// 否则，调用方法，计算子数组的众数int leftCount = countInRange(nums, left, lo, hi);int rightCount = countInRange(nums, right, lo, hi);return leftCount > rightCount ? left : right;//从两个子数组的两个众数中选出它们合并后的数组的众数}public int majorityElement(int[] nums) {return majorityElementRec(nums, 0, nums.length - 1);}
}
//【lo，hi】是子数组的下标范围
//left是左子数组的众数，right是右子数组的众数
//leftCount是左子数组的众数出现的次数，用于与右的比较，在这两个众数中选出它们子数组合并后的众数
法五：Boyer-Moore 投票算法（摩尔投票法）
class Solution {public int majorityElement(int[] nums) {int count = 0;//众数出现的次数Integer candidate = null;//候选众数for (int num : nums) {//遍历数组if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;//如果num和candidate相等，则计数器count的值加1//如果num和candidate不等，则计数器count的值减1}return candidate;}
}
第三题：50.第一个只出现一次的字符
我的答案：哈希表
class Solution {public char firstUniqChar(String s) {char[] chars=s.toCharArray();//把字符串转成字符数组Map<Character,Integer> hashmap=new HashMap<>();//新建一个哈希表，用于统计字符出现的次数 for(int i=0;i<s.length();i++){//遍历字符数组if(!hashmap.containsKey(chars[i])){//如果哈希表中不包含字符c，就把它添进去，次数为1次hashmap.put(chars[i],1);}else{//字符c已经出现过了，那在它原来出现的次数上加1hashmap.put(chars[i],hashmap.get(chars[i])+1);}}for(int i=0;i<s.length();i++){//遍历哈希表，找到值为1的元素，返回它的键if(hashmap.get(chars[i])==1){return chars[i];}}return ' ';}
}
官方答案：
法一：哈希表
class Solution {public char firstUniqChar(String s) {Map<Character, Integer> frequency = new HashMap<Character, Integer>();for (int i = 0; i < s.length(); ++i) {char ch = s.charAt(i);frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);}for (int i = 0; i < s.length(); ++i) {//遍历哈希表，找到值为1的键，然后返回if (frequency.get(s.charAt(i)) == 1) {return s.charAt(i);}}return ' ';}
}
法二：使用哈希表存储索引
class Solution {public char firstUniqChar(String s) {Map<Character, Integer> position = new HashMap<Character, Integer>();//新建一个哈希表int n = s.length();//字符串长度for (int i = 0; i < n; ++i) {char ch = s.charAt(i);if (position.containsKey(ch)) {position.put(ch, -1);//重复出现的字符，键值对的值都赋为-1} else {position.put(ch, i);//只出现一次的字符，键值对的值大小与字符出现的先后顺序一致，存的是字符的索引//值越小，出现得越早}}int first = n;//用打擂台的方式去维护一个最小值for (Map.Entry<Character, Integer> entry : position.entrySet()) {int pos = entry.getValue();if (pos != -1 && pos < first) {//找到哈希表里不为-1的最小值，即为第一个不重复字符的索引first = pos;}}return first == n ? ' ' : s.charAt(first);//没有找到索引最小值，first的值不变，就返回空格}
}法三：队列
class Solution {public char firstUniqChar(String s) {Map<Character, Integer> position = new HashMap<Character, Integer>();Queue<Pair> queue = new LinkedList<Pair>();//新建一个队列，存储的元素类型是Pairint n = s.length();for (int i = 0; i < n; ++i) {char ch = s.charAt(i);if (!position.containsKey(ch)) {//哈希表不包含字符ch，则按照出现顺序存储每一个字符及它们第一次出现的位置，哈希表和队列都各存一份position.put(ch, i);queue.offer(new Pair(ch, i));//队列是先进先出} else {position.put(ch, -1);//字符重复出现，把它在哈希表中的值修改为-1while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {//如果队列的队首在哈希表中存储的值为-1且队列不为空，证明这个元素是重复出现的元素//queue.peek()取出一个元素对象//queue.peek().ch取出该对象的ch属性queue.poll();//就把这个元素弹出队列，丢掉}}}return queue.isEmpty() ? ' ' : queue.poll().ch;//把重复出现的元素都弹出队列，如果最后队列不为空，那队列的队首就是所求}class Pair {//定义了Pair类，属性有ch,pos，分别存放字符和字符索引的char ch;int pos;Pair(char ch, int pos) {this.ch = ch;this.pos = pos;}}
}第四题：53. （0-n-1）中缺失的数字
我的答案：直接遍历
class Solution {public int missingNumber(int[] nums) {for(int i=0;i<nums.length;i++){if(nums[i]!=i){//数组的元素值恰好等于它的索引值，如果不等，则该位置上的元素是错的return nums[i]-1;}}return nums.length;//缺失的元素在数组的末尾，比如【0】缺失的元素是1，恰好等于数组的长度}
}
官方答案：
法一：哈希集合
class Solution {public int missingNumber(int[] nums) {Set<Integer> set = new HashSet<Integer>();int n = nums.length + 1;for (int i = 0; i < n - 1; i++) {//把数组内的元素全部添加进哈希表set.add(nums[i]);}int missing = -1;//用于存储缺失的数字for (int i = 0; i <= n - 1; i++) {//检查【0，n-1】的每个整数是否在哈希集合中if (!set.contains(i)) {missing = i;break;//找到缺失的元素就退出循环}}return missing;}
}法二：直接遍历
class Solution {public int missingNumber(int[] nums) {int n = nums.length + 1;//数组长度加上缺失的数字，一共应该是n个，for (int i = 0; i < n - 1; i++) {if (nums[i] != i) {//数组的元素值恰好等于它的索引值，如果不等，则该位置上的元素是错的return i;}}return n - 1;//这属于缺失的元素位于数组末尾的情况}
}
//+1是算上了缺失的数字
法三：位运算
在数组nums的n-1个数后面再添加0-n-1的每个整数，至此共有2n-1个整数，缺失的数字出现了一次，其余数字都出现了两次。对这2n-1个整数进行按位异或运算，结果即为缺失的数字。
class Solution {public int missingNumber(int[] nums) {int xor = 0;//用于存储缺失的数字int n = nums.length + 1;for (int i = 0; i < n - 1; i++) {//对缺失了数字的数组的n-1个数做异或运算xor ^= nums[i];}for (int i = 0; i <= n - 1; i++) {//接着上面，对完整的n个整数做异或运算xor ^= i;}return xor;//二进制数做异或运算，两个相同的数会相互抵消，变成0//最后剩下的是就是只出现了一次的缺失了的数字}
}法四：高斯求和公式
高斯求和的故事指的是年仅10岁的高斯解出来数学教师布特纳出一道难题，布纳特要求学生将1到100以内的所有整数进行相加，本来布纳特是为了为难学生的，没想到高斯很快算出了答案为5050。高斯用来快速解出答案的办法就被后人称为高斯求和。
class Solution {public int missingNumber(int[] nums) {int n = nums.length + 1;int total = n * (n - 1) / 2;//0~n-1个数的总和，完整的数组int arrSum = 0;for (int i = 0; i < n - 1; i++) {//缺失了数字的数组元素值总和arrSum += nums[i];}return total - arrSum;//差值即为缺失的数字}
}网友答案：二分查找
class Solution {public int missingNumber(int[] nums) {int lo = 0, hi = nums.length - 1;while(lo <= hi) {int mid = lo + (hi - lo >> 1);//对半分数组if(mid == nums[mid]) {lo = mid + 1;} else {hi = mid - 1;}}return lo;}
}