1. 最多可以摧毀的敵人城堡數(shù)目

• 題意

• 思路

兩層循環(huán)，太low了

用一個(gè)變量記錄前一個(gè)位置

• 代碼

class Solution {
public:
    int captureForts(vector<int>& forts) {
        int ans = 0, pre = -1;
        for (int i = 0; i < forts.size(); i++) {
            if (forts[i] == 1 || forts[i] == -1) {
                if (pre >= 0 && forts[i] != forts[pre]) {
                    ans = max(ans, i - pre - 1);
                }
                pre = i;
            }
        }
        return ans;
    }
};

2. 到達(dá)終點(diǎn)的數(shù)字

• 題意
  

• 思路

• 代碼

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int s = 0, n = 0;
        while (s < target || (s - target) % 2) // 沒有到達(dá)（越過）終點(diǎn)，或者相距奇數(shù)
            s += ++n;
        return n;
    }
};

3. 單詞的壓縮編碼

• 題意

• 思路

• 代碼

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> good(words.begin(), words.end());
        for (const string& word: words) {
            for (int k = 1; k < word.size(); ++k) {
                good.erase(word.substr(k));
            }
        }

        int ans = 0;
        for (const string& word: good) {
            ans += word.size() + 1;
        }
        return ans;
    }
};

• 思路2

去找到是否不同的單詞具有相同的后綴，我們可以將其反序之后插入字典樹中。例如，我們有 “time” 和 “me”，可以將 “emit” 和 “em” 插入字典樹中。

然后，字典樹的葉子節(jié)點(diǎn)（沒有孩子的節(jié)點(diǎn)）就代表沒有后綴的單詞，統(tǒng)計(jì)葉子節(jié)點(diǎn)代表的單詞長度加一的和即為我們要的答案。

• 代碼

class TrieNode{
    TrieNode* children[27];
    public:
    int count;
    TrieNode() {
        for (int i = 0;i < 26;i ++) 
            children[i] = NULL;
        count = 0;
    }
    TrieNode* get(char c) {
        if (children[c-'a'] == NULL) {
            children[c-'a'] = new TrieNode();
            count ++;
        }
        return children[c-'a'];
    }
};
class Solution{
    public:
    int minimumLengthEncoding(vector<string>& words) {
        TrieNode* trie = new TrieNode();
        unordered_map<TrieNode*,int> nodes;
        for (int i = 0;i < (int)words.size();i ++) {
            string word = words[i];
            TrieNode* cur = trie;
            for (int j = word.length()-1;j >= 0;j --) 
                cur = cur->get(word[j]);
            nodes[cur] = i;
        }
        int ans = 0;
        for (auto& [node,idx] : nodes) {
            if (node->count == 0) {
                ans += words[idx].length() + 1;
            }
        }
        return ans;
    }
};

字典樹

4. 逃脫阻礙著

• 題意

• 思路

另：

• 代碼

class Solution {
public:
    int manhattanDistance(vector<int>& point1, vector<int>& point2) {
        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]);
    }

    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        vector<int> source(2);
        int distance = manhattanDistance(source, target);
        for (auto& ghost : ghosts) {
            int ghostDistance = manhattanDistance(ghost, target);
            if (ghostDistance <= distance) {
                return false;
            }
        }
        return true;
    }
};

5. 尋找兩個(gè)正序數(shù)組的中位數(shù) O ( l o g ( m + n ) ) O(log(m+n)) O(log(m+n))

• 題意

• 思路

主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進(jìn)行比較

這里的 “/” 表示整除
s1 中小于等于 pivot1 的元素有 nums1[0 … k/2-2] 共計(jì) k/2-1 個(gè)

• nums2 中小于等于 pivot2 的元素有 nums2[0 … k/2-2] 共計(jì) k/2-1 個(gè)
  ivot = min(pivot1, pivot2)，兩個(gè)數(shù)組中小于等于 pivot 的元素共計(jì)不會(huì)超過 (k/2-1) + (k/2-1) <= k-2 個(gè)
