【CPP】《程序员面试金典》习题(1)——数组与字符串

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false
示例 2：

输入: s = "abc"
输出: true
限制：

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-unique-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //使用标记数组,66.6%
    //遇到标记则直接返回，没出现的字符则设置标记
    bool isUnique(string astr) {
        int unique[128];
        //leetcode需要重置数组适应多组数据
        memset(unique, 0, sizeof(int) * 128);
        for (char& c : astr) {
            if (unique[c] == 1)
                return false;
            else
                unique[c] = 1;
        }
        return true;
    }

    //不使用额外的数据结构, 60.6%
    //用位运算来代替数组，测试（问面试官）得知字符来自a-z
    bool isUnique(string astr) {
        //用int来标识字母情况
        int unique = 0;
        int mask;
        for (char& c : astr) {
            //移位制造掩码
            mask = 1 << (c - 'a');
            if (unique & mask)
                return false;
            else
                unique |= mask;
        }
        return true;
    }

给定两个字符串 s1 和 s2，请编写一个程序
确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = "abc", s2 = "bca"
输出: true
示例 2：

输入: s1 = "abc", s2 = "bad"
输出: false
说明：

0 <= len(s1) <= 100
0 <= len(s2) <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

    //传统的数组打表法,100%
    //加入简单的预筛选加快速度
    bool CheckPermutation(string s1, string s2) {
        //两个数组，记得别忘了sizeof(int)
        int check1[128];
        memset(check1, 0, sizeof(int) * 128);
        int check2[128];
        memset(check2, 0, sizeof(int) * 128);
        //筛选
        if (s1.size() != s2.size())
            return false;
        //打表
        for (auto c : s1)
            check1[(int)c] += 1;
        for (auto c : s2)
            check2[(int)c] += 1;
        //逐位对比
        for (int i = 0; i < 128; i++)
            if (check1[i] != check2[i])
                return false;
        return true;
    }

编写一种方法，将字符串中的空格全部替换为%20。
假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。
（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例1:

 输入："Mr John Smith    ", 13
 输出："Mr%20John%20Smith"
示例2:

 输入："               ", 5
 输出："%20%20%20%20%20"
提示：

字符串长度在[0, 500000]范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-url-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //传统方法,82.3%
    //将改变后的字符串输入到新的数组中,记得结尾要附一个结束符
    string replaceSpaces(string S, int length) {
        //长度为目标字符串+1,省点内存
        char* newString = new char[S.size() + 1];
        int cursor = 0;
        for (int i = 0; i < length; i++) {
            if (S[i] == ' ') {
                newString[cursor] = '%';
                newString[cursor + 1] = '2';
                newString[cursor + 2] = '0';
                cursor += 2;
            }
            else {
                newString[cursor] = S[i];
            }
            cursor++;
        }
        //结束符
        newString[cursor] = '\0';
        //string的指针构造
        //string(const char * s, size_type n)
        return string(newString, S.size() + 1);
    }

    //极致优化,100%
    //关闭流同步+使用字符串拼接
    string replaceSpaces(string S, int length) {
        //由于cin，cout与stdin总是保持同步的，所以有很大性能损失
        //此语句关闭流的同步加快cin和cout读取
        ios::sync_with_stdio(false);
        string str = "";
        for (int i = 0; i < length; i++) {
            //使用字符串拼接+=号的效率是最高的
            if (S[i] == ' ') str += "%20";
            else str += S[i];
        }
        return str;
    }

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。

示例1：

输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //奇偶计数法,100%
    //字符串为偶数时，必然不能出现奇数个字符
    //字符串为奇数时，可以出现一次奇数字符
    bool canPermutePalindrome(string s) {
        int valid[128];
        memset(valid, 0, sizeof(int) * 128);
        //计数
        for (auto c : s) {
            valid[c] += 1;
        }
        int odds = 0;
        int sOdds = s.size() % 2;
        for (int i = 0; i < 128; i++) {
            //奇数个字符
            if (valid[i] % 2 == 1) {
                odds++;
            }
            if (sOdds) {
                //字符串奇数
                if (odds > 1)
                    return false;
            }
            else {
                //字符串偶数
                if (odds > 0)
                    return false;
            }
        }
        return true;
    }

