程式員面試金典 01刷題回憶錄

01.01 判斷字符是否唯一

實作一個演算法，確定一個字串 s 的所有字符是否全都不同，

示例 1：

輸入: s = “leetcode”
輸出: false
示例 2：

輸入: s = “abc”
輸出: true
限制：

0 <= len(s) <= 100
如果你不使用額外的資料結構，會很加分，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/is-unique-lcci
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

class Solution {
public:
    bool isUnique(string astr) {
        int x = 0;   //如果大小寫字母都有，應該要用long 型別了
        for(int i = 0; i < astr.size(); i++) {
            if(x & (1 << (astr[i] - 'a'))) return false;
            else x |= (1 << (astr[i] - 'a'));
        }
        return true;
        
    }
};

考察的是位運算，一個int是32個位元組，而小寫字母總共有26個，
&是邏輯與運算子，|是邏輯或運算子

01.02 判斷是否互為字符重排

用哈希表很簡單

01.03 URL化

URL化，撰寫一種方法，將字串中的空格全部替換為%20，假定該字串尾部有足夠的空間存放新增字符，并且知道字串的“真實”長度，（注：用Java實作的話，請使用字符陣列實作，以便直接在陣列上操作，）

示例 1：

輸入："Mr John Smith ", 13
輸出：“Mr%20John%20Smith”
示例 2：

輸入：" “, 5
輸出：”%20%20%20%20%20"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/string-to-url-lcci
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

class Solution {
public:
    string replaceSpaces(string S, int length) {
     int count=0;
     for(int i=0;i<length;i++)
     {
         if(S[i]==' ')  count++;
     }
     int oldindex=length-1,newindex=oldindex+2*count;  //因為是索引，所以要-1
     S=S.substr(0,newindex+1);    //在原陣列里修改...
     while(oldindex<newindex)
     {
         if(S[oldindex]==' ')
         {
             S[newindex--]='0';
             S[newindex--]='2';
             S[newindex--]='%';
             oldindex--;
         }
         else
             S[newindex--]=S[oldindex--];
     }
     return S;

    }
};

這個主要是從后往前對字串進行操作

01.04 回文排列

還是哈希表

01.05 一次編輯

很普通，順著邏輯寫就行

01.06 字串壓縮

字串壓縮，利用字符重復出現的次數，撰寫一種方法，實作基本的字串壓縮功能，比如，字串aabcccccaaa會變為a2b1c5a3，若“壓縮”后的字串沒有變短，則回傳原先的字串，你可以假設字串中只包含大小寫英文字母（a至z），

示例1:

輸入：“aabcccccaaa”
輸出：“a2b1c5a3”
示例2:

輸入：“abbccd”
輸出：“abbccd”
解釋：“abbccd"壓縮后為"a1b2c2d1”，比原字串長度更長，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/compress-string-lcci
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

class Solution {
public:
    string compressString(string S) {
        string res="";
        int len =S.size();
        int num=1;
        for(int i=1;i<len+1;i++){
            if(S[i]==S[i-1])num++;
            else{
                res+=S[i-1]+to_string(num);
                num=1;
            }
        }
        return res.size()>=S.size()?S:res;
    }
};

注意幾點
1.比如string a=“asdf”; a.size()為4，是可以訪問a[4]的，訪問結果是’\0’,但是不能訪問a[5].
2.注意int轉string的函式 to_string()
3.代碼中是從下標1開始進行的回圈，最后一次回圈，比較的是’\0’不等于字串的最后一個，

01.07 旋轉矩陣

給你一幅由 N × N 矩陣表示的影像，其中每個像素的大小為 4 位元組，請你設計一種演算法，將影像旋轉 90 度，

不占用額外記憶體空間能否做到？

示例 1:

給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋轉輸入矩陣，使其變為:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:

給定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋轉輸入矩陣，使其變為:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotate-matrix-lcci
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

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

            }
        }
    }
};

用C++17 寫的，主要是用到了tie和make_tuple()
當然也可以用數學，先進行水平翻轉，再根據主對角線交換兩側，也可以，

01.08 零矩陣

撰寫一種演算法，若M × N矩陣中某個元素為0，則將其所在的行與列清零，

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if (flag_col0) {
                matrix[i][0] = 0;
            }
        }
    }
};

主要是空間復雜度為O(1)很爽
讓第0行和第0列作為判0標記
同時這也導致了for回圈要從最后一行往前跑
當然別忘記第0列的特殊地位

01.09 字串輪轉

字串輪轉，給定兩個字串s1和s2，請撰寫代碼檢查s2是否為s1旋轉而成（比如，waterbottle是erbottlewat旋轉后的字串），

示例1:

輸入：s1 = “waterbottle”, s2 = “erbottlewat”
輸出：True
示例2:

輸入：s1 = “aa”, s2 = “aba”
輸出：Fals

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/string-rotation-lcci
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

原來字串的輪轉是這個意思，可以輕松的用find找到答案

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
         return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;

    }
};

s1和s2的地位是等價的，