• 這樣 pivot 本身最大也只能是第 k-1 小的元素
  pivot = pivot1，那么 nums1[0 … k/2-1] 都不可能是第 k 小的元素。把這些元素全部 “刪除”，剩下的作為新的 nums1 數(shù)組
• 如果 pivot = pivot2，那么 nums2[0 … k/2-1] 都不可能是第 k 小的元素。把這些元素全部 “刪除”，剩下的作為新的 nums2 數(shù)組
  們 “刪除” 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去刪除的數(shù)的個(gè)數(shù)

• 代碼

class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 邊界情況
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }
            // 正常情況
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

6. 正則表達(dá)式匹配

• 題意

• 思路

點(diǎn)號通配符其實(shí)很好實(shí)現(xiàn)，s 中的任何字符，只要遇到 . 通配符，無腦匹配就完事了。主要是這個(gè)星號通配符不好實(shí)現(xiàn)，一旦遇到 * 通配符，前面的那個(gè)字符可以選擇重復(fù)一次，可以重復(fù)多次，也可以一次都不出現(xiàn)，這該怎么辦？

對于這個(gè)問題，答案很簡單，對于所有可能出現(xiàn)的情況，全部窮舉一遍，只要有一種情況可以完成匹配，就認(rèn)為 p 可以匹配 s。那么一旦涉及兩個(gè)字符串的窮舉，我們就應(yīng)該條件反射地想到動(dòng)態(tài)規(guī)劃的技巧了。

• 代碼

待補(bǔ)

7. 一個(gè)圖中聯(lián)通三元組的最小度數(shù)

• 題意

待補(bǔ)

8. 只出現(xiàn)一次的數(shù)字Ⅱ 位運(yùn)算

• 題意

給你一個(gè)整數(shù)數(shù)組 nums ，除某個(gè)元素僅出現(xiàn) 一次 外，其余每個(gè)元素都恰出現(xiàn) **三次 。**請你找出并返回那個(gè)只出現(xiàn)了一次的元素。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法且使用常數(shù)級空間來解決此問題。

• 思路

• 代碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

9. 數(shù)字范圍按位與

• 題意

給你兩個(gè)整數(shù) left 和 right ，表示區(qū)間 [left, right] ，返回此區(qū)間內(nèi)所有數(shù)字 按位與 的結(jié)果（包含 left 、right 端點(diǎn)）。

• 思路

m和n的二進(jìn)制串的最長公共前綴

• 代碼

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            // 抹去最右邊的 1
            n = n & (n - 1);
        }
        return n;
    }
};

Brian Kernighan 算法

10. 階乘后的零

• 題意

• 思路

• 代碼

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

11. 最深葉節(jié)點(diǎn)的最近公共祖先

• 題意

給你一個(gè)有根節(jié)點(diǎn) root 的二叉樹，返回它最深的葉節(jié)點(diǎn)的最近公共祖先。

• 思路

• 代碼

