算法題

數據結構

邏輯結構

• 集合結構
• 線性結構
• 樹形結構
• 圖形結構

物理結構

• 順序存儲

  需要分配連續的存儲空間

• 鏈式存儲

  不需要分配連續的存儲空間，每個單元不僅要存數據也要存一個后繼元素的地址

• 哈希存儲

  通過哈希算法計算存儲位置

• 索引存儲

  需要一個索引表

算法題

簡單

1.兩數之和

問題描述：給定一個數組和目標值target，查找數組中和為target的兩個整數，返回兩個整數的索引。
限制：兩個輸入只對應一個答案；不能使用相同的元素。
解法：
雙層遍歷，或者外層遍歷，內層二分查找，時間復雜度為O(nn), O(nlog2n)
首先字典存儲所有鍵值，然后再進行循環查詢target-nums[i]，此時O(n*n)，圈復雜度為 5；兩個循環串行
也是使用字典，但是使用一個循環，首先查詢字典中是否存在target-nums[i]鍵值，如果存在直接，返回索引；如果不存在，插入。相比于第二種方法好處是避免了另外起一個循環去存字典，而且能夠避免使用相同的元素。

// 哈希表法
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> tempMap;
        for (int i = 0; i < nums.size(); ++i) {
            if (tempMap.count(target - nums[i]) != 0) {
                return {tempMap[target - nums[i]], i};
            }
            tempMap[nums[i]] = i;
        }
        return {};
    }
};

2235.兩整數相加

輸入：兩個整數；輸出：兩數之和；限制條件：無
思路：直接返回兩數之和，使用constexpr直接使用編譯時運算

class Solution { 
public: 
 // constexpr是c++17特性
 constexpr int sum(int num1, int num2) { 
 return num1 + num2; 
 } 
};

1929.數組串聯

輸入：一個數組；輸出：生成一個新的數組；限制條件：新的數組為兩個輸入數組的串聯A->AA
思路：直接向后插入
法一：更省空間

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            nums.push_back(nums[i]);l
        }
        return nums;
    }
};

法二：感覺更好

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        vector<int> ans(nums);
        copy(nums.begin(),nums.end(),back_inserter(ans));
        return ans;
    }
};

771.寶石與石頭

輸入：寶石字符串，石頭字符串，都是字母；輸出：寶石數量；限制：字母區分大小寫。
思路：1. 兩層遍歷O(m+n)，不可取
先將寶石字符串存為哈希值，然后遍歷石頭，計數，O(m+n)

1480.一維數組動態和

輸入：一個數組；輸出：一個數組；限制：[1,2,3,4]->[1,3,6,10]
思想：
兩層遍歷
滾動數組更新，每一個元素都是前幾個元素的和，直接在原數組上累加，每次元素都加上前一個元素，前一個元素已經是它之前元素的和了。需要一個哨兵變量。
解法：

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

709.轉換成小寫字母

輸入：一個字符串，全是字母；輸出：一個字符串；限制：所有字母都轉換為小寫字母

class Solution { 
public: 
 string toLowerCase(string s) { 
 for_each(s.begin(),s.end(),[](auto& item){item = tolower(item);}); 
 return s; 
 } 
};

1672.最富有資產總數

輸入：一個mxn數組accounts，accounts[i][j]代表第i個人在第j家銀行的資產額度
輸出：最富有的資產總數
思路：
哨兵：兩層遍歷，使用accumulator縮短代碼量，計算每一個數組的和，用一個變量保存最大值即可。

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxCount = 0;
        for (int i = 0; i < accounts.size(); ++i) {
            // accumulate累加計算，從值0開始
            maxCount = max(maxCount, accumulate(accounts[i].begin(),accounts[i].end(),0)); 
        }
        return maxCount;
    }
};

66.加一

輸入：一個數組，存儲的是一個整數的每一位，每一位在0~9之間
輸出：加一之后的，數組
限制：除0之外無前導0
思路：
其實就是向前傳遞進位，但是要注意999->1000，需要添加1
所以，先反轉數組，則多余的進位只需要壓入1即可。因為不知道進位有多少次，所以使用while循環進行，其實就是兩數加法

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        reverse(digits.begin(), digits.end());
        int sum = digits[0] + 1;
        digits[0] = sum % 10;
        int carry = sum / 10;
        int i = 1;
        while (carry > 0) {
            if (i == digits.size()) {
                digits.push_back(carry);
                break;
            }
            sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
            i++;
        }
        reverse(digits.begin(), digits.end());
        return digits;
    }
};

724.尋找數組中心下標

問題描述：尋求數組中心下標，其左側所有元素和等價于右側所有元素和。
輸入：一個整數數組，每個元素在-1000~1000之間
輸出：數組中心下標
思路：
1、遍歷數組，使用accumulate函數分別對左右元素加和，然后求是否相等即可。沒找到默認返回-1；初始即可設置index=-1;O(n)，圈復雜度為2，
456ms。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int index = -1; // 默認返回下標-1
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            int lnum = accumulate(nums.begin(), it, 0);
            int rnum = accumulate(it + 1, nums.end(), 0);
            if (lnum == rnum) {
                index = it - nums.begin();
                break;
            }
        }
        return index;
    }
};