字符串有三种编辑操作:
插入一个字符、删除一个字符或者替换一个字符。
给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入:
first = "pale"
second = "ple"
输出: True
 

示例 2:

输入:
first = "pales"
second = "pal"
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/one-away-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //传统的指针同位扫描,51.5%
    //即允许一个字符的出错，长度不同时指针往后错一位
    bool oneEditAway(string first, string second) {
        //注意size返回值是size_t，是无符号数
        //因此需要+1比较
        //当长度差距在两字符以上则false，因为此时无法通过一次编辑来改正
        if ((first.size() + 1 > (second.size() + 2)) || (first.size() + 1 < (second.size())))
            return false;

        int cur1 = 0, cur2 = 0;
        bool flag = false;
        while (cur1 < first.size() && cur2 < second.size()) {
            //当前位是否相同
            if (first[cur1] != second[cur2]) {
                //出现过一次错误就false
                if (flag)
                    return false;
                else {
                    flag = true;
                    //替换，比较下一位是否相同或没有下一位了，相同才能继续，否则false
                    if (first.size() == second.size()) {
                        if (((cur1 + 1) != first.size()) && first[cur1 + 1] != second[cur2 + 1])
                            return false;
                    }
                    //插入或删除，比较长的那一边的下一位是否与短的当前位相同，相同才继续
                    else if (first.size() > second.size()) {
                        if (((cur1 + 1) != first.size()) && first[cur1 + 1] != second[cur2])
                            return false;
                        else {
                            ++cur1;
                            continue;
                        }
                    }
                    else if (first.size() < second.size()) {
                        if (((cur2 + 1) != second.size()) && second[cur2 + 1] != first[cur1])
                            return false;
                        else {
                            ++cur2;
                            continue;
                        }
                    }
                }
            }
            //移动指针
            ++cur1;
            ++cur2;
        }
        return true;
    }

    //在一次检测中判断三种情况,89.1%
    //提前通过交换固定住长串和短串相对位置
    //实现了代码复用并减少了判断次数和复杂性
    bool oneEditAway(string first, string second) {
        int len1 = first.size();
        int len2 = second.size();

        //判断各自长度，将长的字符串放到second的位置
        //长度也要记得交换
        //这一步将插入与删除统一了，因为删除交换后相当于对方的插入
        if (len1 > len2) {
            string t = first;
            first = second;
            second = t;

            int len = len1;
            len1 = len2;
            len2 = len;
        }

        //当长的字符串大于短的超过1，说明一次编辑无法实现
        if (len2 - len1 > 1) {
            return false;
        }

        //错误标记，最多只能发生一次错误所以用bool
        bool state = false;
        //主循环，循环初始化两个指针而循环短字符串到头时结束
        //循环时固定增加的时长字符串的指针因为插入必然发生在长字符串中
        for (int i1 = 0, i2 = 0; i1 < len1; i2++) {
            //发生同字符时
            if (first[i1] != second[i2]) {
                if (state) {
                    return false;
                }
                else {
                    state = true;
                    //原本是花哨的写法，这里我加了些括号
                    //其实就是若长串比较长(长度不是相等)
                    //则短串指针暂停前移一循环，标志插入或删除了
                    //若长度相等，则正常前移，标志发生的是替换
                    //而对于下一位的正确与否交予下一个循环负责
                    i1 += ((len2 - len1) == 1 ? 0 : 1);
                }
            }
            //都相同时，默认也让短串前进
            else {
                i1++;
            }
        }
        return true;
    }

利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
比如，字符串aabcccccaaa会变为a2b1c5a3。
若“压缩”后的字符串没有变短，则返回原先的字符串。
你可以假设字符串中只包含大小写英文字母（a至z）。

示例1:

 输入："aabcccccaaa"
 输出："a2b1c5a3"
示例2:

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：

