Bo2SS

Bo2SS

首頁封存

4 Leetcode題目講解

#计算机#编程算法#海贼班71
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
這是一個關於Leetcode題目的解釋文章，包含了四個題目的解法和思路。第一個題目是整數反轉，解法中提到了兩種判斷溢出的方式。第二個題目是回文數，解法中提到了翻轉一半數字的方法。第三個題目是羅馬數字轉整數，解法使用了switch...case...語句。最後一個題目是最長公共前綴，解法使用了遍歷字符串並比較的方法。

LC-7：整數反轉#

  • 圖片

  • 思路

    • 負數無需額外判斷，邏輯一致
    • 主要判斷 (* 10 操作) 溢出情況，兩種方式
      • ⭐都很巧妙
      • 方式一：用 long long 存翻轉的數字，最後轉 int 判等判斷是否溢出
      • 方式二：翻轉時，每次加一位時判斷是否溢出
        • 與 INT_MAX 比：【已大於 INT_MAX/10】或者【等於 INT_MAX/10 且要加的數 > 7】
        • 與 INT_MIN 比：【已小於 INT_MIN/10】或者【等於 INT_MIN/10 且要加的數 <-8】

  • 代碼

    • 方式一：用 long long
class Solution {
public:
    int reverse(int x) {
        // 個人解答
        // 不需要考慮負號
        long long t = 0;
        while (x) {
            t = t * 10 + x % 10;
            x /= 10;
        }
        // 判斷結果是否在int範圍內
        return int(t) == t ? t : 0;
    }
};
    • 方式二：加位時判斷
class Solution {
public:
    int reverse(int x) {
        // 官方解答
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;  // 每次要加的個位數，提前算用來判斷溢出
            x /= 10;
            // 對應最大值INT_MAX
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            // 對應最小值INT_MIN
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}
      • 要加的個位數 pop 提前算

LC-9：回文數#

  • 圖片

  • 思路

    • 回文數一定不会溢出，因为它就等于它本身
    • ⭐翻轉一半數字
      • 不需要考慮溢出
      • 但要記得考慮奇數位的情況！
    • 前期可以排除【負數】以及【大於 0 的以 0 結尾的數】
    • PS：轉字符串的方式
      • 可以使用 C++ 裡的 string 類，配合 to_string ()
      • 雙指針前後判等即可
string  str = to_string(x);
  • 代碼
class Solution {
public:
    bool isPalindrome(int x) {
        // 【負數】以及【大於0的以0結尾的數】直接出局
        if (x < 0 || x % 10 == 0 && x != 0) return false;
        int rev = 0;
        // 只翻轉一半，也不用考慮溢出問題了
        while (rev < x) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        // 注意考慮奇數位情況
        return rev == x || rev / 10 == x;
    }
};

LC-13：羅馬數字轉整數#

  • 圖片
  • 圖片

  • 思路

    • 涉及加法和減法，用 switch...case... 即可
    • 順序遍歷字符串，對於特殊字符再加一層判斷即可

  • 代碼

class Solution {
public:
    int romanToInt(string s) {
        int ans = 0;
        // 從左到右順序遍歷
        for (int i = 0; i < s.size(); i++) {
            // 判斷情況很多，使用switch...case...
            switch (s[i]) {
                // 先考慮樸素情況
                case 'V' :
                    ans += 5;
                    break;
                case 'L' :
                    ans += 50;
                    break;
                case 'D' :
                    ans += 500;
                    break;
                case 'M' :
                    ans += 1000;
                    break;
                case 'I' :
                    // i + 1會不會溢出？不會，字符串末尾有'\0'
                    if (s[i + 1] == 'V') {
                        ans += 4;
                        i++;  // 手動多加一次
                    } else if (s[i + 1] == 'X') {
                        ans += 9;
                        i++;
                    } else {
                        ans += 1;
                    }
                    break;  // 記得break
                case 'X' :
                    if (s[i + 1] == 'L') {
                        ans += 40;
                        i++;
                    } else if (s[i + 1] == 'C') {
                        ans += 90;
                        i++;
                    } else {
                        ans += 10;
                    }
                    break;
                case 'C' :
                    if (s[i + 1] == 'D') {
                        ans += 400;
                        i++;
                    } else if (s[i + 1] == 'M') {
                        ans += 900;
                        i++;
                    } else {
                        ans += 100;
                    }
                    break;
            }
        }
        return ans;
    }
};
    • i + 1 會不會溢出？不會，字符串末尾有 '\0'

LC-14：最長公共前綴#

