数据结构与算法

<article class=“article fmt article-content”><p>《Programming Abstractions in C》学习第75天，p306-p307总结，总计2页。</p><h2>一、技术总结</h2><h3>1.Quicksort algorithm(疾速排序)</h3><p>由法国计算机科学家C.A.R(Charles Antony Richard) Hoare（东尼.霍尔）在1959年开发(develop), 1961年发表(publish)。</p><p>这里吐槽下维基百科的中文介绍：“在均匀情况下，排序n个我的项目要O(nlogn)(大O符号)次比拟。在最坏状况下则须要O(n^2)次比拟，但这种状况并不常见。"——这句话初看显得莫名其妙，这里的“排序”到底用的是什么排序算法？毫无上下文，难以了解。而英文介绍则好了解得多——“Mathematical analysis of quicksort show that, on average, the algorithm takes O(nlogn) comparisons to sort n items. In the worst case, it makes O(n^2) comparison ”，英文显著的指出应用的是疾速排序。不晓得为什么很多中文介绍常常是省略了很多内容。</p><h2>二、英语总结</h2><h3>1.substantial是什么意思？</h3><p>答：adj. large in size(sizeable)。p305, Even though the selection sort example makes it cleaar that quadratic algorithms have substantial performance problems (重大的性能问题)for large values of N， algorithms whose complexity is O(2^N) are considerably worse。</p><h3>2.tractable是什么意思？</h3><p>答：tractare(“to handle, manage”, treat)， adj. easily controlled。p305, As a general rule of thumb(依据教训)， computer scientists classify problem that can be solved susing algorithms that run in polynomial time as tractable, in the sense that they are amenable to implementation on a computer。</p><h3>3.demonstrate是什么意思？</h3><p>答: de-(entirely) + monstrare(point out, show)。 vt. If you could choose the optimal boundary between the small and large elements on each cycle, this algorithm would divide the array in half each time and end up demonstrating(体现出) the same qualitative characteristics. 这里的 end up 前面跟Ving模式，常翻译成finally(最终)。</p><h3>4.demarcation是什么意思？</h3><p>答：</p><p>(1)demarcate: de-(from) + marcar(to mark the boundaries of), vt. to show the limit of sth。</p><p>(2)demarcation: a board or a rule that show the limit of sth。</p><p>p307, For example, a common approach is to pick the first element, which was 56 in the original array, and use it as the demarcation point between small and large element。</p><h2>四、参考资料</h2><h3>1. 编程</h3><p>(1)Eric S.Roberts，《Programming Abstractions in C》：https://book.douban.com/subject/2003414</p><h3>2. 英语</h3><p>(1)Etymology Dictionary：https://www.etymonline.com</p><p>(2) Cambridage Dictionary：https://dictionary.cambridge.org<br/></p><p>欢送搜寻及关注：编程人(a_codists)</p></article> ...

