文章目录
- LeetCode 2864. 最大二进制奇数
- 思路1
- AC CODE
- 思路2
- AC CODE
LeetCode 2864. 最大二进制奇数
题目链接:https://leetcode.cn/problems/maximum-odd-binary-number/description/
思路1
由于二进制基数的最后一位必须是1,而其他位越大越好,所以让一个1在最低位,其他全部放到最高位即可。
所以我们数出字符串中1的个数,另开一个字符空间,把最后一位置1,把剩余的1全部放在前面。
注意开数组要多开1位,存放’\0’。
AC CODE
#include <stdio.h>
#define ll long long
#define INF 0x3f3f3f3f
const int N = 101;
char *num;
char* maximumOddBinaryNumber(char* s){
int cnt = 0;
int l = strlen(s);
num = (char *) malloc(sizeof(char) * (l + 1));
memset(num, '0', sizeof(char) * (l + 1));
for(int i = 0; i < l; ++i)
if(s[i] == '1')
cnt++;
num[l - 1] = '1';
num[l] = '\0';
for(int i = 0; i < cnt - 1; ++i)
num[i] = '1';
return num;
}
思路2
我们可以利用双指针,一个指着原数组,一个指着新开的数组(全0)。原指针一直走,当原数组中碰到1时,就给交换一下,新指针指向下一位,一直循环。当走到末尾,只要把新指针的后一位跟末尾的0交换即可。
但是其实我们发现这可以在一个数组中直接操作,我们默认新指针指的元素一直是0,等到原指针碰到1交换,最后交换末位。
AC CODE
class Solution {
public:
string maximumOddBinaryNumber(string s) {
int num = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '1'){
swap(s[i], s[num++]);
}
}
swap(s[s.size() - 1], s[num - 1]);
return s;
}
};