【3 编程语言】3.1 数据结构与算法（上）
3.1 数据结构与算法
【考点讲解】
- 面试中假如遇到编程题，不要一上来就盲目作答，首先应该弄清题意，和面试官确认好限定条件，比如：排序算法，如果面试官要求处理的数据量比较大，并且要求空间复杂度比较低，那么你就不应该用计数排序去作答，因为计数排序会占用更多的空间资源。
- 题意清晰之后，如果还是没有头绪，可以先采用归纳法寻找解题规律，找到规律后，再组织成代码；如果涉及大数据量的问题，应当优先想到分治法去解题，把大数据量拆分成一个一个小单元去处理，最后再合并结果。
- 如果编程能力比较薄弱，真的无法完成题目，可以尝试去设计一下该编程题的测试用例，把输入参数和预期结果列举出来。如果可以把编程题的解题思路讲清晰，就算没有真正能够写出完整的代码，也总比吭哧吭哧想半天之后，写出来的代码错漏百出的强。
- 模拟：尝试去模拟题目运行。
- 规律：通过模拟运行，找出题目的规律和解题突破口。
- 匹配：找到合适的数据结构与算法去进行套用解题。
- 边界值：考虑到边界情况，避免程序出Bug。
- 数组
- 链表
- 字符串
- 二叉树
- 树
- 栈
- 堆
- 哈希表
- 贪心算法
- 动态规划
- 双指针迭代
- 搜索
- 排序
- 分治法
- 递归
- 循环
【例题示例】
3.1.1 数组和链表的区别？
- 数组
- 链表
- 数组静态分配内存，链表动态分配内存；
- 数组在内存中连续，链表不连续；
- 数组元素在栈区，链表元素在堆区；
- 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
- 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
3.1.2 如何反转链表？
- 链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
（leetcode 206题）
（1）双指针迭代法：
/**
* Definition for singly-linked list.
* 题目已经帮我们构造好了一个链表节点定义
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 边界值判断：当链表只有一个节点，或者链表为空，无需反转链表
if (head == null || head.next == null){
return head
}
// 定义一个pre变量，用于存储当前节点的前驱节点
ListNode pre = null;
// 定义一个cur变量，用于存储当前节点，链表的第一个节点是传入的 head 节点。
ListNode cur = head;
while (cur != null) {
// next 变量存储当前节点的后继节点
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
head = pre
return head;
}
}
- 时间复杂度：O(n)，其中n是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)。
（2）递归法
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
- 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
- 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
3.1.3 求数组中第k个最大元素？
- 排序算法
- 堆
- 快速排序
在未排序的数组中找到第 k 个最大的元素。请注
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
测试工作无非就是点点点，没有太深的技术难度？<br/> 开发转投测试岗，原以为自身的条件能轻松胜任测试岗却反被面试官虐？<br/> 测试岗究竟要准备哪些技术知识去应对面试？<br/> 如何才能在测试岗面试中做到游刃有余？<br/> <p> <span>本专刊从测试岗面试考察的知识点和能力出发，精选出经典的测试岗面试题，不仅给出面试的典型回答和考点分析，还会剖析知识点，将其讲清讲透，让你彻底领悟题目背后所考察的能力，帮你梳理复习测试岗的知识体系。</span> </p> <h3> <span><br /> </span><span><strong>专刊主要分为3大模块：</strong></span> </h3> <p> <span>1. 岗位校招情况介绍：</span> </p> <p> <span>将对整个测试岗位进行详细的介绍，包括测试岗位的分类、市场需求量、薪资情况和校招概况，都会逐一做介绍，让同学们能对测试岗位的校招情况有个大概的了解<br /> 2. 面试考点和面试题讲解：</span> </p> <p> <span>这是本章最为核心的部分，将会以面试题讲解的形式，不仅给出面试题参考答案，还会对考点进行分析，剖析其中的知识点，把知识点讲清讲透，帮助同学们梳理复习测试岗的知识体系。本章涉及的知识板块有：软件测试基础知识、测试用例设计、排查问题的思路、常用的测试工具、计算机操作系统、计算机网络、编程语言和常考的智力题。内容丰富，基本上涵盖了测试面试常考的知识点。<br /> 3. 求职经验分享：</span> </p> <p> <span>本章将详细讲解面试的注意事项：从面试前的准备、面试当天到面试结束收到offer整个过程，都会进行逐一讲解。</span> </p> <p> <span><br /> </span> </p> <h3> <span>专刊大纲：</span> </h3> <p> <span><img src="https://uploadfiles.nowcoder.com/images/20210625/691666214_1624592824918/B4749CDE6B040FF304C11BA36D1276D5" alt="" width="700" height="1692" title="" align="" /><br /> <br /> </span> </p> <h3> <span>购买须知：</span> </h3> <span>①订阅成功后，用户即可通过牛客网 PC 端、App 端享有永久阅读的权限；<br /> ②牛客专刊为虚拟内容服务，订阅成功后概不退款；<br /> ③在专刊阅读过程中，如有任何问题，可在文章评论区底部留言，或添加牛客求职导师，加入读者交流群；<br /> ④想成为牛客作者，请邮件联系pandengfeng@nowcoder.com，邮件主题【牛客作者+写作方向】，并附上个人简历一份及近期作品一份；<br /> ⑤牛客专刊版权归本平台所有，任何机构、媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发布 / 发表，违者将依法追究责任。<br /> </span> <p> <span>了解专刊更多详细信息，请扫码添加丸子老师微信~</span> </p> <p> <br /> </p> <p> <img src="https://uploadfiles.nowcoder.com/images/20210526/999991364_1622023901811/2E767EB5BD55BF57B67C8E5427B978D8" alt="" /> </p>
