写点什么

算法与数据结构

0 人感兴趣 · 48 次引用

  • 最新
  • 推荐
https://static001.geekbang.org/infoq/24/24e90ab4e8de38d2bb3f569f1d9acde1.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

搜索中常见数据结构与算法探究(二)

本文介绍了几个常见的匹配算法,通过算法过程和算法分析介绍了各个算法的优缺点和使用场景,并为后续的搜索文章做个铺垫;读者可以通过比较几种算法的差异,进一步了解匹配算法演进过程以及解决问题的场景;KMP算法和Double-Array TireTree是其中算法思想的集

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树 (中等)

要求从中序和后序遍历的结果来重新建原二叉树,中序遍历顺序是左 根 右,后序遍历顺序是左 右 根,对于这种树的重建一般采用递归来做,由于后序的顺序的最后一个肯定是根

【牛客刷题 - 算法】1- 算法入门 - 数据结构 - 栈

描述请你实现一个栈。操作:push x:将 加入栈,保证 为 int 型整数。pop:输出栈顶,并让栈顶出栈top:输出栈顶,栈顶不出栈

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 669. Trim a Binary Search Tree 修剪二叉搜索树 (简单)

什么是二叉查找树? 二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树:对于每个父节点,其左子树中所有节点的值小于等于父节点的值,其右子树中所有节点的值大于等于父节点的值。 利用二叉查找树的大小关系,我们可以很容易地利用递归进行树的处理

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 144. Binary Tree Preorder Traversal 二叉树展开为链表 (中等)

二叉树的遍历,常见的有先序遍历、中序遍历、后序遍历和层序遍历,它们用uxjv实现起来都非常简单; 考虑使用非递归来实现,用到时stack来辅助转自,由于先序遍历的顺序为 根左右

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树 (中等)

本题要求用先序和中序遍历来建立二叉树,由于先序的顺序的第一个肯定是根,所以原二叉树的根节点可以知道,题目中给了一个很关键的条件就是树中没有相同元素

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 1110. Delete Nodes And Return Forest 删点成林 (中等)

二叉树的题首先想到用递归,递归方法传递4个参数,当前节点;是否是根节点(如果是根节点、且存在左右子树才会形成新树);再传递一个hashset用来存储要删除的节点,达到常数据级搜索;还有一个保存结果的list。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 101. Symmetric Tree 对称二叉树 (简单)

(1)如果两个子树都为空指针,则它们相等或对称(2) 如果两个子树只有一个为空指针,则它们不相等或不对称(3)如果两个子树根节点的值不相等, 则它们不相等或不对称(4)根据相等或对称要求,进行递归处理。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 114. Flatten Binary Tree to Linked List 二叉树展开为链表 (简单)

思路:非迭代版实现,从根节点开始出发,先检测其左子节点是否存在,如存在则将根节点和其右节点断开,将左子节点及其后面所有结构一起连接到右子节点的位置,把原右子节点连到原左子节点为最后面的右子节点之后。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 104. Maximum Depth of Binary Tree 二叉树的最大深度 (简单)

思路二:也可以用层序遍历二叉树,然后计数总层数,即为二叉树的最大深度,需要注意的是while循环中的for循环的写法,一定要将q.size()放在初始化里,而不能放在普快停止的条件中,因为q的大小是随时变化的,所以放在停止条件中会出错。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 148. Sort List 排序链表 (中等)

用快慢指针将列表分成两部分,将两部分列表递归排序,再将排序后的列表合并

太牛了!四面斩获字节 offer,全靠这份“算法最优解”宝典

因为通过算法面试,可以看出一个程序员的很多基本素养,包括coding能力、反应能力、聪明程度、学习能力等等。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 409 Longest Palindrome 最长回文串 (简单)

思路:先统计每个字符出现的次数,再遍历统计后的字符次数,如果是偶数次,那么一定可以是回文字符串的一部分,加上该次数;如果是奇数n字,那么加上n-1次;最后判断如果出现过奇数次的字符,那么最后结果加1。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 227. Basic Calculator II 基本计算器 II(中等)

如果我们在字符串左边加上一个加号,可以证明其不改变运算结果,且字符串可以分割成多个<运算符, 数字>对子的形式;这样一来我们就可以从左往右处理了。由于乘除的优先级高于加减,因此我们需要使用一个中间变量来存储高优先度的运算结果。

