🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
📘1. 数组中出现次数超过一半的数字
描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：n ≤ 50000，数组中元素的值 100000 ≤ val ≤ 10000
要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)
编辑
解题思路：
🎈1. 方法一：我们可以使用map，根据map的键值对，将数组元素存入map中，相同key值的value值+1，当当前key的value值大于数组元素一半时，return key即可。
🎈2. 方法二：我们发现如果存在一个数字出现的次数超过数组长度的一半，当此数组排序后，出现次数最多的数字，一定在中间位置。
🎈3. 方法三：查询的本质是排除，所以我们可以先定义一个target 指向数组第一个元素，times 指出现次数，然后向后遍历，当后一个元素与target 相同时，times++；当后一个元素与target 不相同时，times --；当times == 0时，将当前元素赋值给 target。循坏结束 target 值就是出现次数最多的数字，然后遍历数组得到target出现的次数，如果大于数组元素一半时，return target 即可。
💡方法一：代码如下：
// 方法一 利用map 键值对 public int MoreThanHalfNum_Solution1(int [] array) { if(array.length == 0 || array ==null){ return 0; } int half = array.length >> 1; Map<Integer,Integer> map = new LinkedHashMap<>(); for (int i = 0; i < array.length; i++) { if(map.containsKey(array[i])){ // map中存在当前key 时，value + 1 map.replace(array[i],map.get(array[i])+1); }else { // map中不存在当前key 时，存入key,并将value 置为1 map.put(array[i],1); } if(map.get(array[i]) > half){ // 当前key的value值大于数组元素一半时，key就是所求值 return array[i]; } } return 0; }
💡方法二：代码如下：
// 方法二 数组排序 public int MoreThanHalfNum_Solution2(int [] array) { if(array.length == 0 || array == null){ return 0; } int half = array.length >> 1; Arrays.sort(array); int target = array[half]; int count = 0; for (int i = 0; i < array.length; i++) { if(target == array[i]){ count++; } } return count > half ? target : 0; }
// 如果确定存在一个数字出现的次数超过数组长度的一半，return array[array.length/2]即可 public int MoreThanHalfNum_Solution(int [] array) { if(array.length == 0 || array == null){ return 0; } return array[array.length/2]; }
💡方法三：代码如下：
// 方法三 查询的本质是排除 public int MoreThanHalfNum_Solution3(int [] array) { if(array.length == 0 || array == null){ return 0; } int half = array.length >> 1; int target = array[0]; int times = 1; for (int i = 1; i < array.length; i++) { if(times == 0){ // 当times == 0时，将当前元素赋值给 target target = array[i]; times = 1; }else if(target == array[i]){ // 当后一个元素与target 相同时，times++ times++; }else { // 当后一个元素与target 不相同时，times-- times--; } } times = 0; for (int i = 0; i < array.length; i++) { if(target == array[i]){ times ++; } } return times > half ? target : 0; }
📘2. 二进制中1的个数
描述
输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
编辑
解题思路：
🎈1. 方法一：我们知道只有1&1 = 1，其余0&0 = 0，1&0 = 0，0&1 = 0。
所以我们可以将整数的二进制每一位按位&1操作，然后整数右移一位，继续&1，统计得数为1的次数，但是我们发现，当整数为负数时，会出现死循环，因为负数右移时，在最高位补得是1；
因此，我们可以将整数的二进制每一位按位&1操作，然后将1左移一位，&操作后值不为0，count++。
🎈2. 方法二：我们可以循坏进行n&(n-1)操作，当n&(n-1) = 0 时，退出循环。因为我们发现，每进行一次n&(n-1)操作，该二进制数排除了一个1，所以我们可以不停的n & (n-1)，直到n == 0000 0000，排除结束。
编辑
💡方法一：代码如下：
// 错解 // 从n的2进制形式的最右边开始判断是不是1 // 可能陷入死循环的解法 // 因为负数右移时，在最高位补得是1 public static int NumberOf1_1(int n) { int count = 0; while (n != 0){ if((n & 1) == 1){ count ++; } // 把n的2进制形式往右推一位 n = n >> 1; } return count; } // 方法一： // 和错解类似，只是我们现在将1左移一位 public static int NumberOf1_2(int n) { int count = 0; int flag = 1; while (flag != 0){ if((n & flag) != 0){ count ++; } flag = flag << 1; } return count; }
💡方法二：代码如下：
// 方法二： // 例： 1000 1010 (n) // 1000 1001 (n-1) // &之后 1000 1000 排除了一个1 // 所以我们可以不停的n & (n-1)，直到n == 0000 0000，排除结束 public static int NumberOf1_3(int n) { int count = 0; while (n != 0){ n = n & (n - 1); count++; } return count; }
📘3. 替换空格
描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路：
🎈1. 方法一：我们可以设置一个空字符串ret，然后遍历题中字符串，当遇到字符为空时ret+="20%"，其余ret += s.charAt(i)，得到新字符串ret ，return ret 即可。
🎈2. 方法二：我们也可以先统计空字符的个数，然后设置新字符串长度，然后从后往前遍历题中字符串，当遇到字符为空时，分别倒置插入字符'0' '2' '%'，其余字符倒置插入即可
💡方法一：代码如下：
// 方法一： public static String replaceSpace1(StringBuffer str) { String s = str.toString(); String ret = ""; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(c == ' '){ ret +="%20"; }else { ret += c; } } return ret; }
💡方法二：代码如下：
// 方法二： public static String replaceSpace(StringBuffer str) { // 找出空格数 int count = 0; for (int i = 0; i < str.length(); i++) { if(str.charAt(i) == ' '){ count++; } } int old_end = str.length() - 1; // 设置新字符串长度 str.setLength(str.length() + count*2); int new_end = str.length() - 1; while (old_end >= 0 && new_end >= 0){ // 填数 if(str.charAt(old_end) == ' '){ str.setCharAt(new_end--, '0'); str.setCharAt(new_end--, '2'); str.setCharAt(new_end--, '%'); old_end--; }else { // 不为空 则平移 str.setCharAt(new_end--,str.charAt(old_end)); old_end--; } } return str.toString(); }
