LeetCode题解-04（位运算、排序、数学）

本文主要是介绍LeetCode题解-04（位运算、排序、数学），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LeetCode题解
- chap-10:位运算
  - 1、二进制求和
  - 2、只出现一次的数字
  - 3、只出现一次的数字 II
  - 4、只出现一次的数字 III【分组异或】
  - 5、丢失的数字
  - 6、生命游戏
  - 7、最大单词长度乘积
  - 8、两整数之和
  - 9、找不同
  - 10、数字转换为十六进制数
  - 11、汉明距离
  - 12、数字的补数
  - 13、汉明距离总和
  - 14、连接连续二进制数字
- chap-11:排序
  - 1、对链表进行插入排序
  - 2、排序链表【×】
  - 3、丑数 II【多路归并】
  - 4、超级丑数
  - 5、排序数组【模板题】
  - 6、数组的相对排序
  - 7、数组中两元素的最大乘积
  - 8、切割后面积最大的蛋糕
  - 9、按照频率将数组升序排序
  - 10、两点之间不包含任何点的最宽垂直面积
- chap-12:数学
  - 1、字符串相乘
  - 2、Pow(x, n)【快速幂】
  - 3、排列序列【康托展开】
  - 4、二进制求和
  - 5、格雷编码
  - 6、直线上最多的点数
  - 7、分数到小数【循环节】
  - 8、阶乘后的零
  - 9、最大数
  - 10、快乐数【快慢指针】
  - 11、数字 1 的个数
  - 12、丑数
  - 13、计数质数【筛质数】
  - 14、矩形面积
  - 15、各位相加
  - 16、Nim 游戏【博弈论】
  - 17、灯泡开关
  - 18、2 的幂
  - 19、3 的幂
  - 20、4的幂
  - 21、整数拆分
  - 22、计算各个位数不同的数字个数
  - 23、水壶问题
  - 24、整数替换
  - 25、Fizz Buzz
  - 26、等差数列划分
  - 27、从英文中重建数字
  - 28、字典序的第K小数字
  - 29、排列硬币
  - 30、重复的子字符串【kmp】
  - 31、最少移动次数使数组元素相等 II
  - 32、岛屿的周长
  - 33、构造矩形
  - 34、n 的第 k 个因子
  - 35、使数组中所有元素相等的最小操作数
  - 36、第 K 条最小指令【组合排列迭代+字典树】

LeetCode题解

chap-10:位运算

1、二进制求和

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<a.size() || j<b.size();){
            if(i<a.size()) t+=a[i++]-'0';
            if(j<b.size()) t+=b[j++]-'0';
            ans += ((t%2) + '0');
            t/=2;
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

2、只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto &c:nums) ans^=c;
        return ans;
    }
};

3、只出现一次的数字 II

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i=0;i<32;i++){
            int sum=0;
            for(int j=0;j<nums.size();j++){
                sum+=(nums[j]>>i)&1;
            }
            ans += ((sum%3)<<i);
        }
        return ans;
    }
};

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

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

5、丢失的数字

class Solution {
public:
    int missingNumber(vector<int>& 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<vector<int>>& 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<string>& words) {
        vector<int> 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<int>& nums) {
        int n=nums.size(), ans=0;
        for(int i=0;i<32;i++){
            int ones = 0;
            for(auto t:nums){
                if((1ll<<i)&t) ones++;
            }
            ans+=ones*(n-ones);
        }
        return ans;
    }
};

14、连接连续二进制数字

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

    int concatenatedBinary(int n) {
        const static int N=1e9+7;
        long long ans = 0;
        for(int i=1;i<=n;i++){
            ans = ans%N;
            int high=find(i);
            ans<<=high;
            ans+=i;
        }
        int t = ans%N;
        return t;
    }
};

