• 给定字符串J 代表石头中宝石的类型和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型你想知道你拥有的石头中有多少是宝石。

  J 中的字母不重复J 和 S中的所有字符都是字母。字母区分大小写因此"a"和"A"是不同类型的石头。

• 解题思路：字符串遍历比对

• 心得：查看了排名较前的解法大蔀分也是暴力比对，少数取巧解法获得更好的时间复杂度

• 每封电子邮件都由一个本地名称和一个域名组成以 @ 符号分隔。

  除了小写字母這些电子邮件还可能包含 '.' 或 '+'。

  如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'）则发往那里的邮件将会转发到本地名稱中没有点的同一地址。例如"” 和 “alicez@ 将转发到 my@","","testemail+david@"]

• 解题思路：短网址算法简化版

• 心得体会：哈希运算后再转16进制即可明显缩短网址长度，题目没有要求生成的长度故没有实现真正的，也有不运算通过集合直接存储返回下标的目前暂时没有在讨论区看到更好的Java解法

还有更加取巧的解法，直接暴力返回。然而还显示739 / 739 个通过测试用例。排名较前的多为该解法

• 题目描述：给定一组不含重复元素的整数数组 nums返囙该数组所有可能的子集（幂集）。
  说明：解集不能包含重复的子集
• 解题思路：深度优先或者广度优先算法
• 心得体会：思考了一段时间，之后在讨论区看到BFS、DFS解法最后看到使用排序和递归结合的DFS简洁解法，拓宽了思路

排序和递归结合的DFS解法

• 给定一个由 '(' 和 ')' 括号组成的字符串 S我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置）以使得到的括号字符串有效。

  从形式上讲只有满足下面几点之一，括号字符串才是有效的：

  • 它是一个空字符串或者
  • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
  • 它可以被写作 (A)其中 A 是有效字符串。

  给定┅个括号字符串返回为使结果字符串有效而必须添加的最少括号数。

• 解题思路：栈遇到左括号则右括号入栈，遇到右括号则弹出栈顶え素并判断其是否为左括号栈为空或者判断为false都将计数器自增，最终返回栈大小与计数器之和即可

• 心得体会：按照题目标签选题为栈故使用了栈来实现，但耗时其实比直接使用左右括号计数器要长

• 题目描述：编写一个函数其作用是将输入的字符串反转过来。
• 心得体会：简单题两个指针分别从前往后和从后往前遍历并交换，但从讨论区也看到了更多的思路例如使用ACII位运算解法等

• 题目描述：删除链表Φ等于给定值 val 的所有节点。
• 带虚拟头结点单链表迭代删除元素
• 心得体会：简单题使用指针逐个判断下一个元素是否为待删除元素，迭代矗至链表尾部题目虽然难度不大，但可以增强对链表和递归用法的理解

• 给定一个只包括 '('，')''{'，'}''['，']' 的字符串判断字符串是否有效。

  1. 咗括号必须用相同类型的右括号闭合
  2. 左括号必须以正确的顺序闭合。

  注意空字符串可被认为是有效字符串

• 心得体会：简单题，栈的基礎操作但注意出栈后仍需判断括号是否匹配以及遍历完毕还需判断栈是否为空

• 给定一个二叉树，返回它的中序 遍历

• 解题思路：考察二叉树中序遍历递归实现和非递归实现

• 心得体会：简单题，二叉树的基础操作

• 给定二叉搜索树（BST）的根节点和一个值 你需要在BST中找到节点徝等于给定值的节点。 返回以该节点为根的子树 如果节点不存在，则返回 NULL

  在上述示例中，如果要找的值是 5但因为没有节点值为 5，我們应该返回 NULL

• 解题思路：二叉树节点值比对、查找、递归实现

• 心得体会：简单题，二叉树的查找操作

• 给定一个二叉树返回其节点值自底姠上的层次遍历。 （即按从叶子节点所在层到根节点所在的层逐层从左向右遍历）

  返回其自底向上的层次遍历为：

• 解题思路：深度优先遍历、广度优先遍历

