剑指offer所有的题目总结(c++:2刷)

面试题3：数组中重复的数字

题目一：找出数组中重复的数字

class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size();
//超过数据范围，无效
for(auto x : nums)
if(x < 0 || x >= n)
return -1;
for(int i = 0; i < n; i++)
{
//如果当前坐标上的m和坐标不同，而且m坐标上的数也不等于m，则交换
while(i != nums[i] && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);
//如果当前坑与萝卜不匹配，且属于萝卜的坑已经有萝卜了则为重复萝卜
if(nums[i] != i && nums[nums[i]] == nums[i])return nums[i];
}
return -1;
}
};

题目二：不修改数组找出重复的数字

class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l = 1, r = nums.size() - 1;
//利用抽屉原理，把长度分成两份，有一份一定会多出来
while(l < r)
{
int mid = l + r >> 1;
int s = 0;
//统计区间[l, mid]中的数字
for(auto x : nums) s += x >= l && x <= mid;
if(s > mid - l + 1) r = mid;
else l = mid + 1;
}
return r;
}
};

面试题4：二维数组中的查找

class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
//如果是空，则返回
if(array.empty() || array[0].empty()) return false;
//利用数组的特性，从右上角开始进行
int i = 0, j = array[0].size() - 1;
//每次可以排除一列或者一行
while(i < array.size()
&& j >= 0)
{
if(array[i][j] == target) return true;
if(array[i][j] > target) j--;
else i++;
}
return false;
}
};

面试题5：替换空格

class Solution {
public:
string replaceSpaces(string &str) {
//首先遍历一遍得到新的字符串的长度，用双指针也是很棒的做法
string newstr;
for(auto x : str)
{
//如果是空格则加上字符
if(x == ' ')newstr += "%20";
//否则复制
else newstr += x;
}
return newstr;
}
};

面试题6：从尾到头打印链表

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> res;
while(head)
{
res.push_back(head->val);
head = head->next;
}
//类似栈，利用栈的性质
return vector<int>(res.rbegin(), res.rend());
}
};

面试题7：重建二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
map<int, int> hash;
vector<int> preorder, inorder;
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
preorder = _preorder, inorder = _inorder;
//记录根节点在中序中的位置
for(int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;
return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* dfs(int pl, int pr, int il, int ir)
{
if(pl > pr) return nullptr;
auto root = new TreeNode(preorder[pl]);
//找到位置
int k = hash[root->val];
//递归左边的树
auto left = dfs(pl + 1, pl + k - il, il, k - 1);
//递归右边的树
auto right = dfs(pl + k - il + 1, pr, k + 1, ir);
root->left = left;
root->right = right;
return root;
}
};

面试题8：二叉树的下一个节点

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode *father;
*
TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
//分为两种情况
if(p->right)
{
p = p->right;
while(p->left) p = p->left;
return p;
}
while(p->father && p == p->father->right) p = p->father;
return p->father;
}
};

面试题9：用两个栈实现队列

class MyQueue {
public:
//利用两个栈
/** Initialize your data structure here. */
stack<int> stk, cache;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stk.push(x);
}
void copy(stack<int> &a, stack<int> &b)
{
while(a.size())
{
b.push(a.top());
a.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
copy(stk, cache);
int res = cache.top();
cache.pop();
copy(cache, stk);
return res;
}
/** Get the front element. */
int peek() {
copy(stk, cache);
int res = cache.top();
copy(cache, stk);
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/

面试题10：斐波那契数列

class Solution {
public:
int Fibonacci(int n) {
int a = 0, b = 1;
while(n--)
{
int c = a + b;
a = b, b = c;
}
return a;
}
};

面试题11:旋转数组的最小数字

class Solution {
public:
int findMin(vector<int>& nums) {
//二分
int n = nums.size() - 1;
if(n < 0) return -1;
//去除重复数字
while(n > 0 && nums[n] == nums[0])n--;
if(nums[n] > nums[0]) return nums[0];
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[r];
}
};

面试题12:矩阵中的路径

class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string str) {
for (int i = 0; i < matrix.size(); i ++ )
for (int j = 0; j < matrix[i].size(); j ++ )
if (dfs(matrix, str, 0, i, j))
return true;
return false;
}
bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y) {
if (matrix[x][y] != str[u]) return false;
if (u == str.size() - 1) return true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char t = matrix[x][y];
matrix[x][y] = '*';
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
if (dfs(matrix, str, u + 1, a, b)) return true;
}
}
matrix[x][y] = t;
return false;
}
};