一、什么是链表动静的线性数据结构。 二、链表的增删改查（一）非递归实现<?phpclass LinkedList{ // protected Node $head; protected Node $dummyHead; // 虚构头结点 private $size; public function __construct() { // $this->head = null; $this->dummyHead = new Node(); $this->size = 0; } public function getSize(): int { return $this->size; } public function isEmpty(): bool { return $this->size == 0; } // 在链表头增加新的元素 public function addFirst($e) { $this->add(0, $e); } // 在链表的 index (0-based) 地位增加新的元素 e public function add($index, $e) { // 判断 index 的合法性 if ($index < 0 || $index > $this->size) { // 留神 index 能够取到 size 的，因为能够在最初一个节点增加元素 throw new \Exception('Add failed. illegal index'); } $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } // 程序很重要 $node = new Node($e); $node->next = $prev->next; $prev->next = $node; // 更优雅的写法 // $prev->next = new Node($e, $prev->next); $this->size ++; } // 在链表开端增加元素 e public function addLast($e) { $this->add($this->size, $e); } // 取得链表中第 index 个地位的元素： public function get($index) { if ($index < 0 && $index >= $this->size) { throw new \Exception('Get failed, Illeal index'); } $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } return $cur->e; } // 取得链表的第一个元素 public function getFrist() { return $this->get(0); } // 取得链表的最初一个元素 public function getLast() { return $this->get($this->size - 1); } // 批改链表的第 index 个地位的元素 public function set($index, $e) { if ($index < 0 && $index >= $this->size) { throw new \Exception('Set failed, Illeal index'); } $cur = $this->dummyHead->next; for ($i = 0; $i < $index; $i++) { $cur = $cur->next; } $cur->e = $e; } // 查找链表中是否存在元素 e public function contains($e) { $cur = $this->dummyHead->next; while ($cur != null) { if ($e == $cur->e) { return true; } $cur = $cur->next; } return false; } // 从链表中删除第 index 个元素，并返回删除元素的值 public function remove($index) { if ($index < 0 || $index >= $this->size) { throw new \Exception('Delete failed, illegal index'); } $prev = $this->dummyHead; for ($i = 0; $i < $index; $i++) { $prev = $prev->next; } $retNode = $prev->next; $prev->next = $retNode->next; $retNode->next = NULL; $this->size--; return $retNode->e; } // 从链表中删除第一个元素，返回删除元素 public function removeFirst() { return $this->remove(0); } // 从链表中删除最初一个元素，返回删除元素 public function removeLast() { return $this->remove($this->size - 1); } public function toString() { $cur = $this->dummyHead->next; $ret = ''; while ($cur != null) { $ret .= $cur->e . '->'; $cur = $cur->next; } $ret .= 'NULL'; return $ret; }}class Node{ public $e; public $next; public function __construct($e = null, $next = null) { $this->e = $e; $this->next = $next; }}1. 虚构头结点（dummy head）为什么要应用虚构头结点？详情参考 链表问题：虚构节点dummy ...

链表删除链表中的某个节点或某一段区间leetcode.203链接https://leetcode.cn/problems/...解题办法：链表中删除一个节点的惯例办法就是找到这个节点的前驱节点，将前驱节点的next指针指向以后节点的后继节点leetcode解题代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* removeElements(ListNode* head, int val) { auto dummy = new ListNode(-1); dummy->next = head; for (auto p = dummy; p; p = p->next){ auto q = p->next; while (q && q->val == val) q = q->next; p->next = q; } return dummy->next; }};leetcode.19链接https://leetcode.cn/problems/...解题办法：与上一题相似，须要先求出链表总长度，再找到以后节点的前驱节点 留神：以后节点的前驱节点为倒数第n+1个点，即为负数第len-n个点 须要挪动len-n-1次挪动到前驱节点leetcode解题代码 ...

KMP算法利用场景KMP算法个别用于字符串匹配问题例如：给出两个字串S，P须要判断P串是否为S串的子串前缀表前缀：蕴含第一个字符不蕴含最初一个字符后缀：蕴含最初一个字符不蕴含最初一个字符 例如：aaba 前缀别离为：a, aa, aab 后缀别离为：a, ba, aba最长相等前后缀：记录前缀和后缀相等的长度，在这个例子中最长相等前后缀为a，长度为1在KMP算法当中，用一个next数组记录每个字符的最长相等前后缀例如：aabaa 前缀别离为：a, aa, aab, aaba 后缀别离为：a, aa, baa, abaa next数组为：a:0, aa:1, aab:0, aaba:1, aabaa:2 next = [0, 1, 0, 1, 2]前缀表在KMP算法中的作用暴力解法中，咱们须要两重循环遍历P串和S串，直到找到匹配的字串，工夫复杂度为O(n*m)，n，m别离示意P串和S串的长度KMP算法的核心思想就是用前缀表记录曾经匹配过的文本内容，使得当产生匹配抵触的时候，能够不须要从新遍历，而是通过前缀表回退到之前匹配胜利过的地位持续匹配，next数组就是前缀表具体原理参考https://www.bilibili.com/vide...next数组的实现（前缀表实现）结构next数组分为四步：初始化 定义两个指针i，j j指向前缀开端地位，i指向后缀开端地位 next数组初始化为0，j从0开始，i从1开始解决前后缀不雷同的状况 以后后缀不相等并且j>0时（后续要回退到j-1的状态所以要保障j>0） j回退到j-1的状态解决前后缀雷同的状况 前后缀雷同时，j向后挪动一位更新next数组 将next数组更新为j代码模板 int j = 0;next[0] = 0;for (int i = 1; i < m; i ++){ while (j > 0 && s[i] != s[j]) j = next[j - 1]; if (s[i] == s[j]) j ++; next[i] = j;}leetcode.28链接https://leetcode.cn/problems/...leetcode解题代码 ...

反转字符串leetcode.344链接https://leetcode.cn/problems/...解题办法：双指针 l，r指针别离放在字符串的首尾两端，每次替换两个字符 每替换一次指针向两头挪动一位leetcode解题代码 class Solution {public: void reverseString(vector<char>& s) { int l = 0, r = s.size() - 1; while (l < r){ swap(s[l], s[r]); l ++, r --; } }};leetcode.541链接https://leetcode.cn/problems/...解题办法：双指针 定义保护的区间[l, r]，每次保护2k个数leetcode解题代码 class Solution {public: string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n - 1; i += k * 2){ int l = i, r = min(i + k, n); reverse(s.begin() + l, s.begin() + r); } return s; }};反转字符串中的单词题目类型：给一个字符串组成的句子(带空格或标点)，而后对句中单个字符串进行一系列解决这类题目能够分为两类，一类是有前置或者后置空格的，另一类是没有前置和后置空格的leetcode.58链接https://leetcode.cn/problems/...解题办法：创立一个长期字符串（用来存每一个单词），和一个答案数组 遍历原字符串，如果遍历到空格，判断长期字符串是否为空 如果长期字符串非空则阐明曾经遍历完一个单词，将其退出答案数组中并清空长期字符串 如果遍历到的不是空格，将其退出长期字符串中leetcode解题代码 ...

一、题目粗心https://leetcode.cn/problems/longest-consecutive-sequence 给定一个未排序的整数数组 nums ，找出数字间断的最长序列（不要求序列元素在原数组中间断）的长度。 请你设计并实现工夫复杂度为 O(n) 的算法解决此问题。 示例 1： 输出：nums = [100,4,200,1,3,2]输入：4解释：最长数字间断序列是 [1, 2, 3, 4]。它的长度为 4。示例 2： 输出：nums = [0,3,7,2,5,8,4,6,0,1]输入：9  提醒： 0 <= nums.length <= 105-109 <= nums[i] <= 109 二、解题思路能够把所有数字放到一个哈希表，而后一直地从哈希表中任意取一个值，并删除掉其之前之后的所有间断数字，而后更新目前的最长间断序列长度。反复这一过程，就能够找到所有的间断数字序列，顺便找出最长的。 三、解题办法3.1 Java实现-超时版public class Solution1 { public int longestConsecutive(int[] nums) { Set<Integer> intSet = new HashSet<>(); for (int num : nums) { intSet.add(num); } int ans = 0; while (!intSet.isEmpty()) { int cur = intSet.stream().findFirst().get(); intSet.remove(cur); int pre = cur - 1; int next = cur + 1; while(intSet.contains(pre)) { intSet.remove(pre--); } while(intSet.contains(next)) { intSet.remove(next++); } ans = Math.max(ans, next - pre - 1); } return ans; }}3.2 Java实现-通过版public class Solution { public int longestConsecutive(int[] nums) { Set<Integer> intSet = new HashSet<>(); for (int num : nums) { intSet.add(num); } int ans = 0; for (int num : nums) { if (intSet.remove(num)) { int pre = num - 1; int next = num + 1; while (intSet.remove(pre)) { pre--; } while (intSet.remove(next)) { next++; } ans = Math.max(ans, next - pre - 1); } } return ans; }}四、总结小记2022/8/16 Map的好些办法在解决大数据量时要慎用呀

前言跳表能够达到和红黑树一样的工夫复杂度O(logN)，且实现简略，Redis中的有序汇合对象的底层数据结构就应用了跳表。本篇文章将对跳表的实现进行学习。 注释一. 跳表的根底概念跳表，即跳跃表（Skip List），是基于并联的链表数据结构，操作效率能够达到O(logN)，对并发敌对，跳表的示意图如下所示。 跳表的特点，能够概括如下。 跳表是多层（level）链表构造；跳表中的每一层都是一个有序链表，并且依照元素升序（默认）排列；跳表中的元素会在哪一层呈现是随机决定的，然而只有元素呈现在了第k层，那么k层以下的链表也会呈现这个元素；跳表的底层的链表蕴含所有元素；跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；跳表中的节点蕴含两个指针，一个指针指向同层链表的后一节点，一个指针指向上层链表的同元素节点。以上图中的跳表为例，如果要查找元素71，那么查找流程如下图所示。 从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，然而如果依照传统链表的形式（即从跳表的底层链表的头节点开始向后查找），那么就须要遍历7个节点，所以跳表以空间换工夫，缩短了操作跳表所须要破费的工夫。 二. 跳表的节点已知跳表中的节点，须要有指向以后层链表后一节点的指针，和指向上层链表的同元素节点的指针，所以跳表中的节点，定义如下。 public class SkiplistNode { public int data; public SkiplistNode next; public SkiplistNode down; public int level; public SkiplistNode(int data, int level) { this.data = data; this.level = level; }}上述是跳表中的节点的最简略的定义形式，存储的元素data为整数，节点之间进行比拟时间接比拟元素data的大小。 三. 跳表的初始化跳表初始化时，将每一层链表的头尾节点创立进去并应用汇合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表以后跳表的层数。初始化后，跳表构造如下所示。 跳表初始化的相干代码如下所示。 public LinkedList<SkiplistNode> headNodes;public LinkedList<SkiplistNode> tailNodes;public int curLevel;public Random random;public Skiplist() { random = new Random(); //headNodes用于存储每一层的头节点 headNodes = new LinkedList<>(); //tailNodes用于存储每一层的尾节点 tailNodes = new LinkedList<>(); //初始化跳表时，跳表的层数随机指定 curLevel = getRandomLevel(); //指定了跳表的初始的随机层数后，就须要将每一层的头节点和尾节点创立进去并构建好关系 SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0); SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0); for (int i = 0; i <= curLevel; i++) { head.next = tail; headNodes.addFirst(head); tailNodes.addFirst(tail); SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1); SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1); headNew.down = head; tailNew.down = tail; head = headNew; tail = tailNew; }}四. 跳表的增加办法每一个元素增加到跳表中时，首先须要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素增加到跳表中之前，还须要扩充跳表的层数，而扩充跳表的层数就是将头尾节点的层数扩充。上面给出须要扩充跳表层数的一次增加的过程。 ...

一、题目粗心标签: 动静布局 https://leetcode.cn/problems/ones-and-zeroes 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，汇合 x 是汇合 y 的 子集 。 示例 1： 输出：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3输入：4解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因而答案是 4 。其余满足题意但较小的子集包含 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 2： ...

1 前言我在很早之前的文章里，分享过有C语言手撸一个基于数组实现的最大堆，所以堆的根本实现思路和办法，不再赘述，详见： 数据与构造与算法: 堆 C语言形容 C语言可能受众小些，且稍微不太好了解，明天就用JavaScript形容一个最小堆，其实是基于最小堆的优先队列，不过两者基本上么有什么太大的区别，无非堆是存最根底的数字，优先队列则贮存的是一个构造体或者对象，有本人的key/value，有本人的属性。 2 与C语言版本的不同Js的数组实质还是对象，长度是可变的，而C语言的数组就是纯正的数组，一旦确定下来，长度就不可变。故而在C版本中，咱们须要保护size属性，不然不晓得数组到底应用到哪里了，这Js版本就不须要，间接读取data.length即可。自带函数，Js这种高级语言，自带很多函数，比方咱们应用pop()函数就间接弹出了数组的开端，其长度主动减一，而C语言版本显然没有这个性能3 代码var Heap = function () { this.data = [] this.insert = (obj) => { let i = this.data.length for (; i > 0 && this.data[Math.floor((i - 1) / 2)].val >= obj.val; i = Math.floor((i - 1) / 2)) { if (i < 1) { break } this.data[i] = this.data[Math.floor((i - 1) / 2)] } this.data[i] = obj } this.pop = () => { if (this.data.length == 0) { return null } if (this.data.length == 1) { return this.data.pop() } let top = this.data[0] this.data[0] = this.data.pop() let i = 0 while (2 * i + 1 < this.data.length) { if (2 * i + 2 < this.data.length) { if (this.data[2 * i + 2].val < this.data[i].val || this.data[2 * i + 1].val < this.data[i].val) { if (this.data[2 * i + 2].val < this.data[2 * i + 1].val) { this.swap(i, 2 * i + 2) i = 2 * i + 2 } else { this.swap(i, 2 * i + 1) i = 2 * i + 1 } } else { break } } else { if (this.data[2 * i + 1].val < this.data[i].val) { this.swap(i, 2 * i + 1) i = 2 * i + 1 } else { break } } } return top } this.swap = (i, j) => { let tmp = this.data[j] this.data[j] = this.data[i] this.data[i] = tmp }};4 理论测试测试代码如下 ...

1. 题目形容LeetCode 122.交易股票的最佳时机 II在每一天，你能够决定是否购买和/或发售股票。你在任何时候最多只能持有一股股票。你也能够先购买，而后在同一天发售。返回你能取得的最大利润 。示例 ： *输出：prices = [7,1,5,3,6,4]输入：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。*这道题常见且并不难，有意思的是解法也十分多，尤其适宜入门级别的枯燥栈和动静布局 2. 贪婪算法这是最容易想到的解法，因为交易次数不受限，只须要在股价的每个上坡底部买入，坡顶卖出，则肯定是利益最大化的 function maxProfit(prices){ let ans = 0; for (let i = 0; i < prices.length - 1; i++) { if (prices[i + 1] > prices[i]) { // 在上坡过程中，【每天都交易】和【底部买入，坡顶卖出】是齐全等效的(疏忽手续费) ans += (prices[i + 1] - prices[i]); } } return ans}3. 枯燥栈枯燥栈顾名思义是枯燥递增/减的一种栈构造，股价的上坡在数据结构上的示意，其实就是一个递增的枯燥栈，咱们只有顺次找到所有的上坡，此时栈顶减去栈底，则是单次上坡的最大利润 ...

题目在数组中的两个数字，如果后面一个数字大于前面的数字，则这两个数字组成一个逆序对。输出一个数组，求出这个数组中的逆序对的总数。 要求：空间复杂度 O(n)，工夫复杂度 O(nlogn) 输出: [7,5,6,4]返回值: 5输出：[1,2,3,4,5,6,7,0]返回值：7输出：[1,2,3]返回值：0思路最简略的思路是暴力求解，遍历数组每个元素，而后挨个和之后的元素比拟。这种做法工夫复杂度是O(n^2)。 最优思路是，利用归并排序的做法。归并排序，将数组递归二分到子数组只有1个元素，而后向上排序合并。 只有左数组的某个元素，大于右数组的某个元素，那么左数组的该元素以及之后的所有元素，都能够和右数组的该元素造成逆序对。 因为下一层通过排序合并返回上一层后，上一层的左、右数组都是从小到大正序的，如果左数组的某个元素就比右数组的某个元素大，那么左数组的该元素前面的元素也必定比右数组的该元素大。 class Solution: # 内部定义一个变量，用来记录逆序对数量 count = 0 def InversePairs(self, data): def mergeSort(nums): n = len(nums) # 归并排序 递归完结条件 分到子数组长度为1不可分时递归完结 if n==1: return nums # 以后数组的两头地位 mid = n//2 # 左数组向下递归持续二分 left = mergeSort(nums[:mid]) # 右数组向下递归持续二分 right = mergeSort(nums[mid:]) # 定义两个指针: l、r，初始时别离指向左数组、右数组的开始 l = r = 0 # 定义一个变量，保留排序合并后的后果 tmp = [] # 当左、右两个数组 都没有遍历完 while l<=len(left)-1 and r<=len(right)-1: # 如果左数组以后元素 <= 右数组以后元素 # 则没有逆序对，左数组元素退出到排序后果中，l指针挪动 if left[l] <= right[r]: tmp.append(left[l]) l+=1 # 如果左数组以后元素 > 右数组以后元素 # 则左数组以后元素 以及 前面的所有元素，都大于右数组以后元素 # 都能够造成逆序对，count+这部分元素的数量 # 右数组以后元素退出到排序后果中，r指针挪动 else: tmp.append(right[r]) self.count+=len(left[l:]) r+=1 while l<=len(left)-1: tmp.append(left[l]) l+=1 while r<=len(right)-1: tmp.append(right[r]) r+=1 return tmp mergeSort(data) return self.count

申明：图片援用自《极客工夫——数据结构与算法之美》二叉树二叉树：就是最多只能有两个叉的树结构。图中1是一般的二叉树，2、3是两种非凡的二叉树。2是满二叉树满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点 3是齐全二叉树齐全二叉树：叶子节点都在最底下两层，最初一层的叶子节点都靠左排列，并且除了最初一层，其余层的节点个数都要达到最大不是齐全二叉树的例子中：第1个，不满足叶子节点都在最底下两层第2个，不满足最初一层的叶子节点都靠左排列第3个，不满足除了最初一层外，其余层的节点个数要达到最大 二叉树的具体存储示意链式存储法 每个节点有三个局部，data存储数据，left、right局部是指针，存储节点的指向。相似链表。 代码中，能够想到用对象构建。 顺序存储法 顺序存储法，就是基于数组的存储形式。不须要像链式存储那样，每个节点还要保留left、right指针，占用额定的空间，顺序存储法只节约一个下标0的存储空间。 以后，前提是这棵树是齐全二叉树，所以齐全二叉树是最适宜用顺序存储法的树结构，这也是为什么齐全二叉树要求最初一层子节点都靠左排列的起因。 如果节点 X 存储在数组中下标为 i 的地位，下标为 2 * i 的地位存储的就是左子节点，下标为 2 * i + 1 的地位存储的就是右子节点。反过来，下标为 i/2 的地位存储就是它的父节点。 二叉树的遍历二叉树的三种遍历形式： 前序遍历 对于树中的任意节点来说，先打印这个节点，而后再打印它的左子树，最初打印它的右子树。中序遍历 对于树中的任意节点来说，先打印它的左子树，而后再打印它自身，最初打印它的右子树。后序遍历 对于树中的任意节点来说，先打印它的左子树，而后再打印它的右子树，最初打印这个节点自身。简略总结：节点本身什么时候打印，就是那种遍历。节点本身最先打印，就是前序遍历；节点本身两头的时候打印，就是中序遍历；节点本身最初一个打印，就是后续遍历。 二叉树的遍历过程就是一个递归，只是递归的程序不同，有了三种不同的遍历形式。 遍历二叉树的工夫复杂度：不论是哪种遍历形式，节点最多会被拜访两次，所以总的遍历工夫只和节点个数n无关，所以工夫复杂度是O(n) 堆堆构造是二叉树构造的一种，它必须满足以下要求： 堆是一个齐全二叉树每个节点的值必须都大于等于（或小于等于）其左右子节点的值节点的值大于等于左右子节点的值，这种堆叫做大顶堆，因为它的根节点的值是最大的。 节点的值小于等于左右子节点的值，这种堆叫做小顶堆，因为它的根节点的值是最小的。 1、2是大顶堆，3是小顶堆，4不是堆，因为它不是齐全二叉树。

题目给定一个长度为 n 的可能有反复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意程序皆可)。 要求：空间复杂度 O(n)O(n) ，工夫复杂度 O(nlogn)O(nlogn) 输出：[4,5,1,6,2,7,3,8],4 返回值：[1,2,3,4]阐明：返回最小的4个数即可，返回[1,3,2,4]也能够 输出：[1],0返回值：[]输出：[0,1,2,1,2],3返回值：[0,1,1]思路第一工夫想到的做法是，利用排序算法，将整个数组从小到大排序，而后选取前k个数，就是该数组的最小的k个数了。 然而，这个做法不是最优的。题目只要求返回最小的k个数，并不要求这k个数也要按程序排好。所以要好好利用这个条件。 更高效的思路是，利用疾速排序的思维，通过基准值，将数组分成小于基准值局部、大于等于基准值局部。只是大体上划分出了较小的局部、和较大的局部，并没有对每个数值都进行排序，这也正好合乎题目的条件。所以，咱们利用疾速排序的思路： 如果小于基准值局部的元素刚好是k个，那么就间接得出了后果如果小于基准值局部的元素多余k个，那么就在小于局部再去执行快排，直到较小局部刚好是k个如果小于基准值局部的元素少于k个，那么就在大于局部去执行快排，直到新的较小局部加上之前的较小局部刚好是k个def GetLeastNumbers_Solution(input, k): def quickSort(nums,left,right,index): # 数组进入快排操作，返回快排后的基准值索引 mid = partition(nums,left,right) # 如果基准值索引 刚好等于 k，阐明基准值后面的数，刚好是最小的k个数 if mid==index: return nums[:index] # 如果基准值索引 > k，阐明以后较小局部的个数多于k个，较小局部持续快排 # 直到mid==index，刚好找到k个最小的数，将后果一层层向上返回 elif mid > index: return quickSort(nums,left,mid-1,index) # 如果基准值索引 < k，阐明以后较小局部的个数少于k个，还有局部最小k个数在较大局部中 # 较大局部进入快排，当mid==index时，mid后面就是最小的k个数，将后果一层层向上返回 else: return quickSort(nums,mid+1,right,index) # 快排操作 def partition(nums,left,right): # 基准值 pivot = nums[left] while left<right: while left<right and nums[right]>=pivot: right-=1 nums[left]=nums[right] while left<right and nums[left] <= pivot: left+=1 nums[right]=nums[left] nums[left]=pivot return left n = len(input) # 边界状况 if k<=0: return [] if k == n: return input # 快排递归 return quickSort(input,0,n-1,k)

题目输出一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。 要求：空间复杂度 O(n)，工夫复杂度 O(n)进阶：空间复杂度 O(1)，工夫复杂度 O(n) 示例1输出：{1,2,3,4,5},2返回值：{4,5}阐明：返回倒数第2个节点4，零碎会打印前面所有的节点来比拟。 示例2输出：{2},8返回值：{}思路最间接的思路是：翻转整个链表，而后再遍历节点，这样做就是空间复杂度O(n)，工夫复杂度O(n)空间复杂度O(1)，则不能存储额定的链表，意味着只能在原链表上操作。如果先遍历一遍链表，失去链表的长度，再减去k，失去倒数第k个节点是正序第几个节点，这样的做法工夫复杂度又不满足O(n)了。 进阶思路：如何不翻转链表，只须要正序遍历链表节点，就可能找到倒数第k个节点呢尾节点作为倒数第1个节点，从它往前挪动k-1个节点，就是倒数第k个节点。所以倒数第k个节点，和尾节点之间的间隔，是k-1步。咱们设置两个指针，former和latter，latter在头节点处，former比latter往前k-1步，而后同时挪动两个指针，直到former指向了尾节点，此时latter指向的节点就是倒数第k个节点了，这样通过正序遍历节点，就能找到倒数第k个节点了。 def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode: former = pHead if not former or not former.next or k==0: return None for i in range(k-1): if former.next: former=former.next else: return None while former.next: pHead = pHead.next former = former.next return pHead

题目输出一个链表的头节点，按链表从尾到头的程序返回每个节点的值（用数组返回）。 示例1输出：{1,2,3}复制返回值：[3,2,1]复制示例2输出：{67,0,24,58}复制返回值：[58,24,0,67]思路第一反馈这不就是反转链表吗，但认真审题后，发现和翻转链表并不一样。题目要求的是，返回链表翻转后的每个节点的值。如果用翻转链表的思路，要先翻转链表，再遍历翻转链表的每个节点。这么做无论空间还是工夫复杂度都不够简洁。 更优雅的思路是，只遍历一次原链表，将每个节点的值存在栈中，最初再将栈的元素一一pop进去存在一个数组中，或者利用python中的切片间接返回栈的逆序，利用栈的先进后出的个性，实现翻转。 def printListFromTailToHead(self , listNode: ListNode) -> List[int]: curNode = listNode stack = [] while curNode: stack.append(ptr.val) curNode=curNode.next return stack[::-1]

题目给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点别离组合在一起，而后返回从新排序的列表。 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。 请留神，偶数组和奇数组外部的绝对程序应该与输出时保持一致。 你必须在 O(1) 的额定空间复杂度和 O(n) 的工夫复杂度下解决这个问题。 输出: head = [1,2,3,4,5]输入: [1,3,5,2,4]输出: head = [2,1,3,5,6,4,7]输入: [2,3,6,7,1,5,4]思路定义4个指针2个指针负责偶数节点链表2个指针负责奇数节点链表其中，1个指针负责定位各自的头节点，1个指针负责挪动批改各自的其余节点的next指向最初将批改好的奇数节点链表的尾 和 偶数节点链表的头连接起来 def oddEvenList(self, head: ListNode) -> ListNode: if head==None or head.next==None: return head # 奇数节点挪动指针 odd = head # 奇数节拍板指针 oddHead = head # 偶数节点挪动指针 even = head.next # 偶数节拍板指针 evenHead = head.next # 当奇数挪动指针，为None，或者它的next指向None，意味着遍历完结 # 为什么是依据奇数挪动指针来判断的？ # 因为题目规定，链表的第一个节点是奇数节点 # 那么整个链表的奇数节点个数，肯定是要么等于偶数节点个数，要么比偶数节点多1个 # 即 奇-偶-奇 或者 奇-偶-奇-偶 # 所以要抉择较多的那一个作为判断循环完结的条件 # 如果抉择偶数的话，奇-偶-奇，第一次循环 奇-偶 第二次循环 奇-None，就出错了 while even and even.next: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = evenHead return oddHead

题目给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 进阶：你是否用 O(n) 工夫复杂度和 O(1) 空间复杂度解决此题？ 输出：head = [1,2,2,1]输入：true输出：head = [1,2]输入：false思路第一个想到的就是，间接把整个链表翻转，而后和原来的链表比拟。然而题目要求工夫复杂度O(n)，空间复杂度O(1)，这个思路要保留翻转后的链表，空间复杂度首先就不满足了。 满足复杂度的思路如下： 将链表从两头一分为二 应用快慢指针，slow每次挪动1个节点，fast每次挪动2个节点。当fast挪动到开端，无奈继续前进2个节点时，slow所在的节点就是链表的两头地位。将右半局部链表翻转遍历左、右两个链表的每个节点，看每个节点的值是否雷同def isPalindrome(self, head: ListNode) -> bool: # 初始化快慢指针 slow = fast = head # 遍历链表，挪动快慢指针，切分链表 # 当fast挪动到尾节点或尾节点的前一个节点时，下一次无奈挪动2个节点，则遍历实现 # 此时slow指针指向了链表的两头地位 while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 翻转右半局部链表 # 在翻转后的右半局部链表头节点设置rightHead指针 rightHead = self.reverseList(slow.next) # 在左半局部链表头节点设置leftHead指针 leftHead = head # 以遍历右半局部链表为准，因为切分链表的时候，如果链表节点个数是奇数，左半局部会多1个节点 while rightHead: # 如果有节点的值不同，就不是回文链表，返回False if leftHead.val != rightHead.val: return False # 挪动指针 leftHead = leftHead.next rightHead = rightHead.next # 遍历完结，节点的值都雷同，是回文链表，返回True return True def reverseList(self,head): if head==None or head.next==None: return head tmp = self.reverseList(head.next) head.next.next = head head.next = None return tmp

题目给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最初残余的节点放弃原有程序。 进阶： 你能够设计一个只应用常数额定空间的算法来解决此问题吗？你不能只是单纯的扭转节点外部的值，而是须要理论进行节点替换。 输出：head = [1,2,3,4,5], k = 3输入：[3,2,1,4,5]输出：head = [1,2,3,4,5], k = 1输入：[1,2,3,4,5]输出：head = [1], k = 1输入：[1]思路总体思路，通过设置指针，来管制链表，将翻转区的链表独自摘出来，送入递归翻转函数，而后再通过指针链接回原来的链表中具体思路：设置如下指针pre指针：指向翻转区的前一个节点next指针：指向翻转区的后一个节点start指针：指向翻转区的头节点end指针：指向翻转区的尾节点pre,【start,...,end】,next翻转区通过翻转后pre,【end,...,start】,next本次翻转实现，再挪动pre、next、start、end指针到下一个翻转区进行翻转 def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # 设置虚构节点放在head前 dummy = ListNode() dummy.next = head # 设置pre、end指针 # pre指向翻转区的前一个节点，end指向翻转区的尾节点 # 初始时都在dummy处 pre = dummy end = dummy while True: # 挪动end到翻转区尾节点 for i in range(k): # 如果k步之内，end指向整个链表尾节点的next，也就是None了 # 阐明最初这个翻转区长度不够，不翻转，跳出for循环 if not end: break end = end.next # 翻转区长度不够，不翻转，完结while循环 if not end: break # 失常翻转 # 设置next指针，指向翻转区的下一个节点 next = end.next # 设置start指针，指向翻转区的头节点 start = pre.next # pre,【start,...,end】,next # 将翻转区链表前后断开，剥离进去 pre.next = None # 翻转区和它的前一个节点断开 end.next = None # 翻转区和它的下一个节点断开 # 翻转区链表进入递归函数翻转 # pre,【end,...,start】,next # 翻转后果的头节点和pre连起来 pre.next = self.reverseList(start) # 翻转后的尾节点和next连起来 start.next = next # 挪动pre、end指针，到下一个翻转区的前一个节点处 pre = start end = start return dummy.next def reverseList(self,head): if head == None or head.next == None: return head tmp = self.reverseList(head.next) head.next.next = head head.next = None return tmp

题目给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 输出：head = [1,2,6,3,4,5,6], val = 6输入：[1,2,3,4,5]示例 2：输出：head = [], val = 1输入：[]示例 3：输出：head = [7,7,7,7], val = 7输入：[]思路删除节点，让该节点的前一个节点，指向它的下一个节点，跳过它本人，达到删除该节点的目标。设置两个指针，cur指向以后遍历节点，pre指向它的前一个节点 def removeElements(self, head: ListNode, val: int) -> ListNode: # 设置一个虚构节点放在头节点前 dummy = ListNode() dummy.next = head # 设置两个指针 cur指向以后遍历节点，pre指向以后的前一个节点 pre = dummy cur = head while cur: if cur.val == val: pre.next = cur.next else: pre = cur cur = cur.next return dummy.next

题目给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。 返回 滑动窗口中的最大值 。 输出：nums = [1,3,-1,-3,5,3,6,7], k = 3输入：[3,3,5,5,6,7]解释：滑动窗口的地位 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7输出：nums = [1], k = 1输入：[1]思路双端队列用一个双端队列，模仿窗口遍历数组： ...

题目请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty） 思路应用两个栈，stack_in栈模仿队列push，stack_out栈模仿队列poppop时，如果stack_out空栈，将stack_in栈顺次pop到stack_out中而后stack_out再pop class MyQueue: def __init__(self): # 应用两个栈，stack_in栈模仿队列push，stack_out栈模仿队列pop # pop时，如果stackstack_out空栈，将stack_in栈顺次pop到stack_out中 # 而后stack_out再pop self.stack_in = [] self.stack_out = [] def push(self, x: int) -> None: self.stack_in.append(x) def pop(self) -> int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) -> int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] def empty(self) -> bool: return not self.stack_in and not self.stack_out

题目给定 n 个非负整数示意每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 输出：height = [0,1,0,2,1,0,1,3,2,1,2,1]输入：6解释：下面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 示意的高度图，在这种状况下，能够接 6 个单位的雨水（蓝色局部示意雨水）。 输出：height = [4,2,0,3,2,5]输入：9思路暴力解法暴力解法尽管简略，然而这道题的暴力思路一时我还没反馈过去，花了挺久工夫才想明确咋回事。首先，大体思路就是，遍历每个柱子，也就是遍历数组每个元素，而后每个元素为核心，向左、右两侧遍历寻找比它高的最高的柱子，这样就能计算出这个柱子上方能接多少水。 看不懂没关系，开始我也看不懂，接下来联合代码具体说一下就懂了：1.首先，最外层for循环：for i in range(1, size-1)遍历柱子，每个柱子作为桶底，向左右两侧寻找高柱子作为桶的左右两个边因为数组的结尾、结尾这两个柱子是边界，它们当桶底不可能造成一个桶，所以遍历的时候，是从第2根柱子开始到倒数第2根柱子完结，所以是range(1,size-1)，而不是range(size) 2.接下来，每次遍历拿到作为桶底的柱子，以它为核心，向左右两侧再遍历，寻找比它高的最高的柱子，作为桶底的左右两个边 for i in range(1, size-1): max_left,max_right = 0,0 # 寻找i右边最高的柱子 for j in range(i+1): max_left = max(height[j],max_left) # 寻找i左边最高的柱子 for k in range(i,size): max_right = max(height[k], max_right) ans += min(max_left,max_right) - height[i]这里有几个点，比拟不容易想明确： 为什么是向左右两边寻找柱子的时候，要从它本人开始始终找到结尾、结尾，而不是只看它左右的那两个柱子；而且为什么要找最高的，而不是只有比它高就行： 因为这里容易陷入一个思考误区，就是感觉一个柱子可能接水，只有它左右相邻的两个柱子比它高，把它围起来，围成一个桶，就能够接水了。 其实并非如此，一个柱子能接水，它左右两边是要有比它高的柱子，然而这两个柱子并不是肯定要和它相邻；并且，这两个柱子不仅比它高，而且还是最高的，看图就明确了： 比方上图中，柱子a是以后作为桶底的柱子，a的左右两侧柱子-a1、a1的确比它高，而且还和它相临，然而再向左右两侧看，-a2、a2更高，他们围城了一个更大的桶。所以，要向左右两侧始终遍历到结尾、结尾，并且要找到最高的柱子作为桶的两边。 咱们在计算水的时候，不要想着怎么去间接计算-a2到a2围城的这个桶外面的水有多少，而是指思考某个柱子上方的水是多少就能够了，设想成柱状图，每个柱子下面的水也是一柱一柱的，不要被“水”这个字眼蛊惑了。比方，只计算a柱子上方的水，这个桶较低的一边是-a2，高度为2，a的宽度是1，所以a柱子上方的水就是2。同理，也能够计算出-a1柱子上方的水，这时要留神，-a1柱子自身高度为1，占据了空间，所以要把它本身的高度减掉。同理，也能够计算出a1柱子上方的水最初，把-a1、a、a1三个柱子上方的水，加起来，就是-a2、a2围城的桶里的水了。同理，遍历每个能够作为桶底的柱子，计算出每个桶底上方的水，最初累加起来，就是最终的答案。 遍历桶底柱子的时候，咱们不须要结尾、结尾的两个柱子，因为他俩不可能作为桶底。而在寻找左右两测最高的桶边柱子时，要包含结尾、结尾的两个柱子，因为它们能够作为桶边。寻找左右桶边的时候，把以后桶底这个柱子，也算在遍历范畴中了，因为如果左右两边没有比它高的柱子，那么它就既是桶底、也是桶边，能够设想成它就是一块木头桩子，显然它下面是不能接水的。所以，最初在计算接水的时候，用桶边较低高度-桶底本身高度，对它来说就是本人减本人等于0，刚好合乎逻辑。当然，你也能够在遍历时，不把桶底这个柱子算在遍历范畴内，只不过遇到左右没有比它高的柱子这种状况时，还要独自写代码解决，就比拟麻烦，所以这样写算是一个小技巧。def trap(height) -> int: size = len(height) ans = 0 # 遍历每个能够作为桶底的柱子，结尾、结尾两个柱子不能作为桶底，不在遍历范畴内 for i in range(1,size-1): max_left,max_right = 0,0 # 寻找i柱子左侧比本人高的最高柱子，没有的话i本人就是最高柱子 # 结尾的柱子能够作为桶边，在遍历范畴内 for j in range(i+1): max_left = max(height[j],max_left) # 寻找i柱子右侧比本人高的最高柱子，没有的话i本人就是最高柱子 # 结尾的柱子能够作为桶边，在遍历范畴内 for k in range(i,size): max_right = max(height[k], max_right) # 较低的桶边柱子高度 - 桶底柱子高度，就是桶底柱子上方的储水量 # 每个桶底柱子上方储水量累加，就是最终答案 ans += min(max_left,max_right) - height[i] return ans工夫复杂度：O(n^2)，每遍历一个元素，就要遍历一次数组空间复杂度：O(1) ...

题目给定一个整数数组 temperatures ，示意每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该地位用 0 来代替。 输出: temperatures = [73,74,75,71,69,72,76,73]输入: [1,1,4,2,1,1,0,0]输出: temperatures = [30,40,50,60]输入: [1,1,1,0]输出: temperatures = [30,60,90]输入: [1,1,0]其实就是，找出数组中每一个元素的左边第一个比他大的元素间隔本人的下标差。 思路：枯燥栈遍历数组，每个元素进入栈，入栈前，该元素和栈顶元素比拟大小，大于栈顶元素，则栈顶元素找到了第一个比他大的元素，计算下标差，弹出栈顶元素该元素再和新的栈顶元素比拟大小，反复上述过程直到该元素小于栈顶元素，或空栈，将该元素入栈 例如：开始遍历73，入栈【73】74，大于73，计算74与73在原数组中的下标差，弹出73【】，74入栈【74】75，大于74，计算75与74在原数组中的下标差，弹出74【】，75入栈【75】71，小于75，入栈【75，71】69，小于71，入栈【75，71，69】72，大于69，计算72和69在原数组中的下标差，弹出69【75，71】 大于71，计算72和71在原数组中的下标差，弹出71【75】小于75，72入栈【75，72】76，大于72，计算76和72在原数组中的下标差，弹出72【75】 大于75，计算76和75在原数组中的下标差，弹出75【】，76入栈【76】73，小于76，入栈【76，73】 def dailyTemperatures(self, temperatures: List[int]) -> List[int]: stack = [] n = len(temperatures) res = [0]*n for i in range(n): while stack and temperatures[i] > temperatures[stack[-1]] : preIndex = stack.pop() res[preIndex]=i-preIndex stack.append(i) return res

题目给定 pushed 和 popped 两个序列，每个序列中的 值都不反复，只有当它们可能是在最后空栈上进行的推入 push 和弹出 pop 操作序列的后果时，返回 true；否则，返回 false 。 输出：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输入：true解释：咱们能够按以下程序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1输出：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输入：false解释：1 不能在 2 之前弹出。思路采纳模仿的思路定义一个空栈stack依照pushed的程序，将每个元素push到stack中每次push进一个元素，就去判断一下，该元素在popped中是否被pop如果被pop了，就将stack中该元素pop，而后再判断以后栈顶元素，是否是下一个要被pop的元素以此类推如果popped序列，可能使pushed的元素全副被pop进来，也就是stack最终是空，那么就返回True def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: stack = [] j = 0 for x in pushed: stack.append(x) # 每append一个元素，就看看该元素是否能够被pop # 如果能被pop，就pop掉，并且持续看之前append的元素是否被pop # 直到所有的元素都被pop了，或者stack曾经空了，须要append新元素或是整个流程都完结了，才进行 while stack and j<len(popped) and popped[j]==stack[-1]: stack.pop() j+=1 return not stack

题目设计一个反对 push ，pop ，top 操作，并能在常数工夫内检索到最小元素的栈。 输出：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输入：[null,null,null,null,-3,null,0,-2]思路辅助栈题目要求在常熟工夫内能检索到最小元素，常数工夫就是O(1)工夫复杂度，因而不能应用for循环遍历检索，for循环的工夫复杂度是O(n) 思路是再保护一个辅助栈 minStack, 让辅助栈的栈顶，始终保留的是以后栈中的最小元素 class MinStack: def __init__(self): # 一般栈 self.stack = [] # 辅助栈，初始化给一个无穷大 self.min_stack = [math.inf] def push(self, val: int) -> None: # 一般栈失常push self.stack.append(val) # 辅助栈只push小于等于栈顶的 self.min_stack.append(min(val,self.min_stack[-1])) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]不应用辅助栈只用一个栈也能够解决问题。辅助栈的办法，是新增一个栈用来保护最小值。而只用一个栈，就只须要新增一个变量来保留最小值。在数据出入栈的同时，通过一些办法，将最小值的变动记录在数据栈中。 办法一： 入栈 3 | | min = 3| | |_3_| stack 入栈 5 | | min = 3| 5 | |_3_| stack 入栈 2 | 2 | min = 2?| 5 | |_3_| stack 入栈2时，栈中最小值变成了2，如果间接将min跟新成2，那之前的最小值3就会失落为了保留之前的最小值3，在入栈2时，先将之前最小值3入栈保留在栈中，而后在入栈2，更新min也就是，当新入栈的值，比之前的最小值还小，就将旧的最小值先保留到栈中，在入栈新的值，并且更新最小值为新入栈的值| 2 | min = 2| 3 | | 5 | |_3_| stack 入栈 6 | 6 | min = 2| 2 | | 3 | | 5 | |_3_| stack 出栈 6 | 2 | min = 2| 3 | | 5 | |_3_| stack 出栈 2 | 2 | min = 2| 3 | | 5 | |_3_| stack出栈时，以后top元素，和以后min值雷同时，阐明以后top元素，在入栈时是更新了最小值的元素，也就是说它的下一个元素，是之前旧的min值所以，出栈2，出栈3，同时更新min=3作者：windliang链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。python代码 ...

题目给你一个字符串表达式 s ，请你实现一个根本计算器来计算并返回它的值。 输出：s = "1 + 1"输入：2输出：s = " 2-1 + 2 "输入：3输出：s = "(1+(4+5+2)-3)+(6+8)"输入：23s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 示意一个无效的表达式'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 有效)'-' 能够用作一元运算(即 "-1" 和 "-(2 + 3)" 是无效的)输出中不存在两个间断的操作符每个数字和运行的计算将适宜于一个有符号的 32位 整数思路计算器类的题目，224、227、772，只须要一个思路：逆波兰表达式+栈。a+b，逆波兰表达式：a,b,+ 例如：s = '2+(35/4+7(2+3))/4' 定义两个栈：stack栈 用来寄存数字以外的符号：运算符、括号res栈 用来寄存数字，以及pop进去的运算符，造成逆波兰表达式 给出一个加减乘除全都有的思路：思路规定：数字，放入res符号，放入stack当以后符号的优先级，<=stack栈顶的符号优先级时，须要将stack栈顶的符号pop进来，放入res中，再将以后符号放入stack中当遇到 ）时，将stack中最初一个（ 之后的所有运算符都pop进来，放入res中 构建逆波兰表达式的过程： 2+(3*5/4+7*(2+3))/4以后字符 2，压入resstack: []res: ['2']以后字符 +，压入stackstack: ['+']res: ['2']以后字符是 (，压入stackstack: ['+', '(']res: ['2']以后字符 3，压入resstack: ['+', '(']res: ['2', '3']以后字符 *，压入stackstack: ['+', '(', '*']res: ['2', '3']以后字符 5，压入resstack: ['+', '(', '*']res: ['2', '3', '5']以后字符 /，优先级<=stack栈顶的*, 将stack栈顶的* pop到res中，再将以后的/压入stackstack: ['+', '(', '/']res: ['2', '3', '5', '*']以后字符 4，压入resstack: ['+', '(', '/']res: ['2', '3', '5', '*', '4']以后字符 +，优先级<=stack栈顶的/, 将stack栈顶的/ pop到res中，再将以后的+压入stackstack: ['+', '(', '+']res: ['2', '3', '5', '*', '4', '/']以后字符 7，压入resstack: ['+', '(', '+']res: ['2', '3', '5', '*', '4', '/', '7']以后字符 *，压入stackstack: ['+', '(', '+', '*']res: ['2', '3', '5', '*', '4', '/', '7']以后字符是 (，压入stackstack: ['+', '(', '+', '*', '(']res: ['2', '3', '5', '*', '4', '/', '7']以后字符 2，压入resstack: ['+', '(', '+', '*', '(']res: ['2', '3', '5', '*', '4', '/', '7', '2']以后字符 +，压入stackstack: ['+', '(', '+', '*', '(', '+']res: ['2', '3', '5', '*', '4', '/', '7', '2']以后字符 3，压入resstack: ['+', '(', '+', '*', '(', '+']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3']以后字符 )，将stack中最初一个 ( 之后的运算符都pop到res中stack: ['+', '(', '+', '*']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+']以后字符 )，将stack中最初一个 ( 之后的运算符都pop到res中stack: ['+']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+']以后字符 /，压入stackstack: ['+', '/']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+']以后字符 4，压入resstack: ['+', '/']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+', '4']stack中残余的操作符，后进先出的pop到res中stack: []res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+', '4', '/', '+']逆波兰表达式计算过程: ...

题目给你一个长度为 n 的链表，每个节点蕴含一个额定减少的随机指针 random ，该指针能够指向链表中的任何节点或空节点。 结构这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针可能示意雷同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 思路感觉这道题的难点，在于读懂题目说的啥...其实题目的意思就是：有一个链表，这个链表的节点，不光有next指针，还有一个random指针，随机指向某个节点或是None。当初让你复制一份这个链表。 def copyRandomList(head): if not head: return None # 设置一个字典 dic = {} # 头节点处初始化一个指针cur cur = head # 第1遍遍历链表的每个节点 while cur!=None: # 以后节点作为key，以后节点的copy节点作为val，存入字典中 dic[cur] = Node(cur.val) # 挪动指针，持续下一个节点 cur = cur.next # 第1遍遍历实现后，每个节点都复制了一份 # cur再放回到表头处 cur = head # 第2遍遍历，为copy节点进行next和random指针的链接 while cur!=None: # copy节点的next指向原节点的next的copy dic[cur].next = dic[cur.next] if cur.next else None # copy节点的random指向原节点的next的random dic[cur].random = dic[cur.random] if cur.random else None # 挪动指针，持续下一个节点 cur = cur.next # 返回头节点的copy，即复制链表的头节点 return dic[head]

题目给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从地位 left 到地位 right 的链表节点，返回 反转后的链表 。 输出：head = [1,2,3,4,5], left = 2, right = 4输入：[1,4,3,2,5]输出：head = [5], left = 1, right = 1输入：[5]思路不要陷入206.反转链表的思维误区，206是反转全副链表，所以用递归的思维，始终到链表最初，注意力在链表最初，从后向前一一反转。 本题的思路，注意力是放在后面：例如，将 [2,3,4] 翻转，重点不应放在4上，而是放在结尾2上，只须要一直将2后的那个节点移到它后面即可：2,(3),4 ——> (3),2,4 ——> 3,2,(4) ——> (4),3,2 def reverseBetween(head, left, right) -> ListNode: # 设置虚构节点，指向头节点 # 设置虚构节点的目标是应答边界状况：原链表第一个节点就开始反转 dummy = ListNode(-1) dummy.next = head # 初始化pre指针 pre = dummy # 挪动pre指针到反转区的前一个节点 for i in range(left-1): pre = pre.next # cur指针指向反转区的第一个节点，固定在这个节点上不动 cur = pre.next # pre到了反转区前一个节点，开始进行反转，例如pre,2,3,4 for j in range(right-left): # 设置个tmp指针，指向cur的下一个节点 # pre,2(cur),3(tmp),4 tmp = cur.next # cur指向tmp的下一个节点 # pre,2(cur),4 cur.next = tmp.next # tmp指向pre的下一个节点 # 3(tmp),2(cur),4 tmp.next = pre.next # pre指向tmp节点 # pre,3(tmp),2(cur),4 pre.next = tmp return dummy.next

题目给定两个大小别离为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的工夫复杂度应该为 O(log (m+n)) 。 输出：nums1 = [1,3], nums2 = [2]输入：2.00000解释：合并数组 = [1,2,3] ，中位数 2输出：nums1 = [1,2], nums2 = [3,4]输入：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5归并排序利用归并排序的思维，在两个数组结尾，设置两个指针，比拟两个指针的大小，小的向后挪动，直到找到中位数。 这个办法工夫复杂度是O(m+n)，达不到题目的要求，且思考边界状况的代码简单。 二分法二分法的思维：一个正序数组的中位数，就是该数组第k小的数。例如数组长度是7，中位数就是第4个数。寻找中位数，转化成寻找第k个数。将该数组拆成2个正序数组，就是别离在2个数组中寻找第k/2个数。 如果数组a的第k/2个数，小于数组b的第k/2个数，那么数组a中从开始地位到第k/2的地位的这部分数，能够排除掉，中位数肯定不在这些数中因为，假如中位数在这些数中，最极其的状况就是a的第k/2个数就是中位数，那么数组b的前k/2个数，都应该小于它。但实际上b的第k/2个数，是大于a的第k/2个数的，所以假如不成立所以，第k/2个数较小的一方，中位数肯定不在它那里。 几个留神点： 每轮循环，k缩小的个数，是由被排除的数字个数决定的，而不是间接减半。查找范畴的边界状况： 如果完结范畴超过了数组范畴，就去数组开端作为完结范畴 如果起始范畴超过了数组范畴，阐明该数组被排空了，间接去另一个数组查看残余的k个数 例如有以下两个数组：A: 1 3 4 9B: 1 2 3 4 5 6 7 8 9两个有序数组的长度别离是4和9，长度之和是13，中位数是整个数组中的第7个元素，因而须要找到第 k=7 小的数。咱们在两个数组中，先各自找出第3小的数：A: 1 3 4 9 ↑B: 1 2 3 4 5 6 7 8 9 ↑A中第3小的数是4，B中第3小的数是3B的第3小<A的第3小，能够得出一个论断：咱们要找的第7小的数，肯定不在B的前3位当中因为，如果第7小的数在B的前3位当中，那么最极其的状况是B中的3就是第7小的数第7小的数后面的6个数都不会大于它，B中的3后面有2个数小于3，剩下4个数应该在A中然而A中不超过3的数只有2个所以，咱们要找的第7小的数，肯定不在B的前3位当中，能够把B的前3个数都排除了此时，寻找第7小的数，曾经排除了其中的3个，剩下4个就在两个数组中，再各自找第2小的数A: 1 3 4 9 ↑B: [1 2 3] 4 5 6 7 8 9 ↑A中第2小的数是3，B中第2小的数是5同上，第7小的数肯定不在A的前2个数中，排除掉这两个数寻找第7小的数，后面曾经排除了3个，当初又排除了2个，还剩2个数就在两个数组中，再各自找第1小的数A: [1 3] 4 9 ↑B: [1 2 3] 4 5 6 7 8 9 ↑A中第1小的数是4，B中第1小的数也是4，相等这种状况，咱们当作A<B解决，排除掉A的这1个数，B不动这是就剩1个数了，此时间接比拟两个数组未排除局部的第1个数，较小的那个数就是第7小的数了A: [1 3 4] 9 ↑B: [1 2 3] 4 5 6 7 8 9 ↑第7小的数是B中的4，因而两个正序数组的中位数就是4def findMedianSortedArrays(nums1, nums2): def getTheKNum(k): # 两个指针，初始都在0的地位 start1,start2 = 0,0 # 开始二分循环排除 while True: # 4. 当start曾经挪动到数组最初+1的地位，阐明该数组以排空，去另一个数组中查看残余的k个数 if start1==m: return nums2[start2+k-1] if start2==n: return nums1[start1+k-1] # 5. 当k被排除到只剩1个的时候，此时间接比拟两个数组start地位的数的大小即可，小的那个就是中位数 if k==1: return min(nums1[start1],nums2[start2]) # 1. 依据k值，确定【实践上】两个数组各自要查看几个数 halfK = k//2 # 2. 确定end的地位: 从start处开始，查看halfk个数，是否会超过数组范畴 # start是索引，所以start处有start+1个数 # 从start开始，查看halfk个数，因为蕴含了start地位的数，所以是halfk-1个数 # 所以从start开始查看halfk个数，共start+1+halfk-1=start+halfk个数 # 是否超过数组自身的长度范畴 len(nums)，超过了就将end定位到数组开端，没超过就失常 # end = min(start+halfk,len)-1 end1 = min(start1+halfK,len(nums1))-1 end2 = min(start2+halfK,len(nums2))-1 # 3. 确定好要查看几个数后，开始比拟end地位数的大小 # 小的，排除掉这部分数，从新计算k值，并且挪动start if nums1[end1] <= nums2[end2]: k = k - (end1-start1+1) start1 = end1+1 else: k = k - (end2-start2+1) start2 = end2+1 m,n = len(nums1),len(nums2) totalLen = m+n if totalLen%2 == 1: return getTheKNum(totalLen//2+1) else: return ((getTheKNum(totalLen//2))+(getTheKNum(totalLen//2+1)))/2

题目给定一个字符串 s ，请你找出其中不含有反复字符的 最长子串 的长度。 输出: s = "abcabcbb"输入: 3 解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。输出: s = "bbbbb"输入: 1解释: 因为无反复字符的最长子串是 "b"，所以其长度为 1。输出: s = "pwwkew"输入: 3解释: 因为无反复字符的最长子串是 "wke"，所以其长度为 3。 请留神，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。暴力枚举思路一：以每个字符为开始，遍历字符串，用一个字典保留遍历的字符，遇到反复的就完结，用一个数组保留本次无反复子串的长度，返回最大的 def lengthOfLongestSubstring(s): if not s: return 0 slen = [1] * len(s) for i in range(0,len(s)): hashTable = {} hashTable[s[i]]=1 for j in range(i+1, len(s)): if s[j] in hashTable: break else: hashTable[s[j]]=1 slen[i]+=1 return max(slen)滑动窗口# 思路二：滑动窗口# 定义两个指针，i和j，i作为无反复子串的结尾，j作为无反复子串的结尾# 定义一个字典st，用来保留每个字符的最初一次呈现的地位# 定义一个ans变量，用来保留最长无反复子串的长度# 初始时，i,j=0，都在结尾地位# 随着for循环遍历字符，j一直向后挪动# 在j挪动的过程中，如果以后字符在st中曾经存在了，阐明之前的字符中存在雷同的字符，这段无反复子串到此就完结了，须要挪动i来调整窗口# 挪动i时须要留神：# 在挪动前，如果i的地位<=反复字符的最新地位（..[i..反复字符..j]..)，# 阐明反复字符就在以后窗口中，须要将i挪动到反复字符的下一个地位(..反复字符[i..j]..)# 如果i的地位>反复字符的最新地位 (..反复字符..[i..j]..)，# 阐明反复字符在以后窗口后面，并不在以后窗口中，以后窗口的子串是无反复的，则i放弃不动，# i和j的地位都确定好后，再更新ans，ans=Max(ans, j-i+1)，以后的长度和之前的长度比拟，选最大的，让ans保留的是最大长度# 最初将{以后字符:呈现的位值}保留在字典st中def lengthOfLongestSubstring(s): st = {} i, ans = 0, 0 for j in range(len(s)): if s[j] in st: i = max(i, st[s[j]]+1) ans = max(ans,j-i+1) st[s[j]] = j return ans;

题目给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。 为了示意给定链表中的环，评测零碎外部应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。 输出：head = [3,2,0,-4], pos = 1输入：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连贯到第二个节点。输出：head = [1], pos = -1输入：返回 null解释：链表中没有环。遍历+哈希最简略的方法就是遍历每个节点，同时把节点存到一个字典中，当遍历下一个节点时，看看该节点是否曾经存在于字典中，如果是，就阐明该节点是环入口节点 def detectCycle(head: ListNode) -> ListNode: hashTable = {} while head: if head in hashTable: return head hashTable[head] = 1 head = head.next return None工夫复杂度：O(n)空间复杂度：O(n) 双指针了解双指针的思路，须要通过画图，计算挪动间隔的等量关系来了解：在链表头节点，定义两个指针：fast和slowfast每次挪动2个节点，slow每次挪动1个节点 如果链表没有环，fast指针会先挪动到null处如果链表有环，fast先进入环，slow随后进入环，最终他们必定会在环中的某个节点相遇 假如fast和slow第一次相遇时的节点如图所示a代表链表头节点到环的入口节点的节点数b代表环的入口节点到fast和slow第一次相遇的节点的节点数c代表第一次相遇节点到环的入口节点的节点数 此时，fast走过的节点数为 a+b+n(c+b) ，n示意fast在环中绕的圈数slow走过的节点数为 a+bfast和slow是一起挪动的，所以任意时刻他们的挪动步数是雷同的，然而fast每次挪动2个节点，雷同的步数下，fast挪动的节点数应该是slow的2倍所以 a+b+n(c+b) = 2(a+b)整顿等式得：a=n(b+c)-b = nb+nc-b = (n-1)b+nc = (n-1)b+(n-1)c+c=(n-1)(b+c)+c得 a = (n-1)(b+c)+c也就是说：头节点到环入口节点的间隔 = 第一次相遇节点到环入口节点的间隔+(n-1)圈环的长度如果此时有两个指针a和b，a从头节点开始挪动，b从slow和fast第一次相遇节点开始挪动，均每次挪动一个节点，a和b最终会在环入口节点处相遇。此时，slow曾经处在第一次相遇节点地位，因而当slow和fast第一次相遇时，再在头节点处定义一个指针，和slow一起每次挪动1个节点，他们相遇的那个节点就是环入口节点。 ...

题目给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都呈现在 大于或等于 x 的节点之前。 你该当 保留 两个分区中每个节点的初始绝对地位。 输出：head = [1,4,3,2,5,2], x = 3输入：[1,2,2,4,3,5]输出：head = [2,1], x = 2输入：[1,2]一开始题目都没读懂...其实题目的意思就是：比方示例中的数组，小于3的都放到后面，大于等于3的都放到前面，并且不扭转绝对程序。 思路保护两个链表：大链表、小链表大链表用来寄存大于等于x的局部小链表用来寄存小于x的局部最初将小链表和大链表拼接起来，就是最终答案 def partition(head: ListNode, x: int) -> ListNode: bigHead, smallHead = ListNode(-1), ListNode(-1) bigTail,smallTail = bigHead,smallHead while head: if head.val < x: smallTail.next = head smallTail = smallTail.next else: bigTail.next = head bigTail = bigTail.next head = head.next smallTail.next = bigHead.next bigTail.next = None return smallHead.next

题目给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 题目数据 保障 整个链式构造中不存在环。留神，函数返回后果后，链表必须 放弃其原始构造 。 输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3输入：Intersected at '8'解释：相交节点的值为 8 （留神，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。哈希表最简略的思路，遍历链表A，把每个节点存在一个字典(hash表)中。再遍历字典B，看B的以后节点是否在字典中，存在的话就是相交节点。 双指针定义两个指针A,B，别离从各自的链表表头开始遍历，如果两个指针指向的节点不同，就持续向后挪动如果两个指针指向的节点雷同，则找到了相交节点，包含两个不相交的链表，两个指针最终都会挪动到尾部节点指向的None，则也会返回None当某个指针挪动到链表开端时，跳转到另一个链表的表头开始遍历，这样做能保障两个不对称的相交链表，通过指针挪动，最终总能同时挪动到相交节点上 def getIntersectionNode(headA,headB): if not headA or not headB: return None A,B = headA,headB while A!=B: A = A.next if A else headB B = B.next if B else headA return A

题目给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]题解考查链表构造的了解，递归办法的实现 def reverseList(head): if not head or not head.next: return head curHead = reverseList(head.next) head.next.next = head head.next = None return curHead

题目给你一个 升序排列 的数组 nums ，请你 原地 删除反复呈现的元素，使每个元素 只呈现一次 ，返回删除后数组的新长度。元素的 绝对程序 应该放弃 统一 。 因为在某些语言中不能扭转数组的长度，所以必须将后果放在数组nums的第一局部。更标准地说，如果在删除反复项之后有 k 个元素，那么 nums 的前 k 个元素应该保留最终后果。 将最终后果插入 nums 的前 k 个地位后返回 k 。 不要应用额定的空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。 输出：nums = [1,1,2]输入：2, nums = [1,2,_]解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被批改为 1, 2 。不须要思考数组中超出新长度前面的元素。输出：nums = [0,0,1,1,1,2,2,3,3,4]输入：5, nums = [0,1,2,3,4]解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被批改为 0, 1, 2, 3, 4 。不须要思考数组中超出新长度前面的元素。双指针如果数组长度为0，示意不蕴含任何元素，则间接返回0。如果数组长度>0，则至多有1个元素，所以排除反复应该从第2个元素即下标1开始排除。定义两个指针fast和slowfast：随着迭代不停向后挪动，寻找不反复的元素slow：先停在以后地位，等fast找到不反复的元素时，扭转以后的元素为不反复元素，并向后挪动。反复这个动作 def removeDuplicates(nums): if not nums: return 0 fast = 1 slow = 1 while fast < len(nums): if nums[fast]!=nums[fast-1]: nums[slow]=nums[fast] slow+=1 fast+=1 return slow工夫复杂度O(n)空间复杂度O(1) ...

题目将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输出：l1 = [1,2,4], l2 = [1,3,4]输入：[1,1,2,3,4,4]输出：l1 = [], l2 = []输入：[]输出：l1 = [], l2 = [0]输入：[0]递归# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextdef mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode: if list1 is None: return list2 if list2 is None: return list1 if list1.val < list2.val: list1.next = mergeTwoLists(list1.next, list2) return list1 else: list2.next = mergeTwoLists(list1, list2.next) return list2工夫复杂度：O(n+m)，其中 n 和 m 别离为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至多有一个链表为空），函数 mergeTwoList 至少只会递归调用每个节点一次。因而，工夫复杂度取决于合并后的链表长度，即 O(n+m)。 ...

题目给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。 无效字符串需满足： 左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。 输出：s = "()"输入：true输出：s = "()[]{}"输入：true输出：s = "(]"输入：false输出：s = "([)]"输入：false输出：s = "{[]}"输入：true栈'()[]'和'([])'这两种无效状况，能够看出，只有右括号后面是左括号，它们肯定是一对，能够互相对消的。利用栈的思维能够很好的解决题目，有种消消乐的感觉。 def isValid(s): # 如果字符串是奇数，那么必定返回False if len(s)%2!=0: return False hash = { ')':'(', ']':'[', '}':'{' } stack = [] for ch in s: # 如果是右括号 if ch in hash: # 如果曾经空栈且右括号，间接False # 如果栈顶的左括号和以后右括号不配对，间接False if not stack or stack[-1]!=hash[ch]: return False # 没空栈，且与栈顶左括号配对，则打消这对括号 stack.pop() else: # 如果是左括号，间接入栈 stack.append(ch) # 通过栈的打消，如果是无效括号，应该是空栈 return not stack工夫复杂度：O(n)空间复杂度：O(n+∣∣)，其中 示意字符集，本题中字符串只蕴含6种括号，∣∣=6。栈中的字符数量为 O(n)，而哈希表应用的空间为 O(∣∣)，相加即可失去总空间复杂度。 ...

题目编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 输出：strs = ["flower","flow","flight"]输入："fl"纵向扫描最间接的思路：选取第一个字符串假如为前缀。用这个前缀的每一个字符，去和所有其余字符串比拟，如果其余字符串在该地位也是这个字符，那这个字符就属于前缀；反之，前缀就到此结束。 不须要思考选取数组中的第一个字符串是否长度是最小或最长的。因为最差状况就是这个字符串是长度最短的，并且所有字符刚好都是前缀。 工夫复杂度：最坏状况，数组有n个字符串，字符串全都一样且长度为m，O(mn)空间复杂度：O(1) def longestCommonPrefix(strs): firstStr = strs[0] for i in range(len(firstStr)): for str in strs[1:]: if str[i] != firstStr[i]: return firstStr[0:i] if i > 0 else ''横向扫描假如数组中第一个字符串是前缀。拿假如前缀，和第二个字符串比拟，共有局部是新的前缀。再拿新的前缀，和第三个字符串比拟，共有局部是新的前缀。始终如此，比到数组最初一个字符串。 工夫复杂度：最坏状况和之前一样，O(mn)空间复杂度：O(1) def longestCommonPrefix(strs): prefix = strs[0] for str in strs[1:]: # 选较短长度作为遍历范畴 for i in range(min(len(prefix), len(str))): if prefix[i] != str[i]: prefix = prefix[:i] break return prefix分治法分治法是一种思维，就是分而治之。 递归是一种编程技巧，分治思维在代码中适宜用递归来实现。 在本题中，将原数组分成两半，别离找出这两局部的公共前缀，再找出这两个前缀的公共前缀，最终就是这个数组的公共前缀。这就是分治思维 工夫复杂度O(mn)空间复杂度O(mlogn)，m是字符串均匀长度，n是字符串数量 def longestCommonPrefix(strs): def split(start, end): # 分到不可再分，返回字符串 if start == end: return strs[start] mid = (start + end) // 2 # 递归宰割数组 left, right = split(start, mid), split(mid + 1, end) # 以两个字符串中较小的长度作为遍历范畴 minLen = min(len(left), len(right)) print(left, right, minLen) for i in range(minLen): # 当呈现不统一，则该层公共前缀已找到 if left[i] != right[i]: return left[:i] # 没有不统一，长度较小的字符串全副遍历完，则长度较小的字符串就是公共前缀 return left[:minLen] return split(0, len(strs) - 1)二分法公共前缀的长度肯定不会超过最小长度的字符串。咱们再最小长度字符串上应用二分法，将其分成两半，用左半边字符去和每个字符串比拟如果每个字符串都有，那么就挪动左指针如果有字符串没有，那么就挪动右指针，放大公共范畴 ...

题目给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121 是回文，而 123 不是。 输出：x = 121输入：true输出：x = -121输入：false解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因而它不是一个回文数。转成字符串翻转最简略最低效的办法，因为将数字转成字符串须要开拓额定的空间，会晋升空间复杂度。 def isPalindrome(x: int) -> bool: return str(x) == str(x)[::-1]利用除法反转数字转成字符串须要多破费空间。间接将数字反转，而后和原值比拟。有的题解说，思考到反转后的数可能会溢出，因而只反转一半，如果x是回文数，则应该是对称的。实际上，x如果是回文数，那x的值曾经确定就不会溢出，x的反转还是他本人所以也不可能溢出。x如果不是回文数，那反转后要么不等于本人，要么会溢出。 数字反转的原理： x%10，余数就是x的最初一个数字x//10，后果就是去除最初一位的其余数字# 不思考溢出，全副反转def isPalindrome(x): if x < 0 or (x % 10 == 0 and x != 0): return False originalNum = x revertedNum = 0 while x > 0: revertedNum = revertedNum * 10 + x % 10 x = x // 10 return revertedNum == originalNum反转一半的原理1221，反转一半12，和残余的12比拟12321，反转一半123，//10取整得12，和残余的12比拟当x>反转的数，就一只反转 ...

题目给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 输出：nums = [2,7,11,15], target = 9输入：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。暴力枚举两层for循环一一遍历，O(n^2) def twoSum(ary,target): for i in range(len(ary)): for j in range(i+1,len(ary)): if ary[i]+ary[j]==target: return [i,j] return []字典模仿hash表一层for循环遍历，将元素值为key下表为value存入字典中。O(n) def twoSum(ary,target): hashTable = {} for i, num in enumerate(ary): if target-num in hashTable: return [hashTable[target-num],i] hashTable[num]=i return []

题目给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 输出: nums = [-1,0,3,5,9,12], target = 9输入: 4解释: 9 呈现在 nums 中并且下标为 4暴力枚举for循环遍历数组元素，挨个判断。工夫复杂度O(n) def search(nums, target) -> int: for i,num in enumerate(nums): if num == target: return i return -1二分法二分法，实用于这种有序数组的查找。二分法的思维，就是每次取两头的值与target比拟，而后放大范畴再取两头的值...： 如果两头值<target，就膨胀left如果两头值>target，就膨胀right如果两头值=target，须要分状况探讨 如果数组是[1,2,3,4]这种有序且不反复，就间接找到了如果数组是其余状况，比方有反复，局部有序，局部有序且有反复，就须要思考左右边界，因为数组中可能有多个等于target的数，须要找最左侧的或是最右侧的二分法工夫复杂度O(logn)，n/2^k=1，k=logn 规范二分，数组有序无反复元素[1,2,3,4,5]，数组有序且无反复元素while循环实现 def search(nums, target) -> int: left,right = 0, len(nums)-1 while left <= right: mid = (left+right)//2 if nums[mid]==target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1递归实现 ...

1. 字典树Trie树，即字典树，又称单词查找树或键树，是一种树形构造，是一种哈希树的变种。 典型利用是用于统计和排序大量的字符串（但不仅限于字符串），所以常常被搜索引擎零碎用于文本词频统计。 Trie的核心思想是空间换工夫。它能最大限度地缩小无谓的字符串比拟，利用字符串的公共前缀来升高查问工夫的开销，查问效率比哈希树高。 2. 字典树的性质 除了根节点外，每一个节点都只蕴含一个字符每个节点的所有子节点蕴含的字符都不雷同从根节点到某个节点，门路上的字符连接起来，为该节点对应的字符串3. 结构字典树public class Trie { static class TrieNode { // 示意以后节点的值 char value; // 示意以后节点是否是终止节点（这里不是指叶子节点，是指是否为单词的结尾） boolean flag; // 示意以后节点的子节点的数组，不思考大小写共有26个字母，所以初始化大小为26 TrieNode[] nextNodes = new TrieNode[26]; public TrieNode() { } public TrieNode(char value) { this.value = value; } } /** * 插入一个新单词 * * @param root 根节点 * @param str 要插入的新单词 */ public void insert(TrieNode root, String str) { if (root == null || str == null || str.length() == 0) { return; } for (int i = 0; i < str.length(); i++) { // index示意以后字符在字符表中的地位 int index = str.charAt(i) - 'a'; // 如果该分支不存在，则创立一个新节点 if (root.nextNodes[index] == null) { root.nextNodes[index] = new TrieNode(str.charAt(i)); } // 把该节点赋给root，进入树的下一层 root = root.nextNodes[index]; } // 设置以后节点为终止节点 root.flag = true; }}4. 查找单词是否在字典树中存在 /** * 查找一个单词是否存在 * * @param root 根节点 * @param str 要查找的单词 */ public boolean search(TrieNode root, String str) { if (root == null || str == null || str.length() == 0) { return false; } for (int i = 0; i < str.length(); i++) { // index示意以后的字符在中的字符表中的地位 int index = str.charAt(i) - 'a'; // 如果该分支不存在，则阐明不存在该字符 if (root.nextNodes[index] == null) { return false; } // 把以后节点赋给root，进入树的下一层 root = root.nextNodes[index]; } // 如果以后节点是终止节点，则阐明存在，否则不存在 return root.flag; }

露从今夜白，月是故土明。引言队列在日常生活中时一个非常常见的名词，比方去食堂打饭时排队，排在最后面的总是最先取到餐。最晚达到这个队列往往排在队列的最初面。也就是先进先出。这种排队的特点同样也被引入到了计算机中，也就是音讯队列，电商在搞大促销的时候，峰值会是平时的好几倍，零碎可能会解决不到位，咱们一边将零碎扩容，一边筹备音讯队列，将超过零碎解决能力的强求放在音讯队列中，零碎顺次解决音讯队列中的申请。这种"先进先出"也别引入到了数据结构中，也就是队列。 队列由下面的探讨咱们能够总结出队列的逻辑构造，数据结构中的队列，即是把一个一个的结点依照某种顺序排列，对其解决的过程和日常生活中的对了是一样的。队列规定为: 排列程序: 结点排成一队，起初的排在队尾。处理过程: 在队头处理事件; 队列中有元素始终解决，直至队空或产生中断事件。队列的定义: 队列(Queue) 是只容许在一端进行操作而在另一端进行删除操作的线性表。删除端被称为"队头"，插入端被称入"队尾"。与栈的不同之处在于，队列是一种先进先出(First In First Out FIFO)的线性表；与栈雷同的是，队列也是一种重要的线性构造。依据队列的定义，队列的基本操作有下列这些:置空队列: 将已有队列置空判空操作: 若队列为空, 则返回的值为true, 否则为false.出队操作: 当队列非空时, 返回队列头元素的值, 批改队列头指针。入队操作: 将结点插入队尾，批改队尾指针取队头元素操作: 当队列非空时, 返回队列头元素的值，但不删除队列头元素。栈应用top来指向栈顶元素，便于咱们实现入栈出栈操作。那对于队列这种一端进一端出的数据结构，咱们就须要两个变量来实现入队和出队操作，一个指向队头，一个指向队尾。咱们仍然用链式存储构造和顺序存储构造来别离实现队列。 程序队列对于程序队列来说有两种类型，一种是无限度的队列, 主动扩容，对入队元素数量无限度。一种是限度容量的队列。对入队元素数量有限度。对于无限度的队列，咱们能够仿照之前做线性表的思路，在原先的根底上进行扩大。在原先的根底上从新提供专属于队列的API，而后入队操作和出队操作在原先的根底上做包装。像上面这样: public class SequenceQueue extends SequenceList{ public void offer(Integer data) { add(data); } public Integer remove() { return remove(size() - 1); } public Integer peek() { if (size() > 0){ return get(0); } return null; } public boolean empty(){ return size() == 0; } // 清空操作 在SequenceList中实现}那对于容量限度的队列来说就有一个假溢出的问题， 咱们举一个例子来阐明这个问题，假设限度数组的容量为10，咱们每次出队就是让头指针迁徙，假如当初头指针曾经到了最初，也就是后面的元素曾经都出队了，然而有新元素过去依然不能出队。即便后面的空间曾经废除掉了，这样队列就只能应用一次，相当鸡肋，所以这种设计存在不合理之处，咱们当然不能让队列只应用一次，那咱们该如何应用后面的废除的空间呢？ 有两种思路: ...

队列的程序、链式存储构造实现Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". 题目作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...题解作者:WildDuck 顺序存储构造的实现形式 struct MyCircularQueue{ int front; int tail; int Max_size; int* data;};typedef struct MyCircularQueue MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* head =(MyCircularQueue*)malloc(sizeof(struct MyCircularQueue)); head->data = (int*)malloc(sizeof(int)*(k+1)); head->front = 0; head->tail = 0; head->Max_size = k+1; return head;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->front == obj->tail) { return true; } else return false;}bool myCircularQueueIsFull(MyCircularQueue* obj) { if((obj->tail+1)%obj->Max_size == obj->front) { return true; } else return false;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){ if(myCircularQueueIsFull(obj) == false) { obj->data[obj->tail] = value; obj->tail = (obj->tail+1)%obj->Max_size; return true; } else return false;}bool myCircularQueueDeQueue(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { obj->data[obj->front] = -1; obj->front = (obj->front+1)%obj->Max_size; return true; } else return false;}int myCircularQueueFront(MyCircularQueue* obj){ if(myCircularQueueIsEmpty(obj) == false) { return obj->data[obj->front]; } else return -1; }int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj) == false) { if(obj->tail-1 >= 0) { return obj->data[obj->tail-1]; } else return obj->data[obj->Max_size-1]; } else return -1;}void myCircularQueueFree(MyCircularQueue* obj) {}/** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj);*/链式存储构造实现 ...

最小栈解决O(1)工夫复杂度内最小值的查找题目形容Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.要求在常数工夫内找到栈中最小值为重点要求。即工夫复杂度为O(1)。题目作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...题目起源：力扣（LeetCode）题解作者：WildDuck题目剖析代码实现 #define Elemtype intstruct MinStack{ Elemtype val; struct MinStack* next; struct MinStack* Min_stack;};typedef struct MinStack MinStack;typedef struct MinStack* MinStack_pointer;/** initialize your data structure here. *///应用链式存储构造实现栈 严格限度从头部开始操作MinStack* minStackCreate() { //头部指针作为栈顶地位，标识并管制整个栈 MinStack_pointer head = (MinStack_pointer)malloc(sizeof(struct MinStack)); head->val = -1; head->next = NULL; head->Min_stack = NULL; return head;}void minStackPush(MinStack* obj, int val) { //依据链式构造实现栈，栈的push必须用头插法实现 //此类实现形式的益处高效应用内存空间、不限定栈大小状况下不会溢出 MinStack_pointer new_elem = (MinStack_pointer)malloc(sizeof(struct MinStack)); obj -> val = obj -> val + 1; new_elem -> val = val; new_elem -> next = obj -> next; new_elem -> Min_stack = NULL; obj ->next = new_elem; if(obj -> Min_stack == NULL) { obj -> Min_stack = new_elem; } else if(obj -> Min_stack != NULL && (obj -> Min_stack -> val) > val) { obj -> Min_stack = new_elem; } new_elem -> Min_stack = obj->Min_stack;}void minStackPop(MinStack* obj) { //依据链式构造实现栈，栈的push必须用头删法实现 MinStack_pointer temp_elem = obj->next; if(obj->Min_stack == obj->next) { if(obj->val > 0) { obj -> Min_stack = ((obj->next)->next)->Min_stack; } else if(obj->val == 0) { obj -> Min_stack = NULL; } } obj -> next = obj->next->next; obj -> val = obj -> val -1; free(temp_elem);}int minStackTop(MinStack* obj) { return obj->next->val;}int minStackGetMin(MinStack* obj) { return obj->Min_stack->val;}/** * Your MinStack struct will be instantiated and called as such: * MinStack* obj = minStackCreate(); * minStackPush(obj, val); * minStackPop(obj); * int param_3 = minStackTop(obj); * int param_4 = minStackGetMin(obj);*/ ...

构建一个虚头结点对立所有结点的删除操作及时free好习惯移除链表元素给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...起源：力扣（LeetCode）题解作者:WildDuck /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode* ListNode_pointer;struct ListNode* removeElements(struct ListNode* head, int val){ //手动构建头结点，将删除elem的操作对立 ListNode_pointer save_head = head; ListNode_pointer free_pointer = NULL; ListNode_pointer temp_head = (ListNode_pointer)malloc(sizeof(struct ListNode)); ListNode_pointer save_temp_head = temp_head; temp_head -> next = head; while(head != NULL) { if(head->val != val) { temp_head = temp_head->next; head = head->next; } else if(head->val == val) { temp_head -> next = head->next; free_pointer = head; head = head->next; free(free_pointer); } } free_pointer = save_temp_head; save_temp_head = save_temp_head->next; free(free_pointer); return save_temp_head; } ...

判断回文链表(仅应用O(1)存储空间和O(n)工夫复杂度)题目形容请判断一个链表是否为回文链表,用 O(n) 工夫复杂度和 O(1) 空间复杂度解决。 题目作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...起源：力扣（LeetCode）题解作者：WildDuck题目剖析 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode* ListNode_pointer;ListNode_pointer insertAtHead(ListNode_pointer head,ListNode_pointer target){ target -> next = head->next; head -> next = target; return head;}bool isPalindrome(struct ListNode* head){ if(head == NULL || head->next == NULL) { return true; } else { ListNode_pointer fast = head; ListNode_pointer slow = head; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } ListNode_pointer Mid_loc = slow; //fast 达到开端NULL工夫、slow肯定在原链表两头地位 //头插法逆置后续地位的所有链表 ListNode_pointer new_head = (ListNode_pointer)malloc(sizeof(struct ListNode)); new_head -> next = NULL; ListNode_pointer temp_new_head = new_head; ListNode_pointer save_next = NULL; while(slow != NULL) { save_next = slow -> next; temp_new_head = insertAtHead(temp_new_head,slow); slow = save_next; } slow = head; temp_new_head = temp_new_head -> next; while(slow != Mid_loc && slow -> val == temp_new_head ->val) { slow = slow -> next; temp_new_head = temp_new_head -> next; } free(new_head); if(slow == Mid_loc) { return true; } else return false; } } ...

题目形容给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。应用一趟扫描实现。题目作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...题解作者：WildDuck题目剖析 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode* ListNode_pointer;struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ //两个指针构建一个窗口套住固定间隔 ListNode_pointer fast = head; ListNode_pointer slow = head; for(int i=0;i<n;i++) { fast = fast -> next; } while(fast != NULL && fast->next != NULL) { fast = fast -> next; slow = slow -> next; } if(fast == NULL)//对仅含一个元素的链表非凡解决 { head = head -> next; free(slow); } else { ListNode_pointer free_p = slow->next; slow -> next = slow->next->next; free(free_p); } return head;}窗口套住固定间隔 ...

旋转链表题目形容给你一个链表的头节点 head ，旋转链表，将链表每个节点向右挪动 k 个地位。题目作者：力扣 (LeetCode)链接：https://leetcode-cn.com/leetb...题目起源：力扣（LeetCode）题解作者：WildDuck剖析思路代码实现 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; *///本题解中的fast指针不会比slow每次走快N步，只是比slow指针先登程，二者步调速度统一，用于造成一个区间typedef struct ListNode* ListNode_pointer;struct ListNode* rotateRight(struct ListNode* head, int k){ if(head != NULL) { ListNode_pointer fast = head; ListNode_pointer slow = head; ListNode_pointer save_pointer = NULL; int list_length=1; while(fast->next != NULL) { fast = fast -> next; list_length = list_length+1; } k = k%list_length; fast = head; for(int i = 0; i<k;i++) { fast = fast->next; } while(fast->next != NULL) { fast = fast->next; slow = slow->next; } if(slow != fast) { save_pointer = slow; slow = slow ->next; fast->next = head; save_pointer->next = NULL; } else if (slow == fast) { slow = head; } return slow; } else return head; } ...

题目形容题目地址：https://leetcode-cn.com/probl...给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。 你能够按任意程序返回答案。   示例 1： 输出：nums = [2,7,11,15], target = 9输入：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2： 输出：nums = [3,2,4], target = 6输入：[1,2]示例 3： 输出：nums = [3,3], target = 6输入：[0,1]  提醒： 2 <= nums.length <= 10的3次方-10的9次方 <= nums[i] <= 10的9次方-10的9次方 <= target <= 10的9次方只会存在一个无效答案 解题思路依据我的了解，首先题目没有说数组是有序的，那么我只能想到的是循环，两数之和等于数组中的两个数相加，那么咱们循环数组，nums[i]作为第一个加数，那么咱们要找的就是另一个加数，另一个加数等于target-nums[i],那么这另一个加数应该从哪里去找呢，应该从nums[i+1]到nums[nums.length - 1]中找，算了，废那么多话还说不清楚 public class Leetcode1 { public static void main(String[] args) { int arr[] = {1,3,4,6,2,9}; int[] ret = twoSum(arr, 10); System.out.println(ret[0]); System.out.println(ret[1]); } public static int[] twoSum(int[] nums, int target) { if(nums == null){ return new int[0]; } int[] arr = new int[2]; int cha = 0; for(int i = 0; i < nums.length; i++) { arr[0] = i; cha = target - nums[i]; for(int j = i+1; j<nums.length; j++) { if (nums[j] == cha) { arr[1] = j; return arr; } } } return null; }}

疾速排序（Quick Sort）疾速排序，又称分区替换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在均匀情况下，排序n个我的项目要O(n\log n)次比拟。在最坏情况下则须要O(n^2)次比拟。（inner loop）能够在大部分的架构上很有效率地达成。 疾速排序应用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，而后递归地排序两个子序列。步骤为： 筛选基准值：从数列中挑出一个元素，称为“基准”（pivot），宰割：从新排序数列，所有比基准值小的元素摆放在基准后面，所有比基准值大的元素摆在基准前面（与基准值相等的数能够到任何一边）。在这个宰割完结之后，对基准值的排序就曾经实现，递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。贴上一份手写golang代码参考： package mainimport ( "fmt")func main() { s := []int {9, 8, 7, 6, 5, 4, 3, 2, 1} res := quickSort(s) fmt.Println(res)}func quickSort(values []int) []int { if len(values) <= 1 { return values } middle := values[0] left := make([]int, 0, 10) right := make([]int, 0, 10) for i := 1; i < len(values); i++ { if middle <= values[i] { right = append(right, values[i]) } else { left = append(left, values[i]) } } left = quickSort(left) right = quickSort(right) return append(left, append([]int {middle}, right...)...)}

1 Manacher算法Manacher算法，又叫“马拉车”算法，能够在工夫复杂度为O(n)的状况下求解一个字符串的最长回文子串长度的问题。 2 字符串解决假如求解的字符串是abcc,要在其前后插入特殊字符(例如#),将其转化为#a#b#c#c#c# 2.1 最大回文半径咱们用 f(i) 来示意以字符串的第 i 位为回文核心，能够拓展出的最大回文半径，那么 f(i) - 1 就是以 i 为核心的最大回文串长度。为什么呢？通常长度等于2倍的最大半径再减去本身反复计算的长度1，即2*f(i) - 1,然而因为咱们插入了特殊字符#,一半的字符是特殊字符是不应该算进来的，故而理论长度等于f(i) - 1。 此时以字符串的第 i 位为回文核心，能够拓展出的最大回文右端点r_m为$i + $f[$i] - 1; 2.2 状态转移方程当咱们计算f(i)时候，就两种状况 状况一：i <=r_m 时候,阐明此时字符串的第 i 位被蕴含在i_m为核心能够拓展出的最大回文内，例如上面例子中下标7,那么此时咱们不必再次核心拓展，因为此时该地位最起码能和其以i_m为核心的对称点f(2*i_m - i)所能拓展出的最大回文相等，毕竟在同一个最大回文嘛，这也是Manacher 算法的核心思想，记录其对称地位的最大回文半径，那么此地位肯定大于等于其对称地位的最大回文半径，我集体了解是有点动静布局的思维，曾经拓展过的，不用再次拓展，只是保留的不是f(i)，而是i的对称点f(2*i_m - i)，然而又因为对称点可能向左有拓展，这边未必能向右拓展，所以对应的f(i) = min( r_m - i + 1, f(2*i_m - i) )，而后再去核心拓展，即状态转移方程就是：$$f(i) = min( r_m - i + 1, f(2*i_m - i) )$$状况二：i >r_m ,间接f(i) = 1 2.3 #a#b#c#c#c#实例上面是#a#b#c#c#的每一步解决例子： 字符 # a # b # c # c # c # c下标 0 1 2 3 4 5 6 7 8 9 10 11半径f(i) 1 2 1 2 1 2 3 4 4 3 2 1最右端点r_m 0 2 2 4 4 6 8 10 11 11 11 11r_m对应的i_m 0 1 1 3 3 5 6 7 8 8 8 8最大回文串 # #a# # #b# # #c# #c#c# #c#c#c# c#c#c#c c#c#c c#c c 在下标为7处，其对称点下标为2*i_m - i = 2*6 - 7 = 5,对应的最大半径为min( f(5), r_m - i + 1 ) = min( f(5), 8 - 7 + 1) = min(2, 1) = 1,则7至多在[7,7]即本身是回文的，而后右边从i - f(i) = 7 - 1 = 6,左边从i + f(i) = 7 + 1 = 8，向两边拓展，最终拓展到[4,10],更新i_m = 7, r_m=10 ...

1. 指标：实现一个繁难哈希表冀望构建一个这样的繁难哈希表： √ 长度为10√ 应用time33散列函数√ key应用16位字符串√ data应用int√ 用单向链表解决哈希碰撞X 暂不反对扩容重哈希2. 代码实现2.1 哈希节点构造体#define HASHSIZE 10typedef struct HashNode { char key[16]; int data;//数据域 struct HashNode *next;//指针域,哈希碰撞时候的后继结点} HashNode;static HashNode *HashTable[HASHSIZE];2.2 time33散列函数这里因为要放在长度为HASHSIZE的HashTable里，故而对HASHSIZE取余 typedef struct HashNode { char key[16]; int data;//数据域 struct HashNode *next;//指针域,哈希碰撞时候的后继结点} HashNode;static HashNode *HashTable[HASHSIZE];2.3 set函数思考该槽为NULL时直接插入思考该槽不为空时，则遍历链表寻找指标key, 找失去就更新, 找不到就尾插新节点void *set(char *key, int data){ struct HashNode *node; unsigned int hash_key = time33(key); printf("set key:%s val:%d hash:%d\n", key, data, hash_key); struct HashNode *new_node; new_node = (struct HashNode *)malloc(sizeof(struct HashNode)); strcpy(new_node->key, key); new_node->data = data; new_node->next = NULL; node = HashTable[hash_key]; //先看在不在 if (NULL == node) { HashTable[hash_key] = new_node; return NULL; }else if(strcmp(node->key, key) == 0){ printf("update key:%s %d => %d \n",key,node->data, data); //update node->data = data; free(new_node); }else{ //碰撞 while(node->next != NULL){ node = node->next; if(strcmp(node->key, key) == 0){ //update node->data = data; printf("update key:%s %d => %d \n",key,node->data, data); free(new_node); } } node->next = new_node; }}2.4 get函数思考该槽为NULL时返回NULL思考该槽不为空时，则遍历链表寻找指标key, 找失去就返回该节点, 找不到返回NULLHashNode *get(char *key){ unsigned int hash_key = time33(key); struct HashNode *node; node = HashTable[hash_key]; while(NULL != node){ if (strcmp(key, node->key) == 0) { printf("get %s :%d \n", key, node->data); return node; } node = node->next; } return NULL;}2.5 遍历哈希getAll函数 用于验证代码void getAll(){ struct HashNode *node; for (int i = 0; i < HASHSIZE; ++i) { if (HashTable[i] != NULL) { node = HashTable[i]; while(node != NULL){ printf("%d %s %d \n", i,node->key,node->data); node = node->next; } } }}3 测试代码int main(int argc, char const *argv[]){ set("zhangsan", 100); set("zhangsan", 200);//update set("lisi", 200); set("wangwu", 300); set("maliu", 400); set("qianer", 500); set("zhaojiu", 600); set("sunzi",700); set("wangwu", 3000);//update getAll(); return 0;}Res: ...

GitHub源码分享微信搜寻：码农StayUp主页地址：https://gozhuyinglong.github.io 源码分享：https://github.com/gozhuyinglong/blog-demos 1. 前言迄今为止，曾经介绍了《 二叉查找树 》和《 AVL树 》，咱们始终假如能够把整个数据结构存储在内存中。可是，如果数据多到内存装不下，这就意味着必须把数据放在磁盘上，显然这些数据结构不再实用。 问题在于磁盘的I/O速度是远远不如内存访问速度的，然而从一棵树中查找到某个元素，必须从根节点一层层往下找，这每一次查找便是一次I/O操作。为了进步性能，就必须要缩小查找的次数。 如能缩小树的高度、减少每个节点中的元素数，便是种无效的解决方案。实现这种想法的一种办法是应用B树。 2. 术语在介绍B树时会用到一些术语，这里先看一下： 根节点（root）：没有父节点的节点叫做根节点叶子节点（leaf）：没有子节点的节点叫做叶子节点外部节点（internal）：除根节点和叶子节点之外的节点叫做外部节点。它们即有父节点，也有子节点。键：B树中的存储元素是键，是用于指向数据记录的指针。键的值是用于存储真正的数据记录。一个节点中能够领有多个键。阶：B树的阶为最大子节点数量，其比键的数量大1。咱们个别称一个B树为M阶的B树，那么该B树最多领有M个子节点，节点中最多领有M-1个键。更多术语请参阅之前分享的《 树 》! 3. B树（B-Tree）B树与[二叉树]()（Binary Tree）不是一个概念，你能够将其翻译成Balance Tree，或者是Bayer Tree。B树是一种自均衡的树，可能保持数据有序。这种数据结构可能让查找数据、程序拜访、插入数据及删除的动作，都在对数工夫内实现。 B树与AVL树不同，能够领有2个以上的子节点，并且每个节点能够有多个键值，这些属性缩小了定位记录时所经验的两头过程，放慢了存取速度。B树更实用于读写绝对较大的数据块存储系统，如磁盘。这种数据结构常被利用在数据库和文件系统的实现上。 对于一个M阶B树具备以下个性： 每个节点最多有 M 个子节点；每个外部节点起码有 ⌈M/2⌉ 个子节点（⌈x⌉为向上取整符号）；如果根节点不是叶子节点，那么它至多有两个子节点。具备 N 个子节点的非叶子节点领有 N-1 个键。所有叶子节点必须处于同一层上。注：如下图是一棵5阶B树的两种画法，最精确的画法应该为图中左B树。但为了不便，通常会将节点中键为空的地位省去不画，如图中右B树。不能因为右图中最多的键为3，就判断这是一棵4阶B树，B树的阶是事后定义好的。 4. B树的操作在对B树进行操作时，可能会违反B树的个性，如最小子节点数、每个节点最小键数。为了保护B树的这些个性，树可能会决裂或合并。 上面咱们会以一棵5阶B树来讲述其搜寻、插入、删除操作。先来看下5阶B树的个性： 外部节点至多有3个子节点（⌈5/2⌉ = 3），最多有5个子节点每个节点至多有2个键（3-1=2），最多有4个键4.1 搜寻B树的搜寻和二叉搜寻树相似，从根节点开始，从上往下递归的遍历树。在每一层节点上，应用二分查找法匹配指标键，或者通过键的范畴来确定子树。 4.2 插入对于新元素的插入，都是产生在叶子节点上的。所有的插入操作都是从根节点开始，搜寻这棵树，并找到该元素应该被插入的节点。将新元素插入到该节点须要如下步骤： 如果该节点上的元素数未满，则将新元素插入到该节点，并放弃节点中元素的程序。如果该节点上的元素已满，则须要将该节点均匀地决裂成两个节点： 从该节点中的元素和新元素先出一个中位数小于中位数的元素放到右边节点，大于中位数的元素放到左边节点，中位数做为分隔值。分隔值被插入到父节点中（减少了树的高度），这可能会导致父节点的决裂，决裂父节点时又可能会使它的父节点决裂，以此类推。如果决裂始终回升到根节点，那么就创立一个新的根节点，它有一个分隔值和两个子节点。（这就是根节点并不像外部节点一样有起码子节点数量限度的起因）下图是一个5阶B树，咱们通过程序插入1到17，来察看节点的决裂过程。 4.3 删除B树的删除就简单了许多，可分为上面几种状况： 删除叶子节点中的元素（1）搜寻要删除的元素（2）如果它在叶子节点上，间接将其删除（3）如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。行将其父节点元素下移至以后节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素）（4）若兄弟节点也达到上限，则合并兄弟节点与宰割键。删除外部节点中的元素（1）外部节点中元素为其左右子节点的宰割值，须要从左子节点最大元素或右子节点最小元素中选出一个新的宰割符。被选中的宰割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。（2）上一步中，若左右子节点元素数均达到上限，则合并左右子节点。（3）若删除元素后，其中节点元素数小于上限，则持续合并。下图是一个5阶B树，咱们通过删除15、14、17、5四个键，来察看删除过程（根本涵盖所有状况）。 5. 代码实现本代码实现了B树的搜寻、插入、删除操作，上面看具体介绍。 5.1 键值类该类用于寄存B树每个节点中的键值数据。 key：节点中的键，用于指向数据记录。value：键向指向的数据记录。因为键在节点中是顺序存储的，所以实现了Comparable接口 class Entry implements Comparable<Entry> { final int key; String value; @Override public int compareTo(Entry o) { return Integer.compare(key, o.getKey()); }}5.2 节点类节点类是B树中的每个节点，其次要包含： ...

GitHub源码分享微信搜寻：码农StayUp主页地址：https://gozhuyinglong.github.io 源码分享：https://github.com/gozhuyinglong/blog-demos 1. 前言迄今为止，曾经介绍了《 二叉查找树 》和《 AVL树 》，咱们始终假如能够把整个数据结构存储在内存中。可是，如果数据多到内存装不下，这就意味着必须把数据放在磁盘上，显然这些数据结构不再实用。 问题在于磁盘的I/O速度是远远不如内存访问速度的，然而从一棵树中查找到某个元素，必须从根节点一层层往下找，这每一次查找便是一次I/O操作。为了进步性能，就必须要缩小查找的次数。 如能缩小树的高度、减少每个节点中的元素数，便是种无效的解决方案。实现这种想法的一种办法是应用B树。 2. 术语在介绍B树时会用到一些术语，这里先看一下： 根节点（root）：没有父节点的节点叫做根节点叶子节点（leaf）：没有子节点的节点叫做叶子节点外部节点（internal）：除根节点和叶子节点之外的节点叫做外部节点。它们即有父节点，也有子节点。键：B树中的存储元素是键，是用于指向数据记录的指针。键的值是用于存储真正的数据记录。一个节点中能够领有多个键。阶：B树的阶为最大子节点数量，其比键的数量大1。咱们个别称一个B树为M阶的B树，那么该B树最多领有M个子节点，节点中最多领有M-1个键。更多术语请参阅之前分享的《 树 》! 3. B树（B-Tree）B树与[二叉树]()（Binary Tree）不是一个概念，你能够将其翻译成Balance Tree，或者是Bayer Tree。B树是一种自均衡的树，可能保持数据有序。这种数据结构可能让查找数据、程序拜访、插入数据及删除的动作，都在对数工夫内实现。 B树与AVL树不同，能够领有2个以上的子节点，并且每个节点能够有多个键值，这些属性缩小了定位记录时所经验的两头过程，放慢了存取速度。B树更实用于读写绝对较大的数据块存储系统，如磁盘。这种数据结构常被利用在数据库和文件系统的实现上。 对于一个M阶B树具备以下个性： 每个节点最多有 M 个子节点；每个外部节点起码有 ⌈M/2⌉ 个子节点（⌈x⌉为向上取整符号）；如果根节点不是叶子节点，那么它至多有两个子节点。具备 N 个子节点的非叶子节点领有 N-1 个键。所有叶子节点必须处于同一层上。注：如下图是一棵5阶B树的两种画法，最精确的画法应该为图中左B树。但为了不便，通常会将节点中键为空的地位省去不画，如图中右B树。不能因为右图中最多的键为3，就判断这是一棵4阶B树，B树的阶是事后定义好的。 4. B树的操作在对B树进行操作时，可能会违反B树的个性，如最小子节点数、每个节点最小键数。为了保护B树的这些个性，树可能会决裂或合并。 上面咱们会以一棵5阶B树来讲述其搜寻、插入、删除操作。先来看下5阶B树的个性： 外部节点至多有3个子节点（⌈5/2⌉ = 3），最多有5个子节点每个节点至多有2个键（3-1=2），最多有4个键4.1 搜寻B树的搜寻和二叉搜寻树相似，从根节点开始，从上往下递归的遍历树。在每一层节点上，应用二分查找法匹配指标键，或者通过键的范畴来确定子树。 4.2 插入对于新元素的插入，都是产生在叶子节点上的。所有的插入操作都是从根节点开始，搜寻这棵树，并找到该元素应该被插入的节点。将新元素插入到该节点须要如下步骤： 如果该节点上的元素数未满，则将新元素插入到该节点，并放弃节点中元素的程序。如果该节点上的元素已满，则须要将该节点均匀地决裂成两个节点： 从该节点中的元素和新元素先出一个中位数小于中位数的元素放到右边节点，大于中位数的元素放到左边节点，中位数做为分隔值。分隔值被插入到父节点中（减少了树的高度），这可能会导致父节点的决裂，决裂父节点时又可能会使它的父节点决裂，以此类推。如果决裂始终回升到根节点，那么就创立一个新的根节点，它有一个分隔值和两个子节点。（这就是根节点并不像外部节点一样有起码子节点数量限度的起因）下图是一个5阶B树，咱们通过程序插入1到17，来察看节点的决裂过程。 4.3 删除B树的删除就简单了许多，可分为上面几种状况： 删除叶子节点中的元素（1）搜寻要删除的元素（2）如果它在叶子节点上，间接将其删除（3）如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。行将其父节点元素下移至以后节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素）（4）若兄弟节点也达到上限，则合并兄弟节点与宰割键。删除外部节点中的元素（1）外部节点中元素为其左右子节点的宰割值，须要从左子节点最大元素或右子节点最小元素中选出一个新的宰割符。被选中的宰割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。（2）上一步中，若左右子节点元素数均达到上限，则合并左右子节点。（3）若删除元素后，其中节点元素数小于上限，则持续合并。下图是一个5阶B树，咱们通过删除15、14、17、5四个键，来察看删除过程（根本涵盖所有状况）。 5. 代码实现本代码实现了B树的搜寻、插入、删除操作，上面看具体介绍。 5.1 键值类该类用于寄存B树每个节点中的键值数据。 key：节点中的键，用于指向数据记录。value：键向指向的数据记录。因为键在节点中是顺序存储的，所以实现了Comparable接口 class Entry implements Comparable<Entry> { final int key; String value; @Override public int compareTo(Entry o) { return Integer.compare(key, o.getKey()); }}5.2 节点类节点类是B树中的每个节点，其次要包含： ...

GitHub源码分享微信搜寻：码农StayUp主页地址：https://gozhuyinglong.github.io 源码分享：https://github.com/gozhuyinglong/blog-demos 1. 前言迄今为止，曾经介绍了《 二叉查找树 》和《 AVL树 》，咱们始终假如能够把整个数据结构存储在内存中。可是，如果数据多到内存装不下，这就意味着必须把数据放在磁盘上，显然这些数据结构不再实用。 问题在于磁盘的I/O速度是远远不如内存访问速度的，然而从一棵树中查找到某个元素，必须从根节点一层层往下找，这每一次查找便是一次I/O操作。为了进步性能，就必须要缩小查找的次数。 如能缩小树的高度、减少每个节点中的元素数，便是种无效的解决方案。实现这种想法的一种办法是应用B树。 2. 术语在介绍B树时会用到一些术语，这里先看一下： 根节点（root）：没有父节点的节点叫做根节点叶子节点（leaf）：没有子节点的节点叫做叶子节点外部节点（internal）：除根节点和叶子节点之外的节点叫做外部节点。它们即有父节点，也有子节点。键：B树中的存储元素是键，是用于指向数据记录的指针。键的值是用于存储真正的数据记录。一个节点中能够领有多个键。阶：B树的阶为最大子节点数量，其比键的数量大1。咱们个别称一个B树为M阶的B树，那么该B树最多领有M个子节点，节点中最多领有M-1个键。更多术语请参阅之前分享的《 树 》! 3. B树（B-Tree）B树与[二叉树]()（Binary Tree）不是一个概念，你能够将其翻译成Balance Tree，或者是Bayer Tree。B树是一种自均衡的树，可能保持数据有序。这种数据结构可能让查找数据、程序拜访、插入数据及删除的动作，都在对数工夫内实现。 B树与AVL树不同，能够领有2个以上的子节点，并且每个节点能够有多个键值，这些属性缩小了定位记录时所经验的两头过程，放慢了存取速度。B树更实用于读写绝对较大的数据块存储系统，如磁盘。这种数据结构常被利用在数据库和文件系统的实现上。 对于一个M阶B树具备以下个性： 每个节点最多有 M 个子节点；每个外部节点起码有 ⌈M/2⌉ 个子节点（⌈x⌉为向上取整符号）；如果根节点不是叶子节点，那么它至多有两个子节点。具备 N 个子节点的非叶子节点领有 N-1 个键。所有叶子节点必须处于同一层上。注：如下图是一棵5阶B树的两种画法，最精确的画法应该为图中左B树。但为了不便，通常会将节点中键为空的地位省去不画，如图中右B树。不能因为右图中最多的键为3，就判断这是一棵4阶B树，B树的阶是事后定义好的。 4. B树的操作在对B树进行操作时，可能会违反B树的个性，如最小子节点数、每个节点最小键数。为了保护B树的这些个性，树可能会决裂或合并。 上面咱们会以一棵5阶B树来讲述其搜寻、插入、删除操作。先来看下5阶B树的个性： 外部节点至多有3个子节点（⌈5/2⌉ = 3），最多有5个子节点每个节点至多有2个键（3-1=2），最多有4个键4.1 搜寻B树的搜寻和二叉搜寻树相似，从根节点开始，从上往下递归的遍历树。在每一层节点上，应用二分查找法匹配指标键，或者通过键的范畴来确定子树。 4.2 插入对于新元素的插入，都是产生在叶子节点上的。所有的插入操作都是从根节点开始，搜寻这棵树，并找到该元素应该被插入的节点。将新元素插入到该节点须要如下步骤： 如果该节点上的元素数未满，则将新元素插入到该节点，并放弃节点中元素的程序。如果该节点上的元素已满，则须要将该节点均匀地决裂成两个节点： 从该节点中的元素和新元素先出一个中位数小于中位数的元素放到右边节点，大于中位数的元素放到左边节点，中位数做为分隔值。分隔值被插入到父节点中（减少了树的高度），这可能会导致父节点的决裂，决裂父节点时又可能会使它的父节点决裂，以此类推。如果决裂始终回升到根节点，那么就创立一个新的根节点，它有一个分隔值和两个子节点。（这就是根节点并不像外部节点一样有起码子节点数量限度的起因）下图是一个5阶B树，咱们通过程序插入1到17，来察看节点的决裂过程。 4.3 删除B树的删除就简单了许多，可分为上面几种状况： 删除叶子节点中的元素（1）搜寻要删除的元素（2）如果它在叶子节点上，间接将其删除（3）如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。行将其父节点元素下移至以后节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素）（4）若兄弟节点也达到上限，则合并兄弟节点与宰割键。删除外部节点中的元素（1）外部节点中元素为其左右子节点的宰割值，须要从左子节点最大元素或右子节点最小元素中选出一个新的宰割符。被选中的宰割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。（2）上一步中，若左右子节点元素数均达到上限，则合并左右子节点。（3）若删除元素后，其中节点元素数小于上限，则持续合并。下图是一个5阶B树，咱们通过删除15、14、17、5四个键，来察看删除过程（根本涵盖所有状况）。 5. 代码实现本代码实现了B树的搜寻、插入、删除操作，上面看具体介绍。 5.1 键值类该类用于寄存B树每个节点中的键值数据。 key：节点中的键，用于指向数据记录。value：键向指向的数据记录。因为键在节点中是顺序存储的，所以实现了Comparable接口 class Entry implements Comparable<Entry> { final int key; String value; @Override public int compareTo(Entry o) { return Integer.compare(key, o.getKey()); }}5.2 节点类节点类是B树中的每个节点，其次要包含： ...

前两篇的地址在这里，没有看过的同学倡议先看下。 来和大家聊聊我是如何刷题的（第一弹）来和大家聊聊我是如何刷题的（第二弹）本章或者是这个系列的最终章。这次给大家聊一点硬核的，聊一些简直所有算法题都能用得上的超实用思维。 上一节给大家抛出了两个问题，别离是： 如何锁定应用哪种算法？比方我看到了这道题，我怎么晓得该用什么解法呢？二分？动静布局？一看就会，一写就废， 如何克服？明天，我就来圆一个当初吹下的牛逼。话不多说，间接上干货。如果你感觉有用，请三连反对我一下，让我可能坚持下去，给大家带来更多的干货。 <!-- more --> 如何锁定应用哪种算法？为什么很多人刚看了一眼题目就晓得怎么解？ 一种可能是 ta 之前做过同样或者相似的题目，造成了外在的记忆，间接提取了之前的记忆。另一种可能是题目给出了明确的提示信息，他们依据这些信息”蒙“的，这种蒙就是题感。最初一种是刚开始也没思路，尝试暴力解，发现某些步骤能够优化，缓缓剥茧抽丝，推导出最终答案。接下来，咱们来聊下第二种和第三种。至于第一种则不是一篇文章能解决的，这须要大家多做题，并且做题的时候要多总结多交换。 关键字关键字能够对解题起到提醒作用。这很好了解，假如题目没有限度信息等关键字，那就是耍流氓，毫无算法可言了。 比方”在一个数组中找 target“，这道题就很无聊，失常不会有这种算法题。 可能的出题模式是加上有序两个字，变成有序数组。那有序就是关键字了。 其余的例子有很多，接下来咱们来看下常见的关键字以及对应的可能解法有哪些。 如果题目是求极值，计数，很有可能是动静布局，堆等。如果题目是有序的，则可能是双指针。比方二分法。如果题目要求间断，则可能是滑动窗口。如果题目要求所有可能，须要门路信息，则可能是回溯。如上的这些只是看到关键词你应该第一工夫想到的可能解法，到底正确与否，以及复杂度是否达标须要在脑子里二次加工。 对于复杂度是否达标这一点，前面给大家介绍。限度条件很多题目都会给一些数据范畴的提醒，大家肯定要留神看。 比方 1681. 最小不兼容性，题目形容就不看了，咱们不打算在这里讲具体怎么解。这道题的函数签名如下： def minimumIncompatibility(self, nums: List[int], k: int) -> int:这道题的提醒是这样的: 1 <= k <= nums.length <= 16nums.length 能被 k 整除。1 <= nums[i] <= nums.length看到了这个你有什么想法么？ 留神到 nums 的长度和值都很小，这道题很可能是暴力回溯 + 状态压缩。对于回溯和状态压缩技巧能够翻翻我的历史文章。 这里再给大家一个超实用小技巧。 如果 n 是 10 左右，那么算法通常是 n! 的工夫复杂度。如果 n 是 20 左右，那么算法通常是 2^n 的工夫复杂度因而 1681. 最小不兼容性 这道题的复杂度很可能就是指数级别。 ...

GitHub源码分享微信搜寻：码农StayUp主页地址：https://gozhuyinglong.github.io源码分享：https://github.com/gozhuyinglong/blog-demos1. AVL树AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树，又叫做均衡二叉树。在AVL树中任何节点的两个子树高度差最多为1，所以它又被称为高度均衡树。 如下图中能够清晰的看出，右边的树其根节点左子树高度为3，右子树高度为2，合乎AVL树的特点；而左边的树其根节点左子树高度为3，右子树高度为1，不合乎AVL树的特点。因而右边的树为AVL树，左边的树不是AVL树。 那么怎样才能放弃这种均衡呢？ 答案便是在插入或删除节点时，通过对树进行简略的修改来保持平衡，咱们称之为旋转。 2. 旋转（rotation）旋转分为单旋转（single rotation）和双旋转（double rotation）。 当左右子树的高度差超过1，并且最高的叶子节点在“外边”时，应用单旋转。当左右子树的高度差超过1，并且最高的叶子节点在“外面”时，应用双旋转。而单旋转又分为： 左旋转，即向左旋转。当右子树的高度大于左子树时，进行左旋转。右旋转，即向右旋转。当左子树的高度大于右子树时，进行右旋转。双旋转又分为： 左-右双旋转，即先向左旋转（左子节点），再向右旋转。当左子树的高度大小右子树，并且左子树最高的叶子节点为其父节点的右子节点，那么须要左-右双旋转。右-左双旋转，即先向右旋转（右子节点），再向左旋转。当右子树的高度大小左子树，并且右子树最高的叶子节点为其父节点的左子节点，那么须要右-左双旋转。单看这些名词概念是不容易了解的，上面咱们通过图例来一一介绍。 3. 左旋转看下图中右边的树，该树是一棵二叉查找树，但是否满足AVL的个性呢？能够发现其根节点的左子树的高度为1，而右子树的高度为3，所以其不一棵AVL树。 通过察看，其右子树高于左子树，并且最高的叶子节点也在左边，那么咱们应用左旋转进行均衡。 具体旋转过程： 将根节点4复制出一个新的节点，其左子节点为3放弃不变，将其右子节点指向5（即原根节点的右子节点的左子节点）。将原根节点的右子节点6的左子节点指向新节点4，其右子节点为7放弃不变，那么6便成了新的根节点。哈哈，是不是有点绕，其实也能够简略了解为：既然右子树比左子树高，那么将树根4向左下移，将树根的右子节点6向上移，成为新的树根，这样便使左右子树的高度均衡了。联合上图，重复练习几次吧。 4. 右旋转右旋转与左旋转正好是对称的，看下图中右边的树，该二叉查找树的左子树高度为3，而右子树高度为1，不满足AVL树的旋转。 因其左子树高于右子树，并且最高的叶子节点在右边，所以咱们应用右旋转。 具体旋转过程： 将根节点7复制出一个新的节点，其右子节点为9放弃不变，左子节点指向5（即原根节点的左子节点的右子节点）。将原根节点的左节点降级为新的根节点，即其左子树为3放弃不变，右子节点指向新的根节点7。左旋转与右旋转肯定要了解，不然上面的双旋转就更容易晕菜了！ 5. 双旋转在介绍双旋转之前，先来看下图，其根节点的左子树高度为3，右子树高度为9，那么咱们先应用右旋转的形式，看能不能达均衡的成果。 通过观察右旋转后的成果，是不满足AVL树的个性的。这便须要应用双旋转了。 咱们应用左-右旋转来均衡上图中的树，即先进行左旋转，再进行右旋转，但其平衡点不同，如下图所示。 具体旋转过程： 先将根节点的左子树（5节点）进行左旋转，升高其（5节点）右子树的高度。再将根节点进行右旋转，便达到了均衡成果。那么反过来，右-左双旋转的具体过程： 先将根节点的右子树进行右旋转，升高其右子树的高度。再将根节点进行左旋转。6. 代码实现AVL树的实现是在二叉查找树的根底上增加了均衡操作。 6.1 求节点高度在Node类中增加节点高度办法height、leftHeight和rightHeight，若节点为空则高度为0。 // 以后节点高度public int height() { return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;}// 左子节点高度public int leftHeight() { if (left == null) { return 0; } return left.height();}// 右子节点高度public int rightHeight() { if (right == null) { return 0; } return right.height();}6.2 左旋转在Node类中减少左旋转办法leftRotate。 ...

GitHub源码分享我的项目主页：https://github.com/gozhuyinglong/blog-demos本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures1. 二叉查找树（Binary Search Tree）二叉查找树又叫二叉排序树（Binary Sort Tree），或叫二叉搜寻树，简称BST。BST是一种节点值之间有秩序的二叉树。其个性是： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；任意节点的左、右子树也别离为二叉查找树； 二叉查找树相比于其余数据结构的劣势在于查找、插入的工夫复杂度较低，为$O(logN)$。用大$O$符号示意的工夫复杂度： 算法均匀最差空间$O(N)$$O(N)$搜寻$O(logN)$$O(N)$插入$O(logN)$$O(N)$删除$O(logN)$$O(N)$2. BST的实现二叉查找树要求所有的节点元素都可能排序，所以咱们的Node节点类须要实现Comparable接口，树中的两个元素能够应用compareTo办法进行比拟。咱们节点中元素的类型为int型，所以该接口泛型为Comparable<Integer>，上面是具体实现： 2.1 节点类element 为数据元素left 为左子节点right 为右子节点class Node implements Comparable<Integer> { private final int element; // 数据元素 private Node left; // 左子树 private Node right; // 右子树 private Node(Integer element) { this.element = element; } @Override public int compareTo(Integer o) { return o.compareTo(element); }}2.2 二叉查找树类root 为树根，所有的操作均始于此前面会在该类中减少其余办法，如增加、查找、删除等 class BinarySearchTree { private Node root; // 树根}3. 插入节点向二叉查找树中插入的节点总是叶子节点，插入过程如下： 若root为空，则将插入节点设为root以后元素与插入元素通过compareTo进行比拟，若插入元素值小，并且左子节点left为空，则插入至以后节点左子节点；否则持续递归若插入元素值大，且右子节点right为空，则插入至以后节点右子节点；否则持续递归。若插入元素等于以后节点元素，则插入失败。注：也能够将其插入到右子节点，我这里为了不便间接放弃插入。具体实现：在BinarySearchTree类中增加两个办法： public boolean add(int element) 为公开办法private boolean add(Node node, int element)为公有办法，外部递归应用 // 增加元素 public boolean add(int element) { if (root == null) { root = new Node(element); return true; } return add(root, element); } // 增加元素（递归） private boolean add(Node node, int element) { if (node.compareTo(element) < 0) { if (node.left == null) { node.left = new Node(element); return true; } else { return add(node.left, element); } } else if (node.compareTo(element) > 0) { if (node.right == null) { node.right = new Node(element); return true; } else { return add(node.right, element); } } else { return false; } }4. 查找节点通过二叉查找树查找元素，其过程如下： ...

GitHub源码分享我的项目主页：https://github.com/gozhuyinglong/blog-demos本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures1. 前言咱们后面讲到了数组和链表两种数据结构，其各自有本人的优缺点，咱们来回顾一下。 数组（Array）长处：通过下标访问速度十分快。毛病：须要检索具体某个值时，或者插入值时（会整体挪动）效率较低 链表（Linked List）长处：在插入某个值时，效率比数组高 毛病：检索某个值时效率依然较低 咱们本篇讲到的树，便能进步数据的存储和读取效率。 2. 树（Tree）树是一种非线性的数据结构，它蕴含n(n>=1)个节点，(n-1)条边的有穷汇合。把它叫做“树”是因为它看起来像一个倒挂的树，也就是说它是根朝上，叶子朝下的。 3. 树结构的特点树结构的每个元素称为节点（node）每个节点都有零个或多个子节点没有父节点的节点叫做根节点（root）每一个非根结点有且只有一个父结点除了根结点外，每个子结点能够分为多个不相交的子树父子节点由一条有向的边（edgeo）相连结。 4. 树的罕用术语联合上图理解树的罕用术语，加深对树的了解。 节点（node）树结构中的每一个元素称为一个节点，如上图中的ABC......M 根节点（root）没有父节点的节点叫做根节点，如上图中的A 父节点（parent）一个节点的下级节点叫做它的父节点，一个节点最多只能有一个父节点，如上图中C是F的父节点 子节点（child）一个节点的上级节点叫做它的子节点，一个节点的子节点能够有多个，如上图中的IJK是E的子节点 兄弟节点（siblings）领有雷同父节点的节点叫做兄弟节点，如上图中的L和M是兄弟节点 叶子节点（leaf）没有子节点的节点叫做叶子节点，如图中的BFGLMIJK 边（dege）父子节点间的连贯称为边，一棵树的边数为(n-1) 节点的权（weight）节点上的元素值 门路（path）从root节点找到该节点的路线，如上图中L的门路为A-D-H-L。门路的长为该门路上边的条数，L门路的长为3（n-1）。 层（layer）间隔根节点相等的门路长度为一层，如上图中A为第一层；BCDE为第二层；FGHIJK为第三层；LM为第四层 子树（child tree）以某一节点（非root）做为根的树称为子树，如以E为根的树称为A的子树 树的高度（height）树的最大层数，上图中树的高度为4 森林（words）多棵子树形成树林 5. 代码实现咱们将第3章中的树结构图通过Java代码进行实现。 TreeNode类为树的一个节点，其中： element：存储以后节点的元素数据firstChild：指向以后节点的第一个子节点（如：A的firstChild为B；D的firstChild为G；G的firstChild为空）nextSibling：指向以后节点的下一个兄弟节点（如：B的nextSibling为C；G的nextSibling为H；H的nextSibling为空）Tree类实现了一棵树的初始化和遍历，listAll遍历算法的外围是递归。具体内容见代码 public class TreeDemo { public static void main(String[] args) { new Tree().initTree().listAll(); } private static class Tree { private TreeNode root; // 树根 /** * 初始化一棵树 */ private Tree initTree() { TreeNode a = new TreeNode("A"); TreeNode b = new TreeNode("B"); TreeNode c = new TreeNode("C"); TreeNode d = new TreeNode("D"); TreeNode e = new TreeNode("E"); TreeNode f = new TreeNode("F"); TreeNode g = new TreeNode("G"); TreeNode h = new TreeNode("H"); TreeNode i = new TreeNode("I"); TreeNode j = new TreeNode("J"); TreeNode k = new TreeNode("K"); TreeNode l = new TreeNode("L"); TreeNode m = new TreeNode("M"); root = a; a.firstChild = b; b.nextSibling = c; c.nextSibling = d; c.firstChild = f; d.nextSibling = e; d.firstChild = g; e.firstChild = i; g.nextSibling = h; h.firstChild = l; i.nextSibling = j; j.nextSibling = k; l.nextSibling = m; return this; } /** * 遍历一棵树，从root开始 */ public void listAll() { listAll(root, 0); } /** * 遍历一棵树 * * @param node 树节点 * @param depth 层级（用于辅助输入） */ public void listAll(TreeNode node, int depth) { StringBuilder t = new StringBuilder(); for (int i = 0; i < depth; i++) { t.append("\t"); } System.out.printf("%s%s\n", t.toString(), node.element); // 先遍历子节点，子节点的层级须要+1 if (node.firstChild != null) { listAll(node.firstChild, depth + 1); } // 后遍历兄弟节点，兄弟节点的层级不变 if (node.nextSibling != null) { listAll(node.nextSibling, depth); } } } private static class TreeNode { private final Object element; // 以后节点数据 private TreeNode firstChild; // 以后节点的第一个子节点 private TreeNode nextSibling; // 以后节点的下一个兄弟节点 public TreeNode(Object element) { this.element = element; } }}输入后果： ...

GitHub源码分享我的项目主页：https://github.com/gozhuyinglong/blog-demos本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures1. 队列（queue）队列和栈一样，也是一个操作受限制的线性表。不同的是队列的插入在一端进行，咱们称为队尾（rear）；而删除（取出）在另一端进行，咱们称为队头（front）。 队列是一个先进先出（FIFO - First In First Out）的有序列表，其操作只有两种： 入队（enqueue）：向队尾增加一个元素出队（dequeue）：从队头删除（取出）一个元素 2. 队列的数组实现如同栈一样，对队列的每一种操作，链表实现或数组实现都给出疾速的运行工夫。队列的链表实现是简略而间接的，咱们就不过介绍了。上面咱们探讨如何应用数组实现一个队列。 先看下图，咱们须要申明一个数组，并保护两个指针： head指针：指向待入列的元素地位tail指针：指向待入列的存储地位能够看出，达到队尾后无奈再增加新的元素，而后后面已入列的地位还空着。 下面问题咱们能够将数组进行首尾相连，造成一个环形数组，即指针达到数组尾部后，从新指向数组头部，如下图所示。 这里须要留神几点： 判断空队列能够通过head == tail判断队列满不能再通过head与tail重合，而是须要空出一个存储空间来，即：head == tail + 1。而环形数组须要取模运算，所以正确判断队列满：head == (tail + 1) % capacity。数组实在容量应为：指定容量 + 13. 代码实现上面代码是应用环形数组实现的队列，所以又叫做环形队列。其容量为：指定容量 + 1，head 与t ail 初始值为0。队列存储元素应用了泛型，所以能够操作你想用的数据类型。上面看具体实现： public class ArrayQueueDemo { public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(5); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("入队：1 --> " + queue.add(1)); System.out.println("入队：2 --> " + queue.add(2)); System.out.println("入队：3 --> " + queue.add(3)); System.out.println("入队：4 --> " + queue.add(4)); System.out.println("入队：5 --> " + queue.add(5)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("入队：6 --> " + queue.add(6)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：7 --> " + queue.add(7)); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：8 --> " + queue.add(8)); System.out.println("入队：9 --> " + queue.add(9)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：10 --> " + queue.add(10)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); } private static class ArrayQueue<T> { private final T[] queue; // 存储队列数据元素 private final int capacity; // 容量 private int head = 0; // 头部指针，指向队头元素 private int tail = 0; // 尾部指针，指向下一个待入队元素的存储地位 public ArrayQueue(int capacity) { this.capacity = capacity + 1; // 环形队列须要空出一个地位，来满足队列满时head与tail不重合 this.queue = (T[]) new Object[this.capacity]; } /** * 向队列增加一个元素 * * @param data * @return */ public boolean add(T data) { // 队列满，增加失败 if (isFull()) { return false; } // tail指向下一个待入队元素的存储地位，所以先赋值再让指针加1 queue[tail] = data; // 环形数组须要取模运算 tail = (tail + 1) % capacity; return true; } /** * 从队列中获取一个元素 * * @return */ public T get() { if (isEmpty()) { return null; } // head指向头元素地位，所以先取出再让指针加1 T data = queue[head]; // 环形数组须要取模运算 head = (head + 1) % capacity; return data; } /** * 以后队列大小 * * @return */ public int size() { int size = tail - head; if (size < 0) { size += capacity; } return size; } /** * 队列是否为空：当tail与head指向同一地位时，示意队列为空 * * @return */ public boolean isEmpty() { return tail == head; } /** * 队列是否已满：因为预留了一个地位，所以tail须要加1；环形队列须要取模运算 * * @return */ public boolean isFull() { return head == (tail + 1) % capacity; } }}输入后果： ...

GitHub源码分享我的项目主页：https://github.com/gozhuyinglong/blog-demos本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures1. 栈（Stack）栈又叫堆栈，是一种运算受限制的线性表，限定只能在一端进行插入和删除操作，该端称为栈顶（Top），绝对的另一端叫栈底（Bottom）。 依据栈的定义可知，最先进入栈的元素在栈底，最初进入栈的元素在栈顶。而删除元素刚好相同，即删除程序从栈顶到栈底 对栈的操作只有两种： 入栈（push）：又叫进栈或压栈，即向栈插入一条新的元素，该元素为新的栈顶元素。出栈（pop）：又叫退栈，即从栈顶删除（取出）最初入栈的元素，而其相邻元素成为新的栈顶元素。 栈是一个先进后出（FILO - First In Last Out）的有序列表。在上图中形容了栈的模型，咱们对栈的操作只有push和pop，栈顶元素是该栈惟一可见的元素。 2. 代码实现因为栈是一个表，因而任何实现表的办法都能实现栈。显然咱们之前用到的《 数组 》和《 链表 》都能够实现栈。上面代码是应用数组实现的一个栈。 size示意栈内元素的大小，栈顶元素为 elementData[size - 1]，栈底元素为 elementData[0]。入栈时执行 size++，出站时执行 size-- public class StackDemo { public static void main(String[] args) { System.out.println("-------------------入站"); Stack<String> stack = new Stack<>(10); stack.push("a"); stack.push("b"); stack.push("c"); stack.push("d"); stack.push("e"); stack.print(); System.out.println("元素大小: " + stack.size()); System.out.println("栈容量: " + stack.capacity()); System.out.println("-------------------出站"); System.out.println("出站元素: " + stack.pop()); System.out.println("出站元素: " + stack.pop()); stack.print(); System.out.println("元素大小: " + stack.size()); System.out.println("栈容量: " + stack.capacity()); } private static class Stack<E> { private int size; // 元素大小 private final int capacity; // 栈的容量 transient Object[] elementData; // 元素数据 public Stack(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("Illegal Capacity: " + capacity); } else { this.capacity = capacity; elementData = new Object[capacity]; } } /** * 获取栈的元素大小 * * @return */ public int size() { return size; } /** * 获取栈的容量 * * @return */ public int capacity() { return capacity; } /** * 入栈 * * @param e * @return */ public boolean push(E e) { if (size >= capacity) { return false; } elementData[size++] = e; return true; } /** * 出栈 * * @return */ public E pop() { if (size <= 0) { return null; } return (E) elementData[--size]; } /** * 打印元素数据 */ public void print() { System.out.print("站内元素: "); for (int i = 0; i < size; i++) { System.out.printf("%s\t", elementData[i]); } System.out.println(); } }}输入后果： ...

GitHub源码分享我的项目主页：https://github.com/gozhuyinglong/blog-demos本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/linkedlist1. 前言通过前篇文章《数组》理解到数组的存储构造是一块间断的内存，插入和删除元素时其每个局部都有可能整体挪动。为了防止这样的线性开销，咱们须要保证数据能够不间断存储。本篇介绍另一种数据结构：链表。 2. 链表（Linked List）链表是一种线性的数据结构，其物理存储构造是零散的，数据元素通过指针实现链表的逻辑程序。链表由一系列结点（链表中每一个元素称为节点）组成，节点能够在内存中动静生成。 链表的个性： 链表是以节点（Node）的形式来存储，所以又叫链式存储。节点能够间断存储，也能够不间断存储。节点的逻辑程序与物理程序能够不统一表能够裁减（不像数组那样还得重新分配内存空间）链表分为单链表、双链表和环形链表，上面通过实例一一介绍。 3. 单链表（Singly Linked List）单链表又叫单向链表，其节点由两局部形成： data域：数据域，用来存储元素数据next域：用于指向下一节点单链表的构造如下图： 3.1 单链表的操作单链表的所有操作都是从head开始，head自身不存储元素，其next指向第一个节点，而后顺着next链进行一步步操作。其尾部节点的next指向为空，这也是判断尾部节点的根据。 这里次要介绍插入和删除节点的操作。 3.1.1 插入节点向单链表中插入一个新节点，能够通过调整两次next指向来实现。如下图所示，X为新节点，将其next指向为A2，再将A1的next指向为X即可。 若是从尾部节点插入，间接将尾部节点的next指向新节点即可。 3.1.2 删除节点从单链表中删除一个节点，能够通过批改next指向来实现，如下图所示，将A1的next指向为A3，这样便删除A2，A2的内存空间会主动被垃圾回收。 若是删除尾部节点，间接将上一节点的next指向为空即可。 3.2 代码实现咱们应用Java代码来实现一个单链表。其中Node类存储单链表的一个节点，SinglyLinkedList类实现了单链表的所有操作方法。SinglyLinkedList类应用带头节点的形式实现，即head节点，该节点不存储数据，只是标记单链表的开始。 public class SinglyLinkedListDemo { public static void main(String[] args) { Node node1 = new Node(1, "张三"); Node node2 = new Node(3, "李四"); Node node3 = new Node(7, "王五"); Node node4 = new Node(5, "赵六"); SinglyLinkedList singlyLinkedList = new SinglyLinkedList(); System.out.println("-----------增加节点（尾部）"); singlyLinkedList.add(node1); singlyLinkedList.add(node2); singlyLinkedList.add(node3); singlyLinkedList.add(node4); singlyLinkedList.print(); System.out.println("-----------获取某个节点"); Node node = singlyLinkedList.get(3); System.out.println(node); singlyLinkedList.remove(node3); System.out.println("-----------移除节点"); singlyLinkedList.print(); System.out.println("-----------批改节点"); singlyLinkedList.update(new Node(5, "赵六2")); singlyLinkedList.print(); System.out.println("-----------按程序增加节点"); Node node5 = new Node(4, "王朝"); singlyLinkedList.addOfOrder(node5); singlyLinkedList.print(); } private static class SinglyLinkedList { // head节点是单链表的开始，不用来存储数据 private Node head = new Node(0, null); /** * 将节点增加到尾部 * * @param node */ public void add(Node node) { Node temp = head; while (true) { if (temp.next == null) { temp.next = node; break; } temp = temp.next; } } /** * 按程序增加节点 * * @param node */ public void addOfOrder(Node node) { Node temp = head; while (true) { if (temp.next == null) { temp.next = node; break; } else if(temp.next.key > node.getKey()){ node.next = temp.next; temp.next = node; break; } temp = temp.next; } } /** * 获取某个节点 * * @param key * @return */ public Node get(int key) { if (head.next == null) { return null; } Node temp = head.next; while (temp != null) { if (temp.key == key) { return temp; } temp = temp.next; } return null; } /** * 移除一个节点 * * @param node */ public void remove(Node node) { Node temp = head; while (true) { if (temp.next == null) { break; } if (temp.next.key == node.key) { temp.next = temp.next.next; break; } temp = temp.next; } } /** * 批改一个节点 * * @param node */ public void update(Node node) { Node temp = head.next; while (true) { if (temp == null) { break; } if (temp.key == node.key) { temp.value = node.value; break; } temp = temp.next; } } /** * 打印链表 */ public void print() { Node temp = head.next; while (temp != null) { System.out.println(temp.toString()); temp = temp.next; } } } private static class Node { private final int key; private String value; private Node next; public Node(int key, String value) { this.key = key; this.value = value; } public int getKey() { return key; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } public Node getNext() { return next; } @Override public String toString() { return "Node{" + "key=" + key + ", value='" + value + '\'' + '}'; } }}输入后果： ...

C语言实现AVL均衡二叉树 1构造体//这里定义一个取较大值的MAX宏#define MAX(a,b) ((a)>(b)?(a):(b))typedef struct AVLTreeNode { int data; //数据域 int height; //数据域 struct AVLTreeNode *left; //左子结点 struct AVLTreeNode *right; //右子结点} AVLTreeNode;2.1右单旋/** * 右单旋 * 8 4 * 4 12 2 8 * 2 6 => 1 6 12 * 1 */AVLTreeNode *right_rotation(AVLTreeNode *root){ struct AVLTreeNode *new_root; new_root = root->left; root->left = new_root->right; new_root->right = root; //旋转完从新计算高度 root->height = MAX(Height(root->left) + 1, Height(root->right)); new_root->height = MAX(Height(new_root->left) + 1, Height(new_root->right)); return new_root;}2.2左单旋/** * 左单旋 * 8 12 * 4 12 8 50 * 9 50 => 4 9 70 * 70 */AVLTreeNode *left_rotation(AVLTreeNode *root){ struct AVLTreeNode *new_root; new_root = root->right; root->right = new_root->left; new_root->left = root; //旋转完从新计算高度 root->height = MAX(Height(root->right) + 1, Height(root->left)); new_root->height = MAX(Height(new_root->right) + 1, Height(new_root->left)); return new_root;}2.3左右旋/** * 左右旋 先对root->left左旋 再对root右旋 * 8 8 6 * 4 12 6 12 4 8 * 2 6 => 4 => 2 5 12 * 5 2 5 */AVLTreeNode *left_right_rotation(AVLTreeNode *root){ root->left = left_rotation(root->left); return right_rotation(root);}2.3右左旋/** * 右左旋 先对root->right右旋 再对root左旋 * 8 8 10 * 4 12 4 10 8 12 * 10 14 => 9 12 => 4 9 14 * 9 14 */AVLTreeNode *right_left_rotation(AVLTreeNode *root){ root->right = right_rotation(root->right); return left_rotation(root);}3 自均衡AVLTreeNode *rebalance(AVLTreeNode *root, int data){ if (Height(root->right) - Height(root->left) == 2) { if (data > root->right->data)//左单旋的状况 { printf("left_rotation \n"); root = left_rotation(root); }else{ printf("right_left_rotation \n");//右左旋的状况 root = right_left_rotation(root); } } if (Height(root->left) - Height(root->right) == 2) { if (data < root->left->data)//右单旋的状况 { printf("right_rotation \n"); root = right_rotation(root); }else{ printf("left_right_rotation \n");//左右旋的状况 root = left_right_rotation(root); } } return root;}4 插入AVLTreeNode *insert(AVLTreeNode *root, int data){ if (NULL == root) { struct AVLTreeNode *node; node = (struct AVLTreeNode *)malloc(sizeof(struct AVLTreeNode)); if (node == NULL) { printf("malloc error \n"); return NULL; } node->data = data; node->right = NULL; node->left = NULL; return node; } if (data >= root->data) { root->right = insert(root->right, data); root->height = MAX(Height(root->left), Height(root->right) + 1);//相比于二叉搜寻树多了高度判断 }else{ root->left = insert(root->left, data); root->height = MAX(Height(root->left) + 1, Height(root->right)); } root = rebalance(root, data); return root;}5.1 查找最大/小节点AVLTreeNode *FindMin(AVLTreeNode *root){ if (NULL == root) { return NULL; } if (root->left == NULL) { return root; }else{ return FindMin(root->left); }}AVLTreeNode *FindMax(AVLTreeNode *root){ if (NULL == root) { return NULL; } if (root->right == NULL) { return root; }else{ return FindMax(root->right); }}5.2删除AVLTreeNode *Delete(AVLTreeNode *root, int target){ if (NULL == root) { return NULL; } if (target > root->data) { root->right = Delete(root->right, target); if (Height(root->left) - Height(root->right) == 2) { AVLTreeNode *l = root->left; if (Height(l->right) > Height(l->left)) root = left_right_rotation(root); else root = left_rotation(root); } }else if(target < root->data){ root->left = Delete(root->left, target); if (Height(root->right) - Height(root->left) == 2) { AVLTreeNode *r = root->right; if (Height(r->left) > Height(r->right)) root = left_right_rotation(root); else root = right_rotation(root); } }else{ //相等的状况 if (root->left && root->right) { if (Height(root->left) > Height(root->right)) { //左子树比右子树高 AVLTreeNode *max = FindMax(root->left); root->data = max->data; root->left = Delete(root->left, max->data); }else{ AVLTreeNode *min = FindMin(root->right); root->data = min->data; root->right = Delete(root->right, min->data); } }else{ struct AVLTreeNode *tmp; tmp = root; if (root->left == NULL) { root = root->right; }else if(root->right == NULL){ root = root->left; }else{ root = NULL;//删除本身 } } } return root;}测试： ...

我是少侠露飞。学习塑造人生，技术扭转世界。开场白疾速排序号称最优雅的算法之一，在开发中可能用得不算多，然而在一些场景下还是很杰出的。最要害的是，各大厂面试官都爱问啊，你说要不要好好把握吧。而后就是网上很多快排的代码和解说，少侠发现很多人本人压根都没搞清楚，代码的边界不清，扔进去一执行就报数组越界异样；要么就是一些人模仿的快排过程都是错的，这让真心想学习的人不免心累。所以少侠决定写一篇记录之，解说未必是最好的，但代码肯定是正确的。 原理及排序过程原理合成：快排的外围就是首先选定一个主元pivot，而后将原数组分解成两个子数组A和B，保障A中的后果小于等于pivot，B中的后果都大于等于pivot。解决：而后针对两个子数组A和B再递归的调用，依照上步合成的逻辑进行。合并：咱们晓得，归并排序最初是须要合并子数组的。但在这里，好消息是快排是旧址排序，不须要合并。 排序过程原理不难理解，然而初学者对这个过程可能还是比拟含糊。这里少侠就抉择一个数组，依照快排的过程一步一步展现给大家。这里咱们抉择初始化数组[6,2,3,9,5,8]。首先抉择主元，怎么选呢，能够抉择某一索引地位的值，也能够抉择多个索引，而后取中位数的值作为主元。这里咱们固定抉择第一个元素为主元。 第一次合成的时候pivot=6，合成的指标就是把所有大于等于6的元素挪动左边，小于等于6的元素移到右边。而后左指针i从起始地位开始，右指针j从结尾开始，循环的边界就是i<j。初始地位如下图： 每次从左边的指针断定。当右指针的值大于pivot时，右指针左移一位，直到遇到小于等于pivot的值。如下图： 当右指针的值小于pivot时，将以后值赋值给指针i对应的地位，同时i向右挪动一位，如下图： 当产生上步的状况（即右指针因小于pivot而产生值的笼罩时候），须要进入该逻辑：就是开始判断左指针的元素值，如果小于pivot，就向右挪动一位，直到遇到大于等于pivot的元素。 此时i挪动到元素值为9的地位，也就是大于pivot，此时须要将此地位的值赋值给j地位并使得指针j左移一位，即： 留神看，此时i=j，左右指针重合，曾经不满足循环边界条件(i<j)了，退出循环。然而此时i地位的值才是pivot应该在的地位，所以执行赋值操作将pivot赋值给nums[i]=pivot;失去本次合成的最终后果： 最初再对主元pivot两侧的数组{5,2,3}和{9,8}递归的调用上述过程，失去最终排序后果。残缺实现代码（Java） public void quickSort(int[] nums) { if (nums == null || nums.length <= 1) { return; } quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int left, int right) { // 左右指针没有相遇前比拟各数据与基元的大小 if (left < right) { // 抉择主元值 int pivot = nums[left]; // 标记左右指针 int i = left, j = right; // 一趟排序，找到比主元大的数据放在基元右侧，比主元小的值放在基元左侧 while (i < j) { // 从右往左扫描，以后值大于主元时跳过，右指针左移一位 while (i < j && nums[j] > pivot) { j--; } // 当走到这里时，意味着以后值左指针和右指针相遇，阐明本趟排序完结 // 也可能是以后数据小于等于主元，此时须要将以后数据赋值给左指针对应的值，并将左指针右移一位 if (i < j) { nums[i++] = nums[j]; } // 从左往右扫描，以后值小于主元时跳过，左指针右移一位 while (i < j && nums[i] < pivot) { i++; } // 当走到这里时，意味着以后值左指针和右指针相遇，阐明本趟排序完结 // 也可能是以后数据大于等于主元，此时须要将以后数据赋值给右指针对应的值，并将右指针左移一位 if (i < j) { nums[j--] = nums[i]; } } // 此时索引i的地位应该就是主元值 nums[i] = pivot; // 左侧依照雷同思路递归 quickSort(nums, left, i - 1); // 右侧依照雷同思路递归 quickSort(nums, i + 1, right); } }小结本篇参考书籍《算法导论》。下期还会写篇对于堆排序的博客，敬请期待，也欢送点赞、关注。咱们下期再见。 ...

对数器作用你想要测的办法a实现复杂度不好然而容易实现的办法b实现一个随机样本产生器把办法a和办法b跑雷同的随机样本，看看失去的后果是否一样如果有一个随机样本使得比对后果不统一，打印样本进行人工干预，改对办法a和办法b当样本数量很多时比对测试仍然正确，能够确定办法a曾经正确。对数器的实现// for testpublic static void comparator(int[] arr) { Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) { // Math.random() -> [0,1) 所有的小数，等概率返回一个 // Math.random() * N -> [0,N) 所有小数，等概率返回一个 // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个 int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机 for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr;}// for testpublic static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true;}// for testpublic static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println();}// for testpublic static void main(String[] args) { int testTime = 500000; int maxSize = 100; // 随机数组的长度0～100 int maxValue = 100;// 值：-100～100 boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { // 打印arr1 // 打印arr2 succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr);}

程序表经典面试题1、反转数组实现计划一 引入一个内部数组变量，用于保留反序之后的数组，而后把原数组中的元素倒序保留于新创建的数组中，新建数组保留的元素就是反转之后的后果 public static void main(String[] args) { int[] arr = {11,22,33,44,55,66,77}; int[] newArr = new int[arr.length]; for (int i = 0; i < arr.length; i++) { newArr[i] = arr[arr.length - 1 - i]; } System.out.println(Arrays.toString(newArr));}实现计划二 间接对数组中的元素进行首尾替换。这样防止了新建一个数组来保留反转之后的后果，并且循环遍历的次数也降为计划一的一半，进步了算法的效率 public static void main(String[] args) { int[] arr = {11,22,33,44,55,66,77};// int[] newArr = new int[arr.length]; for (int i = 0; i < arr.length / 2; i++) {// newArr[i] = arr[arr.length - 1 - i]; int temp = arr[i]; arr[i] = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = temp; } System.out.println(Arrays.toString(arr)); }2、找数组中反复的元素题目形容 ...

二叉树遍历中序递归遍历：左子树，根，右子树 private void inOrderTraverse(Node node) { if (node != null) { //遍历左子树 this.inOrderTraverse(node.leftChild); //输入根的值 System.out.print(node.value + " "); //遍历右子树 this.inOrderTraverse(node.rightChild); } }树的高度 private int getHeight(Node node) { if (node == null) { return 0; } else { //获取左子树高度 int lh = this.getHeight(node.leftChild); //获取右子树高度 int rh = this.getHeight(node.rightChild); //返回 return lh > rh ? lh + 1 : rh + 1; } }树的结点数量 private int size(Node node) { if (node == null) { return 0; } else { int lsize = this.size(node.leftChild); int rsize = this.size(node.rightChild); return lsize + rsize + 1; } }树档次遍历：借助队列public void levelOrderByStack() { if (root == null) return; Queue<Node> queue = new LinkedList<Node>(); queue.add(root); while (queue.size() != 0){ for (int i = 0; i < queue.size(); i++) { //取出以后队列中的结点 Node temp = queue.poll(); //打印一下结点的值 System.out.print(temp.value+"--"); //把该结点的左子树加到队列中 if (temp.leftChild != null) queue.add(temp.leftChild); //把右子树加到队列中 if (temp.rightChild != null) queue.add(temp.rightChild); } } }中序遍历 非递归public void inOrderByStack() { Deque<Node> stack = new LinkedList<>(); Node current = root; while (current != null || !stack.isEmpty()){ while (current != null){ stack.push(current); current = current.leftChild; } if(!stack.isEmpty()){ current = stack.pop(); System.out.println(current.value+" "); current = current.rightChild; } } }

树和二叉树基本概念树是由一个汇合以及在该汇合上定义的一种关系形成的汇合中的元素称为树的结点，所定义的关系称为父子关系父子关系在树的结点之间建设了一个层次结构树的结点蕴含一个数据元素和指向其子树的若干分支根结点具备非凡位置，简称为根 树（tree）是n（n>=0）个结点的无限集 或者是一个空树（n=0），空树中不蕴含任何结点或者是一棵非空树（n>0），此时有且仅有一个称为根的特定的结点结点的度与树的度结点领有的子树的数目称为结点的度（Degree）度为0的结点称为叶子（leaf）结点或终端结点度不为0的结点称为非终端结点或分支结点。除根之外的分支结点也称为外部结点树内各结点的度的最大值称为树的度 结点的档次和树的深度结点的档次（level）从根开始定义，根结点档次为1，其子树档次为2树中的最大档次数称为数的深度（Depth）或高度 父亲、儿子、兄弟父亲（parent）：一个结点的间接前驱结点儿子（child）：一个结点的间接后继结点兄弟（sibling）：同一个父亲结点的其余结点先人、子孙、堂兄弟先人：从根到该结点的门路上的所有结点子孙：以某结点为根的树中的任一结点都是该结点的子孙堂兄弟：父亲结点在同一档次的结点有序树、m叉树、森林有序树：树中结点的各子树从左至右看成有程序的（若不特指阐明，个别探讨的都是有序树）无序树：不思考子树的程序m叉树：树中所有结点的最大度为m的有序树森林：m（m>=0）棵互不相交的树的汇合二叉树每个结点的度均不超过2的有序树，称为二叉树（binary tree）二叉树或者是一棵空树，或者是由一个根结点和两个互不相交的左子树和右子树组成的非空树 满二叉树高度为k并且有$2^k+1$ 个结点的二叉树满二叉树中每层都达到最大数，即每层结点都是满的齐全二叉树在一棵满二叉树中，从最上层最右侧起，去掉相邻的若干叶子节点，失去的即为齐全二叉树满二叉树肯定是齐全二叉树，而齐全二叉树不肯定是满二叉树 二叉树的性质在二叉树的第i层上，最多有$2^(n-1)$个结点（根是第1层）高度为h的二叉数至少有$2^h$-1个结点对于任意一棵二叉树，叶子节点数 = 度为2的结点数 + 1有n个结点的齐全二叉树的高度为$log_2^n$+1，其中$log_2^n$是向下取整含有n>=1个结点的二叉树高度至少为n-1；高度至多为$log_2^n$+1，其中$log_2^n$是向下取整如果对一棵含有n个结点的齐全二叉树的结点进行编号，则对任意结点i 如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点为i/2向下取整如果2i>n,则结点i无左孩子；否则其左孩子为2i如果2i+1>n，则结点i无右孩子；否则其右孩子为2i+1二叉树的存储构造二叉树的存储构造有两种：顺序存储构造和链式存储构造 顺序存储构造对于满二叉树和齐全二叉树来说，能够将其存储在一组间断的存储单元中用一维数组来实现顺序存储构造时，将二叉树第i个结点寄存到数组中第i个重量中依据二叉树的性质，能够失去结点i的父结点、左右孩子结点别离寄存在i/2、2i、2i+1重量中这种存储形式对于满二叉树和齐全二叉树是十分适合并且高效不便的，因为满二叉树和齐全二叉树采纳顺序存储构造即不节约空间，也能依据公式很快确定结点之间的关系然而对于个别的二叉树而言，必须用“虚结点”将一棵二叉树补成一棵齐全二叉树来存储，否则无奈确定结点之间的前驱后继关系，然而这样就会造成空间的节约链式存储构造设计不同的节点构造可形成不同的链式存储构造在二叉树中，每个结点都有两个孩子，则能够设计成每个结点至多蕴含3个域：数据域、左孩子域、右孩子域利用此构造失去的二叉树存储构造称为二叉链表。数据域存放数据元素，左孩子域寄存指向左孩子结点的指针，右孩子域寄存指向右孩子的指针为了不便找到父结点，能够在上述结点构造中增加一个指针域，指向结点的父结点，采纳此构造失去的存储构造称为三叉链表

栈和队列栈和队列是操作受到限制的线性表 栈的定义栈（stack）又称堆栈，它是运算受限的线性表只能在表的一端进行插入和删除操作， 不容许在其余任何地位进行插入、查找、删除等操作表中进行插入和删除操作的一端称为栈顶（top），另一端称为栈底（bottom）当栈中没有数据元素时称为空栈向一个栈中插入元素称为入栈从一个栈中删除元素称为出栈因为栈的插入和删除操作仅在栈顶进行，后进栈的元素必然先出栈，所以又把堆栈称为后进先出表（Last In First Out，简称LIFO）栈的业余词汇：push入栈、pop出栈、peek获取栈顶元素 栈的存储构造和线性表相似，堆栈也有两种根本的存储构造：顺序存储构造和链式存储构造 程序栈链栈队列定义队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表仅容许在表的一端进行插入，而在表的另一端进行删除在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）向队尾插入元素称为入队，新元素入队后称为新的队尾元素从队列中删除元素称为出队，元素出队后，其后续元素成为新的队首元素因为队列的插入和删除操作别离在队尾和队首进行，每个元素必然依照进入的秩序归队，也就是说先进队的元素必然先归队，所以称队列为先进先出表（First In First Out，FIFO）队列的存储构造程序队列 办法一：应用数组作为存储构造 毛病：通过出队操作将数据弹出队列后，front之前的空间不能再次失去，会导致大量空间失落办法二：应用循环数组作为存储构造 在循环数组中，开端元素的下一个元素不是数组外，而是数组的头元素，这样就能再次应用front之前的存储空间了链式队列 能够应用单链表实现（带头节点）链表的头部作为队首，链表的尾部作为队尾一共设置两个指针，一个队首指针和一个队尾指针队首指针指向队首元素的前一个结点，即始终指向链表中空的头结点；队尾指针指向队列以后队尾元素所在结点当队列为空时，队首指针和队尾指针都指向空的头结点双端队列（double ended queue） 双端队列指两端都能够进行出队和入队操作的队列，将队列的两端别离称为前端和后端双端队列进队时，前端进的元素排在队列中后端进的元素的后面，后端进的元素排在队列中前端进的元素的前面双端队列出队时，无论前端出还是后端出，先出的元素排在后出的元素的后面输入受限的双端队列，即一个端点能够插入和删除，另一个端点只能插入 输出受限的双端队列，即一个端点能够插入和删除，另一个端点只能删除 双端队列既能够用来实现队列，也能够用来实现栈（只操作一端就是栈了，Java中就是这样做的）Java中的栈和队列类Stack类：栈类，过期，因为他的父类Vector过期Queue类：队列类（接口）Deque类：双端队列（接口，栈操作应用，当成栈） LinkedList即能够当线性表，又能够当栈，还能够当队列Java中实现栈和队列操作都能够通过应用LinkedList类实现，底层应用的是链表借助栈实现十进制转换二进制public class TestConvert { public static void main(String[] args) { int t = 13; int n = t; //定义空栈，寄存余数 Deque deque = new LinkedList(); do { int mod = n % 2; //余数入栈 deque.push(mod); n = n / 2; }while (n != 0); //打印后果 System.out.print(t+"---->"); while (!deque.isEmpty()){ System.out.print(deque.pop()); } }} ...

单链表实现创立节点类 public class Node { /** * 为了便于了解 不应用private润饰 */ Object data;//存储数据的援用 Node next;//下一个节点的援用public Node() { } public Node(Object data, Node next) { this.data = data; this.next = next; } }创立链表类 public class SingleLinkedList implements List { private Node head = new Node();//头节点，不存储数据，为了编程不便 private int size;//一共有几个结点 }查找第i 个节点的值在单链表中进行查找操作只能从链表的首节点开始，通过每个节点的next 援用来顺次拜访链表中的每个节点，以实现相应的查找操作 public Object get(int i) {//如果i的地位谬误报异样 if (i<0 ||i >size){ throw new MyArrayIndexOutOfBoundsException("指针越界异样："+"i"); } //和程序表不一样了，不能通过索引间接定位，须要从头节点开始进行查找 //从头节点开始挪动指针 Node p = head; for (int j = 0; j <= i; j++) { p = p.next; } return p.data; }增加节点操作增加节点不须要挪动元素，只须要批改元素的指针须要先查找到增加地位i，再增加新节点 ...

模仿实现程序表ArrayList一、定义接口无论是程序表还是链表，它们都是线性表，都须要进行增删改查操作。所以首先，定义一个线性表接口List，蕴含线性表的操作 /** * 线性表接口 * 和存储构造无关（程序表，链表） */public interface List{ //返回线性表的大小，即元素的个数 public int size(); //返回线性表中序号为i 的数据元素 public Object get(int i); //如果线性表为空，返回true，否则返回false public boolean isEmpty(); //判断线性表中是否蕴含数据元素e public boolean contains(Object e); //返回数据元素e 在线性表中的序号 public int indexOf(Object e); //将数据元素e 插入到线性表中i 号地位 public void add(int i, Object e); //将数据元素e 插入到线性表开端 public void add(Object e); //将数据元素e 插入到元素obj 之前 public boolean addBefore(Object obj, Object e); //将数据元素e 插入到元素obj 之后 public boolean addAfter(Object obj, Object e); //删除线性表中序号为i 的元素，并返回之 public Object remove(int i); //删除线性表中第一个与e 雷同的元素 public boolean remove(Object e); //替换线性表中序号为i 的数据元素为e， 返回原数据元素 public Object replace(int i, Object e);}二、创立程序表类ArrayList并实现接口List1、程序表底层采纳的是数组，长度能够动态变化 private Object[] elementData; //底层是一个数组，目前还没有确定长度 private int size; //不是数组调配了几个空间，而是数组中元素的个数2、编写构造方法指定数组初始长度public ArrayList(int initalCapacity) { //给数组调配指定数量的空间 elementData = new Object[initalCapacity]; //指定程序表的元素个数，默认是0// size = 0; }public ArrayList() { //没有指定长度，默认长度是4 this(4); }以上代码写完，就能够创立程序表了，然而外面的操作方法还没有实现 ...

模仿实现程序表ArrayList一、定义接口无论是程序表还是链表，它们都是线性表，都须要进行增删改查操作。所以首先，定义一个线性表接口List，蕴含线性表的操作 /** * 线性表接口 * 和存储构造无关（程序表，链表） */public interface List{ //返回线性表的大小，即元素的个数 public int size(); //返回线性表中序号为i 的数据元素 public Object get(int i); //如果线性表为空，返回true，否则返回false public boolean isEmpty(); //判断线性表中是否蕴含数据元素e public boolean contains(Object e); //返回数据元素e 在线性表中的序号 public int indexOf(Object e); //将数据元素e 插入到线性表中i 号地位 public void add(int i, Object e); //将数据元素e 插入到线性表开端 public void add(Object e); //将数据元素e 插入到元素obj 之前 public boolean addBefore(Object obj, Object e); //将数据元素e 插入到元素obj 之后 public boolean addAfter(Object obj, Object e); //删除线性表中序号为i 的元素，并返回之 public Object remove(int i); //删除线性表中第一个与e 雷同的元素 public boolean remove(Object e); //替换线性表中序号为i 的数据元素为e， 返回原数据元素 public Object replace(int i, Object e);}二、创立程序表类ArrayList并实现接口List1、程序表底层采纳的是数组，长度能够动态变化 private Object[] elementData; //底层是一个数组，目前还没有确定长度 private int size; //不是数组调配了几个空间，而是数组中元素的个数2、编写构造方法指定数组初始长度public ArrayList(int initalCapacity) { //给数组调配指定数量的空间 elementData = new Object[initalCapacity]; //指定程序表的元素个数，默认是0// size = 0; }public ArrayList() { //没有指定长度，默认长度是4 this(4); }以上代码写完，就能够创立程序表了，然而外面的操作方法还没有实现 ...

1. 如何用链表实现栈2. 归并排序思维https://www.cnblogs.com/Yunru...https://segmentfault.com/a/11...

题干本题来自LeetCode Problem 50。其大意为给定 x （浮点数）和 n （整数），求 x 的 n 次幂。 解法暴力解法暴力解法……当然是直接拿 x 乘 n 次咯，注意如果 n 取负数的时候，要先对 x 求倒数，再乘以 -n 次。 class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1 if n < 0: return myPow(1 / x, -n) ans = 1 for i in range(n): ans *= x return ans但是很显然当 n 的绝对值很大的时候会有很恐怖的时间消耗，而且不必要。 快速幂算法递归实现由小学数学我们很容易得知，myPow(x, 2n) = myPow(x, n) * myPow(x, n)，因此我们对给定 n，只需计算其 n / 2 次幂，再将其相乘即可，注意如果 n 是奇数的话，例如 n = 5 时，先计算n // 2 = 2，向下取整，之后再计算myPow(x, 5) = myPow(x, 2) * myPow(x, 2) * x。这样就很容易地把时间复杂度降到了O(log n)级别。话不多说上代码： ...