/**
 * 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:
    pair<TreeNode*,int> f(TreeNode* root) {
        if (!root) {
            return {root,0};
        }

        auto left = f(root->left);
        auto right = f(root->right);

        if (left.second > right.second) {
            return {left.first,left.second+1};
        }

        if (left.second < right.second) {
            return {right.first,right.second+1};
        }

        return {root,left.second+1};
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return f(root).first;
    }
};

12. 連續(xù)整數(shù)求和

• 題意

• 思路

• 代碼

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;
        int bound = 2 * n;
        for (int k = 1; k * (k + 1) <= bound; k++) {
            if (isKConsecutive(n, k)) {
                ans++;
            }
        }
        return ans;
    }
  
    bool isKConsecutive(int n, int k) {
        if (k % 2 == 1) {
            return n % k == 0;
        } else {
            return n % k != 0 && 2 * n % k == 0;
        }
    }
};

13. 構(gòu)造最長非遞減子數(shù)組

• 題意

• 思路

動(dòng)態(tài)規(guī)劃

• 代碼

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int ans = 1, n = nums1.size();
        vector<vector<int>> dp(n, vector<int>(2, 1));
        for (int i = 1; i < n; ++i) {
            if (nums1[i] >= nums1[i-1]) dp[i][0] = dp[i-1][0] + 1;
            if (nums1[i] >= nums2[i-1]) dp[i][0] = max(dp[i][0], dp[i-1][1] + 1);
            if (nums2[i] >= nums1[i-1]) dp[i][1] = dp[i-1][0] + 1;
            if (nums2[i] >= nums2[i-1]) dp[i][1] = max(dp[i][1], dp[i-1][1] + 1);
            ans = max(ans, max(dp[i][0], dp[i][1]));
        }
        return ans;
    }
};

14. 等值距離和

• 題意

• 思路

分組+前綴和

• 代碼

class Solution {
public:
    vector<long long> distance(vector<int> &nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; ++i)
            groups[nums[i]].push_back(i); // 相同元素分到同一組，記錄下標(biāo)

        vector<long long> ans(n);
        long long s[n + 1];
        s[0] = 0;
        for (auto &[_, a]: groups) {
            int m = a.size();
            for (int i = 0; i < m; ++i)
                s[i + 1] = s[i] + a[i]; // 前綴和
            for (int i = 0; i < m; ++i) {
                long long target = a[i];
                long long left = target * i - s[i]; // 藍(lán)色面積
                long long right = s[m] - s[i] - target * (m - i); // 綠色面積
                ans[target] = left + right;
            }
        }
        return ans;
    }
};

15. 使數(shù)組元素全部相等的最少操作次數(shù)

• 題意

• 思路

• 代碼

class Solution {
public:
    vector<long long> minOperations(vector<int> &nums, vector<int> &queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long sum[n + 1]; // 前綴和
        sum[0] = 0;
        for (int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + nums[i];

        int m = queries.size();
        vector<long long> ans(m);
        for (int i = 0; i < m; ++i) {
            int q = queries[i];
            long long j = lower_bound(nums.begin(), nums.end(), q) - nums.begin();
            long long left = q * j - sum[j]; // 藍(lán)色面積
            long long right = sum[n] - sum[j] - q * (n - j); // 綠色面積
            ans[i] = left + right;
        }
        return ans;
    }
};

16. 課程表Ⅲ

• 題意

• 思路
  
  ?origin_url=https%3A%2F%2Fcdn.jsdelivr.net%2Fgh%2Fharder-er%2Fblogimage%40main%2Fimgimage-20230911202337410.png&pos_id=img-SARb3m5Q-2023091120233710.png46

• 代碼

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(),courses.end(),[](const auto& c0,const auto& c1){
            return c0[1] < c1[1];
        });
        priority_queue<int> q;

        int total = 0;
        for (const auto & courses: courses) {
            int ti = courses[0],di = courses[1];
            if (total + ti <= di) {
                total += ti;
                q.push(ti);
            } else if (!q.empty() && q.top() > ti) {
                total -= q.top() - ti;
                q.pop();
                q.push(ti);
            }
        }
        return q.size();
    }
};

17. 安排工作以達(dá)到最大收益

• 題意

• 思路

我們可以以任意順序考慮工人，所以我們按照能力大小排序。

如果我們先訪問低難度的工作，那么收益一定是截至目前最好的。

算法

我們使用 “雙指針” 的方法去安排任務(wù)。我們記錄最大可用利潤 best。對于每個(gè)能力值為 skill 的工人，找到難度小于等于能力值的任務(wù)，并將如結(jié)果中。

• 代碼

1. 排序+線性查找

   class Solution {
   public:
       int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
           const int n = (int)difficulty.size();
           vector<pair<int,int>>jobs(n);
   
           for (int i = 0;i < n;i ++) {
               jobs[i] = make_pair(difficulty[i],profit[i]);
           }
           sort(jobs.begin(),jobs.end());
           sort(worker.begin(),worker.end());
           int ans = 0;
           int idx = 0;int best = 0;
           for (int level:worker) {
               while (idx < n&&level >= jobs[idx].first) {
                   best = max (best,jobs[idx++].second);
               }
               ans += best;
           }
           return ans;
       }
   };
   

   2. 排序+預(yù)處理+二分查找

   class Solution {
   public:
       int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
           const int n = (int)difficulty.size();
           vector<pair<int,int>>jobs(n);
   
           for (int i = 0;i < n;i ++) {
               jobs[i] = make_pair(difficulty[i],profit[i]);
           }
           sort(jobs.begin(),jobs.end());
           int maxPofit = 0;
           for (int i = 0;i < n;i ++) {
               jobs[i].second = max(maxPofit,jobs[i].second);
               maxPofit = jobs[i].second;
           }
           
           sort(worker.begin(),worker.end());
           int ans = 0;
           int idx = 0;int best = 0;
           for (int i = 0;i < worker.size();i ++) {
               int l = -1, r = n;
               while (l + 1 != r) {
                   int mid = (l + r)>>1;
                   if (jobs[mid].first <= worker[i]) {
                       l = mid;
                   } else {
                       r = mid;
                   }
               }
               if (l != -1) {
                   best = max(best,jobs[l].second);
                   ans += best;
               }
           }
           return ans;
       }
   };
   

18. 子串能表示從 1 到 N 數(shù)字的二進(jìn)制串

• 題意

• 思路

• 代碼

class Solution {
public:
    bool help(const string& s,int k,int mi,int ma) {
        unordered_set<int> st;
        int t = 0;
        for (int r = 0;r < s.size();r ++) {
            t = t*2+(s[r] - '0');
            if (r >= k) {
                t -= (s[r-k]-'0')<<k;
            }
            if (r >= k-1&&t >= mi&&t <= ma) {
                st.insert(t);
            }
        }
        return st.size() == ma-mi+1;
    }
    bool queryString(string s, int n) {
        if (n == 1) return s.find('1') != -1;
        int k = 30;
        while ((1<<k) > n) {
            -- k;
        }
        if (s.size() < (1 <<(k-1))+k-1||s.size() < n-(1<<k)+k+1) return false;
        return help(s,k,1<<(k-1),(1<<k)-1)&&help(s,k+1,1<<k,n);
    }
};

19. 最大連續(xù)1的個(gè)數(shù)Ⅱ

• 題意

給定一個(gè)二進(jìn)制數(shù)組 nums 和一個(gè)整數(shù) k，如果可以翻轉(zhuǎn)最多 k 個(gè) 0 ，則返回 數(shù)組中連續(xù) 1 的最大個(gè)數(shù) 。

• 思路

動(dòng)態(tài)規(guī)劃，no，貪心：找到每個(gè)‘1’塊之間的距離，加起來。

• 方法一

  

• 代碼

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> P(n+1);
        for (int i= 1;i <= n;i ++) {
            P[i] = P[i-1] + (1-nums[i-1]);//1變成0，0變成1
        }

        int ans = 0;
        for (int right = 0;right < n; right ++) {
            int left = lower_bound(P.begin(),P.end(),P[right+1]-k)-P.begin();
            ans = max(ans,right - left + 1);
        }
        return ans;
    }
};

• 方法二

文章來源地址http://www.zghlxwxcb.cn/news/detail-698019.html

• 代碼

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0,lsum = 0,rsum = 0;
        int ans = 0;
        for (int right = 0;right < n;right ++) {
            rsum += 1-nums[right];
            while (lsum < rsum - k) {
                lsum += 1-nums[left];
                ++ left;
            }
            ans = max(ans,right - left + 1);
        }
        return ans;
    }
};

到了這里，關(guān)于LeetCode 刷題記錄——從零開始記錄自己一些不會(huì)的的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！