目录
面试题 01.01. 判定字符是否唯一
面试题 01.03. URL化
面试题 01.04. 回文排列
面试题 01.05. 一次编辑
面试题 01.06. 字符串压缩
面试题 01.07. 旋转矩阵
面试题 01.08. 零矩阵
面试题 01.09. 字符串轮转
面试题 02.01. 移除重复节点
面试题 02.02. 返回倒数第 k 个节点
面试题 02.03. 删除中间节点
面试题 02.04. 分割链表
面试题 02.05. 链表求和
面试题 02.06. 回文链表
面试题 02.07. 链表相交
面试题 02.08. 环路检测
面试题 03.01. 三合一
面试题 03.02. 栈的最小值
面试题 03.03. 堆盘子
面试题 03.04. 化栈为队
面试题 03.05. 栈排序
面试题 05.02. 二进制数转字符串
面试题 05.03. 翻转数位
面试题 01.01. 判定字符是否唯一
题解: 位存储
因为题目要求不能用额外的数据结构,哈希不可采取,暴力更不可取。
总共有26个字母,一个int有32位,我们只需要创建一个int变量用于存储,每遍历一个字符串元素就找到这个变量的对应位,看看是否为1,为1说明在这之前这个字母已经出现了,为0就置1。比如b这个字母,因为b和a只相距一个,将int变量右移一个单位,最低位是1还是0。
代码:
class Solution {
public:bool isUnique(string astr) {int res=0;for(auto c:astr){int cval=c-'a';if((res>>cval)&1==1)return false;elseres|=1<<cval;}return true;}
};
结果:
面试题 01.03. URL化
URL化。编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。(注:用Java实现的话,请使用字符数组实现,以便直接在数组上操作。)
题解:
已经知道字符串的真实长度,所以遍历一遍数组,创建一个字符串类型变量,遇到空格就+%20,遇到字符就加上这个字符。
代码:
class Solution {
public:string replaceSpaces(string S, int length) {string str;for(int i=0;i<length;++i){if(S[i]==' ')str+="%20";elsestr+=S[i];}return str;}
};
结果:
面试题 01.04. 回文排列
给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词
题解: 哈希表
因为是字符串,可以用128位的位表去存储,遍历字符串,对每一个字符,如果第一次遇到该字符,反转从0-》1,如果是第二次,反转从1-》0。遍历完字符串,位表中1的个数小于等于1即为回文字符串。
代码:
class Solution {
public:bool canPermutePalindrome(string s) {bitset<128>map;for(char c:s){map.flip(c);}return map.count()<=1;}
};
结果:
面试题 01.05. 一次编辑
字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。
题解:
首先排除特殊情况,两个字符串大小相差1以上,返回false;
遍历第二个字符串,如果在位置i处的字符不相等,即出现下面的情况
①替换:两个字符串位置i后面的子串是相等的,返回true,否则返回false;
②删除:second位置i以及后面的子串和first位置i后面的子串是相等的,返回true,否则返回false;否则返回false;
③插入:second后面的子串和first位置i以及后面的子串是相等的,返回true,否则返回false;否则返回false;
代码:
class Solution {
public:bool oneEditAway(string first, string second) {int len = first.size()-second.size(); if (len>1||len<-1) {return false;}for(int i=0;i<second.size();++i){//特殊情况if(i==second.size()-1&&first[i]!=second[i]&&len>0)return false;if(i!=second.size()-1&&first[i]!=second[i]){//替换if(second.compare(i+1,second.size()-i,first,i+1,first.size()-i)==0)return true;//删除else if(second.compare(i,second.size()-i,first,i+1,first.size()-1-i)==0)return true;//插入else if(second.compare(i+1,second.size()-1-i,first,i,first.size()-i)==0)return true;else return false;break;} }return true;}
};
结果:
面试题 01.06. 字符串压缩
字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。
题解:
遍历字符串,计算重复字符的个数,并添加到另一个字符串中,最后比较新字符串和旧字符串的长度,输出短的那个。
代码:
class Solution {
public:string compressString(string S) {int count=1;string str;str+=S[0];for(int i=1;i<S.size();++i,++count){if(S[i]!=S[i-1]){str+=to_string(count)+S[i];count=0;}}return S.size()>str.size()+1?str+to_string(count):S;}
};
结果:
面试题 01.07. 旋转矩阵
给你一幅由 N × N
矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。
不占用额外内存空间能否做到?
题解:
因为不能占用额外的空间,可将下图的0 1 2 3相互交换位置,三次交换即可。
关键代码:
swap(matrix[i][j],matrix[j][n-1-i]);
swap(matrix[i][j],matrix[n-1-i][n-1-j]);
swap(matrix[i][j],matrix[n-1-j][i]);
代码:
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();int r = (n/2)-1; //左上角区域的最大行下标,int c = (n-1)/2; //左上角区域的最大列下标,行列下标从 0 开始。//if(!n) return;for(int i=0;i<=r;++i)for(int j=0;j<=c;++j){swap(matrix[i][j],matrix[j][n-1-i]);swap(matrix[i][j],matrix[n-1-i][n-1-j]);swap(matrix[i][j],matrix[n-1-j][i]);}}
};
方法二: 先主对角线翻转,再按列号倒排
代码:
class Solution {
public://先按照主对角线翻转,再按列号倒排void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int i=0 ; i<n ; ++i){for(int j = 0 ; j<i ; ++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]);}}}
};
面试题 01.08. 零矩阵
编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零。
题解: 遍历+记录
首先,创建两个数组记录行和列,然后遍历矩阵,将值为0的行与列标记记录下来。
再次遍历矩阵,根据记录数组将标记的行与列的数置为0.
代码:
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<bool> row(m),col(n);for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(matrix[i][j]==0){row[i]=col[j]=true;}}}for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(row[i]||col[j])matrix[i][j]=0;}}}
};
结果:
面试题 01.09. 字符串轮转
字符串轮转。给定两个字符串s1
和s2
,请编写代码检查s2
是否为s1
旋转而成(比如,waterbottle
是erbottlewat
旋转后的字符串)。
题解: 旋转字符串相加+查询
以waterbottle为例,erbottlewat是它旋转后的字符串,erbottlewat+erbottlewat=erbottlewaterbottlewat
我们只需要判断相加后的字符串中是否有旋转前的字符串即可
代码:
class Solution {
public:bool isFlipedString(string s1, string s2) {if(s1.size()!=s2.size()) return false;string str=s2+s2;return str.find(s1)==-1?false:true;}
};
结果:
面试题 02.01. 移除重复节点
编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
题解: 哈希表
用哈希表记录出现过的数字,遍历链表,每过一个节点都查一下表,如果表中存在这个数据,就删除节点。
代码:
class Solution {
public:ListNode* removeDuplicateNodes(ListNode* head) {if(head==nullptr||head->next==nullptr) return head;unordered_map<int,bool>map;ListNode *pre=head,*p=head->next;map[head->val]=true;while(p!=nullptr){if(map[(p->val)]){pre->next=p->next;p=pre->next;}else{map[p->val]=true;pre=p;p=p->next;}}return head;}
};
结果:
面试题 02.02. 返回倒数第 k 个节点
题解:
创建左右两个指针pre和p,先让p走k个节点,之后pre和p同时走,当p为空指针时,pre指向的就是倒数第k个节点。
代码:
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode *p=head,*pre=head;while(k--)p=p->next;while(p!=nullptr){p=p->next;pre=pre->next;}return pre->val;}
};
结果:
面试题 02.03. 删除中间节点
若链表中的某个节点,既不是链表头节点,也不是链表尾节点,则称其为该链表的「中间节点」。
假定已知链表的某一个中间节点,请实现一种算法,将该节点从链表中删除。
例如,传入节点 c(位于单向链表 a->b->c->d->e->f 中),将其删除后,剩余链表为 a->b->d->e->f
题解:
将下一个节点的值赋值给当前节点,再把下一节点删除
代码:
class Solution {
public:void deleteNode(ListNode* node) {node->val=node->next->val;node->next=node->next->next;}
};
结果:
面试题 02.04. 分割链表
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
题解: 大小链表
首先,设置两个链表,一个记录大于等于x的节点,一个记录小于x的节点,遍历一遍链表,最后得到一大一小两个链表,拼接到一块即可。
代码:
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode *large=new ListNode(0);ListNode *small=new ListNode(0);ListNode *largehead=large;ListNode *smallhead=small; while(head!=nullptr){if(head->val<x){small->next=head;small=small->next;head=head->next;small->next=nullptr;}else{large->next=head;large=large->next;head=head->next;large->next=nullptr;}}small->next=largehead->next;return smallhead->next;}
};
结果:
面试题 02.05. 链表求和
给定两个用链表表示的整数,每个节点包含一个数位。
这些数位是反向存放的,也就是个位排在链表首部。
编写函数对这两个整数求和,并用链表形式返回结果。
题解: 数学加法
因为链表是从左到右低位到高位,我们需要新建一个链表用于存储结果,然后遍历两条链表,两两相加,如果大于等于10,进位carry=1。如果有一条走完了,就将其看成0,直到两条链表都走完。最后,如果进位carry==1,在后面加一个值为1的节点。
代码:
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry=0;ListNode *head=new ListNode(0),*tail=head;while(l1!=nullptr||l2!=nullptr){int num1=l1==nullptr?0:l1->val;int num2=l2==nullptr?0:l2->val;int sum=num1+num2+carry;carry=sum>=10?1:0;tail->next=new ListNode(sum%10);tail=tail->next;l1=l1==nullptr?nullptr:l1->next;l2=l2==nullptr?nullptr:l2->next;}if(carry==1)tail->next=new ListNode(1);return head->next;}
};
结果:
面试题 02.06. 回文链表
编写一个函数,检查输入的链表是否是回文的。
题解:
首先,用快慢指针找到链表的中点,然后将后半段链表逆转,对比前半段和后半段链表是否相等。
代码:
class Solution {
public:bool isPalindrome(ListNode* head) {if(!head) return true;ListNode *slow=head,*fast=head; while(fast&&fast->next){fast=fast->next->next;slow=slow->next;} ListNode *pre=nullptr;while(slow){ListNode *node=slow->next;slow->next=pre;pre=slow;slow=node;}while(pre){if(pre->val!=head->val)return false;pre=pre->next;head=head->next;}return true;}
};
结果:
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题解:
设两个链表公共部分为c,剩余部分分别为a,b,很基本的数学等式a+c+b=b+c+a;也就是说走完自己的链表,再走完另一个链表的非公共部分,就会相遇在公共节点的第一个。
代码:
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *l1=headA,*l2=headB;while(l1!=l2){ l1=l1==nullptr?headB:l1->next;l2=l2==nullptr?headA:l2->next;}return l1;}
};
结果:
面试题 02.08. 环路检测
给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
题解: 哈希表+遍历
遍历链表,每经过一个链表就记录下来,出现重复的链表就输出为该链表。
若无回路,输出空指针。
代码:
class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_map<ListNode*,bool>map;while(head){if(map[head])return head;elsemap[head]=true;head=head->next;}return nullptr;}
};
结果:
面试题 03.01. 三合一
三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标,value表示压入的值。
构造函数会传入一个stackSize参数,代表每个栈的大小。
题解:
用一个数组表示三个栈,原理很简单,栈号mod 3,但是做起来有点麻烦,注意边界。
代码:
class TripleInOne {
private:int numberOfStacks = 3; //一共有3个栈int stackCapacity;vector<int> sizes; //存放每个栈的当前元素个数vector<int> values;public:TripleInOne(int stackSize) {stackCapacity = stackSize;sizes.resize(3);values.resize(numberOfStacks * stackSize);}void push(int stackNum, int value) {if (!isFull(stackNum)){sizes[stackNum] ++ ;values[indexOfTop(stackNum)] = value;}}int pop(int stackNum) { //弹出指定栈顶元素并返回其值if (!isEmpty(stackNum)){int topIndex = indexOfTop(stackNum);int value = values[topIndex];values[topIndex] = 0;sizes[stackNum] -- ;return value;}return -1;}int peek(int stackNum) {if (!isEmpty(stackNum)){return values[indexOfTop(stackNum)];}return -1;}bool isEmpty(int stackNum) { //判断栈是否为空return sizes[stackNum] == 0;}bool isFull(int stackNum) {return sizes[stackNum] == stackCapacity;}//取得指定栈的栈顶元素所在数组中的下标int indexOfTop(int stackNum){return stackNum * stackCapacity + sizes[stackNum] - 1;}
};
结果:
面试题 03.02. 栈的最小值
请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
题解:
设置两个栈,一个正常的栈,一个单调栈
push:正常栈,正常push;单调栈,栈空或者x的值小于等于当前栈顶元素,push。
pop:正常栈,正常pop;单调栈,x的值等于当前栈顶元素,pop。
top:返回正常栈栈顶元素。
getMIn:返回单调栈栈顶元素。
代码:
class MinStack {
public:stack<int>minstack;stack<int>st;/** initialize your data structure here. */MinStack() {}void push(int x) {if(minstack.empty()||x<=minstack.top()){minstack.push(x);}st.push(x); }void pop() {if(minstack.top()==st.top())minstack.pop();st.pop();}int top() {return st.top();}int getMin() {return minstack.top();}
};
结果:
面试题 03.03. 堆盘子
代码:
class StackOfPlates {
public:StackOfPlates(int cap) {capacity = cap;}void push(int val) {if (capacity == 0) {// 如果capacity为0,直接returnreturn;}if (stks.empty() || stks.back().size() == capacity) {// 当前vector为空或当前栈满,新增一个栈stks.push_back(stack<int>());}stks.back().push(val);}int pop() {if (capacity == 0 || stks.empty()) {// capacity为0或当前vector为空,直接return -1return -1;}int res = stks.back().top();stks.back().pop();if (stks.back().empty()) {// 如果最后一个栈为空,需要弹出最后一个栈stks.pop_back();}return res;}int popAt(int index) {if (capacity == 0 || index >= stks.size() || stks[index].empty()) {// capacity为0或下标越界或当前栈空,直接return -1return -1;}int res = stks[index].top();stks[index].pop();if (stks[index].empty()) {// 如果当前栈空,最后删除当前栈stks.erase(stks.begin() + index);}return res;}
private:vector<stack<int>> stks;int capacity;
};
结果:
面试题 03.04. 化栈为队
题解:
代码:
class MyQueue {
public:/** Initialize your data structure here. */stack<int>pushstack;stack<int>popstack;MyQueue() {}/** Push element x to the back of queue. */void push(int x) {while(!popstack.empty()){pushstack.push(popstack.top());popstack.pop(); }pushstack.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {while(!pushstack.empty()){popstack.push(pushstack.top());pushstack.pop(); }if(popstack.empty())return -1;int res=popstack.top();popstack.pop();return res;}/** Get the front element. */int peek() {while(!pushstack.empty()){popstack.push(pushstack.top());pushstack.pop(); }return popstack.top();}/** Returns whether the queue is empty. */bool empty() {if(popstack.empty()&&pushstack.empty())return true;return false;}
};
结果:
面试题 03.05. 栈排序
栈排序。 编写程序,对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据,但不得将元素复制到别的数据结构(如数组)中。该栈支持如下操作:push、pop、peek 和 isEmpty。当栈为空时,peek 返回 -1。
题解: 辅助栈
注意一点,就是push的时候判断一下栈中有多少个数是大于val的,val需要处于它们下面。
代码:
class SortedStack {
public:stack<int>st;stack<int>st2;SortedStack() {}void push(int val) {while(!st.empty()&&val>st.top()){st2.push(st.top());st.pop();}st.push(val);while(!st2.empty()){st.push(st2.top());st2.pop();}}void pop() {if(!st.empty())st.pop();}int peek() {if(!st.empty())return st.top();return -1;}bool isEmpty() {if(st.size()==0)return true;return false;}
};
结果:
题解:
代码:
结果:
面试题 05.02. 二进制数转字符串
二进制数转字符串。给定一个介于0和1之间的实数(如0.72),类型为double,打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示,则打印“ERROR”。
题解: 乘2
十进制的小数部分转化为二进制,需要不断乘2,如果结果大于1,二进制位就置为1,如果结果小于1,二进制位就置0。对于那些无法表示的数,可以一直乘2下去,同时设定条件,当字符串的长度大于32时,表示无法用二进制表示。
代码:
class Solution {
public:string printBin(double num) {string res="0.";while(num!=0){num=num*2;if(num>=1){res+="1";num=num-1;}elseres+="0";if(res.length()>32) return "ERROR";}return res;}
};
结果:
面试题 05.03. 翻转数位
给定一个32位整数 num
,你可以将一个数位从0变为1。请编写一个程序,找出你能够获得的最长的一串1的长度
题解: 动态规划
我们可以设两个数组,为了节约空间,我这边只设了两个数,一个是没翻转连续1的个数dp0,一个是翻转后连续1的个数dp1。
遍历数位,如果数位为1,dp0和dp1同时加1;如果是0,假设把这个位置翻转了,dp1=dp0+1,假设没翻转,dp0=0;直到循环结束,取dp1在这个过程中的最大值即可。
代码:
class Solution {
public:int reverseBits(int num) {int dp0=0,dp1=0;int res=0;for(int i=0;i<32;++i){if((num>>i)&0x01==1){++dp0;++dp1;if(dp1>res) res=dp1;}else{dp1=dp0+1;dp0=0;if(dp1>res) res=dp1;}}return res;}
};
结果:
题解:
代码:
结果: