代码面试编程知识点总结，内容来自牛客网剑指offer和题霸面试必考真题【算法篇】专题。
剑指offer
数据结构
链表
JZ6 从尾到头打印链表
- 利用STL中的
reverse()函数反转区间元素次序； - 利用
stack“先进后出”的特性反转区间元素次序；
JZ24 反转链表
使用两个指针完成，一个指针ppre用来指向当前节点的前一节点；一个指针pnext用来指向当前节点的下一节点。
核心代码：
while(pHead) {
pnext = pHead->next;
pHead->next = ppre;
ppre = pHead;
pHead = pnext;
}
JZ25 合并两个排序的链表
使用两个指针完成。
JZ52 两个链表的第一个公共节点
使用双指针，先后遍历两个链表，会在公共节点处相遇。
核心代码：
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 != p2) {
if (p1 == nullptr) p1 = pHead2;
if (p2 == nullptr) p2 = pHead1;
}
}
JZ22 链表中倒数最后k个结点
使用两个相距k的指针同时前进。
JZ18 删除链表的节点
- 使用两个指针分别指向当前节点和当前节点的上一节点；
- 注意删除链表头结点的特殊情况；
核心代码：
if (head == nullptr) return nullptr;
if (head->val == val) return head->next;
ListNode* p_last = nullptr;
ListNode* p_current = head;
while(p_current) {
if (p_current->val == val) {
p_last->next = p_current->next;
}
p_last = p_current;
p_current = p_current->next;
}
return head;
树
JZ55 二叉树的深度
递归调用，分别计算左右子树的深度并取最大值；
核心代码：
if (!pRoot) return 0;
int lval = TreeDepth(pRoot->left);
int rval = TreeDepth(pRoot->right);
return max(lval, rval) + 1;
JZ77 按之字形顺序打印二叉树
- 使用
queue保存上一层根节点，不断在循环中更新； - 使用
vector<vector>保存每一层节点； - 根据层数判断是否需要反转输出；
JZ7 重建二叉树
- 判断空二叉树、单节点情况；
- 前序遍历中，根在最前面；
- 在中序遍历中找到根节点，分出左右树，左闭右开；
- 递归调用重建；
JZ27 二叉树的镜像
交换左右节点，递归调用。
队列&栈
JZ9 用两个栈实现队列
- 实现
stack的push()和pop()成员函数； - 一个栈保存正序队列，另外一个栈保存反序队列；
JZ30 包含min函数的栈
使用两个栈，一个正常保存元素，一个保存当前最小值；
算法
搜索算法
JZ72 数字在升序数组中出现的次数
- 暴力求解；
- 数组有序，采用二分查找；
- 利用STL中的
equal_range()函数查找，本质上也是二分查找；
JZ4 二维数组中的查找
- 判断输入二维数组是否为空（两个维度都要判断）；
- 考虑元素排列有序，从左下角开始遍历优于从右上角开始遍历，因为不需考虑下标越界的问题；
- 如果当前元素大于目标元素，则减小行数；如果当前元素小于目标元素，则增大列数；
- 暴力求解注意行列数可能不同；
JZ11 旋转数组的最小数字
采用两头比较，两个指针指向数组头尾。
动态规划
JZ42 连续子数组的最大和
dp[i]代表以第i个元素为截止点的连续子序列的最大和。
JZ69 跳台阶
递归调用。
JZ10 斐波那契数列
可以通过递归调用求解，类似问题还有JZ70 矩形覆盖。
此类问题可以转化为动态规划问题，找到递推公式后自下而上求解，例如：JZ71 跳台阶扩展问题。
回溯
排序
JZ3 数组中重复的数字
- 数组中数字有范围；
- 使用
a[i]保存数字i出现的次数；
JZ40 最小的K个数
- 使用
vector保存最小的K个数； - 每次循环后都利用STL中的
sort()函数排序； - 新元素只需与其中的最大值比较；
位运算
JZ65 不用加减乘除做加法
- 无进位和运算是按位异或运算；
- 进位和运算是按位与运算并且结果左移一位；
- 计算无进位和+进位和；
核心代码：
while (num2 != 0) {
// 负数左移会在低位补1，所以转化为无符号整数
int c = ((unsigned int)(num1 & num2)) << 1;
num1 ^= num2;
num2 = c;
}
return num1;
JZ15 二进制中1的个数
-
使用位运算；
核心代码：
if (n & 1) { // 取最后一位数字，优于n % 2; count++; } n = n >> 1; // 右移一位，优于n = n / 2; -
采用其他方法注意负数补码；
JZ12 数值的整数次方
- 底数和指数不能同时为零；
- 正负指数分类讨论；
- 负指数时底数不能为零；
模拟
其他算法
JZ51 构建乘积数组
双层循环暴力求解。
JZ2 替换空格
使用string类的append()和push_back()成员函数，注意二者作用的区别。
JZ13 调整数组顺序使奇数位于偶数前面
- 使用两个
queue分别保存奇数和偶数； - 利用
queue“先进先出”的特性调整数组顺序；
JZ28 数组中出现次数超过一半的数字
- 暴力求解：根据数据范围构建一维数组
a[]，使用a[i]保存数字i出现的次数，以空间换时间； - 对数组排序，若数组中出现次数超过一半的数字存在，则下标为
[N/2]的元素满足要求；
题霸面试必考真题
NC1 大数加法
- 判断输入是否为空；
- 为输出字符串多留一位，供进位使用；
- 从最低位开始计算；
-
字符转整数；
核心代码：
int x = ind1 >= 0 ? s[ind1] - '0' : 0; int y = ind2 >= 0 ? t[ind2] - '0' : 0; - 判断是否进位，若有，取子字符串输出；
NC4 判断链表中是否有环
使用快慢指针，慢指针每次走一步，快指针每次走两步，如果相遇说明有环。
NC14 按之字形顺序打印二叉树
同JZ59。
NC34 求路径
动态规划问题，dp[i][j]表示从起点到达第i行第j列的路径数。
NC53 删除链表的倒数第n个节点
- 判断输入是否为空；
- 两个相距n的指针同时前进；
NC66 两个链表的第一个公共节点
同JZ36。
NC127 最长公共子串
动态规划问题；
NC140 排序
几种常用的排序算法；
以选择排序为例：
int N = arr.size();
for (int i = 0; i < N - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < N - 1; j++) {
if (arr.at(j) < arr.at(minIdx)) {
minIdx = j;
}
}
swap(arr.at(i), arr.at(minIdx));
}
还可以直接利用STL中的sort()函数排序。