秋招突击——算法练习——8/30、9/4——技巧题练习——复习{}——新作{只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数}

引言

• 手撕的代码大部分都是出自于这里，还是要继续加强，把剩下一些零碎的题目再过一遍，然后再把hot100再刷一遍，这次重在于思想，而不是代码和答案。

复习

新作

136、只出现一次的数字

• 题目链接
  
  注意
• 输入的是数组，并且不会越界，使用int就能够存储
• 元素中出了一个元素只出现一次，其余元素都出现了两次
• 输出仅仅出现一次的元素

个人实现

• 这个题目就是使用异或运算，异或运算，满足交换性，自反性和结合性。

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

169、多数元素

题目链接

注意

• 给的是一个有重复元素的数组，一定存在一个元素出现的次数是超过了总数量的一半
• 数组不为空，一定会有一个答案

个人实现

• 直白的就是遍历整个数组，然后统计一下次数，然后返回最大的结果。

class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();int[] res = {0,0};for(int x:nums){map.put(x,map.getOrDefault(x,0) + 1);int count = map.get(x);if( count >= res[1]){res[0] = x;res[1] = count; }}return res[0];}
}

总结

• 如果这个题目是一个场景题，现在有10亿个数字，你应该怎么做？
• 没有办法全部加载到内存中，只能一部分一部分加载到内存中，然后统计次数，保存到hashmap中吗？不对，感觉这个方法不对！

摩尔投票算法

class Solution {public int majorityElement(int[] nums) {int count = 0;int num = 0;for(int x:nums){if(count == 0){count = 1;num = x;}else{if(x == num) count ++;else count --;}}return num;}
}

75、颜色分类

题目链接

注意

• 总共只有三种数字，分别是0、1、2，然后相同的数字放在一起，然后按照0、1、2进行排序
• 只能使用常数空间实现！

个人实现

• 如果常数空间，直白的话就是使用交换排序，因为元素是知道的，然后相对顺序也是知道的，直接双指针交换就行了！

这里有一个思路，这个右侧肯定是2，然后左侧肯定是0，所以逐个进行遍历，出现2往右移动，出现0往左移动就行了！

class Solution {public void sortColors(int[] nums) {int m = nums.length - 1;int l = 0,r = m;int cur = l ;// 使用三指针，中间的指针用来遍历，左右指针用来保存while(cur <= r){// 往右加换2，保证r指针右侧都是2// if(nums[cur] == 2){while(r > cur && nums[r] == 2) r--;int temp = nums[r];nums[r] = nums[cur];nums[cur] = temp;r--;}// 往左交换0，保证l左侧的指针都是0if(nums[cur] == 0){while(l < cur && nums[l] == 0) l ++;int temp = nums[l];nums[l] = nums[cur];nums[cur] = temp;l ++;}        // 然后在移动对应的cur指针cur ++;    }return;}
}

总结

• 这道题感觉做的还是有点久的，因为一开始用了双指针进行交换，但是有一些问题解决不了，就想着用三指针，因为知道2就往右，0就往左，是固定的！
• 然后重新写了一下！

参考实现

• 单指针就需要遍历两次，然后双指针就是需要遍历一次，这里用的方法和我的差不多，不过代码上更简洁一点，具体实现如下

流程图直接看这里

class Solution {public void sortColors(int[] nums) {int m = nums.length - 1;int p0 = 0, p1 = 0;// 使用三指针，中间的指针用来遍历，左右指针用来保存for (int i = 0; i <= m; i++) {if (nums[i] == 1) {int temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;p1++;} else if (nums[i] == 0) {int temp = nums[i];nums[i] = nums[p0];nums[p0] = temp;if (p0 < p1) {temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;}p0++;p1++;}}return;}
}

31、下一个排列

题目链接

注意

• 当前序列会有若干序列，需要找出下一个字典序中的序列是什么
• 只能原地修改，只允许使用额外的常数空间

个人实现

• 这个没什么好的方法，然后直接看参考实现吧！

参考实现

class Solution {public void nextPermutation(int[] nums) {// 主要分为两部，先是找到较小的，然后再找比较小的大的// 然后进行交换，然后在排序// 这里需要遍历对应的元素int n = nums.length;if(n == 1)  {return;}if(n == 2){swap(nums,0,1);return;}// 超过两个元素的情况int i = nums.length - 2;while(i >= 0 && nums[i] >= nums[i + 1]){i --;}if(i >= 0){int j = nums.length - 1;while(j >= 0 && nums[i] >= nums[j]){j --;}swap(nums,i ,j);}reverse(nums,i + 1 ,nums.length - 1);}// 交换元素public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public void reverse(int[] nums ,int i ,int j){// 将从i到j 的序列进行反转while(i <= j){swap(nums,i , j);i ++;j --;}}
}

287寻找重复数

题目链接

注意

• 有一个数字树出现了多次，然后其他的数字仅仅出现了一次
• 找出这个出现多次的数字

个人实现

个人思路

• 不能修改原来的数组，所以不能进行排序了，如果能够排序，那就好做了！
• 然后只能使用常数的存储空间，就不能创建一个类似hash表的结构进行处理的
• 针对这类题目，常规的会使用bitmap，操作位图，然后需要遍历的，但是这样就不是常数的存储空间了，而且就算申请了固定的存储存储空间也是取巧！
• 抓住两个点，所有的数组都是在1到n之间的，而且只有一个数字是重复的，其他的数字都是唯一的
  • 求和感觉看不出来什么，其他的也看不出来啥，为什么求和，是因为他是一个顺序不一样的操作，所以不得行！，那想想看，能不能对每一个元素做差，然后再求绝对值，然后在求和，最小的时候，就是最大的！

• 平均减一，做差求和的思路去试试看
• 通过下述的方式，可以看出来重复多少次，以及具体是什么值
  

class Solution {public int findDuplicate(int[] nums) {int n = nums.length;int preSum = 0;int res = 0;for(int j = 0;j < n;j ++){preSum += nums[j];}for(int i = 1;i <= n;i ++){int sum = 0;for(int j = 0;j < n;j ++){sum += Math.abs(nums[j] - i);}// 判定是否相等System.out.println(sum + "  " + preSum);if(preSum > sum){res ++;}preSum = sum;}return res;}
}

总结

• 这个不会，属实整不会了，不知道怎么弄！因为如果是单单最小的和话，1这种情况无解！

参考实现

• 这里使用了快慢指针来实现，因为所有数字都是在1到n的，所以可以转成图论来看这个问题，具体如下
  

• 使用快慢指针的话，快慢相遇表示会成环

• 然后在确定环的切入点就行

class Solution {public int findDuplicate(int[] nums) {int a = 0, b = 0;while (true) {a = nums[a]; // a走一步b = nums[nums[b]]; // b走两步if (a == b) {a = 0;while (a != b) {a = nums[a];b = nums[b];}return a;}}}
}

切入点的疑惑

• 找到相遇点了，为什么a直接从零开始遍历，再次相遇，然后同时运行，再次相遇就是相遇点了！

总结

• 继续加油，秋招还有机会！
• 感觉要做一个自己的博客网站了，CSDN不是很好用，首先搜索我自己的博文的时候，居然没有办法进行模糊匹配，我搜环形链表，居然搜出来为空，然后只能自己一个一个找，这个效率太低了！
  • 搞一个自己的博客，至少以后面试也有的讲！
• 秋招还是比较难得，好不容易面过了美团，结果没有HC，直接回到了人才池，然后重新开始面试吧！