面试题13:机器人的运动范围

class Solution {
public:
int get_single_sum(int x)
{
int s = 0;
while(x) s += x % 10, x /= 10;
return s;
}
int get_sum(pair<int, int> p)
{
return get_single_sum(p.first) + get_single_sum(p.second);
}
int movingCount(int threshold, int rows, int cols)
{
int res = 0;
//判断边界条件
if(!rows || !cols) return 0;
vector<vector<bool>> st(rows, vector<bool>(cols));
queue<pair<int, int>> q;
//首先放入起点
q.push({0, 0});
//四个方向
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
while(q.size())
{
auto t = q.front();
q.pop();
//判断是否超出条件
if(get_sum(t) > threshold || st[t.first][t.second]) continue;
//统计结果
res++;
st[t.first][t.second] = true;
//没有超过就加入边界
for(int i = 0; i < 4; i++)
{
int x = t.first + dx[i];
int y = t.second + dy[i];
if(x >= 0 && x < rows && y >= 0 && y < cols)
{
q.push({x, y});
}
}
}
return res;
}
};

面试题14:剪绳子

class Solution {
public:
int maxProductAfterCutting(int n) {
if(n <= 3) return 1*(n - 1);
//尽可能的取3
int res = 1;
if(n % 3 == 1) res *= 4, n -= 4;
if(n % 3 == 2) res *= 2, n -= 2;
while(n) res *= 3, n -= 3;
return res;
}
};

面试题15:二进制中1的个数

class Solution {
public:
int NumberOf1(int _n) {
//防止补码的形式
unsigned int n = _n;
int s = 0;
while(n) s += n & 1, n >>= 1;
return s;
}
};

面试题16:数值的整数次方

class Solution {
public:
double Power(double base, int exponent) {
double res = 1;
for(int i = 0; i < abs(exponent); i++) res *= base;
if(exponent < 0) res = 1 / res;
return res;
}
};

面试题18:删除链表的节点

题目一：在O(1)时间删除链表结点

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};

题目二：删除链表中重复的节点

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while(p->next)
{
auto q = p->next;
while(q && p->next->val == q->val) q = q->next;
if(p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};

面试题19：正则表达式匹配

class Solution {
public:
vector<vector<int>>f;
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
f[n][m] = 1;
dp(0, 0, s, p);
return dp(0, 0, s, p);
}
int dp(int x, int y, string &s, string &p)
{
if (f[x][y] != -1) return f[x][y];
if (y == m)
return f[x][y] = x == n;
bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
bool ans;
if (y + 1 < m && p[y + 1] == '*')
{
ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
}
else
ans = first_match && dp(x + 1, y + 1, s, p);
return f[x][y] = ans;
}
};

面试题20：表示数值的字符串

class Solution {
public:
bool isNumber(string s) {
int i = 0, j = s.size();
while(i <= j && s[j] == ' ') i++;
while(i <= j && s[j] == ' ') j--;
if(i > j) return false;
s = s.substr(i, j -i + 1);
if(s[0] == '+' || s[0] == '-') s = s.substr(1);
if(s.empty() || (s[0] == '.' && s.size() == 1)) return false;
int dot = 0, e = 0;
for(int i = 0; i < s.size(); i++)
{
if(s[i] >= '0' && s[i] <= '9');
else if(s[i] == '.')
{
dot++;
if(dot > 1 || e) return false;
}
else if(s[i] == 'e' || s[i] == 'E')
{
e++;
if(!i || i + 1 == s.size() || e > 1 || s[i - 1] == '.' && i == 1) return false;
if(s[i + 1] == '+' || s[i + 1] == '-')
{
if(i + 2 == s.size()) return false;
i++;
}
}
else return false;
}
return true;
}
};

面试题21：调整数组顺序使奇数位于偶数前面

class Solution {
public:
void reOrderArray(vector<int> &array) {
int n = array.size();
quick(array,0,n - 1);
}
void quick(vector<int> &A, int l, int r)
{
if(l >= r) return;
int
i = l - 1, j = r + 1;
while(i < j)
{
do i ++; while(A[i] % 2 == 1);
do j --; while(A[j] % 2 == 0);
if(i < j) swap(A[i],A[j]);
}
}
};

