算法

算法 面试题
Publish Date:   2021-10-16

@TOC

1.链表篇

反转链表

难度：easy

考察次数：189

传送门

题目描述
输入一个链表，反转链表后，输出新链表的表头。

思路:创建三个指针，一个表示前一个结点pre，一个表示当前节点cur，一个表示后一个节点next。循环next=cur->next，cur->next=pre，pre=cur，cur=next，直到当前节点为NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    ListNode* cur=pHead,*pre=NULL,*next;
        while(cur!=NULL)
        {
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;}
};

判断链表中是否有环

难度：easy

考察次数：120

传送门

题目描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度的解法么？

思路：采用快慢指针解决，慢指针每次向前移动一步，快指针每次向前移动2步，如果链表中有环，快慢指针一定会相遇，注意一下溢出，判断快指针的下一步是不是NULL，如果为NULL则fast->next->next就溢出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast=head,*cur=head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            cur=cur->next;
            fast=fast->next->next;
            if(cur==fast)return true;
        }
        return false;
    }
};

合并有序链表

难度： middle

考察次数：57

传送门

题目描述

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。

思路：先确定表头，创建一个cur表示当前指针，之后比较两个链表表头节点，每次都让cur->next=较小表头的指针，并让该指针移动到其next，直到某链表为空，将剩余链表全部接到cur后面即可。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        ListNode* cur,*head;
            if(l1==NULL)return l2;
            else if(l2==NULL)return l1;
            else if(l1->val<=l2->val){cur=l1;l1=l1->next;}
        else {cur=l2;l2=l2->next;}
        head=cur;
        while(!(l1==NULL&&l2==NULL))
        {
            if(l2==NULL){cur->next=l1;l1=l1->next;}
            else if(l1==NULL) {cur->next=l2;l2=l2->next;}
            else if(l1->val<=l2->val){cur->next=l1;l1=l1->next;}
            else {cur->next=l2;l2=l2->next;}
            cur=cur->next;
        }
        return head;
    }
};

2.动态规划篇

跳台阶

难度: easy

考察次数： 55

传送门

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路： d[i]表示从0到第i个台阶总共的方案数。转移方程：dp[i]=dp[i-1]+dp[i-2]，因为当前台阶可以由前两级台阶走到，初始dp[0]=1,dp[1]=1
。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int jumpFloor(int number) {
    int dp[10000];
        dp[1]=1,dp[0]=1;
        for(int i=2;i<=number;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }
};

子数组的最大累加和

难度：easy

考察次数：52

传送门

题目描述

给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据
[要求]
时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)

思路：dp[i]为以第i个元素为结尾的最大累加和，状态转移方程：dp[i]=max(dp[i-1]+arr[i]，arr[i])，从这可看出其实dp[i]只与dp[i-1]有关，所以对于dp的存储只需要一个空间，每次更新当前dp即可dp(相当于更新后的dp[i])=max(dp(相当于dp[i-1])+arr[i]，arr[i])。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int dp=0,ans=0;
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        for(int i=0;i<arr.size();i++)
        {
            dp=max(dp,0)+arr[i];
            ans=max(ans,dp);
        }
        return ans;
        
    }
};

求路径

难度：easy

考察次数：15

传送门

题目描述

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

在这里插入图片描述

备注：m和n小于等于100,并保证计算结果在int范围内

思路： dp[i][j]表示走到 位置 i,j 的路径数，状态转移方程 dp[i][j]=dp[i-1][j]+dp[i][j-1] ，注意边界的处理情况。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    
    long long dp[105][105];
    long long dfs(int x,int y,int n,int m)
    {
        if(dp[x][y])return dp[x][y];
        if(x<1||x>n||y<1||y>m)return 0;
        return dp[x][y]=dfs(x-1,y,n,m)+dfs(x,y-1,n,m);
    }
    long long uniquePaths(int m, int n) {
        // write code here
        dp[1][1]=1;
        return dfs(m,n,m,n);
    }
};

最长公共子串

难度：middle

考察次数：52

传送门

题目描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