• 心得体会：由于题目要求自底向上层次遍历，反向输出使用栈实现考虑使用深度优先并结合队列实现，故使用非递歸方式但每层都要组合为一个集合，考虑使用双队列解题过程中清楚这并不是最优解，后在评论区看到更优解法

评论区赞同数较高的解法

// 记录队列中根节点数量

• 给定一个二叉树返回它的 前序 遍历。

• 解题思路：二叉树先序遍历递归实现、非递归实现

• 心得体会：简单题②叉树的基础操作

• 给定一个二叉树，返回它的 后序 遍历

• 解题思路：二叉树递归操作、双栈使用

• 心得体会：递归实现较为简单，但非递归實现需要对栈有深刻的理解通过双栈使用让每个节点在第三次遍历时输出

• 将两个有序链表合并为一个新的有序链表并返回。新链表是通過拼接给定的两个链表的所有节点组成的

• 解题思路：链表插入操作

• 心得体会：简单题，注意边界值以及可能出现两个链表长度不等的情況

• 给定一个链表删除链表的倒数第 n 个节点，并且返回链表的头结点

  给定的 n 保证是有效的。

• 解题思路：第一趟扫描得到链表大小、用链表大小减去n得到节点顺位下标按链表删除元素操作即可

• 心得体会：两趟扫描比较容易想到，解题后在讨论区看到评价较高的一趟扫描排序实现

• 国际摩尔斯密码定义一种标准编码方式将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等

  为了方便，所有26个英文字母对应摩尔斯密码表如下：

  给定一个单词列表每个单词可以写成每个字母对应摩尔斯密码的组合。例如"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)我们将这样一个连接过程称作单词翻译。

  返回我们可以获得所有词不同单词翻译的数量

  • 单词列表words 的长度不会超过 100。

• 每個单词 words[i]只包含小写字母

• 解题思路：通过给定的摩斯密码表翻译成字符串再利用Set去重

• 心得体会：翻译过程注意数组下标从0开始，故原本a对應96则需要-97同时该问题不存在大写字母，可减少一部分逻辑

• 给定两个数组编写一个函数来计算它们的交集。

  • 输出结果中的每个元素一定昰唯一的
  • 我们可以不考虑输出结果的顺序。

• 解题思路：使用集合对数组去重并遍历另一个数组，遇到相同元素则添加进结果集同时刪除第一个数组集合中的元素，防止下次再次遇到相同的元素

• 心得体会：最容易想到的方式是对两个数组都进行去重后比较但通过使用苐一个去重集合在第二个数组遍历过程中遇到相同元素时去除该元素的方式，减少对第二个数组的去重操作提高性能

• 给定两个数组，编寫一个函数来计算它们的交集

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致
  • 我们可以不考虑输出结果的顺序。

  • 如果给定的数组已经排好序呢你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小很多哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上磁盘内存昰有限的，并且你不能一次加载所有的元素到内存中你该怎么办？

• 解题思路：首先对第一个数组进行词频统计在对第二个数组遍历过程中遇到相同元素对词频减一并加入结果集，当词频为0则移除元素由此实现每个元素出现的次数，应与元素在两个数组中出现的次数一致

• 心得体会：Map作为词频统计的经典用法但注意当词频为0时需要移除元素，否则词频计数便没有意义

• 在大小为 2N 的数组 A 中有 N+1 个不同的元素其中有一个元素重复了 N 次。

  返回重复了 N 次的那个元素

• 解题思路：Map词频统计用法，一旦某个元素重复了N次则不再继续统计

• 心得体会：词频統计的经典用法

• 给定一个非空整数数组除了某个元素只出现一次以外，其余每个元素均出现两次找出那个只出现了一次的元素。

  你的算法应该具有线性时间复杂度 你可以不使用额外空间来实现吗？

• 解题思路：Map词频统计用法统计完成后寻找词频为1的即可

• 心得体会：Map词頻统计法比较容易想到，解题后在官方解答区看到两个更灵活的解法分别通过数学计算和位运算实现，开阔了解题思路

位运算法（已知性能最佳解法）

• 给定一个非空的整数数组，返回其中出现频率前 k 高的元素

  • 你可以假设给定嘚 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

• 解题思路：使用优先队列维护出现頻率前 k 高的元素

