算法面试高频题解指南【一】

​

 博客主页：choice~的博客主页

 

欢迎关注点赞收藏留言

本文由choice~原创，csdn首发！

参考网站：牛客网

首发时间：2022年7月22日

你的收入跟你的不可替代成正比

如果觉得博主的文章还不错的话，请三连支持一下博主哦
给大家介绍一个求职刷题收割offer的地方点击进入网站

目录

 1.NC110 旋转数组

描述：

探讨：

算法思想一：使用额外数组

代码展示：

复杂度分析

算法思想二：数组翻转

解题思路：

代码展示：

复杂度分析

算法思想三：数组变换

代码展示：

复杂度分析

​2.NC78 反转链表

描述：

解法一：迭代

Java参考代码：

解法二：递归

C++参考代码：

算法思路三：使用额外栈

代码展示：

---

 1.NC110 旋转数组

描述：

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围：0 < n \le 1000<n≤100，0 \le m \le 10000≤m≤1000

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

​编辑

这是C语言给的OJ模块 ：

/** * 旋转数组 * @param n int整型 数组长度 * @param m int整型 右移距离 * @param a int整型一维数组 给定数组 * @param aLen int a数组长度 * @return int整型一维数组 * @return int* returnSize 返回数组行数 */int* solve(int n, int m, int* a, int aLen, int* returnSize ) {}

探讨：

这道题呢是牛客网的面试高频榜单题NC110 旋转数组，中等级别,关联的企业和关联职位都要这道题，大家可以拿着这道题好好刷。

​编辑

 分析一下这道题的出现概率是非常大的居然考察数高达87次，这是多么庞大的数字啊，难度也是中等一般，（看下图）通过率也是偏低的；我们知道了为什么我拿这道题讲解的原因了吧！所以很有必要看看

​编辑

题目主要信息:

• 一个长度为nnn的数组，将数组整体循环右移mmm个位置（mmm可能大于nnn）
• 循环右移即最后mmm个元素放在数组最前面，前n−mn-mn−m个元素依次后移
• 不能使用额外的数组空间

算法思想一：使用额外数组

解题思路：

可以使用额外的数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+m) mod n （为了防止右移的长度大于数组的长度，所以才有取余）的位置，最后返回新数组即可

图解：​编辑

代码展示：

JAVA版本

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