2、分別利用兩個循環從正反兩個方向進行一維動態數組求和，然后再采用一個循環，進行比較即可, 4ms。2

中等

198.數組輪轉

問題描述：要求數組向后進行輪轉，例如[1,2,3,4,5,6,7]，向后輪轉3位，變為[5,6,7,1,2,3,4]
輸入：一個數組，一個整數代表輪轉位數
輸出：無返回值
思路：
1、首先避免多余的輪轉操作，先計算最小的k，然后先前插入，但是這樣帶來的后果是會產生begin(), begin()+k元素的移位操作，超時作法：這種超時是由移位操作帶來的

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        while(k > 0) {
            int tmp = nums.back();
            nums.pop_back();
            nums.insert(nums.begin(), tmp);
            k--;
        }
    }

2、避免移位操作的做法：利用一個額外數組存儲元素，然后將更新后的元素按順序復制到新的數組中，然后對數組進行交換。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> fnums(nums);
        k %= nums.size();
        copy(fnums.end()-k, fnums.end(), nums.begin());
        copy(fnums.begin(), fnums.end()-k, nums.begin() + k);
    }
};

swap可以交換兩個容器

48.旋轉圖像

問題描述：圖像順時針旋轉90度
輸入：一個矩陣
輸出：無
限制：原位旋轉
思路：這道題的思路其實比較簡單主要是需要看出，要將第一行旋轉到最后一列，第二列旋轉到倒數第二列。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        vector<vector<int>> tmpMatrix(matrix);
        int m = tmpMatrix.size(), n = tmpMatrix[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[j][n -1 -i] = tmpMatrix[i][j];
            }
        }
    }
};

6.Z字型變換

算術評級：4

將一個給定字符串 s 根據給定的行數 numRows ，以從上往下、從左到右進行 Z 字形排列。
比如輸入字符串為 "PAYPALISHIRING" 行數為 3 時，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的輸出需要從左往右逐行讀取，產生出一個新的字符串，比如："PAHNAPLSIIGYIR"。
請你實現這個將字符串進行指定行數變換的函數：
string convert(string s, int numRows);
示例 1：
輸入：s = "PAYPALISHIRING", numRows = 3
輸出："PAHNAPLSIIGYIR"
示例 2：
輸入：s = "PAYPALISHIRING", numRows = 4
輸出："PINALSIGYAHRPI"
解釋：
P I N
A L S I G
Y A H R
P I
示例 3：

輸入：s = "A", numRows = 1
輸出："A"

class Solution {
public:
    string convert(string s, int numRows) {
        // 考慮到字符串可能只有1個
        if (s.size() == 1) return s;

        // 用一個容器存儲，每行的字符串，可能會出現行數比字符串長的情況
        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        for (auto c : s) {
            // 先完成將字符放進去的邏輯
            rows[currentRow] += c;
            // 處理邊界
            if ( currentRow == 0 or currentRow == numRows -1 ) {
                goingDown = !goingDown;
            }
            // 以方向轉變做判斷，確定下一行行號
            currentRow = goingDown? ++currentRow : --currentRow;
        }

        // 生成結果字符串
        // string result;
        // for (auto item : rows) {
        //     result += item;
        // }
        string result = accumulate(rows.begin(), rows.end(), string());
        return result;
        
    }
};

7.整數反轉

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        int max_div_10 = INT_MAX / 10; // 214748364
        
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            // 檢查是否溢出
            if (rev > max_div_10 || rev < (-1 * max_div_10)) {
                return 0;
            }
            
            rev = rev * 10 + pop;
        }
        
        return rev;
    }
};

8.字符串轉為整數

class Solution {
public:
    int myAtoi(std::string s) {
        int i = 0; // 用于遍歷字符串
        int n = s.size(); // 字符串長度
        int sign = 1; // 符號，默認為正
        long long num = 0; // 使用 long long 防止溢出

        // 1. 跳過前導空格
        while (i < n and s[i] == ' ') {
            i++;
        }

        // 2. 檢查符號
        if (i < n && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }

        // 3. 讀取數字
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0'; // 將字符轉換為數字
            num = num * 10 + digit;

            // 4. 檢查是否超出 32 位整數范圍
            if (num * sign > INT_MAX) {
                return INT_MAX;
            } else if (num * sign < INT_MIN) {
                return INT_MIN;
            }
            i++;
        }

        // 5. 應用符號并返回結果
        return num * sign;
    }
};

困難

10.正則表達式匹配

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        int m = s.size(); // 字符串 s 的長度
        int n = p.size(); // 模式 p 的長度

        // dp[i][j] 表示 s 的前 i 個字符是否能被 p 的前 j 個字符匹配
        std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));

        // 空字符串和空模式匹配
        dp[0][0] = true;

        // 處理模式 p 中的 '*'，使得 dp[i][j] 可以由 dp[i][j-2] 轉移而來
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 動態規劃填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    // '*' 表示前面的字符可以出現零次或多次
                    dp[i][j] = dp[i][j - 2]; // '*' 表示前面的字符出現零次
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j]; // '*' 表示前面的字符出現多次
                    }
                } else if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    // 當前字符匹配
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
};