本文主要是介绍LeetCode程序员面试金典（第 6 版）上，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
面试题 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. 栈排序
面试题 04.01. 节点间通路
面试题 04.02. 最小高度树
面试题 04.03. 特定深度节点链表
面试题 04.04. 检查平衡性
面试题 04.06. 后继者
面试题 04.08. 首个共同祖先
面试题 04.10. 检查子树
面试题 04.12. 求和路径
面试题 05.01. 插入
面试题 05.02. 二进制数转字符串
面试题 05.03. 翻转数位
面试题 05.08. 绘制直线
面试题 08.01. 三步问题
面试题 08.03. 魔术索引
面试题 08.04. 幂集
面试题 08.05. 递归乘法
面试题 08.07. 无重复字符串的排列组合
面试题 08.08. 有重复字符串的排列组合
面试题 08.09. 括号
面试题 08.10. 颜色填充
面试题 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.02. 判定是否互为字符重排
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
题解： 排序
两个字符串排序一下，看最后结果是否相同
代码：
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());if(s1==s2)return true;return false;}
};结果：
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());if(s1==s2)return true;return false;}
};结果：
面试题 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;}
};结果：
题解：
代码：
结果：
面试题 04.01. 节点间通路
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
题解： BFS
利用队列进行广度优先搜索
首先，用map建立一个哈希表，这步很关键，不然容易超时。
然后每次压入队列之前查看第二个数是否等于target
代码：
class Solution {
public:bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {queue<int>que;que.push(start);//初始值unordered_map<int,vector<int>>map;int i=0;for(auto e:graph){//建立哈希表，这步很关键map[e[0]].push_back(e[1]);}while(!que.empty()){if(i++>n) return false;//循环n次还找不到就没有回路for(auto e:map[que.front()]){ if(e==target) return true;que.push(e);}que.pop();}return false;}
};结果：
面试题 04.02. 最小高度树
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
题解： 二分+递归
数组的顺序是有序的，可以用二分的思想去递归，以数组的中位数为根节点，中位数的左边的数值为左子树，右边为右子树。
代码：
class Solution {
public:TreeNode* helper(vector<int>& nums,int l,int r){if(l>r) return nullptr;int mid=(l+r)/2;TreeNode *root=new TreeNode(nums[mid]);root->left=helper(nums,l,mid-1);root->right=helper(nums,mid+1,r);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums,0,nums.size()-1);}
};结果：
题解：
代码：
结果：
面试题 04.03. 特定深度节点链表
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组
题解： 队列+层次遍历
代码：
class Solution {
public:vector<ListNode*> listOfDepth(TreeNode* tree) {vector<ListNode*>res;queue<TreeNode*>Q;Q.push(tree);while(!Q.empty()){int sz=Q.size();ListNode *top=nullptr,*pre=nullptr;while(sz--){auto tree_node=Q.front();ListNode* node=new ListNode(tree_node->val);if(pre!=nullptr){pre->next=node;pre=pre->next;}else{top=node;pre=node;}if(tree_node->left) Q.push(tree_node->left);if(tree_node->right) Q.push(tree_node->right);Q.pop();}res.push_back(top);}return res;}
};结果：
面试题 04.04. 检查平衡性
题解：
一种比较容易理解的递归
代码：
class Solution {
public:
bool flag=true;int dfs(TreeNode* root){if(root==nullptr) return 0;int left=dfs(root->left);int right=dfs(root->right);if(abs(left-right)>1)flag=false ;return max(left,right)+1;}bool isBalanced(TreeNode* root) {dfs(root);return flag;}
};结果：
面试题 04.06. 后继者
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
题解： 递归+中序遍历
中序遍历顺序 ：左子树->根节点->右子树
所以可以设一个标志位，如果遍历到该节点，标志位置为1，然后根据中序遍历顺序递归到下一个节点，然后返回该节点即可。
代码：
class Solution {
public:bool flag=false;TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(root==nullptr) return nullptr;TreeNode* l=inorderSuccessor(root->left,p);if(flag) {flag=false;return root;}if(root==p) flag=true;TreeNode* r=inorderSuccessor(root->right,p);if(l!=nullptr)return l;return r;}
};结果：
面试题 04.08. 首个共同祖先
题解：
代码：
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr) return nullptr;// 到底了还没找到，返回 nullif(root==p||root==q) return root;// 如果找到了 p 或 q，返回它// 记录 p 或 q 是在左(右)子树找到的TreeNode* left=lowestCommonAncestor(root->left,p, q);TreeNode* right=lowestCommonAncestor(root->right,p, q);// 如果 left 和 right 都记录了找到的节点，那么肯定是一个记录了 p ，另一个记录了 q// 它们分别在以 root 为根的左右子树中，所以 root 就是它们的最近公共祖先if(left&&right) return root;// 由于节点 p,q 一定在二叉树中，left和right不会同时为null// 若 left != null && right == null，说明在左子树中找到 p 或 q，而在右子树找不到 p 或 q，则剩下一个也在左子树// 所以 left 就是最近公共祖先// 另一种情况同理if(left&&!right) return left;return right;}
};结果：
面试题 04.10. 检查子树
题解： 递归
创建一个检查函数，当遍历到与字数根节点相同的节点时，就检查一遍是否相同。
代码：
class Solution {
public:bool check(TreeNode* t1, TreeNode* t2){if(t1==nullptr&&t2==nullptr) return true;if(t1==nullptr||t2==nullptr||t1->val!=t2->val) return false;bool l=check(t1->left,t2->left);bool r=check(t1->right,t2->right);return l&&r;}bool checkSubTree(TreeNode* t1, TreeNode* t2) {if(t1==nullptr) return false;if(t1->val==t2->val)if(check(t1,t2)) return true;//一定要用判断，不能用return check(t1,t2)bool l=checkSubTree(t1->left, t2);bool r=checkSubTree(t1->right, t2);return l||r;}
};结果：
面试题 04.12. 求和路径
题解： 前缀和+深度优先搜索
比如：我们从root遍历到节点node，序列就是root->n1->n2->...->node，这样我们就有root,n1,n2,n3...node的前缀和（该节点前所有节点相加之和）。遍历到当前节点node，root到node所有节点相加为cur，在哈希表中找是否有cur-sum的值，因为有的话，必然有一段的值为sum。
代码：
class Solution {
public:unordered_map<long long,int>map;int dfs(TreeNode* root, int sum,int cur){if(root==nullptr) return 0;cur+=root->val;int res=0;if(map[cur-sum]) res+=map[cur-sum];map[cur]++;res+= dfs(root->left,sum,cur);res+= dfs(root->right,sum,cur);map[cur]--;return res;}int pathSum(TreeNode* root, int sum) {map[0]=1;return dfs(root,sum,0);}
};结果：
面试题 05.01. 插入
题解： 按位操作
遍历i到j，判断M的对应位是1还是0，如果是1就移到N对应位上，如果是0，就将N的位翻转为0.
代码：
class Solution {
public:int insertBits(int N, int M, int i, int j) {for(int k=i;k<=j;++k){if(M&0x01)N=N|(0x01<<k);elseN&=~(0x01<<k); M=M>>1;}return N;}
};结果：
面试题 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;}
};结果：
面试题 05.06. 整数转换
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
题解：
遍历32个位，比较位与位之间是否相等
代码：
class Solution {
public:int convertInteger(int A, int B) {int res=0;for(int i=0;i<32;++i){if((A&0x01)!=(B&0x01))++res;A=A>>1;B=B>>1;}return res;}
};结果：
面试题 05.08. 绘制直线
已知一个由像素点组成的单色屏幕，每行均有 w 个像素点，所有像素点初始为 0，左上角位置为 (0,0)。
现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中，再依次存入长度为 length 的一维数组中。
我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线（即像素点修改为 1），请返回绘制过后的数组。
题解：
该题重点在于理解，就是把一个数的位数当成32个数来用，这样数组就可以看作是一个矩阵。
我们需要定位到行：确定矩阵一行有几个n=w/32，行就是y*n+i/32，其实是数组中的某一个数。
然后定位到列：某个数的某一位，把找到该位，然后置为1.
因为是从高位到地位，需要31-i%32
代码：
class Solution {
public:vector<int> drawLine(int length, int w, int x1, int x2, int y) {vector<int>res(length,0);int n=w/32;//列// int m=length/n;//行int start=y*n;//从第几行开始for(int i=x1;i<=x2;++i)res[start+i/32]|=(1<<(31-i%32));return res;}
};结果：
题解：
代码：
结果：
面试题 08.01. 三步问题
题解： 动态规划
和青蛙跳台阶一样，具体看代码
代码：
class Solution {
public:int waysToStep(int n) {if(n<3) return n;if(n==3) return 4;long dp1=1,dp2=2,dp3=4;// long long sumfor(int i=4;i<=n;++i){long sum=(dp1+dp2+dp3)%1000000007;dp1=dp2;dp2=dp3;dp3=sum;}return dp3;}
};结果：
面试题 08.03. 魔术索引
魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
题解： 太简单了，可以尝试一下二分法
代码：
class Solution {
public:int findMagicIndex(vector<int>& nums) {for(int i=0;i<nums.size();++i){if(i==nums[i])return i;}return -1;}
};结果：
面试题 08.04. 幂集
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
题解： 递归
代码：
class Solution {
public:vector<int> t;vector<vector<int>> ans;void dfs(int cur, vector<int>& nums) {if (cur == nums.size()) {ans.push_back(t);return;}t.push_back(nums[cur]);dfs(cur + 1, nums);t.pop_back();//不选该节点dfs(cur + 1, nums);}vector<vector<int>> subsets(vector<int>& nums) {dfs(0, nums);return ans;}
};结果：
面试题 08.05. 递归乘法
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
题解： 位运算
例如：3（0b0011）和5（0b0101），固定一个数，比如3，然后从右到左遍历5的32个位，如果是1，对应的3左移n（第n位）。0b0011<<0+0b0011<<2=0b1111(15)
代码：
class Solution {
public:int multiply(int A, int B) {int res=0;for(int i=0;i<32;++i){if(((B>>i)&0x01)==1)res+=(A<<i);}return res;}
};结果：
面试题 08.07. 无重复字符串的排列组合
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
题解： 深度优先+交换
我们可以先换第一个数，有n种可能，再交换第二个数有n-1种可能
代码：
class Solution {
public:vector<string>res;void dfs(string &s,int i){if(i==s.size()) res.push_back(s);for(int j=i;j<s.size();++j){swap(s[i],s[j]);dfs(s,i+1);//当前已经交换，开始交换下一个swap(s[i],s[j]);}}vector<string> permutation(string S) {dfs(S,0);return res;}
};结果：
面试题 08.08. 有重复字符串的排列组合
题解： 深度优先+哈希
这题其实和8.7是一样的，只不过我们需要用一个哈希表来存储已经使用过的字符，用于去重复。
代码：
class Solution {
public:vector<string>res;void dfs(string s,int i){if(i==s.size()) res.push_back(s);unordered_set<char>set;//无序哈希表for(int j=i;j<s.size();++j){if(set.find(s[j])==set.end()){//哈希表内没有这个数才执行set.insert(s[j]);swap(s[j],s[i]);dfs(s,i+1);swap(s[j],s[i]);}} } vector<string> permutation(string S) {cout<<S;dfs(S,0);return res;}
};结果：
面试题 08.09. 括号
题解： 递归
选择括号只有两种可能，一种是选左括号，这种只要不是left==0，就一直可以选；第二种是选择右括号，这种只有右括号的数量大于左括号时才能选
代码：
class Solution {
public:vector<string>res;void dfs(string str,int left,int right){if(left==0&&right==0){res.push_back(str);return;}if(left!=0)dfs(str+'(',left-1,right);if(right>left)dfs(str+')',left,right-1);}vector<string> generateParenthesis(int n) {int left=n,right=n;string str;dfs(str,left,right);return res;}
};结果:
面试题 08.10. 颜色填充
编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
题解： 递归
这题用简单的递归即可，从该点一直蔓延到上下左右四个方向的点
代码：
class Solution {
public:void dfs(vector<vector<int>>& image,int sr, int sc, int oldColor,int newColor){if(sr<0||sc<0||sr==image.size()||sc==image[0].size()||image[sr][sc]!=oldColor) return;image[sr][sc]=newColor;dfs(image,sr-1, sc, oldColor,newColor);dfs(image,sr+1, sc, oldColor,newColor);dfs(image,sr, sc-1, oldColor,newColor);dfs(image,sr, sc+1, oldColor,newColor);}vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {if(image.size()==0) return image;if(image[sr][sc]!=newColor)dfs(image,sr,sc,image[sr][sc],newColor);return image;}
};结果:
题解：
代码：
结果
这篇关于LeetCode程序员面试金典（第 6 版）上的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