import java.util.*; public class Solution {     /**      * 旋转数组      * @param n int整型 数组长度      * @param m int整型 右移距离      * @param a int整型一维数组 给定数组      * @return int整型一维数组      */     public int[] solve (int n, int m, int[] a) {         // write code here         // 额外新数组         int[] newArr = new int[n];         // 遍历原数组         for (int i = 0; i < n; ++i) {             // 数组元素旋转             newArr[(i + m) % n] = a[i];         }         return newArr;     } }

复杂度分析

时间复杂度 O(n)：其中 n 为数组的长度，遍历数组时间O(n)

空间复杂度O(n)： 额外新数组占用空间

算法思想二：数组翻转

解题思路：

该方法基于如下的事实：将数组的元素向右移动 k 次后，尾部 m mod n 个元素会移动至数组头部，其余元素向后移动 m mod n 个位置。
该方法为数组的翻转：翻转算法参考 反转链表中的双指针方法 题解 | #反转链表#_牛客博客

1、可以先将所有元素翻转，这样尾部的 m mod n 个元素就被移至数组头部，

2、然后再翻转 [0,m mod n−1] 区间的元素

3、 最后翻转[m mod n,n−1] 区间的元素即能得到最后的答案。

实例：
以 n=7，m=3 为例进行如下展示：

操作	结果
原始数据	【1，2，3，4，5，6，7】
翻转所有元素	【7，6，5，4，3，2，1】
翻转 [0,m mod n −1] 区间的元素	【5，6，7，4，3，2，1】
翻转 [m mod n, n −1] 区间的元素	【5，6，7，1，2，3，4】

最后返回：【5，6，7，1，2，3，4】

代码展示：

Python版本

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution:     def solve(self , n , m , a ):         # write code here         m = m % n         # 数组反转         # 翻转全部         self.reverse(a, 0, n - 1);         # 再翻转 【0，m-1】         self.reverse(a, 0, m - 1);         # 再翻转 【m，n-1】         self.reverse(a, m, n - 1);         return a               def reverse(self, nums, start, end):         # 数组翻转         while start < end :             # 双指针遍历翻转             temp = nums[start];             nums[start] = nums[end];             nums[end] = temp;             start += 1;             end -= 1;

复杂度分析

时间复杂度：O(N)，其中 N 为数组的长度。每个元素被翻转两次，一共 N 个元素，因此总时间复杂度为 O(2N)=O(N)。
空间复杂度：O(1)。使用常数级空间变量
 

算法思想三：数组变换

解题思路：

简单便利的方法：数组直接变换

1、tmp = m mod n，找到右移的距离

2、采用 a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp] 直接变换

代码展示：

Python版本

1 2 3 4 5 6 7 8

class Solution:     def solve(self , n , m , a ):         # write code here         # 获取移动的距离         tmp = m % n         # 交换移动数组         a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp]         return a

复杂度分析

时间复杂度：O(n)，其中 n 为数组的长度。一共移动n个元素
空间复杂度：O(1)。使用常数级空间变量

举一反三：

学习完本题的思路你可以解决如下题目：

BM99. 顺时针旋转矩阵

方法：三次翻转（推荐使用）

思路：

循环右移相当于从第mmm个位置开始，左右两部分视作整体翻转。即abcdefg右移3位efgabcd可以看成AB翻转成BA（这里小写字母看成数组元素，大写字母看成整体）。既然是翻转我们就可以用到reverse函数。

具体做法:

• step 1：因为mmm可能大于nnn，因此需要对nnn取余，因为每次长度为nnn的旋转数组相当于没有变化。
• step 2：第一次将整个数组翻转，得到数组的逆序，它已经满足了右移的整体出现在了左边。
• step 3：第二次就将左边的mmm个元素单独翻转，因为它虽然移到了左边，但是逆序了。
• step 4：第三次就将右边的n−mn-mn−m个元素单独翻转，因此这部分也逆序了。

图示：​编辑

Java代码实现:

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

publicclassSolution {     publicint[] solve (intn, intm, int[] a) {         //取余，因为每次长度为n的旋转数组相当于没有变化         m = m % n;         //第一次逆转全部数组元素         reverse(a, 0, n - 1);         //第二次只逆转开头m个         reverse(a, 0, m - 1);         //第三次只逆转结尾m个         reverse(a, m, n - 1);         returna;     }     //反转函数     publicvoidreverse(int[] nums, intstart, intend){         while(start < end){             swap(nums, start++, end--);         }     }     //交换函数     publicvoidswap(int[] nums, inta, intb){         inttemp = nums[a];         nums[a] = nums[b];         nums[b] = temp;     } }

C++代码实现:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

classSolution { public:     vector<int> solve(intn, intm, vector<int>& a) {         //取余，因为每次长度为n的旋转数组相当于没有变化         m = m % n;         //第一次逆转全部数组元素         reverse(a.begin(), a.end());         //第二次只逆转开头m个         reverse(a.begin(), a.begin() + m);         //第三次只逆转结尾m个         reverse(a.begin() + m, a.end());         returna;     } };

Python实现代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

classSolution:     def solve(self , n: int, m: int, a: List[int]) -> List[int]:         #取余，因为每次长度为n的旋转数组相当于没有变化         m = m % n         #第一次逆转全部数组元素         a.reverse()         b = a[:m]         #第二次只逆转开头m个         b.reverse()         c = a[m:]         #第三次只逆转结尾m个         c.reverse()         a[:m] = b         a[m:] = c         returna

复杂度分析：

• 时间复杂度：O(n)O(n)O(n)，三次reverse函数的复杂度都最坏为O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)，没有使用额外的辅助空间

接下来再来一道

​编辑2.NC78 反转链表

描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0\leq n\leq10000≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

​编辑

 我们看输出样式

​编辑

/** * struct ListNode { *	int val; *	struct ListNode *next; * }; * * C语言声明定义全局变量请加上static，防止重复定义 * * C语言声明定义全局变量请加上static，防止重复定义 *//** *  * @param pHead ListNode类  * @return ListNode类 */struct ListNode* ReverseList(struct ListNode* pHead ) {    // write code here}

相关企业职位有百度快手，大企 ...

​编辑

解法一：迭代

• 在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

图解：​编辑

Java参考代码：

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

/* public class ListNode {     int val;     ListNode next = null;     ListNode(int val) {         this.val = val;     } }*/ publicclassSolution {     publicListNode ReverseList(ListNode head) {         //pre指针：用来指向反转后的节点，初始化为null         ListNode pre = null;          //当前节点指针         ListNode cur = head;         //循环迭代         while(cur!=null){             //Cur_next 节点，永远指向当前节点cur的下一个节点             ListNode Cur_next = cur.next;             //反转的关键：当前的节点指向其前一个节点(注意这不是双向链表，没有前驱指针)             cur.next = pre;             //更新pre             pre = cur;             //更新当前节点指针             cur = Cur_next ;         }         //为什么返回pre？因为pre是反转之后的头节点         returnpre;     } }

复杂度分析：

时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)，常数空间复杂度

解法二：递归

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ans
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
• 同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。

C++参考代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

/* struct ListNode {     intval;     struct ListNode *next;     ListNode(intx) :             val(x), next(NULL) {     } };*/ classSolution { public:     ListNode* ReverseList(ListNode* pHead) {         //特判：注意不要漏掉pHead->next==NULL的情况     if(pHead==NULL || pHead->next==NULL){         returnpHead;     }         //递归调用         ListNode* ans = ReverseList(pHead->next);         //让当前结点的下一个结点的 next 指针指向当前节点         pHead->next->next=pHead;        //同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转         pHead->next=NULL;         returnans;     } };

复杂度分析：

时间复杂度：O(N)，其中 N 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(N)，其中 N 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 N 层

算法思路三：使用额外栈

解题思路：

新建额外的新栈 stack

循环遍历原链表，并将链表元素入栈，遍历结束后，将栈内元素依次出栈并建立链表

图解：

​编辑

代码展示：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public ListNode ReverseList(ListNode head) {     Stack<ListNode> stack = new Stack<>();     //把链表节点全部摘掉放到栈中     while (head != null) {         stack.push(head);         head = head.next;     }     if (stack.isEmpty())         return null;     ListNode node = stack.pop();     ListNode dummy = node;     //栈中的结点全部出栈，然后重新连成一个新的链表     while (!stack.isEmpty()) {         ListNode tempNode = stack.pop();         node.next = tempNode;         node = node.next;     }     //最后一个结点就是反转前的头结点，一定要让他的next     //等于空，否则会构成环     node.next = null;     return dummy; }

复杂度分析：

时间复杂度O(N)：N表示链表长度

空间复杂度O(N)：辅助栈空间

今天就到这，欢迎成为牛客网的一员！！！点击有惊喜哦​编辑

​