4、只出现一次的数字 III【分组异或】

class Solution {
public:
    vector singleNumber(vector& nums) {
        int t = nums[0], i=0;
        for(i=1;i>i)&1 == 1) break;
        int a=0,b=0;
        for(auto &c:nums){
            if((c>>i)&1) a^=c;
            else b^=c;
        }
        return vector({a,b});
    }
};

5、丢失的数字

class Solution {
public:
    int missingNumber(vector& nums) {
        int ans=0;
        for(int i=0;i<=nums.size();i++) ans^=i;
        for(auto &c:nums) ans^=c;
        return ans;
    }
};

6、生命游戏

如何做到不用额外的空间，且把所有位置细胞的状态同时改变呢？因为想到只有0和1两个状态，可以用二进制中的第二位来存储变化后的状态。

0000：一开始是死细胞，后来还是死细胞
0101：一开始是活细胞，后来变成死细胞
1010：一开始是死细胞，后来变成活细胞
1111：一开始是活细胞，后来还是活细胞

class Solution {
public:
    void gameOfLife(vector>& board) {
        if (board.empty() || board[0].empty()) return;
        int n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) {
                int live = 0;
                for (int x = max(0, i - 1); x <= min(n - 1, i + 1); x ++ )
                    for (int y = max(0, j - 1); y <= min(m - 1, j + 1); y ++ )
                        if ((x != i || y != j) && (board[x][y] & 1))
                            live ++ ;
                int cur = board[i][j] & 1, next;
                if (cur) {
                    if (live < 2 || live > 3) next = 0;
                    else next = 1;
                } else {
                    if (live == 3) next = 1;
                    else next = 0;
                }
                board[i][j] |= next << 1;
            }

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                board[i][j] >>= 1;
    }
};

7、最大单词长度乘积

class Solution {
public:
    int maxProduct(vector& words) {
        vector state;
        for (auto word: words) {
            int s = 0;
            for (auto c: word)
                s |= 1 << (c - 'a');
            state.push_back(s);
        }

        int res = 0;
        for (int i = 0; i < words.size(); i ++ )
            for (int j = i + 1; j < words.size(); j ++ )
                if ((state[i] & state[j]) == 0)
                    res = max(res, (int)(words[i].size() * words[j].size()));
        return res;
    }
};

8、两整数之和

class Solution {
public:
    int getSum(int a, int b) {
        if(a == 0) return b;
        if(b == 0) return a;
        int sum = a ^ b;
        int carry = unsigned(a & b) << 1;
        return getSum(sum, carry);
    }
};

9、找不同

class Solution {
public:
    char findTheDifference(string s, string t) {
        char ans=0;
        for(auto c:s) ans^=c;
        for(auto c:t) ans^=c;
        return ans;
    }
};

10、数字转换为十六进制数

class Solution {
public:
    string toHex(unsigned int n) {
        if(!n) return "0";
        string ans, nums = "0123456789abcdef";
        while(n){
            ans = nums[n&0xf] + ans;
            n=n>>4;
        }
        return ans;
    }
};

11、汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> t(x^y);int ans = 0;
        for(int i=0;i<32;i++) if(t[i] == 1) ans++;
        return ans;
    }
};

12、数字的补数

class Solution {
public:
    int findComplement(int num) {
        int cnt = 0;
        for (int x = num; x; x >>= 1) cnt ++ ;
        return ~num & ((1ll << cnt) - 1); // 消除高位
    }
};

13、汉明距离总和

