给秋招加点料——Hot15道高频算法面试题！

桃扇骨 2021-07-16 15:15 492阅读 0赞

### 目录 ###

*  1.链表篇
 *   *  反转链表
     *  判断链表中是否有环
     *  合并有序链表
 *  2.动态规划篇
 *   *  跳台阶
     *  子数组的最大累加和
     *  求路径
     *  最长公共子串
 *  3.树篇
 *   *  两个节点最近公共祖先
     *  实现二叉树先中后序排列
     *  二叉树之字形遍历
 *  4.二分篇
 *   *  求平方根
 *  5.其他
 *   *  岛屿数量
     *  最长无重复子串
     *  括号生成
     *  有重复数字的所有排列

# 1.链表篇 #

## 反转链表 ##

**难度：easy**

**考察次数：189**

[**传送门**][Link 1]

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

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

/* 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**

[传送门][Link 2]

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

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

/** * 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**

**[传送门][Link 3]**

**题目描述**

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

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

**AC code**

/** * 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**

**[传送门][Link 4]**

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

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

**AC code**

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**

[**传送门**][Link 5]

**题目描述**

给定一个数组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**

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**

[**传送门**][Link 6]

**题目描述**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]

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

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

**AC code**

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**

**[传送门][Link 7]**

**题目描述**  
给定两个字符串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**

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**

[**传送门**][Link 8]

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

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

**AC code**

/** * 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**

[**传送门**][Link 9]

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

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

**AC code**

/** * 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**

[**传送门**][Link 10]

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

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

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

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

**AC code**

/** * 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**

**[传送门][Link 11]**

**题目描述**  
实现函数 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**

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**

**[传送门][Link 12]**

**题目描述**

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

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

**AC code**

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**

**[传送门][Link 13]**

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

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

**AC code**

#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**

**[传送门][Link 14]**

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

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

**AC code**

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**

**[传送门][Link 15]**

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

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

**AC code**

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;
        }
    };

[Link 1]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=117&tqId=37777&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 2]: https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=117&tqId=37714&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 3]: https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=117&tqId=37735&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 4]: https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=117&&tqId=37764&&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking
[Link 5]: https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=117&tqId=37797&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 6]: https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=117&tqId=37736&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/e0a37a38edc6464c83e814ec64727f34.png
[Link 7]: https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117&tqId=37799&companyId=146&rp=1&ru=%2Fcompany%2Fhome%2Fcode%2F146&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
[Link 8]: https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&tqId=37826&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 9]: https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117&tqId=37819&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 10]: https://www.nowcoder.com/practice/47e1687126fa461e8a3aff8632aa5559?tpId=117&tqId=37722&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 11]: https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=117&tqId=37734&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 12]: https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=117&tqId=37833&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 13]: https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=117&tqId=37816&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 14]: https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca?tpId=117&tqId=37748&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey
[Link 15]: https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=117&tqId=37739&companyId=146&rp=1&ru=/company/home/code/146&qru=/ta/job-code-high/question-ranking&tab=answerKey