由于之前要准备paper以及研电赛，好久没有更新了，paper已经投了个会议了，然后研电赛只拿到了西北赛区人工智能组的二等奖，没能晋级国赛有点遗憾。废话不多说，准备秋招了，刷点编程题练练手。每题都有思路，有些是参考的，会注明出处。题目顺序参照牛客网，语言选择C++，因为C++速度确实快。
1 二维数组的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution {
public:
/**
利用
每一行都按照从左到右递增的顺序排序
每一列都按照从上到下递增的顺序排序
如果 xx 小于target，则 xx 左边的数一定都小于target，我们可以直接排除当前一整行的数；
如果 xx 大于target，则 xx 下边的数一定都大于target，我们可以直接排序当前一整列的数；
参考：https://www.acwing.com/solution/AcWing/content/702/
*/
bool Find(int target, vector<vector<int> > a) {
//如果a为空 直接返回false
if(a.empty()||a[0].empty())return false;
int i = 0, j = a[0].size() - 1;//要从右上角往左下角找
while(i < a.size() && j >= 0){
if(a[i][j] == target)return true;//找到直接返回
if(a[i][j] > target) j--;//列往左边移动
else i++;//行往下移动找
}
return false;
}
}; 2 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str,int length) {
if(str == NULL) return; //如果是空 直接返回
//空格数 原始串的长 新串的长
int blanks = 0, len = 0, newlen = 0;
for(int i = 0;str[i]!='\0';i++){
len++;
if(str[i]==' ')
blanks++;
}
//新串的长 每次替换 多增加两个字符
newlen = len + 2*blanks;
//如果新串的长大于length 直接返回
if(newlen + 1 > length)return;
//str1指针指向旧串的最后一个字符
char * str1 = str + len;
//str2指针指向新串的最后一个字符
char * str2 = str + newlen;
//从后向前自制旧串 并替换空格
while(str1 != str2){
if(*str1 == ' '){
*str2 -- = '0';
*str2 -- = '2';
*str2 -- = '%';
}
else
*str2 -- = *str1;
--str1;
}
}
}; 3 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
没有什么要求，直接遍历一次链表，每次向vector.begin()处插入就行了
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
while(head){
res.insert(res.begin(),head->val);
head = head->next;
}
return res;
}
}; 4 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
算法
(递归) O(n)O(n)
递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。
具体步骤如下：
先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；
在中序遍历中找到根节点的位置 kk，则 kk 左边是左子树的中序遍历，右边是右子树的中序遍历；
假设左子树的中序遍历的长度是 ll，则在前序遍历中，根节点后面的 ll 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；
时间复杂度分析
我们在初始化时，用哈希表(unordered_map<int,int>)记录每个值在中序遍历中的位置，
这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，
只需要 O(1)O(1) 的时间。此时，创建每个节点需要的时间是 O(1)O(1)，所以总时间复杂度是 O(n)O(n)。
参考：https://www.acwing.com/solution/AcWing/content/706/
*/
class Solution {
public:
TreeNode* dfs(unordered_map<int,int> &pos,vector<int> &pre, vector<int> &vin, int pl, int pr, int vl, int vr){
if(pl > pr)return 0;
int k = pos[pre[pl]] - vl ;//k的左边为左子树，右边为右子树
TreeNode* root = new TreeNode(pre[pl]);//创建根
root->left = dfs(pos, pre, vin, pl + 1, pl + k, vl, vl + k - 1);//递归创建左子树，更新下次pre和vin
root->right = dfs(pos, pre, vin, pl + k + 1, pr, vl + k + 1, vr);//递归创建右子树，更新下次pre和vin
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int n = pre.size();
unordered_map<int,int> pos;//记录中序遍历的位置
for(int i = 0; i < n; i++){
pos[vin[i]] = i;
}
return dfs(pos, pre, vin, 0, n - 1, 0, n - 1);
}
}; 5 用栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
/**
用两个栈 一个缓存用
当操作时 先把主栈的数据先全部放到缓存
然后再pop
完成后放到主栈
**/
class Solution
{
public:
void copy(stack<int> &a, stack<int> &b) {
while (a.size()) {
b.push(a.top());
a.pop();
}
}
void push(int node) {
stack1.push(node);
}
int pop() {
copy(stack1,stack2);
int res = stack2.top();
stack2.pop();
copy(stack2,stack1);
return res;
}
private:
stack<int> stack1;//主栈
stack<int> stack2;//缓存栈
}; 6 旋转数组中最小的数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
/**
数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转
可以看出
因为旋转前数组是递增
旋转后有一个这个递增就断了
相当于找到一个数比第一个数小的情况
就可以返回这个数
**/
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(!rotateArray.size())return 0;
int res = rotateArray[0];
for(int i = 1; i < rotateArray.size(); i++){
if(rotateArray[i] < res)return rotateArray[i];
}
return res;
}
}; 7 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。
/**
这个没什么好说的
建议用递推
除非面试官要求 否则不要用递归
**/
class Solution {
public:
int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int first = 0, second = 1, third = 0;
while(n--){
third = first + second;
first = second;
second = third;
}
return first;
}
}; 8 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
/**
假设处于当前台阶
那么从其他台阶跳上来的
要么从前一个台阶跳上来 要么从前面第2个跳过来
那么 跳到当前台阶的就有f(n-1) + f(n - 2)
**/
class Solution {
public:
int jumpFloor(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
return jumpFloor(n - 1) + jumpFloor(n - 2);
}
}; 9 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
/**
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
假设
f(1) = 1;
所以：
f(2)=1+f(1)=1+1=2=2^1;
f(3)=1+f(2)+f(1)=1+2+1=4=2^2;
f(4)=1+f(3)+f(2)+f(1)=1+4+2+1=8=2^3;
......
归纳：
f(n) = 2^(n-1);（n>=1的整数）
**/
class Solution {
public:
int jumpFloorII(int number) {
int a = 1;
return a << (number - 1);//左移乘2 右移除2 如在折半查找中 可以 int mid = (l + r) >> 1
}
}; 10 矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution {
public:
int rectCover(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int first = 1, second = 2, third = 0;
for(int i=3;i<=n;i++){
third = first + second;
first = second;
second = third;
}
return third;
}
}; 11 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
/**
(位运算) O(logn)O(logn)
迭代进行如下两步，直到 nn 变成0为止：
如果 nn 在二进制表示下末尾是1，则在答案中加1；
将 nn 右移一位，也就是将 nn 在二进制表示下的最后一位删掉；
这里有个难点是如何处理负数。
在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 nn 永远不为0，就死循环了。
解决办法是把 nn 强制转化成无符号整型，这样 nn 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。
时间复杂度
每次会将 nn 除以2，最多会除 lognlogn 次，所以时间复杂度是 O(logn)O(logn)。
参考大神：https://www.acwing.com/solution/AcWing/content/732/
**/
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int u = n;
while(u) res += u & 1, u >>= 1;
return res;
}
}; 12 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
/**
求幂就是n个base相乘
如果是负数，取倒数
**/
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;
}
}; 13 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
/**
由于没有内存申请限制
直接用两个队列 一个装奇数 一个装偶数
依次按放到原来的数组
**/
class Solution {
public:
void reOrderArray(vector<int> &array) {
queue<int> s1,s2;
for(auto it: array){
if(it % 2 == 0)
s2.push(it);
else s1.push(it);
}
for(int i = 0; i < array.size(); i++){
if(!s1.empty()){
array[i] = s1.front();
s1.pop();
}
else{
array[i] = s2.front();
s2.pop();
}
}
}
}; 14 链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
先算出链表的长度n
倒数第k个结点即为顺数第n-k个结点
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
int len = 0;
auto cur = pListHead;
while(cur){
len++;
cur = cur->next;
}
if(pListHead == NULL || k > len || k < 1)return NULL;
int i = len - k;
cur = pListHead;
while(i--){
cur = cur->next;
}
return cur;
}
}; 15 反转链表
输入一个链表，反转链表后，输出新链表的表头
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *pre = NULL, *next = NULL;
while(pHead){
//做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
//如此就可以做到反转链表的效果
//先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
next = pHead->next;//记录当前结点的下一个结点
//保存完next，就可以让head从指向next变成指向pre了
pHead->next = pre;
//head指向pre后，就继续依次反转下一个节点
//让pre，head，next依次向后移动一个节点，继续下一次的指针反转
pre = pHead;
pHead = next;
}
//如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
//直接输出pre就是我们想要得到的反转后的链表
return pre;
}
}; 16 合并两个有序链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
没有什么可说的
就像合并两个有序数组
*/
class Solution {
public:
ListNode* Merge(ListNode* p1, ListNode* p2)
{
auto d = new ListNode(-1);//虚拟头结点
auto t = d;
while(p1&&p2){
if(p1->val < p2->val){//小的先排
t->next = p1;
p1 = p1->next;
t = t->next;
}
else{
t->next = p2;
p2 = p2->next;
t = t->next;
}
}
if(p1)t->next = p1;//如果还有直接接到t的屁股后面
if(p2)t->next = p2;
return d->next;
}
}; 17 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
算法
(二叉树，递归) O(nm)O(nm)
代码分为两个部分：
遍历树A中的所有非空节点R；
判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；
对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。
对于第二部分，我们同时从根节点开始遍历两棵子树：
如果树B中的节点为空，则表示当前分支是匹配的，返回true；
如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；
时间复杂度
最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
所以时间复杂度是 O(nm)O(nm)，其中 nn 是树A中的节点数， mm 是树B中的节点数。
参考大神：https://www.acwing.com/solution/AcWing/content/745/
};*/
class Solution {
public:
bool isSubtree(TreeNode* r1, TreeNode* r2){
if(!r2)return true;
if(!r1 || r1->val != r2->val)return false;
return isSubtree(r1->left, r2->left) && isSubtree(r1->right, r2->right);
}
bool HasSubtree(TreeNode* r1, TreeNode* r2)
{
if(!r1 || !r2)return false;
if(isSubtree(r1, r2))return true;
return HasSubtree(r1->left, r2) || HasSubtree(r1->right, r2);
}
}; 18 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
/*
没什么好说的
直接交换当前结点的左右孩子
如果当前结点还有左右孩子
分别递归交换
直到递归结束
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *r) {
if(!r)return;//没有左右孩子则直接返回
swap(r->left,r->right);//交换左右孩子
Mirror(r->left);//递归，继续遍历左子树
Mirror(r->right);//递归，继续遍历右子树
}
}; 19 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
/**
分别得到行和列的开始和末尾索引
首先遍历完当前行后 开始行++
然后列从开始行索引开始遍历后 列--
末尾行从末尾列往回遍历
开始列从末尾行到开始行往回遍历
直到list长度和size一样 结束循环
由于没有其他空间，不算题目要的list的话 空间复杂度O(1) 时间复杂度O(n^2)
**/
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> list;
if(matrix.size() == 0) return list;
//水平行的最开始的索引 和 最后的索引
int h_first_index = 0, h_last_index = matrix.size() - 1;
//垂直列的最开始的索引 和 最后的索引
int v_first_index = 0, v_last_index = matrix[0].size() - 1;
//数组的长度
int size = (h_last_index + 1)*(v_last_index + 1);
//是否遍历结束
bool flag = true;
while(flag){
// 先算开始第一行
for(int i = v_first_index;i <= v_last_index;i++) {
list.push_back(matrix[h_first_index][i]);
if(list.size() >= size){
flag = false;
break;
}
}
h_first_index ++;
if(list.size() >= size){
break;
}
// 再算最后一列
for(int i=h_first_index;i<=h_last_index;i++) {
list.push_back(matrix[i][v_last_index]);
if(list.size() >= size){
flag = false;
break;
}
}
v_last_index --;
if(list.size()>=size){
break;
}
// 再算最后一行
for(int i=v_last_index;i>=v_first_index;i--) {
list.push_back(matrix[h_last_index][i]);
if(list.size() >= size){
flag = false;
break;
}
}
h_last_index --;
if(list.size()>=size){
break;
}
// 最后算开始第一列
for(int i = h_last_index;i >= h_first_index;i--) {
list.push_back(matrix[i][v_first_index]);
if(list.size() >= size){
flag = false;
break;
}
}
v_first_index ++;
if(list.size() >= size){
break;
}
}
return list;
}
}; 另外，我还写了一个递归的版本可以用一个bool数组来判断是否遍历，这个消耗一点空间，但是代码看起来很清晰，代码：
int di[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
vector<int> res;
vector<vector<bool>> used;
bool isArea(int x, int y, int row, int col){
return row>=0 && row<x && col>=0 && col<y;
}
void dfs(int d, const vector<vector<int> > &matrix, int x, int y, int row, int col){
int dx = di[d%4][0], dy = di[d%4][1];
if(isArea(x,y,row,col) && !used[row][col]){
int tempRow = row, tempCol = col;
row += dx, col += dy;
if(!isArea(x,y,row,col) || used[row][col] ){
if(res.size() + 1 == x * y){//只有最后一个元素了，直接添加并返回
res.push_back(matrix[tempRow][tempCol]);
return;
}
dfs(d + 1, matrix, x, y, row - dx, col - dy);
}else{
cout<<matrix[tempRow][tempCol]<<endl;
res.push_back(matrix[tempRow][tempCol]);
used[tempRow][tempCol] = true;
dfs(d, matrix, x, y, row, col);
}
}
}
vector<int> printMatrix(vector<vector<int> > &matrix) {
if(!matrix.size() || !matrix[0].size()) return res;
int x = matrix.size(),y = matrix[0].size();
used = vector<vector<bool>>(x, vector<bool>(y, false));
dfs(0, matrix, x, y, 0, 0);
return res;
} 也可以参考yxc大神的方法。
class Solution {
public:
vector<int> printMatrix(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.empty()) return res;
int n = matrix.size(), m = matrix[0].size();
vector<vector<bool>> st(n, vector<bool>(m, false));
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int x = 0, y = 0, d = 1;
for (int k = 0; k < n * m; k ++ )
{
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;
}
};
参考链接：https://www.acwing.com/solution/AcWing/content/748/
20 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
class Solution {
public:
/**
我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
下面介绍如何维护单调栈：
当我们向栈中压入一个数时，如果该数 ≤≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。
时间复杂度
四种操作都只有常数次入栈出栈操作，所以时间复杂度都是 O(1)O(1).
参考链接：https://www.acwing.com/solution/AcWing/content/749/
*/
stack<int> m;
stack<int> s;
void push(int value) {
s.push(value);
if(m.empty() || m.top() >= value)
m.push(value);
}
void pop() {
if(m.top() == s.top()) m.pop();
s.pop();
}
int top() {
return s.top();
}
int min() {
return m.top();
}
};
京公网安备 11010502036488号