思路： dp[i][j]代表str1串第以第i个字符结尾和str2串的公共串长度。状态转移方程：如果：str1[i]==str2[j]，dp[i][j]=dp[i-1][j-1]+1,如果str1[i]!=str2[j]，dp[i][j]=0。然后题目求的是最长串，那我们只需记录哪时dp[i][j]最大，最长公共串即为此时的i向前取dp[i][j]长度。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    int dp[5005][5005];
        int ans=0;

   
        string LCS(string str1, string str2) {
        
        string str;
        for (int i = 0;i < str1.size();i++)
        {
            for (int j = 0;j < str2.size();j++)
            {
                if (str1[i] == str2[j])
                {
                    if (i - 1 >= 0 && j - 1 >= 0)
                    {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        if (dp[i - 1][j - 1] + 1 > ans)
                        {
                            str = str1.substr(i - dp[i - 1][j - 1], dp[i - 1][j - 1] + 1);
                            ans = max(dp[i - 1][j - 1] + 1, ans);
                        }
                    }
                    else {[`
                        dp[i][j] = 1;
                        if (1 >= ans) { ans = 1;str = str1[i]; }
                    }
                }
                else dp[i][j] = 0;
            }
        }
        return str;
    }
    
};

3.树篇

两个节点最近公共祖先

难度：middle

考察次数：32

传送门

题目描述
给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

思路： 用一个map[i]记录以当前节点i为根，如果子树有一个所要求的节点则map[i]=1,两个则map[i]=2，从根节点深度优先搜索，第一个map为二的节点即为最近的公共祖先。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
   map<int, int> ma;
int dfs(TreeNode* n,int a,int b)
{
	if (n == NULL)return 0;
	if (n->val == a )ma[a]++;
	if (n->val == b )ma[b]++;

		int g = ma[n->val] + dfs(n->left, a, b) + dfs(n->right, a, b);
		if (f==-1 && g >= 2)
		{
			f = n->val;
		}
	return g;
}
int f = -1;
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
	dfs(root, o1, o2);
    return f;

}
};

实现二叉树先中后序排列

难度：middle

考察次数：97

传送门

题目描述
分别按照二叉树先序，中序和后序打印所有的节点。

思路： 深度优先搜索，先序遍历即每到一个节点优先访问当前的节点值，后续遍历最后访问当前节点值，中序遍历先访问左节点再访问当前节点值最后访问右节点。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
#include<stack>

class Solution {
public:
    /**
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    int lst[4][100005];
    int g[4];
    void preorder(TreeNode *p)
    {
        if(p==NULL)return;
        lst[1][++g[1]]=p->val;
        preorder(p->left);
        preorder(p->right);
    }
    void pastorder(TreeNode *p)
    {
        if(p==NULL)return;
        pastorder(p->left);
        pastorder(p->right);
        lst[3][++g[3]]=p->val;
    }
    void inOrder(TreeNode* p)
    {
        if(p==NULL)return;
        inOrder(p->left);
        lst[2][++g[2]]=p->val;
        inOrder(p->right);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        g[1]=0,g[2]=0,g[3]=0;
        preorder(root);
        
        inOrder(root);
        
        pastorder(root);
            
        vector<vector<int>> ans;
        
        for(int i=1;i<=3;i++)
        {
            vector<int> vec;
            for(int j=1;j<=g[i];j++)vec.push_back(lst[i][j]);
            ans.push_back(vec);
        }
        return ans;
    }
};

二叉树之字形遍历

难度：middle

考察次数：37

传送门

题目描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树之字形层序遍历的结果是

[
[3],
[20,9],
[15,7]
]

思路： 每次遍历一层的节点保存到一个列表中，然后下一层要从相反方向遍历，那么只需从当前层的后面往前面遍历子节点即可（每个下一层都是前一层的相反方向就实现了之字形遍历了），还要注意每次到新的一层要改变一下遍历方向，比如这层先遍历左节点再右节点，下层先右节点再左节点。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        if(root==NULL)return ans;
        vector<TreeNode*> vec,t;
        vector<int> lst{root->val};
        ans.push_back(lst);
        vec.push_back(root);
        
        int f=1;
        while(!vec.empty())
        {
           t.clear();
                for(int i=vec.size()-1;i>=0;i--)
                {
                    if(f==1)
                    {
                    if(vec[i]->right!=NULL)t.push_back(vec[i]->right);
                    if(vec[i]->left!=NULL)t.push_back(vec[i]->left);
                        
                    }
                    else
                    {
                    if(vec[i]->left!=NULL)t.push_back(vec[i]->left);
                    if(vec[i]->right!=NULL)t.push_back(vec[i]->right);
                        
                    }
                }
            vec=t;
            vector<int> tt;
            for(int i=0;i<vec.size();i++)tt.push_back(vec[i]->val);
            if(tt.size()==0)break;
            ans.push_back(tt);
            f=-f;
        }
        return ans;
    }
};

4.二分篇

求平方根

难度：easy

考察次数：27

传送门

题目描述
实现函数 int sqrt(int x).
计算并返回x的平方根（向下取整）

思路： 初始化l=0,r=x。直接暴力二分100次，mid=(l+r)/2，如果mid*mid<=x , l=x , 如果mid*mid>x ， r=mid。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        double l=0,r=x,m;
        int i=1;
        while(1)
        {
            if(++i>=500)break;
            m=(l+r)/2;
            if(m*m>=x)r=m;
            else l=m;
        }
        return floor(r);
    }
};

5.其他

岛屿数量

难度：middle

考察次数：24

传送门

题目描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

思路： 用一个book[i][j]记录之前有没有遍历过该处，然后把整个矩阵暴力dfs一遍，遇到lst[i][j]==1则dfs该处，如果该处四周的元素有值为1的，则接着dfs搜索下去每搜索一个地方记录。最后当全部都遍历一遍看需要从矩阵进入遍历几次即为岛屿数量。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int book[505][505];
int x,y;
void dfs(int n,int m,vector<vector<char>> vec)
{
    if(book[n][m]||n<0||m<0||n>x||m>y)return;
    book[n][m]=1;
    if(n+1<=x&&vec[n+1][m]=='1')dfs(n+1,m,vec);
    if(n-1>=0&&vec[n-1][m]=='1')dfs(n-1,m,vec);
    if(m+1<=y&&vec[n][m+1]=='1')dfs(n,m+1,vec);
    if(m-1>=0&&vec[n][m-1]=='1')dfs(n,m-1,vec);
}
    int solve(vector<vector<char> >& grid) {
        // write code here
        x=grid.size()-1;
        y=grid[0].size()-1;
        int ans=0;
        for(int i=0;i<=x;i++)
            for(int j=0;j<=y;j++)
            {
                if(book[i][j]==0)
                {
                    if(grid[i][j]=='1')
                    {
                        dfs(i,j,grid);
                        ans++;
                    }
                }
            }
        return ans;
    }
};

最长无重复子串

难度：middle

考察次数：52

传送门

题目描述
给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

思路：尺取法，用两个坐标记录当前子串前后，每次将前面的坐标往前挪动一格，发现有重复的则将后面的坐标往前收缩直到无重复。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<map>
class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        map<int,int> ma;
        int sum=0;int j=0;
        int ans=0;
        for(int i=0;i<arr.size();i++)
        {
            ma[arr[i]]++;
            if(ma[arr[i]]>=2)sum++;
            while(sum!=0)
            {
                int t=arr[j];
                ma[arr[j++]]--;
                if(ma[t]==1)sum--;
             }
             
            ans=max(ans,i-j+1);
             
        }
        return ans;
    }
};

括号生成

难度：middle

考察次数：13

传送门

题目描述
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
“((()))”, “(()())”, “(())()”, “()()()”, “()(())”,

思路：回溯+剪枝，用一个open代表左括号，close代表右括号，然后dfs遍历所有情况，细节见代码。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> ans;
    int len;
    void solve(int open,int close,string str)
    {
        if(str.size()==2*len)ans.push_back(str);
        if(open<len)solve(open+1,close,str+"(");
        if(close<open)solve(open,close+1,str+")");
    }
    vector<string> generateParenthesis(int n) {
        len=n;
        solve(0,0,"");
        return ans;
    }
};

有重复数字的所有排列

难度：middle

考察次数：11

传送门

题目描述
给出一组可能包含重复项的数字，返回该组数字的所有排列。

思路：回溯，标记好哪个数字被使用与否，暴力dfs，用一个map记录出现过的排列。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int b[10005],n;
    vector<vector<int>> ans;
    vector<int> lst;
    map<vector<int>,int> ma;
    void solve(vector<int> vec,int h)
    {
        if(h==n)
        {
            if(ma[vec]==0)
            {ans.push_back(vec);ma[vec]++;}
            
            return;
        }
        for(int i=0;i<=n-1;i++)
        {
            if(b[i]==0)
            {
                vector<int> t;
                t=vec;
                vec.push_back(lst[i]);
                b[i]=1;
                solve(vec,h+1);
                b[i]=0;
                vec=t;
                
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        n=num.size();
        lst=num;
        vector<int> ss; 
        solve(ss,0);
        return ans;
    }
};
Author: cyy
Link: http://example.com/2021/10/16/%E7%BB%99%E7%A7%8B%E6%8B%9B%E5%8A%A0%E7%82%B9%E6%96%99%E2%80%94%E2%80%94Hot15%E9%81%93%E9%AB%98%E9%A2%91%E7%AE%97%E6%B3%95%E9%9D%A2%E8%AF%95%E9%A2%98%EF%BC%81/
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source cyy !
算法 面试题
赏
 Previous
线段树实现与应用 线段树实现与应用
引子子问题–1给出n个数，m次问询，每次问询给出一个范围l、r，求区间l–r的总和很容易想到用前缀和可以解决 O(n) 子问题–2给出n个数，m次修改，每次给出一个范围l、r和一个值k，将区间l—r的数全部+k，m次修改后，再问询1次求区
2021-10-16 cyy
c++ 算法
Next 
循环链表解决约瑟夫斯问题 循环链表解决约瑟夫斯问题
循环链表解决约瑟夫斯问题问题描述：设有n个人围坐成一个圆圈，按一定指向方向，从第s个人开始报数，数到m的人出列，然后从下一个人重新报数，数到m的人又出列，…，直到n个人全部出列为止。输入：n m s，按次序输出得到的n个人的顺序表。
2021-10-15 cyy
c++ 算法
  TOC