  • 圖片

  • 思路

    • 拿此時的公共前綴與下一個字符串比較，更新公共前綴
      • 初始公共前綴為第一個字符串
      • 中途如果已經為空了，直接返回空
      • 直到遍歷完所有字符串
      • 需有一個變量存儲一次比較後的公共前綴

  • 代碼

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";  // 按照慣例，先判斷空
        string ans = strs[0];  // 答案初始化為第1個字符串
        // 從第二個字符串開始遍歷
        for (int i = 1; i < strs.size(); i++) {
            string t = ans;  // 存儲此時公共前綴 t，不能直接拿ans去遍歷！
            ans = "";  // 記錄一次比較後的公共前綴
            // 長度小於【要遍歷的字符串長度】和【此時公共前綴】的長度
            for (int j = 0; j < strs[i].size() && j < t.size(); j++) {
                if (strs[i][j] == t[j]) {
                    ans += t[j];
                } else {
                    break;
                }
            }
            if (ans == "") {
                break;
            }
        }
        return ans;
    }
};
    • 先判斷空數組
    • 需有新變量存儲上次的公共前綴

LC-26：刪除排序數組中的重複項#

  • 圖片
  • 圖片

  • 思路

    • 已排序，原地修改
    • 雙指針
      • 存值的指針 + 遍歷數組的指針
      • 兩個指針的值
        • 不一樣，則將值存在前一個指針，並且兩個指針一起往後走
        • 一樣，則只走後一個指針

  • 代碼

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        // 存儲指針 p、快指針 i
        int p = 1;  // 第0個數肯定存在
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1]) {
                nums[p] = nums[i];
                p++;
                // nums[p++] = nums[i];
            }
        }
        return p;
    }
};
    • 雙指針～

LC-27：移除元素#

  • 圖片

  • 思路

    • 與LC-26 題類似，甚至更簡單
    • 同樣兩個指針
      • 相等則快指針往後走
      • 不相等則存儲指針存值，並且一起往後走

  • 代碼

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0) return 0;
        int p = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[p++] = nums[i];  // 不等於時就存值
            }
        }
        return p;
    }
};

LC-35：搜索插入位置#

  • 圖片

  • 思路

    • 已排序
    • 找到目標值索引，或找按順序的插入位置
    • 0000011111111 特殊二分！

  • 代碼

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 特殊情況：目標值比最大數還大
        if (nums[nums.size() - 1] < target) {
            return nums.size();
        }
        // 特殊二分：000001111111
        int l = 0, r = nums.size() - 1;
        while (l != r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
};
    • 記得考慮特殊情況：0000000000，提前判斷

LC-38：外觀數列#

  • 圖片
  • 圖片

  • 思路

    • 依次根據前一項求後一項
      • 計數器計數，初始為 1，記得重置為 1
      • 判斷連續了多少個字符，判斷前一個和當前字符是否相等

  • 代碼

