先从力扣——程序员面试金典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; ifor(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; iif(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面试题 01.03. URL化ascii[s1[i]]++; ascii[s2[i]]--; } for(int i=0;i<128;i++) if(ascii[i]!=0) return false; return true; } };
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面试题 01.05. 一次编辑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: 输入: 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