先从力扣——程序员面试金典109题开始刷，链接如下：
程序员面试金典109题
- 面试题 01.01. 判定字符是否唯一
- 面试题 01.02. 判定是否互为字符重排
- 面试题 01.03. URL化
- 面试题 01.04. 回文排列
- 面试题 01.05. 一次编辑
- 面试题 01.06. 字符串压缩
- 面试题 01.07. 旋转矩阵
- 面试题 01.08. 零矩阵
- 面试题 01.09. 字符串轮转
//直接暴力双重for循环
class Solution {
public:
bool isUnique(string astr) {
if(astr.length()==0 || astr.length()==1){
return true;
}
for(int i=0; i
for(int j=i+1; j
if(astr[i] == astr[j])
return false;
}
}
return true;
}
};
//这里看到的另外一种方法，主要是使用到C++中的find和rfind两个函数
class Solution {
public:
bool isUnique(string astr) {
for(int i=0; i
if(astr.find(astr[i])!=astr.rfind(astr[i])){
return false;
}
}
return true;
}
};
这里码一个比较全的字符串相关函数，方便后续学习！
字符串相关函数
//看到评论有这样一段，可以作为思考 如果我是面试官，会考虑主要考察什么，就我的工作经验看，大多数主要是招聘工程师的， 面试者如果什么问题都没有，直接写个二重循环搞定，会首先给个50分，如果能写点判断字符串是否为null的，60分。 直接上手什么bitset，什么位运算的，我会先问他，题目中有没有交代字符串的字符一定是26个英文字母？ 如果是unicode环境，你是不是要准备2^16/8个字节的空间？ 在实际项目中，风险可控，结果可期更重要，绝大多数时候不在乎那点时间和资源。 所以我期望面试者不要急于解答，我希望他先问我问题： 字符串的字符范围，如果我告诉他，26个小写英文字母，那可能一开头直接判断如果字符长度>26, 直接返回False，做到这一点的，80分 如果我告诉他ascii字符集，然后他的代码里有边界检查，并且针对不同的范围有不同的侧重点， 比如说ascii字符集，那也就是128个可能性，16个字节的位运算比较好 如果我告诉他是unicode，没有字符范围，老老实实排序再判断是比较符合我对工程师的要求的， 因为算法性能稳定，没有额外资源要求，一眼看出没什么不可预见的风险，100分。面试题 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());
降序：sort(begin,end,greater()).
//很多题都涉及到了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
ascii[s1[i]]++;
ascii[s2[i]]--;
}
for(int i=0;i<128;i++)
if(ascii[i]!=0)
return false;
return true;
}
};
面试题 01.03. URL化
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。
示例 1： 输入："Mr John Smith ", 13 输出："Mr%20John%20Smith" 示例 2： 输入：" ", 5 输出："%20%20%20%20%20"
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);
}
};
substr有2种用法： 假设：string s = "0123456789"; string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789" string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"面试题 01.04. 回文排列
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词.
示例1： 输入："tactcoa" 输出：true（排列有"tacocat"、"atcocta"，等等）
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
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;
}
};
面试题 01.05. 一次编辑
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1: 输入: first = "pale" second = "ple" 输出: True 示例 2: 输入: first = "pales" second = "pal" 输出: False
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，如果小于等于1，那么跳过那个位置其它应该是相等的。
面试题 01.06. 字符串压缩字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。 示例1: 输入："aabcccccaaa" 输出："a2b1c5a3" 示例2: 输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
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;
}
};
这道题要注意题目题目说的，要满足压缩后的字符数小于未压缩的，所以要加一个判断。
面试题 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] ]
class Solution {
public:
void rotate(vector>& matrix) {
reverse(matrix.begin(), matrix.end());
for(int i=0; i
for(int j=i+1; j
swap(matrix[i][j],matrix[j][i]);
}
}
}
};
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面试题 01.08. 零矩阵v = {5,4,3,2,1}; reverse(v.begin(),v.end());//容器v的值变为1,2,3,4,5
编写一种算法，若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] ]
class Solution {
public:
void setZeroes(vector>& 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;
}
}
}
};
使用一个标记变量记录第一列是否原本存在 0。这样，第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
复杂度分析
时间复杂度：O(mn)，其中 mm 是矩阵的行数，nn 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度：O(1)。我们只需要常数空间存储若干变量。
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
示例1: 输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True 示例2: 输入：s1 = "aa", s2 = "aba" 输出：False 提示： 字符串长度在[0, 100000]范围内。 说明: 你能只调用一次检查子串的方法吗？
class Solution {
public:
bool isFlipedString(string s1, string s2) {
if(s1.length() != s2.length()){
return false;
}
s1 = s1 + s1;
return s1.contains(s2);
}
};
这里用到了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
