🤞目录🤞
💖1. 数组中出现次数超过一半的数字
💖2. 二进制中1的个数
💖3. 替换空格
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
📘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();
}相关文章
