有了网站源码怎么做网页,app界面设计图怎么做,提出网络营销思想的网站改版计划,华为最新消息目录
第一题#xff1a;03.数组中重复的数字
第二题#xff1a;39.数组中出现次数超过一半的数字
第三题#xff1a;50.第一个只出现一次的字符
第四题#xff1a;53. #xff08;0-n-1#xff09;中缺失的数字 第一题#xff1a;03.数组中重复的数字 我的答案03.数组中重复的数字
第二题39.数组中出现次数超过一半的数字
第三题50.第一个只出现一次的字符
第四题53. 0-n-1中缺失的数字 第一题03.数组中重复的数字 我的答案
法一普通数组
class Solution {public int findRepeatNumber(int[] nums) {int lennums.length;//数组长度int num-1;//暂存重复值用于返回int[] nums2new int[len];//创建一个新数组长度与旧数组一样for(int i0;ilen;i){//新数组的下标为旧数组的元素值新数组的元素值即为对应的下标值在旧数组中出现的次数nums2[nums[i]];}for(int i0;ilen;i){//遍历新数组如果出现元素值大于1即为其下标值在旧数组中重复出现if(nums2[i]1) {numi;break;}}return num;}
} 法二哈希表
class Solution {public int findRepeatNumber(int[] nums) {MapInteger,Integer countnew HashMap();//新建一个哈希表int num-1;//用于存储重复出现的元素for(int i0;inums.length;i){//重点在于如何让哈希表键值对的值实现自增Integer ncount.get(nums[i]);//因为n可能为null所以类型设为Integer而不是intif(nnull){//如果n为null证明这次的元素是第一次出现count.put(nums[i],1);}else{//如果n不为null则由键取到它原来的旧值在旧值上加1count.put(nums[i],n1);}}for(Map.EntryInteger,Integer e:count.entrySet()){//遍历哈希表if(e.getValue()1){nume.getKey();break;//找到一个重复的元素后直接结束循环然后返回num}}return num;}
} 官方答案
法一哈希集合
class Solution {public int findRepeatNumber(int[] nums) {SetInteger set new HashSetInteger();//新建一个哈希集合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 lennums.length;return nums[(int)Math.floor(len/2)];//Math.floor(len/2)向下取整得到数组中间位置的值//但此时是double值所以要强转为int值}
}
//len/2已经是取整了不必再写前面的数学函数了 法二哈希表
class Solution {public int majorityElement(int[] nums) {MapInteger,Integer countnew HashMap();int n(int)Math.floor(nums.length/2);int num0;for(int i0;inums.length;i){Integer mcount.get(nums[i]);if(mnull){count.put(nums[i],1);}else{count.put(nums[i],m1);}if(count.get(nums[i])n){numnums[i];}}return num;}
} 官方答案
法一哈希表
class Solution {private MapInteger, Integer countNums(int[] nums) {MapInteger, Integer counts new HashMapInteger, 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) {MapInteger, Integer counts countNums(nums);//Map.EntryInteger, Integer majorityEntry null;//用打擂台的方式去维护一个最大值for (Map.EntryInteger, 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);}
}
//【lohi】是子数组的下标范围
//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[] charss.toCharArray();//把字符串转成字符数组MapCharacter,Integer hashmapnew HashMap();//新建一个哈希表用于统计字符出现的次数 for(int i0;is.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 i0;is.length();i){//遍历哈希表找到值为1的元素返回它的键if(hashmap.get(chars[i])1){return chars[i];}}return ;}
} 官方答案
法一哈希表
class Solution {public char firstUniqChar(String s) {MapCharacter, Integer frequency new HashMapCharacter, 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) {MapCharacter, Integer position new HashMapCharacter, 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.EntryCharacter, 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) {MapCharacter, Integer position new HashMapCharacter, Integer();QueuePair queue new LinkedListPair();//新建一个队列存储的元素类型是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 i0;inums.length;i){if(nums[i]!i){//数组的元素值恰好等于它的索引值如果不等则该位置上的元素是错的return nums[i]-1;}}return nums.length;//缺失的元素在数组的末尾比如【0】缺失的元素是1恰好等于数组的长度}
} 官方答案
法一哈希集合
class Solution {public int missingNumber(int[] nums) {SetInteger set new HashSetInteger();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) {//检查【0n-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;}
}