[Go Back~~](# LeetCode题解)

chap-11:排序

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

2、排序链表【×】

/**
 * 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);
    }
};

3、丑数 II【多路归并】

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<n;i++){
            help[i] = min(min(help[f2]*2,help[f3]*3),help[f5]*5);
            if(help[f2]*2 == help[i]) f2++;
            if(help[f3]*3 == help[i]) f3++;
            if(help[f5]*5 == help[i]) f5++;
        }
        return help[n-1];
    }
};

4、超级丑数

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int m = primes.size();
        vector<int> f(m,0);        
        auto help = new int[n];
        help[0] = 1;
        for(int i=1;i<n;i++){
            int t = INT_MAX;
            for(int j=0;j<m;j++) t = min(help[f[j]]*primes[j],t);
            help[i] = t;
            for(int j=0;j<m;j++){
                if(t == help[f[j]]*primes[j]) f[j]++;
            }
        }
        return help[n-1];
    }
};

5、排序数组【模板题】

// 归并排序
class Solution {
public:
    void merge(vector<int>&nums,int l1,int l2,int r1,int r2){
        vector<int> 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<temp.size()) nums[a++] = temp[idx++];
    }

    void sort_(vector<int>& 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<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        if(n > 1) sort_(nums,0,n-1);
        return nums;
    }
};

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

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

6、数组的相对排序

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& a, vector<int>& b) {
        unordered_map<int,int> hash;
        int n = b.size();
        for(int i=0;i<n;i++) hash[b[i]]=i;
        auto cmp = [&](int x,int y){
            int t1 = n+x;
            int t2 = n+y;
            if(hash.count(x)) t1 = hash[x];
            if(hash.count(y)) t2 = hash[y];
            return t1<t2;
        };
        sort(a.begin(),a.end(),cmp);
        return a;
    }
};

7、数组中两元素的最大乘积

class Solution {
public:
    int maxProduct(vector<int>& 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);
    }
};

8、切割后面积最大的蛋糕

class Solution {
public:
    int maxArea(int h, int w, vector<int>& hc, vector<int>& 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<hc.size();i++) ht = max(ht, hc[i]-hc[i-1]); 
        for(int i=1;i<vc.size();i++) vt = max(vt, vc[i]-vc[i-1]);
        return (long long)(ht)*vt%MOD;
    }
};

9、按照频率将数组升序排序

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int,int> 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;
    }
};

10、两点之间不包含任何点的最宽垂直面积

class Solution {
public:
    int maxWidthOfVerticalArea(vector<vector<int>>& 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;
    }
};

[Go Back~~](# LeetCode题解)

chap-12:数学

1、字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int>A,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<int> C(m + n);
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++)
                C[i+j] += A[i] * B[j];
        }
        for(int i = 0,t = 0;i<m+n;i++){
            t += C[i];
            C[i] = t % 10;
            t /= 10;
        }
        int k = m+n-1;
        while(!C[k] && k)k--;
        string res;
        while(k>=0) res += (C[k--] + '0');
        return res;
    }
};

2、Pow(x, n)【快速幂】

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

3、排列序列【康托展开】

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

4、二进制求和

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<a.size() || j<b.size();){
            if(i<a.size()) t+=a[i++]-'0';
            if(j<b.size()) t+=b[j++]-'0';
            ans += ((t%2) + '0');
            t/=2;
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

5、格雷编码

class Solution {
public:
    // 0 0 0 镜面
    // 0 1 0
    // 0 1 1
    // 0 0 1
    vector<int> grayCode(int n) {
        vector<int> res = vector<int>(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<int> grayCode(int n) {
        // binary2gray
        vector<int> ans;
        for(int i=0;i<pow(2,n);i++){
            ans.push_back(i^(i>>1));
        }
        return ans;
    }
};

6、直线上最多的点数

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        typedef long double LD;
        int res = 0;
        for(int i=0;i<points.size();i++){
            int x1 = points[i][0], y1 = points[i][1];
            int vs = 0, ss = 0;
            unordered_map<LD,int> hash;
            for(int j=0;j<points.size();j++){
                int x2 = points[j][0], y2 = points[j][1];
                if(x2 == x1 && y2 == y1) ss++;
                else if(x2 == x1) vs++;
                else {
                    LD k = ((LD)y2-y1)/(x2-x1);
                    hash[k]++;
                }
            }            
            for(auto [k,t]:hash) vs = max(vs,t);
            res = max(res, ss + vs);
        }

        return res;
    }
};

7、分数到小数【循环节】

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_map<ll,int>hash;
        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;
    }
};

8、阶乘后的零

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

9、最大数

class Solution {
public:
    string largestNumber(vector<int>& 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);
    }
};

10、快乐数【快慢指针】

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

11、数字 1 的个数

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        vector<int> 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;
    }
};

12、丑数

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

13、计数质数【筛质数】

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;
        vector<bool> f(n+1,false);
        for(int i=2;i<n;i++){
            if(f[i] == false) primes.push_back(i);
            for(int j=0;i*primes[j] < n;j++){
                f[primes[j]*i] = 1;
                if(i%primes[j] == 0) break;
            }
        }
        return primes.size();
    }
};

14、矩形面积

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

15、各位相加

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

16、Nim 游戏【博弈论】

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

17、灯泡开关

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

18、2 的幂

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

19、3 的幂

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

20、4的幂

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

21、整数拆分

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

22、计算各个位数不同的数字个数

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(!n) return 1;
        n = min(n,10);
        vector<int> f(n);
        f[0] = 9;
        for(int i=1;i<n;i++) f[i] = f[i-1]*(10-i);
        int res=0;
        for(auto t:f) res+=t; // n中的每个
        return res+=1; // 0单独计算
    }
};

23、水壶问题

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

24、整数替换

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<LL, int> 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;
    }
};

25、Fizz Buzz

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> 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;
    }
};

26、等差数列划分

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        for (int i = nums.size() - 1; i > 0; i -- ) nums[i] -= nums[i - 1];
        int res = 0;
        for(int i=1;i<nums.size();i++){
            int j=i;
            while(j<nums.size() && nums[j] == nums[i])j++;
            int len = j-i;
            res += len*(len-1)/2;
            i=j-1;
        }
        return res;
    }
};

27、从英文中重建数字

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<char,int> 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<help[ix].size();j++){
                    if(hash[help[ix][j]] == 0){
                        while(--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;
    }
};

28、字典序的第K小数字

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

29、排列硬币

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

30、重复的子字符串【kmp】

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> 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<n && n%last == 0;
    }
};

31、最少移动次数使数组元素相等 II

class Solution {
public:
    int minMoves2(vector<int>& 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;
    }
};

32、岛屿的周长

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int ans = 0;
        int row[] = {-1,0,1,0};
        int col[] = {0,-1,0,1};
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j] == 0) continue;
                for(int k=0;k<4;k++){
                    int r = i+row[k], c = j+col[k];
                    if(r>=0 && r<grid.size() && c >=0 && c<grid[0].size()){
                        if(grid[r][c] == 0) ans++;
                    }else ans++;
                }
            }
        }
        return ans;
    }
};

33、构造矩形

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

34、n 的第 k 个因子

class Solution {
public:
    int kthFactor(int n, int k) {
        vector<int> 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;
    }
};

35、使数组中所有元素相等的最小操作数

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

36、第 K 条最小指令【组合排列迭代+字典树】

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int zero = destination[1], one = destination[0];
        const int n = one + zero;
        vector<vector<int>> C(n+1,vector<int>(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;
    }    
};

[Go Back~~](# LeetCode题解)

这篇关于LeetCode题解-04（位运算、排序、数学）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

LeetCode题解-04（位运算、排序、数学）

LeetCode题解

chap-10:位运算

1、二进制求和

2、只出现一次的数字

3、只出现一次的数字 II

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

5、丢失的数字

6、生命游戏

7、最大单词长度乘积

8、两整数之和

9、找不同

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

11、汉明距离

12、数字的补数

13、汉明距离总和

14、连接连续二进制数字

chap-11:排序

1、对链表进行插入排序

2、排序链表【×】

3、丑数 II【多路归并】

4、超级丑数

5、排序数组【模板题】

6、数组的相对排序

7、数组中两元素的最大乘积

8、切割后面积最大的蛋糕

9、按照频率将数组升序排序

10、两点之间不包含任何点的最宽垂直面积

chap-12:数学

1、字符串相乘

2、Pow(x, n)【快速幂】

3、排列序列【康托展开】

4、二进制求和

5、格雷编码

6、直线上最多的点数

7、分数到小数【循环节】

8、阶乘后的零

9、最大数

10、快乐数【快慢指针】

11、数字 1 的个数

12、丑数

13、计数质数【筛质数】

14、矩形面积

15、各位相加

16、Nim 游戏【博弈论】

17、灯泡开关

18、2 的幂

19、3 的幂

20、4的幂

21、整数拆分

22、计算各个位数不同的数字个数

23、水壶问题

24、整数替换

25、Fizz Buzz

26、等差数列划分

27、从英文中重建数字

28、字典序的第K小数字

29、排列硬币

30、重复的子字符串【kmp】

31、最少移动次数使数组元素相等 II

32、岛屿的周长

33、构造矩形

34、n 的第 k 个因子

35、使数组中所有元素相等的最小操作数

36、第 K 条最小指令【组合排列迭代+字典树】

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