字符串长度在[0, 50000]范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compress-string-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  //传统的读取计数压入,90.1%
  //先压入首次出现的字符，再计数，然后压入最终数字，进入下次循环
  string compressString(string S) {
    //长度小于3的字符串必然无法压缩，直接返回
    if (S.size() < 3) {
      return S;
    }

    int old = S.size();
    string retS;
    char last;
    int count = 1;
    //第一次压入
    last = S[0];
    retS += last;
    for (int i = 1; i < old; ++i) {
      //相同时技术
      if (last == S[i]) {
        ++count;
      }
      else {
        //用C11以后的自带函数to_string将数字转为字符串
        //to_string效率低于sprintf但是也很高
        retS += to_string(count);
        count = 1;
        last = S[i];
        retS += last;
      }
    }
    retS += to_string(count);
    //最后比较长度并返回
    if (retS.size() < old) {
      return retS;
    }
    else {
      return S;
    }
  }

  //优化了压入字符串速度的写法,100%
  //用字符串模板流ostringstream加速构造
  string compressString(string S) {
    //LeetCode常用的加速读写语句
    //Lambda表达式，先关闭cincout同步，使cincout不经过缓冲区加速
    //接触cin与cout的绑定
    //这样写是加速了LeetCode自身评审时的速度
    static auto speedup = []() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      return nullptr;
    }();
    //直接返回
    if (S == "") return "";
    char last = S[0];
    int nCount = 1;
    string str = "";
    //字符串模板类，会动态分配内存
    //动态申请适合大小的内存，既满足了内存节省又满足了空间局部性
    ostringstream ss;
    //循环扫描字符串
    for (int i = 1; i < S.size(); ++i) {
      //重复字符时
      if (S[i] == last) { ++nCount; continue; }
      //将内容输入ss
      ss << last << nCount;
      nCount = 1;
      last = S[i];
    }
    ss << last << nCount;
    //最后从ss中得到所需的字符串
    str = ss.str();
    //返回较短者
    return str.size() < S.size() ? str : S;
  }

给定一幅由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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //单循环版本,78.1%
    //在循环中完成各个位置的转置，但无法很好地利用空间局部性
    void rotate(vector<vector<int>>& matrix) {
        int s = matrix[0].size();
        //i是层数
        for (int i = 0; i < s / 2; ++i) {
            //j是层内的循环，从i到s-i对称
            //但是要注意最边缘的在循环中操作了所以边缘是 s - i - 1
            for (int j = i; j < s - i - 1; ++j) {
                //在循环中完成一个位置的全部转置
                int tmp1 = matrix[i][j];
                int tmp2 = matrix[j][s - i - 1];
                int tmp3 = matrix[s - i - 1][s - j - 1];
                int tmp4 = matrix[s - j - 1][i];
                matrix[j][s - i - 1] = tmp1;
                matrix[s - i - 1][s - j - 1] = tmp2;
                matrix[s - j - 1][i] = tmp3;
                matrix[i][j] = tmp4;
            }
        }
    }

    //双循环版本,78.1%
    //利用了 右旋=主对角线交换+行轴对称交换 得到
    //矩阵的初等变换又只有行列互换和加减，好像没有与对角线有关的啊
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        //先利用双循环来将矩阵按主对角线交换
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        //再对每行的元素按照中间对称轴交换
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n / 2; j++) {
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }
        return;
    }

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
示例 2：

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zero-matrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //原位标记染色法，以时间换空间，28.7%
    //用-65535来标记被清除的部分，之前写国际象棋判断有遇到
    void setZeroes(vector<vector<int>>& matrix) {
        int M = matrix.size();
        int N = matrix[0].size();
        //为0时设为-65535来标记，-65535只是一个比较特殊的标记数而已
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (matrix[i][j] == 0) {
                    setNegOne(matrix, i, j);
                }
            }
        }
        //将标记部分设为0
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (matrix[i][j] == -65535) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    //用于将数组对应的行列标记
    void setNegOne(vector<vector<int>>& matrix, int y, int x) {
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if ((i == y || j == x) && matrix[i][j] != 0) {
                    matrix[i][j] = -65535;
                }
            }
        }
    }

    //额外列表法，空间换时间,88.4%
    //用一个额外的列表来记录哪些行列需要清除，然后最后再一次性清除
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty())
            return;
        int m = matrix.size();
        int n = matrix[0].size();
        //行列标记向量
        vector<int> row(m, 0);
        vector<int> col(n, 0);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    //检测到0时，将需要清除的行列记录下来
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                //第二次循环时将有记录的行列清0
                if (row[i] || col[j])
                    matrix[i][j] = 0;
            }
    }

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成
（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

 输入：s1 = "waterbottle", s2 = "erbottlewat"
 输出：True