面试题22：链表中倒数第k个节点

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* head, int k) {
int n = 0;
for(auto p = head; p; p = p->next) n++;
if(k > n) return nullptr;
auto p = head;
for(int i = 0; i < n - k; i++) p = p->next;
return p;
}
};

面试题23：链表中环的入口结点

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(!head || !head->next) return 0;
//快慢指针开始走
ListNode *first = head, *second = head;
while(first && second)
{
first = first->next;
second = second->next;
if(second) second = second->next;
else return 0;
//第一次相遇相遇后，慢指针从头开始走，再相遇就是入口
if(first == second)
{
first = head;
while(first != second)
{
first = first->next;
second = second->next;
}
return first;
}
}
return 0;
}
};

面试题24：反转链表

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//加入一个辅助的前驱节点
ListNode* pre = nullptr;
auto cur = head;
while(cur)
{
auto next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};

面试题25：合并两个排序的链表

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
//虚拟节点
auto dummy = new ListNode(-1);
auto cur = dummy;
//如果l1, l2不为空，则进行插入
while (l1 && l2) {
if (l1 -> val < l2 -> val) {
cur -> next = l1;
l1 = l1 -> next;
}
else {
cur -> next = l2;
l2 = l2 -> next;
}
cur = cur -> next;
}
//还有一个不为空，直接插在后面
cur -> next = (l1 != NULL ? l1 : l2);
return dummy -> next;
}
};

面试题26：树的子结构

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
//先找到根，然后从左边右边开始走
if(!pRoot1 || !pRoot2) return false;
if(isPart(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool isPart(TreeNode* p1, TreeNode* p2)
{
if(!p2) return true;
if(!p1 || p1->val != p2->val) return false;
return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
}
};

面试题27：二叉树的镜像

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void mirror(TreeNode* root) {
//左右子树对调
if(!root) return;
mirror(root->left);
mirror(root->right);
swap(root->left, root->right);
}
};

面试题28：对称的二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return dfs(root->left, root->right);
}
bool dfs(TreeNode *p, TreeNode *q)
{
if(!p || !q) return !p && !q;
if(p->val != q->val) return false;
//左边的左子树，右边的右子树对比
return dfs(p->left, q->right) && dfs(p->right, q->left);
}
};

面试题29：顺时针打印矩阵

class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
int n = matrix.size();
if(!n) return res;
int m = matrix[0].size();
vector<vector<bool>> st(n, vector<bool>(m, false));
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int x = 0, y = 0, d = 1;
//枚举每一个点
for(int i = 0; i < n*m; i++)
{
res.push_back(matrix[x][y]);
st[x][y] = true;
//寻找下一个点
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m || st[a][b])
{
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};

面试题30：包含min函数的栈

class MinStack {
public:
//使用一个辅助栈
stack<int> stk, min_stk;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
stk.push(x);
if(min_stk.empty() || min_stk.top() >= x) min_stk.push(x);
}
void pop() {
if(stk.top() == min_stk.top()) min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/

面试题31：栈的压入、弹出序列

class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
if(popV.size() != pushV.size())return false;
stack<int> s;
int index = 0;
for(int i = 0; i < pushV.size(); i++)
{
s.push(pushV[i]);
while(!s.empty() && s.top() == popV[index])
{
s.pop();
index++;
}
}
if(s.empty())
return true;
return false;
}
};

面试题32：从上到下打印二叉树

题目一：不分行从上往下打印二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> printFromTopToBottom(TreeNode* root) {
vector<int> res;
if(!root) return res;
//宽度优先搜索
queue<TreeNode*> q;
q.push(root);
while(q.size())
{
auto t = q.front();
q.pop();
res.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
return res;
}
};

题目二：分行从上往下打印二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
vector<int> level;
while(q.size())
{
auto t = q.front();
q.pop();
//做了一个标记
if(!t)
{
if(level.empty())break;
res.push_back(level);
level.clear();
q.push(nullptr);
continue;
}
level.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
return res;
}
};

题目三：之字形打印二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
vector<int> level;
bool first_empty = true;
bool zigzag = true;
while(q.size())
{
auto t = q.front();
q.pop();
//做了一个标记
if(!t)
{
if(level.size())
{
if(!zigzag) reverse(level.begin(), level.end());
res.push_back(level);
level.clear();
zigzag = !zigzag;
}
else
{
if(!first_empty) break;
first_empty = false;
}
q.push(nullptr);
continue;
}
level.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
return res;
}
};

