Leetcode 每日一题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    string addBinary(string a, string b) {
        int p1 = a.length()-1, p2 = b.length()-1, flag = 0;
        string ans = "";
        while(p1>=0 || p2>=0){ // 双指针
            int sum = flag;
            if(p1>=0) sum += a[p1];
            if(p2>=0) sum += b[p2];
            flag = (sum & 2)>>1; // 标志位记录进位
            ans = to_string(sum & 1) + ans;
            p1--, p2--;
        }
        if(flag) ans = "1" + ans;   // 处理最后进位
        if(ans == "") return "0";   // 特殊情况
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        p1, p2, flag, res = len(a) - 1, len(b) - 1, 0, ""
        while p1 >= 0 or p2>=0:
            sum = flag
            if p1 >= 0:
                sum += int(a[p1])
            if p2 >= 0:
                sum += int(b[p2])
            flag, res = sum // 2, str(sum&1) + res
            p1, p2= p1-1, p2-1
        if flag:
            res = "1" + res
        if res == "":
            res = "0"
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int reverseBits(int n) {
        int res = 0, bits = 0;
        while(n!=0){
            res = (res<<1) | (n&1);
            bits+=1, n>>=1;
        }
        return ((long) res<<(32-bits));
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def reverseBits(self, n: int) -> int:
        res, bits = 0, 0
        while n:
            res = (res<<1) | (n&1)
            n >>= 1
            bits += 1
        return res<<(32-bits)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        auto countOne = [](int num){
            int cnt = 0;
            while(num){
                cnt+=(num&1);
                num>>=1;
            }
            return cnt;
        };
        // 打表小时和分钟的可能性
        vector<vector<string>> h(20);
        vector<vector<string>> m(60);
        for(int i=0;i<=11;i++) h[countOne(i)].push_back(to_string(i));
        for(int i=0;i<=59;i++){
            if(i<10){
                m[countOne(i)].push_back("0"+to_string(i));
            }
            else{
                m[countOne(i)].push_back(to_string(i));
            }
        }
        vector<string> ans;
        for(int i=0;i<=turnedOn;i++){
            int h_one = i, m_one = turnedOn - i;
            for(string& hstr: h[h_one]){
                for(string& mstr: m[m_one]){
                    ans.emplace_back(hstr+":"+mstr);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        h, m, ans = [[] for i in range(12)], [[] for i in range(60)], []
        def cntOne(num: int):
            res = 0
            while num>0:
                res, num = res + (num&1), num>>1
            return res
        
        for i in range(12):
            h[cntOne(i)].append(f"{i}")
        for i in range(60):
            m[cntOne(i)].append(f"{i}" if i>=10 else f"0{i}")
        
        for i in range(turnedOn + 1):
            hone, mone = i, turnedOn - i
            for hstr in h[hone]:
                for mstr in m[mone]:
                    ans.append(hstr + ":" + mstr)

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool hasAlternatingBits(int n) {
        bool flag = n&1;
        while(n>0){
            if(flag == (bool)(n&1)) n = n>>1, flag = !flag;
            else return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        flag = n&1
        while n:
            if n&1 == flag:
                n, flag = n>>1, not flag
            else:
                return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int countBinarySubstrings(string s) {
        int flag = s[0] - '0', res = 0, cnt = 0, last_cnt = 0, idx = 0, l = s.length();
        while(idx<l){
            while(idx<l && s[idx] - '0'==flag) cnt++, idx++;
            res = res + min(cnt, last_cnt), last_cnt=cnt, cnt = 0, flag = 1-flag;
        }
        return res;

    }
};

1
2
3
4
5
6
7
8

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        cnt, last_cnt, flag, res, n, idx = 0, 0, int(s[0]), 0, len(s), 0
        while idx < n:
            while idx < n and int(s[idx])==flag:
                idx, cnt = idx + 1, cnt + 1
            res, last_cnt, cnt, flag = res + min(cnt, last_cnt), cnt, 0, 1 - flag
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    string makeLargestSpecial(string s) {
        int n = s.length();
        auto check = [&n, &s](){
            vector<pair<int, int> > pos;
            for(int i=0;i<n;i++){
                for(int l=2;l+i<=n;l++){
                    int cnt0=0, cnt1=0, idx = 0, flag = true;
                    while(idx<l){
                        cnt0 += s[i+idx]=='0', cnt1 += s[i+idx]=='1', idx++;
                        if(cnt0>cnt1){flag=false; break;}
                    }
                    if(flag && cnt0 == cnt1) pos.push_back(std::make_pair(i,l));
                }
            }
            return pos;
        };
        auto getStr = [](string& s, int p, int l){
            return s.substr(p, l);
        };
        while(1){
            bool flag = true;
            auto l = check();
        
            bool jumpflag = false;
            for(int i=0;i<l.size();i++){
                for(int j=i+1;j<l.size();j++){
                    int b1 = l[i].first, l1 = l[i].second;
                    int b2 = l[j].first, l2 = l[j].second;
                    if(b1 + l1 != b2) continue;
                    string tmp_s1 = getStr(s, b1, l1);
                    string tmp_s2 = getStr(s, b2, l2);
                    if(tmp_s1 < tmp_s2 && tmp_s1 != getStr(tmp_s2, 0, l1)){
                        tmp_s1 = tmp_s2 + tmp_s1;
                        for(int j=0;j<tmp_s1.length();j++){
                            s[b1+j] = tmp_s1[j]; 
                        }
                        flag = false;
                        jumpflag = true;
                        break;
                    }
                }
                if(jumpflag) break;
                
            }
            if(flag) break;
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        n = len(s)
        def checkSub(s, b, l):
            cnt0, cnt1, flag = 0, 0, True
            for i in range(l):
                cnt0, cnt1 = cnt0 + (s[b+i]=='0'), cnt1 + (s[b+i]=='1')
                if cnt0 > cnt1:
                    flag = False
                    break
            return flag and (cnt0 == cnt1)

        def findSub(s):
            pos, n = [[] for c in s], len(s)
            for i in range(n):
                for l in range(2, n+1):
                    if i+l > n:
                        break
                    if checkSub(s, i, l):
                        pos[i].append(l)
            return pos
        while 1:
            bflag, jumpflag, pos = True, False, findSub(s)
            for i in range(n):
                if len(pos[i]) == 0:
                    continue
                for il in pos[i]:
                    if i + il >= n or len(pos[i + il]) == 0:
                        continue
                    j = i + il
                    for jl in pos[i + il]:
                        if s[i:i+il] < s[j:j+jl] and s[j:j+jl][:il] != s[i:i+il]:
                            # swap
                            # s[i:i+il+jl] = s[j:jl] + s[i:i+il]
                            s = s[:i] + s[j:j+jl] + s[i:i+il] + s[j+jl:]
                            jumpflag, bflag = True, False
                            break
                    if jumpflag:
                        break
                if jumpflag:
                    break

            if bflag:
                break
        return s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        vector<int> prime(33, 0);
        prime[2] = prime[3] = prime[5] = prime[7] = prime[11] = prime[13] = prime[17] = prime[19] = prime[23] = prime[29] = prime[32] = 1;
        auto cntOne = [](int num){
            int res = 0;
            while(num){
                res += 1, num = num & (num - 1);
            }
            return res;
        };
        int res = 0;
        while(left<=right){
            res += prime[cntOne(left++)];
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int binaryGap(int n) {
        int res = 0, cnt = 0;
        while(n){
            if(n&1) res = max(res, cnt), cnt = 1;
            else if(cnt>0) cnt++;
            n>>=1;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def binaryGap(self, n: int) -> int:
        cnt, res = 0, 0
        while n:
            if n&1==1:
                res, cnt = max(res, cnt), 1
            elif cnt>0:
                cnt += 1
            n >>= 1
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        map<string, int> mp;
        string tmp_s = s.substr(0,k);
        mp[tmp_s] = 1;
        for(int i=k;i<s.length();i++){
            // 滑动窗口
            tmp_s = tmp_s.substr(1) + s[i];
            mp[tmp_s] = 1;
        }
        return mp.size() == pow(2,k);
    }
};

1
2
3
4
5
6

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        tmp_s, mp = s[0:k], {s[0:k]:1}
        for i in range(k, len(s)):
            tmp_s, mp[tmp_s] = tmp_s[1:] + s[i], 1
        return len(mp) == 2**k

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int res = 0;
        auto dfs = [&res](this auto &&self, TreeNode* root, int val){
            if(root == nullptr) return;
            val = (val<<1) + root->val;
            if(root->left == nullptr && root->right == nullptr) res+=val;
            self(root->left, val), self(root->right, val);
        };
        dfs(root, 0);
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root, val) -> int:
            if root == None:
                return
            val = (val<<1) + root.val
            if root.left == None and root.right == None:
                nonlocal res
                res += val
                return
            dfs(root.left, val), dfs(root.right, val)
        dfs(root, 0)
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        auto cntOne = [](int num){
            int res = 0;
            while(num) res++, num = num & (num-1);
            return res;
        };

        sort(arr.begin(), arr.end(), [&cntOne](int& a, int &b){
            int ca = cntOne(a), cb = cntOne(b);
            if(ca != cb) return ca<cb;
            return a<b;
        });
        return arr;
    }
};

1
2
3
4
5
6
7
8
9

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def cntOne(num: int)->int:
            res = 0
            while num:
                res, num = res + 1, num & (num - 1)
            return res
        arr.sort(key = lambda x: (cntOne(x), x))
        return arr

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numSteps(string s) {
        // 1. 扫描0
        // 2. 扫描1
        int n = s.length(), idx = s.length() - 1, res = 0;
        while(idx>=1){
            while(idx>=1 && s[idx]=='0') idx--, res++;
            if(idx>=1 && s[idx]=='1'){
                res++; // 第一个1加1操作
                while(idx>=0 && s[idx]=='1') idx--, res++; // 扫描到开头位
                if(idx>=1 && s[idx] == '0') s[idx] = '1'; // 进位
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def numSteps(self, s: str) -> int:
        flag, res = 0, 0
        while not((s == '1' and flag == 0) or (s=="" and flag ==1) ):
            tmp_r = int(s[-1]) + int(flag)
            s, flag = s[0:-1] + str(tmp_r & 1), ((tmp_r & 2) >> 1)
            # print(s, flag, res)
            if s[-1] == '0':
                s, res = s[0:-1], res + 1
            else:
                s, res, flag = s[0:-1], res + 2, flag + 1
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 下面代码的剪枝超时，需要不断从剩余状态集合中加入新状态
class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n, vis, q, cnt0, idx = len(s), [-1] + [-1 for c in s], [], 0, 0
        for c in s:
            cnt0 += (c=='0')
        vis[n-cnt0] = 0
        q.append(n-cnt0)
        while len(q)>idx:
            c0, c1, idx = n - q[idx], q[idx], idx + 1
            for i in range(max(k-c1, 0), min(k, c0) + 1): # 反转i个0
                nc0, nc1 = c0 - i + k - i, i + c1 - k + i
                if nc0<0 or nc0 > n or nc1 < 0 or nc1 > n or vis[nc1] != -1:
                    continue
                q.append(nc1)
                vis[nc1] = vis[c1] + 1
        return vis[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int concatenatedBinary(int n) {
        long res = 0, m = 1e9+7, flag = 1, bits = 0;
        for(int i=1; i<=n; i++){
            if(i>=flag) flag <<= 1, bits += 1; // 标记当前数字的二进制位数
            res = ((res<<bits) + i ) % m;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from bisect import bisect_right
class Solution:
    def concatenatedBinary(self, n: int) -> int:
        # res<<x + b
        res, m, table = 0, 1e9 + 7, [1]
        for i in range(32):
            table.append(table[-1]*2) # 1 2 4 8 16
        for i in range(1, n+1):
            # print(i, res, bisect_right(table, i))
            res = int( ((res << bisect_right(table, i) ) + i ) % m ) # 查表找二进制位数
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int minPartitions(string n) {
        // 1 10 11 100 101 110 111
        // greedy
        int res = 0, l = n.length();
        for(int i=0; i<l; i++){
            res = max(n[i]-'0', res);
        }
        return res;
    }
};

1
2
3

class Solution:
    def minPartitions(self, n: str) -> int:
        return max([int(c) for c in n])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size(), res = 0;
        vector<int> l(n, 0);
        vector<int> vis(n, 0);
        // 预处理末尾的0
        for(int i=0;i<n;i++){// row 0
            for(int j = n-1; j>=0;j--){
                if(grid[i][j]==0) l[i]++;
                else break;
            }
        }
        int idx = 0, cnt = 0;
        // 贪心 每个位置都找最近的符合条件的行 把符合条件的行交换到当前行
        while(cnt<n-1){
            if(vis[idx]){
                idx++;
                continue;
            }
            if(l[idx] >= (n - 1 - cnt)){
                idx++, cnt++;
            }
            else{
                int flag = 1, tmp_cnt = 1;
                for(int i = idx+1;i<n;i++){
                    if(!vis[i] && l[i]>=(n-1-cnt)){
                        flag = 0, vis[i] = 1, cnt++, res+=tmp_cnt;
                        break;
                    }
                    if(!vis[i]) tmp_cnt++;
                }
                if(flag) return -1;
            }
        }

        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        suff, n, res = [0 for i in range(len(grid))], len(grid), 0
        # 预处理
        for i in range(n):
            for k in range(n):
                j = n - 1 - k
                if grid[i][j] == 0:
                    suff[i] += 1
                else:
                    break
        # 对每个位置找第一个符合条件的行
        idx, vis = 0, [0 for i in range(n)]
        for i in range(n-1):
            # find unvis suff
            while idx < n-1 and vis[idx] == 1:
                idx += 1
            if idx >= n:
                return -1
            # 当前位置满足条件
            if suff[idx] >= n - 1 - i:
                idx += 1
            else:
                # 需要向后查找第一个满足条件的要求
                swap_step, flag = 0, 1
                for j in range(idx+1, n):
                    if not vis[j]:
                        swap_step += 1
                        if suff[j] >= n - 1 - i:
                            res, flag, vis[j] = res + swap_step, 0, 1
                            break
                if flag:
                    return -1
            print(i, idx, res, vis)
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    inline char charNot(char c){
        return c=='0'?'1':'0';
    }
    char findKthBit(int n, int k) {
        // 1 3 7 15
        // l(n) = 2 * l(n-1) + 1
        // l(n) = 2^(n+1) - 1

        if(n==1) return '0';
        long long l = (1<<n) - 1;
        long long mid = (l >> 1) + 1;
        if(k==mid) return '1';
        if(k<mid){
            return findKthBit(n-1, k);
        }
        return charNot(findKthBit(n-1, l-k+1));
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n==1:
            return "0"
        l = (1<<n) - 1
        mid = (l>>1) + 1
        if k == mid:
            return "1"
        if k < mid:
            return self.findKthBit(n-1, k)
        return "0" if self.findKthBit(n-1, l - k + 1) == "1" else "1"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), res = 0;
        vector<int> r(m+1, 0);
        vector<int> c(n+1, 0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                r[i+1] += mat[i][j];
                c[j+1] += mat[i][j];
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j] && r[i+1]==1 && c[j+1]==1) res+=1;
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n, res = len(mat), len(mat[0]), 0
        r, c = [0 for i in range(m+1)], [0 for i in range(n+1)]
        for i in range(m):
            for j in range(n):
                r[i+1] += mat[i][j]
                c[j+1] += mat[i][j]
                
        for i in range(m):
            for j in range(n):
                if mat[i][j]==1 and r[i+1]==1 and c[j+1]==1:
                    res += 1
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minOperations(string s) {
        int cnt=0, flag='0', n=s.length();
        for(char& c:s){
            if(c==flag) cnt++;
            flag = '1' - flag + '0';
        }
        return n - max(cnt, n-cnt);
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def minOperations(self, s: str) -> int:
        cnt, flag, n = 0, 0, len(s)
        for i in range(n):
            if s[i]==str(flag):
                cnt+=1
            flag = 1 - flag
        return n - max(cnt, n-cnt)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool checkOnesSegment(string s) {
        bool flag = 1;
        for(char& c: s){
            if(c=='1' && flag==1) continue; 
            if(c=='0'){
                flag = 0;
                continue;
            }
            else return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        idx, n, flag = 0, len(s), -1
        while idx<n:
            flag += 1
            while idx<n and s[idx]=='1':
                idx += 1
            while idx<n and s[idx]=='0':
                idx += 1
        return not flag

1
2
3
4

0 |1| 2| 3| 4| 5| 0| 1|
奇|偶|奇|偶|奇|偶           <- 原始字符串
   奇|偶|奇|偶|奇|偶        <- 操作1 一次后的字符串
      奇|偶|奇|偶|奇|偶     <- 操作1 两次后的字符串

1
2
3
4

0 |1| 2| 3| 4| 5| 6| 0| 1|
奇|偶|奇|偶|奇|偶|奇|  <- 原始字符串
   奇|偶|奇|偶|奇|偶|奇|  <- 操作1 一次后的字符串
      奇|偶|奇|偶|奇|偶|奇|  <- 操作1 两次后的字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minFlips(self, s: str) -> int:
        cnt, n = 0, len(s)
        if n%2==0:
            for i in range(n):
                if i%2==int(s[i]):
                    cnt+=1
            # cnt, n-cnt
            return min(cnt, n-cnt)
        else:
            pre, res = [0], n
            for i in range(n):
                pre.append(pre[i]+int(i%2==int(s[i])))
            for i in range(n +  1):
                l1, l2 = i, n - i
                cnt1, cnt2 = pre[l1], pre[n] - pre[l1]
                res = min(res, min(cnt1+l2-cnt2, l1-cnt1 + cnt2))
            return res
        return 0
                    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool checkOnesSegment(string s) {
        bool flag = 1;
        for(char& c: s){
            if(c=='1' && flag==1) continue; 
            if(c=='0'){
                flag = 0;
                continue;
            }
            else return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        idx, n, flag = 0, len(s), -1
        while idx<n:
            flag += 1
            while idx<n and s[idx]=='1':
                idx += 1
            while idx<n and s[idx]=='0':
                idx += 1
        return not flag

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        # 0 1 2
        unvis, n = set(i for i in range(len(nums) + 1)), len(nums)
        def cntOne(str: s):
            cnt = 0
            for c in s:
                cnt += (c=='1')
            return cnt
        for s in nums:
            cnt = cntOne(s)
            if cnt in unvis:
                unvis.remove(cnt)
        cnt = unvis.pop()
        return "1"*cnt + "0"*(n-cnt)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    void dfs(int &res, int num){
        if(num==0) return;     
        dfs(res, num>>1);
        res = !(num&1) + (res<<1);
    }
    int bitwiseComplement(int n) {
        if(n==0) return 1;
        int res = 0;
        dfs(res, n);
        return res;
    }
};