class Solution {
public:
    int totalHammingDistance(vector& nums) {
        int n=nums.size(), ans=0;
        for(int i=0;i<32;i++){
            int ones = 0;
            for(auto t:nums){
                if((1ll<

class Solution {
public:
    int find(int n){        
        for(int i=0;i<31;i++){
            if(n >= (1<

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummy = new ListNode(INT_MIN);
        dummy->next = head;
        auto cur = dummy;
        while(cur->next){
            if(cur->next->val >= cur->val){
                cur = cur->next;
            }else{
                auto t = cur->next;
                cur->next = t->next;
                auto pre = dummy;
                while(pre->next->val <= t->val) pre = pre->next;
                t->next = pre->next;
                pre->next = t;
            }
        }
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l, ListNode* r){
        auto dummy = new ListNode(0);
        auto t = dummy;
        while(l && r){
            if(l->val <= r->val){
                t->next = l; l = l->next; t = t->next;
            }else{
                t->next = r; r = r->next; t = t->next;
            }
        }
        while(l) {t->next = l; l = l->next; t = t->next;}
        while(r) {t->next = r; r = r->next; t = t->next;}
        t = dummy->next;
        delete dummy;
        return t;
    }

    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head; //
        auto slow = head; auto fast = head;
        while(fast->next && fast->next->next){ //
            slow = slow->next;
            fast = fast->next->next;
        }    
        fast = slow->next;
        slow->next = nullptr;
        auto l = sortList(head);
        auto r = sortList(fast);
        return merge(l,r);
    }
};

class Solution {
public:
    int nthUglyNumber(int n) {
        auto help = new int[n];
        help[0] = 1;
        int f2,f3,f5;
        f2 = f3 = f5 = 0;
        for(int i=1;i

class Solution {
public:
    int nthSuperUglyNumber(int n, vector& primes) {
        int m = primes.size();
        vector f(m,0);        
        auto help = new int[n];
        help[0] = 1;
        for(int i=1;i

// 归并排序
class Solution {
public:
    void merge(vector&nums,int l1,int l2,int r1,int r2){
        vector temp(r2-l1+1,0);
        int idx = 0, a = l1;
        while(l1<=l2 && r1<=r2){
            if(nums[l1] < nums[r1]) temp[idx++] = nums[l1++];
            else temp[idx++] = nums[r1++];
        }
        while(l1<=l2) temp[idx++] = nums[l1++];
        while(r1<=r2) temp[idx++] = nums[r1++];
        idx = 0;
        while(idx& nums,int l,int r){
        if(l>=r) return;
        int mid = l+r>>1;
        sort_(nums,l,mid); sort_(nums,mid+1,r);
        merge(nums,l,mid,mid+1,r);
    }

    vector sortArray(vector& nums) {
        int n = nums.size();
        if(n > 1) sort_(nums,0,n-1);
        return nums;
    }
};

// 快速排序
class Solution {
public:
    void sort_(vector&nums,int l,int r){
        if(l>=r) return;
        int i=l-1, j=r+1, x = nums[l+r>>1];
        while(ix);
            if(i sortArray(vector& nums) {
        int n = nums.size();
        if(n > 1)
            sort_(nums,0,n-1);
        return nums;
    }
};

class Solution {
public:
    vector relativeSortArray(vector& a, vector& b) {
        unordered_map hash;
        int n = b.size();
        for(int i=0;i

class Solution {
public:
    int maxProduct(vector& nums) {
        int a = INT_MIN, b = INT_MIN;
        for(auto t:nums){
            if(t > a){
                b = a;
                a = t;
            }else if(t>b) b = t;

        }
        return (a-1)*(b-1);
    }
};

class Solution {
public:
    int maxArea(int h, int w, vector& hc, vector& vc) {
        const static int MOD=1e9+7;
        sort(hc.begin(), hc.end()); hc.push_back(h);
        sort(vc.begin(), vc.end()); vc.push_back(w);
        int ht = hc[0], vt = vc[0];
        for(int i=1;i

class Solution {
public:
    vector frequencySort(vector& nums) {
        unordered_map hash;
        for(int t:nums) hash[t]++;
        auto cmp = [&](int x,int y){
            if(hash[x] < hash[y]) return true;
            else if(hash[x] == hash[y]){
                return x>y;
            }else return false;
        };
        sort(nums.begin(),nums.end(),cmp);
        return nums;
    }
};

class Solution {
public:
    int maxWidthOfVerticalArea(vector>& points) {
        sort(points.begin(), points.end());
        const int n = points.size();
        int ans = 0;

        for (int i = 1; i < n; i++)
            if (ans < points[i][0] - points[i - 1][0])
                ans = points[i][0] - points[i - 1][0];

        return ans;
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        vectorA,B;
        int n = num1.size(), m = num2.size();
        for(int i = n-1;i>=0;i--) A.push_back(num1[i] - '0');
        for(int i = m-1;i>=0;i--) B.push_back(num2[i] - '0');
        vector C(m + n);
        for(int i = 0;i=0) res += (C[k--] + '0');
        return res;
    }
};

class Solution {
public:
    double myPow(double x, int m) {
        long long n = m;
        double res = 1;
        bool f = false;
        if(n < 0) {f = true; n = -n;}
        while(n){
            if(n & 1) res *= x;
            x *= x;
            n = n >> 1;
        }
        return f == true ? 1 / res : res;
    }
};

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans;
        vector f(n,0);
        for(int i=0;i=k){
                        f[j] = true;
                        ans += to_string(j+1);
                        break;
                    } k-=t;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string ans;

        for(int i=0,j=0,t=0;t!=0 || i

class Solution {
public:
    // 0 0 0 镜面
    // 0 1 0
    // 0 1 1
    // 0 0 1
    vector grayCode(int n) {
        vector res = vector(1,0);
        while(n--){
            for(int i=res.size()-1;i>=0;i--){
                res[i] *=  2;
                res.push_back(res[i] + 1);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector grayCode(int n) {
        // binary2gray
        vector ans;
        for(int i=0;i>1));
        }
        return ans;
    }
};

class Solution {
public:
    int maxPoints(vector>& points) {
        typedef long double LD;
        int res = 0;
        for(int i=0;i hash;
            for(int j=0;j

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        typedef long long ll;
        ll x = numerator,y = denominator;
        if(x % y == 0) return to_string(x/y);
        string res;
        if((x < 0) ^ (y<0)) res += '-';
        x = abs(x);y = abs(y);
        res += to_string(x / y) + '.'; x %= y;
        unordered_maphash;
        while(x){
            hash[x] = res.size();
            x *= 10;
            res += to_string(x/y);
            x %= y;
            if (hash.count(x)) {
                res = res.substr(0, hash[x]) + '(' + res.substr(hash[x]) + ')';
                break;
            }
        }

        return res;
    }
};

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while(n) res += n / 5, n/=5;
        return res;
    }
};

class Solution {
public:
    string largestNumber(vector& nums) {
        sort(nums.begin(),nums.end(),[](int a,int b)
        {string x = to_string(a),y = to_string(b);return x+y > y+x;});
        string res;
        for(auto&num:nums) res += to_string(num);
        int k = 0;
        while(k+1 < res.size() && res[k] == '0')k++;
        return res.substr(k);
    }
};

class Solution {
public:
    int get(int x){
        int t = 0;
        while(x) t+=(x%10)*(x%10), x/=10;
        return t;
    }

    bool isHappy(int n) {
        int fast = get(n);
        int slow = n;
        while(slow != fast){
            fast = get(get(fast));
            slow = get(slow);
        }
        return fast == 1;
    }
};

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        vector nums;
        while (n) nums.push_back(n % 10), n /= 10;
        reverse(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            int d = nums[i];
            int left = 0, right = 0, p = 1;
            for (int j = 0; j < i; j ++ ) left = left * 10 + nums[j];
            for (int j = i + 1; j < nums.size(); j ++ ) {
                right = right * 10 + nums[j];
                p = p * 10;
            }
            if (d == 0) res += left * p;
            else if (d == 1) res += left * p + right + 1;
            else res += (left + 1) * p;
        }
        return res;
    }
};

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0)
            return false;
        while (num % 2 == 0)
            num /= 2;
        while (num % 3 == 0)
            num /= 3;
        while (num % 5 == 0)
            num /= 5;
        return num == 1;
    }
};

class Solution {
public:
    int countPrimes(int n) {
        vector primes;
        vector f(n+1,false);
        for(int i=2;i

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x1 = ax1, y1 = ay2; int x2 = ax2, y2 = ay1;
        int x1_ = bx1, y1_ = by2; int x2_ = bx2, y2_ = by1;
        ax1 = max(x1,x1_); ay1 = min(y1,y1_);
        ax2 = min(x2,x2_); ay2 = max(y2,y2_);
        int ans = abs((y2 - y1) * (x2 - x1)) + abs((y2_ - y1_) * (x2_ - x1_));
        if(ax1 < ax2 && ay1 > ay2)
            return ans - abs((ax2 - ax1)*(ay2 - ay1));
        else return ans;
    }
};

class Solution {
public:
    int addDigits(int num) {
        if(num < 10) return num;
        int t = 0;
        while(num) t+=num%10, num/=10;
        return addDigits(t);
    }
};

// O(1)
class Solution {
public:
    int addDigits(int num) {
        if(!num) return num;
        return num%9 ? num%9 : 9;
    }
};

class Solution {
public:
    bool canWinNim(int n) {
        return n&3; // n%4 != 0
    }
};

class Solution {
public:
    int bulbSwitch(int n) {
        // 约数个数为奇数个则亮
        // 约数为奇数表明该数为完全平方数
        return sqrt(n);
    }
};

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // lowbit
        return n>0 ? (n&(-n)) == n : false;
    }
};

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467%n == 0; 
    }
};

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n<1) return false;
        while(n){
            if(n == 1) return true;
            if(n%3) return false;
            n/=3;
        }
        return true;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        // 法1:4的整数次幂，等价于 n 是平方数，且 n 的质因子只有2
        // return (n>0) && sqrt(n)*sqrt(n) == n && (!((1<<30)%n));
        
        // // 法2:
        if (num < 0 || num & (num-1)){//check(is or not) a power of 2.
            return false;
        }
        return num & 0x55555555;//check 1 on odd bits
    }
};

class Solution {
public:
    int integerBreak(int n) {
        if(n < 4) return n-1;
        int ans = 1;
        if(n % 3 == 1) ans*=4, n-=4;
        else if(n%3 == 2) ans*=2, n-=2;
        while(n) ans*=3, n-=3;
        return ans;
    }
};

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(!n) return 1;
        n = min(n,10);
        vector f(n);
        f[0] = 9;
        for(int i=1;i

class Solution {
public:
    int gcd(int a,int b){
        if(b == 0) return a;
        return gcd(b, a%b);
    }

    bool canMeasureWater(int a, int b, int t) {
        // 裴蜀定理
        if (t > a + b) return false;
        a = gcd(a,b);
        if(t && t%a == 0) return true;
        else return false;
    }
};

class Solution {
public:
    int integerReplacement(long long n) {
        int ans = 0;
        while(n != 1){
            ans++;
            if((n&3) == 3 && n != 3) n++;
            else if(n&1) n--;
            else n>>=1;
        }
        return ans;
    }
};

typedef long long LL;
class Solution {
public:
    unordered_map dp;
    int integerReplacement(int n) {
        return f(n);
    }

    int f(LL n) {
        if (dp.count(n)) return dp[n];
        if (n == 1) return 0;
        if (n % 2 == 0) return dp[n] = f(n / 2) + 1;
        return dp[n] = min(f(n + 1), f(n - 1)) + 1;
    }
};

class Solution {
public:
    vector fizzBuzz(int n) {
        vector ans;
        for(int i=1;i<=n;i++){
            string t = "";
            if((i%3) == 0) t+="Fizz";
            if((i%5) == 0) t+="Buzz";
            if(t.empty()) t+=to_string(i);
            ans.emplace_back(t);
        }
        return ans;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector& nums) {
        for (int i = nums.size() - 1; i > 0; i -- ) nums[i] -= nums[i - 1];
        int res = 0;
        for(int i=1;i

class Solution {
public:
    string originalDigits(string s) {
        string help[] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
        int idx[] = {0,2,4,3,5,6,1,7,8,9};
        string ans;
        unordered_map hash;
        for(auto c:s) hash[c]++;
        for(int i=0;i<10;i++){
            int ix = idx[i];
            while(true){
                bool f = false;
                for(int j=0;j= 0) hash[help[ix][j]]++;
                        f = true;
                        break;
                    }else {
                        hash[help[ix][j]]--;
                        if(j == help[ix].size()-1) ans+=to_string(ix);
                    }
                }
                if(f) break;
            }
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

class Solution {
public:
    int cal(int pre,int n){
        int tot = 0;
        long long t = pre, k=1;
        while(10*t <= n){
            tot+=k;
            k*=10, t*=10;
        }
        if(t <= n){
            if(n - t < k) tot+=n-t+1;
            else tot+=k;
        }
        return tot;
    }
    int findKthNumber(int n, int k) {
        int prefix = 1;
        while(k>1){
            int sz = cal(prefix,n);
            if(sz >= k){
                prefix*=10;
                k--;
            }else prefix++, k-=sz;
        }
        return prefix;
    }
};

typedef long long ll;

class Solution {
public:
    int arrangeCoins(ll n) {
        // (1+k)*k / 2 = n -> k^2 + k - 2n = 0
        n = n << 3;
        int ans = (sqrt(n + 1) - 1) / 2;
        return ans;
    }
};

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector next(n+1);
        s = ' ' + s;
        for(int i=2,j=0;i<=n;i++){
            while(j && s[i] != s[j+1]) j = next[j];
            if(s[i] == s[j+1]) j++;
            next[i] = j;
        }
        int last = n - next[n];
        return last

class Solution {
public:
    int minMoves2(vector& nums) {
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + n/2, nums.end());
        int t = nums[n/2], ans=0;
        for(auto &c:nums) ans+=abs(c-t);
        return ans;
    }
};

class Solution {
public:
    int islandPerimeter(vector>& grid) {
        int ans = 0;
        int row[] = {-1,0,1,0};
        int col[] = {0,-1,0,1};
        for(int i=0;i=0 && r=0 && c

class Solution {
public:
    vector constructRectangle(int area) {
        int t = sqrt(area);
        while(area%t != 0) t--;
        return {area/t,t};
    }
};

class Solution {
public:
    int kthFactor(int n, int k) {
        vector f1,f2;
        for(int i=1;i*i<=n;i++){
            if(n%i == 0){
                f1.push_back(i);
                if(i*i != n) f2.push_back(n/i);
            }
        }
        if(k <= f1.size()) return f1[k-1];
        
        if(k <= (f1.size() + f2.size())) return f2[f1.size() + f2.size() - k];

        return -1;
    }
};

class Solution {
public:
    int minOperations(int n) {
        int tot = 0, t = n/2;
        while(t--){
            tot+= 2*(--n) - 2*t;
        }
        return tot>>1;
    }
};

class Solution {
public:
    string kthSmallestPath(vector& destination, int k) {
        int zero = destination[1], one = destination[0];
        const int n = one + zero;
        vector> C(n+1,vector(n+1));
        // 计算排列数
        C[0][0] = 1;
        for(int i=1;i<=n;i++){
            C[i][0] = 1;
            for(int j=1;j<=i;j++)
                C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
        string ans;
        for(int i=n;i>=1;i--){
            if(zero == 0) ans+='V';
            else{
                if(k > C[i-1][zero-1]){
                    k-=C[i-1][zero-1];
                    one--;
                    ans+='V';
                }else{
                    ans+='H';
                    zero--;
                }
            }
        }
        return ans;
    }    
};