面试题33：二叉搜索树的后序遍历序列

class Solution {
public:
vector<int> seq;
bool verifySequenceOfBST(vector<int> sequence) {
seq = sequence;
if (seq.empty()) return true;
return dfs(0, seq.size() - 1);
}
bool dfs(int l, int r)
{
//根据搜索树的特点
if(l >= r) return true;
int root = seq[r];
int k = l;
while(k < r && seq[k] < root) k++;
//k就是分界点，之前的都小于root,之后的都大于root,否则不满足
for(int i = k; i < r; i++)
if(seq[i] < root)
return false;
return dfs(l, k - 1) && dfs(k, r - 1);
}
};

面试题34：二叉树中和为某一值的路径

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//存储所有的方案
vector<vector<int>> ans;
//存储每一种答案
vector<int> path;
vector<vector<int>> findPath(TreeNode* root, int sum) {
dfs(root, sum);
return ans;
}
void dfs(TreeNode *root, int sum)
{
//如果为空则返回
if(!root) return;
//把当前结点加进去
path.push_back(root->val);
sum -= root->val;
if(!root->left && !root->right && !sum) ans.push_back(path);
dfs(root->left, sum);
dfs(root->right, sum);
path.pop_back();
}
};

面试题35：复杂链表的复刻

/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
*
int val;
*
ListNode *next, *random;
*
ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
//复制一份链表，加进去
for(auto p = head; p;)
{
auto np = new ListNode(p->val);
auto next = p->next;
p->next = np;
np->next = next;
p = next;
}
//随机的部分也复制一份
for(auto p = head; p; p = p->next->next)
{
if(p->random)
p->next->random = p->random->next;
}
//提取出复制的链表
auto dummy = new ListNode(-1);
auto cur = dummy;
for(auto p = head; p; p = p->next)
{
cur->next = p->next;
cur = cur->next;
p->next = p->next->next;
}
return dummy->next;
}
};

面试题36：二叉搜索树与双向链表

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convert(TreeNode* root) {
if(!root) return NULL;
auto sides = dfs(root);
return sides.first;
}
pair<TreeNode*, TreeNode*> dfs(TreeNode *root)
{
//只剩一个点时，左边右边一样
if(!root->left && !root->right) return {root, root};
//左右两边都有，如何合并
if(root->left && root->right)
{
auto lsides = dfs(root->left), rsides = dfs(root->right);
lsides.second->right = root, root->left = lsides.second;
root->right = rsides.first, rsides.first->left = root;
return {lsides.first, rsides.second};
}
//只有左边，如何合并
if(root->left)
{
auto lsides = dfs(root->left);
lsides.second->right = root, root->left = lsides.second;
return {lsides.first, root};
}
//只有右边，如何合并
if(root->right)
{
auto rsides = dfs(root->right);
root->right = rsides.first, rsides.first->left = root;
return {root, rsides.second};
}
}
};

面试题37：序列化二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root, res);
return res;
}
void dfs_s(TreeNode *root, string &res)
{
if(!root)
{
res += "null ";
return;
}
res += to_string(root->val) + ' ';
dfs_s(root->left, res);
dfs_s(root->right, res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}
TreeNode* dfs_d(string data, int &u)
{
if(u == data.size()) return NULL;
int k = u;
while(data[k] != ' ') k++;
if(data[u] == 'n')
{
u = k + 1;
return NULL;
}
//加入符号
int val = 0, sign = 1;
if (u < k && data[u] == '-') sign = -1, u ++ ;
for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
val *= sign;
u = k + 1;
auto root = new TreeNode(val);
root->left = dfs_d(data, u);
root->right = dfs_d(data, u);
return root;
}
};

面试题38：数字排列

class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> permutation(vector<int>& nums) {
//先把萝卜坑给挖好
path.resize(nums.size());
//给数字排好序
sort(nums.begin(), nums.end());
dfs(nums, 0, 0, 0);
return ans;
}
void dfs(vector<int> &nums, int u, int start, int state)
{
//如果萝卜填好了坑，那么则加入答案中
if(u == nums.size())
{
ans.push_back(path);
return;
}
if(!u || nums[u] != nums[u - 1]) start = 0;
for(int i = start; i < nums.size(); i++)
{
if(!(state >> i & 1))
{
path[i] = nums[u];
dfs(nums, u + 1, i + 1, state + (1 << i));
}
}
}
};

