LeetCode常见算法题

哈希表

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

方法一：哈希表

使用哈希表实现重复元素滤重，遍历哈希表，当值n+1也在哈希表中时，说明是连续的，开始循环，直到找到不在哈希表中的元素，即为当前元素。

哈希表去重法

public int longestConsecutive(int[] nums) {
      if (nums == null || nums.length == 0) {
          return 0;
      }
      // 先去重
      Set<Integer> set = new HashSet<>();
      for (int i = 0; i < nums.length; i++) {
          set.add(nums[i]);
      }
      int max = 1;
      for (Integer num : set) {
          // 不连续，从最小开始往上数
          if (!set.contains(num - 1)) {
              int curMax = 1;
              int it = num;
              while (set.contains(it + 1)) {
                  curMax++;
                  it++;
              }
              max = Math.max(max, curMax);
          }
      }
      return max;
  }

方法二：排序

对数组排序，循环记录当次连续的长度。注意当相邻元素相等时，不计长度。

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解法哈希表
使用2个Hash表分别存s->t和t-s的映射，遍历检查正反都能隐射上。

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

解法一 哈希表
使用哈希表，key是字符，value是字符出现的次数。2次遍历，第一次向哈希表中插值，第二次从哈希表中删值。哈表表如果被清空，说明字符串是字母异位词。

解法二 排序先对字符串排序，按序排的字符一样，说明字符串是字母异位词。

290. 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 “遵循” 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

解法哈希表
和同构字符串的解法一样，也是用2个哈希表。

栈

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的简化路径必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的规范路径。

解法栈

使用栈，题目中输入都是合法的路径，根据 / 分割字符串，遇到 .. 出栈一次，遇到 . 则不做任何处理，其他情况都入栈，最后将栈中字符用 / 拼接起来。

需要注意的点是，栈中只存路径名，不存分隔符，能简化很多逻辑。

堆

树

199. 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解法一

使用层次遍历，记录最右边的节点。

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

解法一 哈希表

计算每个每个位数上平方和，存在哈希表中，下次遍历如果哈希表中存在元素，说明有环不是快乐数。

解法二 快慢指针

计算每个位数的平方和，慢指针每次只算一次，快指针算2次，当快慢指针相等了，说明有环。比方法一更省内存。

530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。

解法

中序遍历二叉搜索树，序列一定是升序的，所以只需要记录遍历的前一个节点即可。

二叉搜索树遍历有3种方法：

递归，先遍历左子树，读当前节点，再次遍历右节点。
栈，先将左子树全入栈，读当前节点，再将右节点入栈。
Morris遍历

图

双指针

11. 盛最多水的容器

难度：⭐️⭐️

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

解法一：双指针

左右指针像中间靠拢，取最小高度 * 指针差值为当次的最大面积。

左右双指针

  public int maxArea(int[] height) {
      int max = 0;
      int left = 0;
      int right = height.length - 1;
      while (left < right) {
          int sum;
          if (height[left] < height[right]) {
              max = Math.max(max, height[left] * (right - left));
              left++;
          } else {
              max = Math.max(max, height[right] * (right - left));
              right--;
          }
      }
      return max;
  }

15. 三数之和

难度：⭐️⭐️⭐️

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。