class Solution {
public:
    string ans[5] = {"", "1"};  // 第0項不管，第1項是"1"
    // ↑只需要兩個字符串交替存儲
    void func(int s1, int s2) {
        ans[s2] = "";
        int cnt = 1;  // 計數：當前字符連續了多少次
        // cnt初始為1，從第二個字符開始
        for (int i = 1; i < ans[s1].size(); i++) {
            if (ans[s1][i - 1] == ans[s1][i]) {
                cnt++;
            } else {
                ans[s2] += cnt + '0';  // 數字轉字符！
                ans[s2] += ans[s1][i - 1];  // cnt個什麼字符
                cnt = 1;
            }
        }
        // 注意：最後一輪還沒輸出
        ans[s2] += cnt + '0';
        ans[s2] += ans[s1][ans[s1].size() - 1];  // 最後一個字符
    }
    void swap(int *a, int *b) {
        // 掌握交換的寫法
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    // 題目給的函數
    string countAndSay(int n) {
        int a = 1, b = 0;  // 用來交換字符串編號
        for (int i = 2; i <= n; i++) {
            func(a, b);  // 根據前一個字符串ans[a]求後一個ans[b]
            swap(&a, &b);
        }
        return ans[a];
    }
};
    • 可以使用兩個字符串交替記錄
    • 記得數字轉字符
    • 注意最後一輪要單獨輸出

LC-53：最大子序和#

  • 圖片

  • 思路

    • ans [x] = 以 x 結尾的最大連續和
    • ans[x] = max(ans[x - 1] + num[x], num[x])
    • 不需要數組，只需要兩個變量
      • 上一次最大 ans
      • 當前最大 now

  • 代碼

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, now = 0;  // 也可以直接用nums[0]代替INT_MIN
        for (int i = 0; i < nums.size(); i++) {
            now = max(now + nums[i], nums[i]);  // 關鍵，當前可達最大值
            ans = max(ans, now);  // 更新目前最大值
        }
        return ans;
    }
};
    • 處理好 ans 和 now！

LC-66：加一#

  • 圖片

  • 思路

    • 比大數加法還要簡單，不需要翻轉
      • 只需要從後往前判斷進位情況
      • 注意處理最高位進位情況，使用 vector 的 insert 方法

  • 代碼

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        digits[digits.size() - 1]++;
        // 處理加一後每一位的進位即可
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] == 10) {
                digits[i] = 0;
                // 特殊處理最高位的進位 else
                if (i != 0) {
                    digits[i - 1]++;
                } else {
                    digits.insert(digits.begin(), 1);  // O(N)
                    // insert、digit.begin()
                }
            } else {
                break;
            }
        }
        return digits;
    }
};

LC-69：x 的平方根#

  • 圖片

  • 思路

    • 整數二分
      • 例如：求 8 的平方根
      • 遍歷 0 - 8：0123456789
      • 目標是得到 2
      • 所以對應 1110000000 情況

  • 代碼

class Solution {
public:
    int mySqrt(int x) {
        // 111110000
        long long l = 0, r = x;
        while (l != r) {
            // 定義long long
            long long mid = (l + r + 1) / 2;
            if (mid * mid <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};
    • mid * mid 可能溢出，所以統一定義 long long 類型

LC-70：爬樓梯#

  • 圖片

  • 思路

    • 即斐波那契數列
    • 兩種方式：遞歸 + 記憶化；遞推
    • 延伸：可能有大整數類型的；一次可以爬更多的台階

  • 代碼

class Solution {
public:
    int ans[50] = {0, 1, 2};
    int climbStairs(int n) {
        // 函數返回值為int，n=46時，結果會溢出
        // 方式一：遞歸 + 記憶化
        if (ans[n]) {
            return ans[n];
        }
        // 記得保存ans[n]
        return ans[n] = climbStairs(n - 1) + climbStairs(n - 2);
        // 方式二：遞推
        for (int i = 3; i <= n; i++) {
            ans[i] = ans[i - 1] + ans[i - 2];
        }
        return ans[n];
    }
};
    • 根據題意，函數返回的是 int 類型，所以 n 最多到 45，n = 46 時會溢出

LC-88：合併兩個有序數組#

  • 圖片

  • 思路

    • nums1 有足夠大的空間，多出來的空間等於 nums2 的長度
    • 從後往前存遍歷兩個數組，大的從後往前存在 num1 裡
      • ❌若從前往後會覆蓋，還需處理

  • 代碼

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // nums1空間大
        for (int i = m + n - 1; i >= 0; i--) {
            // 從後往前存
            if (m == 0 || n!= 0 && nums2[n - 1] > nums1[m - 1]) {
                // nums2元素存進去
                nums1[i] = nums2[n - 1];
                n--;
            } else {
                // nums1元素存進去
                nums1[i] = nums1[m - 1];
                m--;
            }
        }
    }
};
    • 判斷條件要嚴謹！
    • nums2 的元素存到後面
      • nums1 已經遍歷完了 ，即 m = 0
      • 或者
      • nums2 對應的值大於 nums1 並且【nums2 還沒遍歷完！】👈一定要判斷
        • 即 n!= 0 && nums2 [n - 1] > nums1 [m - 1]
    • 否則，nums1 的元素存到後面

LC-118：楊輝三角#