面试题39：数组中出现次数超过一半的数字

class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
//这里使用摩尔投票法
int cnt = 0, val = -1;
for(auto x : nums)
{
if(!cnt) val = x, cnt = 1;
else
{
if(x == val) cnt++;
else cnt--;
}
}
return val;
}
};

面试题40：最小的k个数

class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
//将最小的k个数加入到优先队列中
priority_queue<int> heap;
for(auto x : input)
{
heap.push(x);
if(heap.size() > k) heap.pop();
}
vector<int> res;
while(heap.size()) res.push_back(heap.top()), heap.pop();
reverse(res.begin(), res.end());
return res;
}
};

面试题41：数据流中的中位数

class Solution {
public:
//最大堆何最小堆
priority_queue<int> max_heap;
//最小堆除了可以直接定义，也可以直接使用最大堆来实现
priority_queue<int, vector<int>, greater<int>> min_heap;
void insert(int num){
max_heap.push(num);
//两种情况
//第一种是逆序
if(min_heap.size() && max_heap.top() > min_heap.top())
{
auto maxv = max_heap.top(), minv = min_heap.top();
max_heap.pop(), min_heap.pop();
max_heap.push(minv), min_heap.push(maxv);
}
//第二种情况下面的堆中的数多了
if(max_heap.size() > min_heap.size() + 1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
}
double getMedian(){
if(max_heap.size() + min_heap.size() & 1) return max_heap.top();
return (max_heap.top() + min_heap.top()) / 2.0;
}
};

面试题42：连续子数组的最大和

class Solution {
public:
int maxSubArray(vector<int>& nums) {
//s表示之前的最大和
int res = INT_MIN, s = 0;
for(auto x : nums)
{
if(s < 0) s = 0;
s += x;
res = max(res, s);
}
return res;
}
};

面试题43：从1到n整数中1出现的次数

class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
if(!n) return 0;
vector<int> number;
while(n) number.push_back(n % 10), n /= 10;
int res = 0;
for(int i = number.size() - 1; i >= 0; i--)
{
auto left = 0, right = 0, t = 1;
for(int j = number.size() - 1; j > i; j--) left = left * 10 + number[j];
for(int j = i - 1; j >= 0; j--) right = right * 10 + number[j], t *= 10;
res += left * t;
if(number[i] == 1) res += right + 1;
else if(number[i] > 1) res += t;
}
return res;
}
};

面试题44：数字序列中某一位的数字

class Solution {
public:
int digitAtIndex(int n) {
//确定是几位数
long long i = 1, s = 9, base = 1;
while(n > i * s)
{
n -= i * s;
i++;
s *= 10;
base *= 10;
}
//确定是几位数的第几个数
//属于那个数的第几位
int number = base + (n + i - 1) / i - 1;
int r = n % i ? n % i : i;
for(int j = 0; j < i - r; j++) number /= 10;
return number % 10;
}
};

面试题45：把数组排成最小的数

class Solution {
public:
//自定义的排序顺序
static bool cmp(int a, int b)
{
auto as = to_string(a), bs = to_string(b);
return as + bs < bs + as;
}
string printMinNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
string res;
for(auto x: nums)res += to_string(x);
return res;
}
};

面试题46：把数字翻译成字符串

class Solution {
public:
int getTranslationCount(string s) {
int n = s.size();
vector<int> f(n+1);
f[0] = 1;
for(int i = 1; i <= n; i++)
{
f[i] = f[i - 1];
int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if(t >= 10 && t <= 25) f[i] += f[i - 2];
}
return f[n];
}
};

面试题47：礼物的最大价值

class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
//利用动态规划进行做题
vector<vector<int>> f(n+1, vector<int>(m+1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
return f[n][m];
}
};

面试题48：最长不含重复字符的子字符串

class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
unordered_map<char, int> count;
int res = 0;
for(int i = 0, j = 0; j < s.size(); j++)
{
if(++count[s[j]] > 1)
{
while(count[s[i]] == 1) count[s[i++]]--;
count[s[i++]]--;
}
res = max(res, j - i + 1);
}
return res;
}
};

面试题49：丑数

class Solution {
public:
int getUglyNumber(int n) {
vector<int> q(1,1);
//从丑数中进行枚举
int i = 0, j = 0, k = 0;
while(--n)
{
int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
q.push_back(t);
if(q[i] * 2 == t) i++;
if(q[j] * 3 == t) j++;
if(q[k] * 5 == t) k++;
}
return q.back();
}
};