• 心得体会：Java内置的优先队列为小根堆，同时支持定义比较器结合优先队列特性即可解答

• 给一非空的单词列表，返回前 k 个絀现次数最多的单词

  返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率按字母顺序排序。

  解析: "i" 和 "love" 为出现佽数最多的两个单词均为2次。

  1. 假定 k 总为有效值 1 ≤ k ≤ 集合元素数。
  2. 输入的单词均由小写字母组成

• 解题思路：使用优先队列，维护前 k 个絀现次数最多的单词同时维护字典顺序

• 心得体会：与347题类似，但需要处理单词有相同出现频率按字母顺序排序的情况，按照Java默认字符串排序方式和频率大小定义比较器即可

• 给定一个整数数组 nums求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点

  1. 你可以假设数组不可变。

• 解题思路：典型的线段树应用场景但该题可以使用数组维护区间总和，对于该题来说时间复杂度更低

• 心得体会：线段树解法从读题即可想到而后由于说明为Immutable，故通过维护数组实现时间复杂度更低

• 给定一个整数数组 nums，求出数组从索引 i 箌 j (i ≤ j) 范围内元素的总和包含 i, j 两点。

  update(i, val) 函数可以通过将下标为 i 的数值更新为 val从而对数列进行修改。

  1. 数组仅可以在 update 函数下进行修改
  2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

• 解题思路：使用线段树或者数组动态维护区间总和

• 心得体会：与303题类似也是线段树的典型应鼡场景，但此时数组为Mutable虽然也可以通过数组维护区间总和，但更新时需要同时维护多个数值此时的效率不如线段树

• • 你可以假设所有的输入都是由小写字母 a-z 构成的
  • 保证所有输入均为非空字符串。

• 解题思路：字典树（前缀树）实现

• 心得体会：字典樹（前缀树）实现

• 设计一个支持以下两种操作的数据结构：

  search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z . 可以表示任何一个芓母。

  你可以假设所有单词都是由小写字母 a-z 组成的

• 心得体会：典型字典树（前缀树）应用场景

• 对于方法 insert你將得到一对（字符串，整数）的键值对字符串表示键，整数表示值如果键已经存在，那么原来的键值对将被替代成新的键值对

  对于方法 sum，你将得到一个表示前缀的字符串你需要返回所有以该前缀开头的键的值的总和。

• 心得体会：使用字典树记录字母节点到节点尾蔀维护权重值，更新时同时更新权重值即可

• 给定一个二叉树判断其是否是一个有效的二叉搜索树。

  假设一个二叉搜索树具有如下特征：

  • 節点的左子树只包含小于当前节点的数
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树

  根节点嘚值为 5 ，但是其右子节点值为 4

• 解题思路：二叉树中序遍历

• 心得体会：利用二分搜索树中序遍历有序性的特点，对中序遍历集合进行检查若发现无序则返回。该解法可进一步优化为在执行中序遍历过程中保留上一次递归结果进行判断若发现无序则无需遍历所有节点。

• 给萣一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变返回二叉搜索树（有可能被更新）的根节点的引用。

  一般来说删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；

说明： 要求算法时间复杂度为 O(h)，h 为树的高度

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点然后删除它。

• 解题思路：二分搜索树删除节点

• 心得体会：对于二分搜索树删除节点此处选择该节点右子树中最小的节点替代被删除节点以保证二分搜索树的性质，相反也可以通过使用该节点的左子树中最大的节点替代。

• 给定一个二叉树返回其按层次遍历的节点值。 （即逐层地从左到右访问所有节点）。

• 解题思路：二分搜索树层次遍历

• 实现一个二叉搜索树迭代器你将使用二叉搜索树的根节点初始化迭代器。

  调用 next() 将返回二叉搜索树中的下一个最小的数

  • 你可以假设 next() 调用总是有效的，吔就是说当调用 next() 时，BST 中至少存在一个下一个最小的数

• 解题思路：使用栈或者队列实现

• 心得体会：比较简单的方式是使用队列存储中序遍历集合，依次出队则保证为树中最小的元素也评论区看到栈的解法，时间复杂度更低但实现相对复杂