数据结构与算法面试常考题

 关于“树”的那些事，一起来学习吧！

题目描述：给定一个 n 个数，求解有多少个长度为奇数的区间的中位数位置刚好就在正中间。输入：第一行输入 t ，表示 t 组输入第二行输入 n，数组大小为 n 第三行输入 n 个数。t 组输入的 n 的个数和不超过 10000。思路：通过数据，可以预估该题时间复杂度，初步预估O（nlogn），不过发现二分啥的都解不了。思考O（n * n）思路。发现常数不大，完全没问题。思路一：（dp数数）数数题，一般思路，遍历一遍数组，在 i 位置时统计添加一个 a[i] 元素，会新增多少个满足答案的区间。例：3 2 1 4 5 i = 1时，新增 1 个区间。[1, 1]i = 2时，新增 1 个区间。[2,...

 排序相关题目，转需！

无论你是刚入门编程还是已经有一定经验，掌握数据结构与算法都是提升你编程技能的关键。在这个精彩的领域里，我们将深入探索各种数据结构和算法的原理、应用和优化方法，让你成为一个更出色的程序员。你可以通过巧妙地选择合适的数据结构，在处理海量数据时实现高效率；或者运用精心设计的算法解决复杂问题，并获得最佳解决方案。这不仅仅是关于提高代码性能，更是关于拓宽思维、培养抽象分析能力和解决问题的技巧。本篇将带领你逐步了解各种常见数据结构（如数组、链表、栈、队列、树等）和经典算法（如排序、查找、图算法等），并深入研究它们之间的联系和优劣势。我们还会介绍高级主题，如动态规划、贪心算法和回溯等，以及应用于实际项目中的...

有更好的方法或者是有问题想讨论的同学可以评论or私信我，大家一起学习一起进步～       2022/4/2   I.链表环相关    牛客网-在线编程-算法篇-面试必刷top101-链表bm6   1.判断链表中是否有环   -方法1. 使用快慢指针 time: O(n) space: O(1)   定义慢指针slow和快指针fast, slow一次走一步，fast一次走两步。若链表无环，则slow和fast不可能相遇。若slow和fast相遇了，则链表一定有环。具体代码如下，   function hasCycle( head ) {   //corner case, empty link...

思路：将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法建立单链表)，直到最后一个结点为止   代码如下（摘自：C语言中文网）：    LinkList Reverse_l(LinkList &L) {     //L是带头结点的单链表，本算法将L就地逆置     p = L->next;            //p为工作指针，从第一个元素结点开始     L->next = NULL;         //先将头结点L的next域置为NULL     while (p != NULL) {     //依次将元素结点摘下         r = p-&g...

单点更新，区间查询 假设有一个数组，对他大量的修改和查询，修改的是数组中某一个元素的值，查询的是数组中任意一个区间的和。对于修改比较简单，时间复杂度是 O(1) ，而查询的时间复杂度是 O(n) 。有同学可能会说使用前缀和来优化，前缀和查询的时间复杂度确实是 O(1) ，但如果我们修改某一个元素的时候，前缀和后面的值也都要修改，时间复杂度是 O(n) 。那么我们综合一下，有没有一种方式可以让修改和查询时间复杂度降一个数量级呢？有的，那就是树状数组，他的修改和查询时间复杂度都是 O(logn) ，综合来看还是不错的。如下图所示，他就是一个树状数组，其中数组 a[] 是原始数组，数组 c[] 是树...