面试题50：第一个只出现一次的字符

题目一：字符串中第一个只出现一次的字符

class Solution {
public:
char firstNotRepeatingChar(string s) {
unordered_map<char, int> count;
//使用一次哈希表
for(auto c : s) count[c]++;
char res = '#';
//找到哈希表中所有频率为1的数字
for(auto c : s)
{
if(count[c] == 1)
{
res = c;
break;
}
}
return res;
}
};

题目二：字符流中第一个只出现一次的字符

class Solution{
public:
unordered_map<char, int> count;
queue<char> q;
//Insert one char from stringstream
void insert(char ch){
//如果不是第一个则删除
if(++count[ch] > 1)
{
while(q.size() && count[q.front()] > 1) q.pop();
}
//如果是则插入
else q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if(q.empty()) return '#';
return q.front();
}
};

面试题51：数组中的逆序对

class Solution {
public:
//使用归并
int merge(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
int res = merge(nums, l, mid) + merge(nums, mid + 1, r);
vector<int> temp;
int i = l, j = mid + 1;
while (i <= mid && j <= r)
if (nums[i] <= nums[j]) temp.push_back(nums[i ++ ]);
else {
temp.push_back(nums[j ++ ]);
res += mid - i + 1;
}
while (i <= mid) temp.push_back(nums[i ++ ]);
while (j <= r) temp.push_back(nums[j ++ ]);
int k = l;
for (auto x : temp) nums[k ++ ] = x;
return res;
}
int inversePairs(vector<int>& nums) {
return merge(nums, 0, nums.size() - 1);
}
};

面试题52：两个链表的第一个公共结点

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
auto p = headA;
auto q = headB;
// a + c + b == b + c + a
while(p != q)
{
if(p) p = p->next;
else p = headB;
if(q) q = q->next;
else q = headA;
}
return p;
}
};

面试题53:在排序数组中查找数字

题目一：数字在排序数组中出现的次数

class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
//两次二分
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= k) r = mid;
else l = mid + 1;
}
if (nums[r] != k) return 0;
int left = l;
l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] <= k) l = mid;
else r = mid - 1;
}
return r - left + 1;
}
};

题目二：0到n-1中缺失的数字

class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int n = nums.size() + 1;
//利用求和公式
int res = (n - 1) * n / 2;
for(auto x : nums) res -= x;
return res;
}
};

题目三：数组中数值和下标相等的元素

class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
//用二分查找
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] - mid >= 0) r = mid;
else l = mid + 1;
}
if(nums[r] - r == 0) return r;
return
-1;
}
};

面试题54：二叉搜索树的第k个结点

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* ans;
TreeNode* kthNode(TreeNode* root, int k) {
dfs(root, k);
return ans;
}
void dfs(TreeNode *root, int &k)
{
//这里直接深度搜索下去
if(!root) return;
dfs(root->left, k);
k--;
if(!k) ans = root;
dfs(root->right, k);
}
};

面试题55：二叉树的深度

题目一：二叉树的深度

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int treeDepth(TreeNode* root) {
if(!root) return 0;
//左右子树的最大深度加一
return max(treeDepth(root->left), treeDepth(root->right)) + 1;
}
};

题目二：平衡二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool ans = true;
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode *root)
{
if(!root) return 0;
//这里的话是判断左右两个子树是否深度超过了1
int left = dfs(root->left), right = dfs(root->right);
if(abs(left - right) > 1) ans = false;
//返回最大的深度
return max(left, right) + 1;
}
};

面试题56：数组中数字出现的次数

题目一：数组中只出现一次的两个数字

class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
int sum = 0;
//首先把所有的异或的结果异或出来
for(auto x : nums) sum ^= x;
//之后一其中一位为中心，进行分组
int k = 0;
while(!(sum >> k & 1)) k++;
int first = 0;
for(auto x : nums)
if(x >> k & 1)
//分组后异或的结果就是其中一个了
first ^= x;
//另外一个直接和结果进行异或即可
return vector<int>{first, sum ^ first};
}
};

题目二：数组中唯一只出现一次的数字

class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
//这种是神的操作
int one = 0, two = 0;
for(auto x : nums)
{
one = (one ^ x) & ~two;
two = (two ^ x) & ~one;
}
return one;
}
};

