网站做移动端市场营销实务

---

---

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;}
};