https://static001.geekbang.org/infoq/62/623e07008ae8c11d24149cfab26bb6b4.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 696. Count Binary Substrings 计数二进制子串 (简单)

还可以从字符串的每个位置开始,向左向右延长,判断存在多少当前位置为中轴的由01连续二进制字符串。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 647. Palindromic Substrings 回文子串 (中等)

我们可以从字符串的每个位置开始,向左向右延长,判断存在多少当前位置为中轴的回文字符串。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 205. Isomorphic Strings 同构字符串 (简单)

我们可以记录两个字符串每个位置的字符第一次出现的位置,如果两个字符串中相同位置的字符与它们第一次出现的位置一样,那么这两个字符串同构。例如:paper和title,当我们现在遍历到第三个字符p和t,

https://static001.geekbang.org/infoq/0e/0e555a1c885eb1bfa34978a012fc674b.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 242. Valid Anagram 有效的字母异位词 (简单)

建立一个哈希表映射,一共26个字母,可以用一个数组来代替哈希表,我们先判断两个字符串长度不相同返回false。然后把s中所有字符出现个数统计起来,存入一个大小为26的数组中。再统计t字符串,如果发现不匹配则返回false。

https://static001.geekbang.org/infoq/91/9152512618d270ce3ca730ce1a869cd9.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 594. Longest Harmonious Subsequence 最长和谐子序列 (简单).md

题目给我们一个数组,让我们找出最长的和谐子序列,和谐子序列就是序列中数组的最大最小差值均为1,这里只让我们求长度,而不需要返回具体的子序列。所以我们可以对数组进行排序,实际上只要找出来相差为1的两个数的总共出现个数就是一个和谐子序列长度了。

https://static001.geekbang.org/infoq/0e/0e555a1c885eb1bfa34978a012fc674b.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 503. Next Greater Element II 下一个更大元素 II(中等)

我们可以用单调栈来解决这个问题,因为是循环数组,我们遍历两倍的数组,然后对坐标i取余,取出数字,如果此时栈不为空,且栈顶元素小于当前数字,说明当前数字就是栈顶元素的右边第一个较大的数,此时建立二者的映射

https://static001.geekbang.org/infoq/64/6410672682ecb7cde63f9636494652e3.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 560. Subarray Sum Equals K 和为 K 的子数组 (中等)

第三个:定义一个hash来保存sum出现的次数,这样累加sum-k出现的次数就是答案了

https://static001.geekbang.org/infoq/63/633c14fa6d20d2ae3fef620c32ce6db2.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 303. Range Sum Query - Immutable 区域和检索 - 数组不可变 (简单)

这道题让我们检索一个数组的某个区间的所有数字之和,题目中给了两个条件,首先数组内容不会变化,其次有很多的区间和检索。那么我们用传统的遍历相加来求每次区间和检索,十分的不高效,而且无法通过OJ。

https://static001.geekbang.org/infoq/a9/a9bd1867a0e42fe8ae038725c0553aa0.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

点赞破百万!字节算法大佬亲撰 30W 字数据算法笔记:GitHub 标星 93K

什么是数据结构?数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效果。数据结构往往同高效的检索算法和索引技术有关。

https://static001.geekbang.org/infoq/eb/eb56d34c6ada31c204957aa28a1b0d48.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 204. Count Primes 计数质数 (Easy)

埃拉托斯特尼筛法,是判断一个整数是否是质数的方法。并且它可以在判断一个整数n时,同时判断所小于n的整数,因此非常适合这个问题。

https://static001.geekbang.org/infoq/77/77325d825cec2fce90f7f54795fd1e3a.jpeg?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 665. Non-decreasing Array 非递减数列 (中等)

最多只有一次修改某个数字的机会,问能否将数组变为非递减数组。

https://static001.geekbang.org/infoq/b5/b50ea2c1f59159d0a4ce9fd5b352c324.webp?x-oss-process=image%2Fresize%2Cw_416%2Ch_234

leetcode 135. Candy 分发糖果 (困难)

通过两次遍历,分配的糖果就可以满足题目要求了。这里的贪心策略即为,在每次遍历中,只考虑并更新相邻一侧的大小关系。

算法与数据结构_算法与数据结构技术文章_InfoQ写作社区