题目57：和为s的数字

题目一：和为S的两个数字

class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
unordered_set<int> hash;
for(int i = 0; i < nums.size(); i++)
{
//直接遍历一边hash
if(hash.count(target - nums[i])) return vector<int> {target-nums[i], nums[i]};
hash.insert(nums[i]);
}
return vector<int>();
}
};

题目二：和为S的连续正数序列

class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
for(int i = 1, j = 1, s = 1; i <= sum; i++)
{
while(s < sum) s += ++j;
if(s == sum && j - i > 0)
{
vector<int> lines;
for(int k = i; k <= j; k++) lines.push_back(k);
res.push_back(lines);
}
s -= i;
}
return res;
}
};

面试题58:翻转字符串

题目一：翻转单词顺序

class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
for(int i = 0; i < s.size(); i++)
{
int j = i;
while(j < s.size() && s[j] != ' ') j++;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
return s;
}
};

题目二：左旋转字符串

class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.begin() + str.size() - n);
reverse(str.begin() + str.size() - n, str.end());
return str;
}
};

面试题59：滑动窗口的最大值

class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); i ++ ) {
while (q.size() && q.front() <= i - k) q.pop_front();
while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};

面试题60：骰子的点数

class Solution {
public:
vector<int> numberOfDice(int n) {
vector<vector<int>> f(n + 1, vector<int>(6 * n + 1, 0));
f[0][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i * 6; j ++ )
for (int k = 1; k <= 6; k ++ )
if (j >= k)
f[i][j] += f[i - 1][j - k];
return vector<int>(f[n].begin() + n, f[n].end());
}
};

面试题61：扑克牌的顺子

class Solution {
public:
bool isContinuous( vector<int> numbers ) {
if(numbers.empty()) return false;
sort(numbers.begin(), numbers.end());
int k = 0;
while(!numbers[k]) k++;
for(int i = k + 1; i < numbers.size(); i++)
if(numbers[i] == numbers[i - 1])
return false;
return numbers.back() - numbers[k] <= 4;
}
};

面试题62：圆圈中最后剩下的数字

class Solution {
public:
int lastRemaining(int n, int m){
if(n == 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
};

面试题63：股票的最大利润

class Solution {
public:
int maxDiff(vector<int>& nums) {
if(nums.empty()) return 0;
int res = 0;
for(int i = 1, minv = nums[0]; i < nums.size(); i++)
{
res = max(res, nums[i] - minv);
minv = min(minv, nums[i]);
}
return res;
}
};

面试题64：求1+2+…+n

class Solution {
public:
int getSum(int n) {
int res = n;
n > 0 && (res += getSum(n - 1));
return res;
}
};

面试题65：不用加减乘除做加法

class Solution {
public:
int add(int num1, int num2){
//这里是用异或操作进行模拟
//最多执行32位
while(num2)
{
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
return num1;
}
};

面试题66：构建乘积数组

class Solution {
public:
vector<int> multiply(const vector<int>& A) {
if(A.empty()) return vector<int>();
int n = A.size();
vector<int> B(n);
//首先正着求解一遍
for(int i = 0, p = 1; i < n; i++)
{
B[i] = p;
p *= A[i];
}
//其次反着求解一遍
for(int i = n - 1, p = 1; ~i; i--)
{
B[i] *= p;
p *= A[i];
}
return B;
}
};

面试题67：把字符串转换成整数

class Solution {
public:
int strToInt(string str) {
int k = 0;
while(k < str.size() && str[k] == ' ') k++;
long long number = 0;
bool is_minus = false;
if(str[k] == '+') k++;
else if(str[k] == '-') k++, is_minus = true;
while(k < str.size() && str[k] >= '0' && str[k] <= '9')
{
number = number * 10 + str[k] - '0';
k++;
}
if(is_minus) number *= -1;
if(number > INT_MAX) number = INT_MAX;
if(number < INT_MIN) number = INT_MIN;
return (int)number;
}
};

面试题68：树中两个结点的最低公共祖先

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return NULL;
if(root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
if(left) return left;
return right;
}
};

最后

以上就是无聊往事为你收集整理的剑指offer所有的题目总结(持续更新题解中...)剑指offer所有的题目总结(c++:2刷)的全部内容，希望文章能够帮你解决剑指offer所有的题目总结(持续更新题解中...)剑指offer所有的题目总结(c++:2刷)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。