力扣——程序员面试金典109题刷题笔记1（数组与字符串）_程序员 经典题 优化查字典

先从力扣——程序员面试金典109题开始刷，链接如下：
程序员面试金典109题

面试题 01.01. 判定字符是否唯一

//直接暴力双重for循环
class Solution {
public:
    bool isUnique(string astr) {
        if(astr.length()==0 || astr.length()==1){
            return true;
        }
        for(int i=0; i<astr.length(); i++){
            for(int j=i+1; j<astr.length(); j++){
                if(astr[i] == astr[j])
                    return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//这里看到的另外一种方法，主要是使用到C++中的find和rfind两个函数
class Solution {
public:
    bool isUnique(string astr) {
        for(int i=0; i<astr.size();i++){
            if(astr.find(astr[i])!=astr.rfind(astr[i])){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

这里码一个比较全的字符串相关函数，方便后续学习！
字符串相关函数

//看到评论有这样一段，可以作为思考
如果我是面试官，会考虑主要考察什么，就我的工作经验看，大多数主要是招聘工程师的，
面试者如果什么问题都没有，直接写个二重循环搞定，会首先给个50分，如果能写点判断字符串是否为null的，60分。

直接上手什么bitset，什么位运算的，我会先问他，题目中有没有交代字符串的字符一定是26个英文字母？
如果是unicode环境，你是不是要准备2^16/8个字节的空间？
在实际项目中，风险可控，结果可期更重要，绝大多数时候不在乎那点时间和资源。

所以我期望面试者不要急于解答，我希望他先问我问题：

字符串的字符范围，如果我告诉他，26个小写英文字母，那可能一开头直接判断如果字符长度>26, 直接返回False，做到这一点的，80分
如果我告诉他ascii字符集，然后他的代码里有边界检查，并且针对不同的范围有不同的侧重点，
比如说ascii字符集，那也就是128个可能性，16个字节的位运算比较好
如果我告诉他是unicode，没有字符范围，老老实实排序再判断是比较符合我对工程师的要求的，
因为算法性能稳定，没有额外资源要求，一眼看出没什么不可预见的风险，100分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面试题 01.02. 判定是否互为字符重排

//排序再比较
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        if(s1==s2){
            return true;
        }
        return false;
    }
};

//贴一下排序方式
升序：sort(begin,end,less<data-type>());
降序：sort(begin,end,greater<data-type>()).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//很多题都涉及到了ASCII码来做，可以关注学习一下
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int ascii[128] = {0};
        int len1 = s1.size();
        int len2 = s2.size();
        if(len1!=len2)
            return false;
        for(int i=0;i<len1;i++) {
            ascii[s1[i]]++;
            ascii[s2[i]]--;
        }
        for(int i=0;i<128;i++)
            if(ascii[i]!=0)
                return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

面试题 01.03. URL化

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。

示例 1：
输入："Mr John Smith    ", 13
输出："Mr%20John%20Smith"
示例 2：
输入："               ", 5
输出："%20%20%20%20%20"
1
2
3
4
5
6

class Solution {
public:
    string replaceSpaces(string S, int length) {
        int pos = S.size()-1;
        for(int i= length-1; i>=0; i--){
            if(S[i] == ' '){
                S[pos--] = '0';
                S[pos--] = '2';
                S[pos--] = '%';
            }
            else{
                S[pos--] = S[i];
            }
        }
        return S.substr(pos+1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

substr有2种用法：
假设：string s = "0123456789";
string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789"
string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"

1
2
3
4
5

面试题 01.04. 回文排列

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

示例1：
输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
1
2
3

class Solution {
public:
    bool canPermutePalindrome(string s) {
        int ascii[128] = {0};
        int len1 = s.size();
        int flag1 = 0, flag2 = 0;

        for(int i=0;i<len1;i++) {
            ascii[s[i]]++;
        }
        for(int i=0;i<128;i++){
            if(ascii[i]%2 == 0)
                flag1++;
            else
                flag2++;
        }
        if(flag2 > 1)
            return false;
        else
            return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题 01.05. 一次编辑

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

示例 1:
输入: 
first = "pale"
second = "ple"
输出: True
 
示例 2:
输入: 
first = "pales"
second = "pal"
输出: False
1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int s1 = first.size();
        int s2 = second.size();
        if(abs(s1-s2) > 1)
            return false;
        if(s1 < s2)
            return oneEditAway(second, first);
        for(int i = 0, flag =0;i < s1; i++){
            if(first[i] != second[i - (s1 - s2)*flag] && ++flag >1){
                return false;
            }
        } 
        return true;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里主要就是判断更改的距离是否大于1，如果小于等于1，那么跳过那个位置其它应该是相等的。

面试题 01.06. 字符串压缩

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

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

示例1:
 输入："aabcccccaaa"
 输出："a2b1c5a3"
示例2:
 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
1
2
3
4
5
6
7
8
9

class Solution {
public:
    string compressString(string S) {
        string res;
        int cnt = 1;
        for(int i = 0; i < S.size(); i++){
            if (i != S.size() - 1 && S[i] == S[i+1]){
                cnt++;
                continue;
            }
            res.push_back(S[i]);
            res.append(to_string(cnt));
            cnt = 1;
        }
        return res.size() >= S.size() ? S : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这道题要注意题目题目说的，要满足压缩后的字符数小于未压缩的，所以要加一个判断。

面试题 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]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(), matrix.end());
        for(int i=0; i<matrix.size(); i++){
            for(int j=i+1; j<matrix[0].size(); j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11

C++ reverse函数的用法
reverse函数功能是逆序（或反转），多用于字符串、数组、容器。头文件是 #include < algorithm >
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值

string str="hello world , hi";
reverse(str.begin(),str.end());//str结果为 ih , dlrow olleh
vector<int> v = {5,4,3,2,1};
reverse(v.begin(),v.end());//容器v的值变为1,2,3,4,5
1
2
3
4

面试题 01.08. 零矩阵

编写一种算法，若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]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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;
            }
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

使用一个标记变量记录第一列是否原本存在 0。这样，第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。

复杂度分析
时间复杂度：O(mn)，其中 mm 是矩阵的行数，nn 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度：O(1)。我们只需要常数空间存储若干变量。

面试题 01.09. 字符串轮转

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

示例1:

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

 输入：s1 = "aa", s2 = "aba"
 输出：False

提示：
字符串长度在[0, 100000]范围内。
说明:
你能只调用一次检查子串的方法吗？
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        string s = s2 + s2;
        return s.find(s1) != string::npos;
    }
};
1
2
3
4
5
6
7
8
9
10

这里用到了array_contains(Array, value)函数

返回结果：如果Array中包含value，则返回True，否则返回False

返回类型：boolean

select array_contains(array(1, 2), 3);  -- 结果为 false
select array_contains(array('A', 'B', 'C'), 'A');  -- 结果为 true
1
2