示例2:

 输入：s1 = "aa", "aba"
 输出：False
提示：

字符串长度在[0, 100000]范围内。
说明:

你能只调用一次检查子串的方法吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flipped-string-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  //最原始暴力的检测子串,98.3%，4ms
  //由于调用了n次判断子串，O(n2)的复杂度，非常慢
  //但是由于Leetcode的样例库不大所以速度还是快
  //旋转后的串拼接，若原串可在拼接串找到，则存在
  bool isFlipedString(string s1, string s2) {
    if (s1.size() != s2.size())
      return false;
    if (s1.size() < 2)
      return true;
    //先把旋转后的串拼接
    //由于s1=xy,s2=yx; => s2s2=yxyx => s2s2= ys1x
    //检测是否存在
    string s = s2 + s2;
    //记得缩小搜索范围
    for (int i = 0; i < s.size()-s1.size(); ++i) {
      if (checkSame(s1, s, i))
        return true;
    }
    return false;
  }
  //暴力检测，非常慢，调用函数时记得使用常量引用来避免拷贝构造以加速
  bool checkSame(const string& s1, const string& s, int start) {
    for (int i = start; i < start + s1.size(); ++i) {
      if (s[i] != s1[i - start]) {
        return false;
      }
    }
    return true;
  }

  //不调用内部函数但进行内部匹配，92.1%,8ms
  //进行字符串匹配，使用KMP算法
  //KMP算法来自：
  //如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎
  //https://www.zhihu.com/question/21923021/answer/281346746
  bool isFlipedString(string s1, string s2) {
    if (s1.size() != s2.size())
      return false;
    if (s1.size() < 2)
      return true;
    int length = s1.size();
    //拼接
    string s = s2 + s2;
    int length2 = s.size();
    int* next = new int[length];
    memset(next, 0, sizeof(int) * length);
    next[0] = -1;
    //得到next数组，相当于自己作为自己的匹配串
    //被匹配串比匹配串前进一位
    //i是被匹配的，j是匹配的，所以j指针会回退，i不会
    int j = -1, i = 0;
    while (i < length - 1)
    {
      //匹配串的串头或检测到相同的字符
      if (j == -1 || s1[i] == s1[j]) {
        //匹配串和被匹配串指针都前进
        //j是匹配的字符个数
        ++i; ++j;
        //记录当前自己被匹配的进度，记录为匹配的个数
        next[i] = j;
      }
      else {
        //失配时相当于回到之前字符串出现内重复的部分再次尝试
        //所以匹配个数j也会回退
        j = next[j];
      }
    }
    //具体匹配阶段
    i = 0;
    j = 0;
    //next=0代表此字符失配时回到0号位置，next=-1时则会后移
    while (j < length && i < length2)
    {
      //相同时指针一同前进
      if (j == -1 || s[i] == s1[j]) {
        ++i; ++j;
      }
      //失配时j指针回到之前上次重复匹配的位置
      else {
        j = next[j];
      }
    }

    //若匹配串j到达终点表示有出现完全匹配的部分
    //此时实际匹配的位置为i-j，即匹配的开始位置
    if (j == length)
      return true;
    else
      return false;
  }

  //调用内部函数来搜索,98.3%,4ms
  bool isFlipedString(string s1, string s2) {
    if (s1.size() != s2.size()) return false;
    if (s1.empty()) return true;
    //string::npos指size_t的最大值，通常标识不存在
    return (s1 + s1).find(s2) != string::npos;
  }