  • 圖片

  • 思路

    • 每位的值等於上左 + 上的值
    • 給出的樣本中是用 vector 實現，不能使用數組的補 0 大法了！
      • 之後注意 vector 的具體細節

  • 代碼

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //vector 不能像數組那樣留一圈0了，得把每行左右邊界提前處理好
        vector<vector<int> > ans;  // 老標準中<int>後有一個空格
        // 特判
        if (numRows == 0) {
            return ans;
        }
        // 第一行
        ans.push_back({1});
        // 第二行對應i = 1
        for (int i = 1; i < numRows; i++) {
            vector<int> v;  // 先定義一個臨時的vector存這一行
            v.push_back(1);  // 左邊界
            // 第i行除了兩端的1還有i - 1個元素
            for (int j = 1; j < i; j++) {
                v.push_back(ans[i - 1][j - 1] +ans[i - 1][j]);
            }
            v.push_back(1);  // 右邊界
            ans.push_back(v);
        }
        return ans;
    }
};
    • vector 的方法：push_back

LC-121：買賣股票的最佳時機 Ⅰ#

  • 圖片

  • 思路

  • 只買賣一次

    • 遍歷
      • 更新當前最小值：先初始為第一個數
      • 更新答案：【臨時答案】與【當前值 - 當前最小值】作比較
        • 答案初始為 0
      • 輸出答案

  • 代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            // 需要特判，否則下面初始化時的prices[0]不存在會報錯
            return 0;
        }
        int ans = 0, mmin = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            ans = max(ans, prices[i] - mmin);
            mmin = min(mmin, prices[i]);
        }
        return ans;
    }
};
    • 答案 ans 初始為 0，當前最小值 mmin 初始為第一個數 prices [0]
      • 用兩個 m 是為了避免與 C++ 的 min () 函數重名
      • 需要特判，prices 裡可能沒有值
      • vector.size()

LC-122：買賣股票的最佳時機 Ⅱ#

  • 圖片

  • 思路

    • 可以買賣任意次
    • 兩天兩天地考慮，只看相鄰兩天能否賺

  • 代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 分成數個兩天
        // 可加特判
        int ans = 0;
        for (int i = 1; i < prices.size(); i++) {
            // 只要當前這天比前一天股價高
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
};
    • 特判可加可不加，因為 prices.size () 已經限制了循環

LC-136：只出現一次的數字#

  • 圖片

  • 思路

    • 精髓：按位異或
      • 0 ^ x = x
      • x ^ x = 0

  • 代碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i]; 
        }
        return ans;
    }
};

附加知識點#

前綴和#

  • 圖片

  • 快速求解區間和

    • 前綴和數組 sum
    • 區間 [x, y] 的和：sum [y] - sum [x - 1]
    • 數組多開一個 0 位，避免①對應的 sum [1 - 1] 無值

  • 維護額外的數組，避免多次詢問的耗時

思考點#

Tips#

課程速記#

  • 自做：67、119 (參考 118)、125
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。