剑指offer

Leetcode剑指offer合集

先看Cyc2018

常遗忘梳理

• 丑数: 多链表归并
• 约瑟夫环
• 正则表达式匹配
• 打印从 1 到最大的 n 位数、
  • 回溯法生成，维护长度N的数组
• 数组中只出现一次的数字
  • 先所有元素异或，然后diff结果取最低位: diff &= -diff;,根据最低位所有元素分成两组，每组各自异或就是结果。

leetcode hot200

Cyc2018

常遗忘梳理

• 荷兰国旗三色排序

• 区间相关
  • Cyc
  • 一般都是结束时间排序

• 信件错拍

• 最长递增子序列

• 462. 最小操作次数使数组元素相等 II 改变数组元素使所有的数组元素都相等，求最小的每个数改变的差的绝对值。 Solution: 其实就是排序后，找中位数，然后遍历计算。

• 二叉树得到最底层最左边的点，可以层次遍历，每次遍历先right后left，最后一个点就是。

• 538. 把二叉搜索树转换为累加树, 先遍历右子树。

• 501. 二叉搜索树中的众数 一种就是hash存起来，不存起来的话可以利用中序遍历结果是非递减的，比如[0,1,1,1,2,2]，这样就可以统计最大计数然后更新了。

• 统计并返回这个字符串中 回文子串 的数目。

  • Manacher 算法 记得arm_len是除当前之前的长度，aaa中间的长度是1

• 判断一个整数是否是回文数 不能用额外存储空间

  • public boolean isPalindrome(int x) {
        if (x == 0) {
            return true;
        }
        if (x < 0 || x % 10 == 0) {
            return false;
        }
        int right = 0;
        while (x > right) {
            right = right * 10 + x % 10;
            x /= 10;
        }
        return x == right || x == right / 10;
    }
    

• 有序矩阵的 Kth Element 每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

  • 多路归并。 klog(n)
  • 二分法也行。按值域来。 nlog(r - l) n是行/列的长度

• 找出数组中重复的数，数组值在 [1, n] 之间

  • 可以交换到对应位置，如果不能交换也可以快慢指针

• 数组相邻差值的个数

  • 让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 … k/2 k/2+1.，后面的按需加就可以，这样差值依次为k,k-1,k-2,k-3…2,1,1,1,1,…

• 位运算实现整数的加法

  public int getSum(int a, int b) {
      return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
  }
  

leetcode blind 75

Array

• Two Sum 哈希表
• Best Time to Buy and Sell Stock
• Contains Duplicate 哈希表
• Product of Array Except Self 可以ans算左边的，然后维护变量R不断乘以右边的。
• Maximum Subarray
• Maximum Product Subarray 两个变量维护当前结尾最大的和最小的
• Find Minimum in Rotated Sorted Array 如果有相等情况，当a[mid] == a[right], right-=1
• Search in Rotated Sorted Array 当左右中间都相等时， left+=1, right-=1
• 3Sum 排序+双指针
• Container With Most Water 多个柱子，挑两个柱子，统计最多能接多少水，双指针，不断缩小两边矮的那个

Binary

• Sum of Two Integers 不用+做加法，记得python的负数处理，要取负数的补码，需要&0xffffffff。 负数的补码还原到python的负数，如-2， 需要&下0xffffffff,然后取反加一，外面再加个负号。
• Number of 1 Bits
• Counting Bits 统计1-n里每个数字二进制的1的个数，动态规划，最低设置位。 res[i] = res[i & (i - 1)] + 1
• Missing Number 异或
• Reverse Bits 反转位，一个新值，不断从右边增加然后左移

Dynamic Programming

• Climbing Stairs
• Coin Change
• Longest Increasing Subsequence
• Longest Common Subsequence
• Word Break Problem
• Combination Sum 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
• House Robber
• House Robber II
• Decode Ways Z -> 26的字符串反解码可能性
• Unique Paths
• Jump Game 贪心

Graph

• Clone Graph

• Course Schedule

• Pacific Atlantic Water Flow 太平洋大西洋水流问题

• Number of Islands

• Longest Consecutive Sequence 找1，2，3，4这样连续，可以每个开头一次循环找最大，整体o(n)

• Alien Dictionary (Leetcode Premium) 有一种新的使用拉丁字母的外来语言。但是，你不知道字母之间的顺序。你会从词典中收到一个非空的单词列表，其中的单词在这种新语言的规则下按字典顺序排序。请推导出这种语言的字母顺序。

  输入：["wrt","wrf","er","ett","rftt"]
  输出："wertf"
  解释：
  从 "wrt"和"wrf" ,我们可以得到 't'<'f'
  从 "wrt"和"er" ,我们可以得到'w'<'e'
  从 "er"和"ett" ,我们可以得到 get 'r'<'t'
  从 "ett"和"rftt" ,我们可以得到 'e'<'r'
  所以返回 "wertf"
  

  解答: 每连续两个单词可以得到字母和字母顺序，然后拓扑排序即可。

• Graph Valid Tree (Leetcode Premium) 判断图是否是树，即无环。可以dfs/bfs/unionfind

• Number of Connected Components in an Undirected Graph (Leetcode Premium) 无向图里连通数量，可以并查集。

Interval

贪心的可以按end排序，否则涉及插入、合并的都是按start排序

秒懂力扣区间题目：重叠区间、合并区间、插入区间

找最多不重合的数量，按end排序

• Insert Interval 按start排序，遇到重叠就合并,start = min(start, left), right= max(right, end)

• Merge Intervals 合并区间，按start排序

• Non-overlapping Intervals

• Meeting Rooms (Leetcode Premium) Given an array of meeting time intervals consisting of start and end times[[s1,e1],[s2,e2],...](si< ei), determine if a person could attend all meetings.

  解答: 按start排序，看有无重合区间

• Meeting Rooms II (Leetcode Premium) Given an array of meeting time intervals consisting of start and end times[[s1,e1],[s2,e2],...](si< ei), find the minimum number of conference rooms required.

  可以用heap弹出，复杂度高。最佳是扫描线算法。遇到start则+1, end则-1. 参考

Linked List

• Reverse a Linked List
• Detect Cycle in a Linked List
• Merge Two Sorted Lists
• Merge K Sorted Lists 分治合并 和 heap取最小合并复杂度相同
• Remove Nth Node From End Of List
• Reorder List

Matrix

• Set Matrix Zeroes 有0的位置横和竖都变0，可以利用第一行和第一列来记录
• Spiral Matrix 螺旋遍历
• Rotate Image
• Word Search

String

• Longest Substring Without Repeating Characters

• Longest Repeating Character Replacement 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

  解答: 双指针

• Minimum Window Substring 滑动窗口

• Valid Anagram 判断 *t* 是否是 *s* 的字母异位词。 hash表

• Group Anagrams 按频次统计分组，hash表

• Valid Parentheses

• Valid Palindrome

• Longest Palindromic Substring

• Palindromic Substrings 解答: 回文子串的数目

• Encode and Decode Strings (Leetcode Premium)

Tree

• Maximum Depth of Binary Tree
• Same Tree
• Invert/Flip Binary Tree 左右翻转
• Binary Tree Maximum Path Sum
• Binary Tree Level Order Traversal
• Serialize and Deserialize Binary Tree
• Subtree of Another Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST 第k小
• Lowest Common Ancestor of BST 236. 二叉树的最近公共祖先
• Implement Trie (Prefix Tree)
• Add and Search Word
• Word Search II 字典树剪枝

Heap

• Merge K Sorted Lists
• Top K Frequent Elements
• Find Median from Data Stream 两个堆

Important Link:

14 Patterns to Ace Any Coding Interview Question

其他

• bfs最小转弯路径
  • pop一个点，对4个方向都遍历到头，然后加进队列里，每次放队列时就设置visit

• 442. 数组中重复的数据

  • 给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
  • 数字交换到它的位置上，可以o(1)空间复杂度

          for i in range(n):
              while nums[i] - 1 != i and nums[nums[i] - 1] != nums[i]:
                  a, b = nums[i], nums[nums[i] - 1]
                  nums[nums[i] - 1], nums[i] = a, b

• 42. 接雨水

  • 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
  • 一种是记录leftMax, rightMax。 另一种更优的是单调栈，pop时，栈下一个就是比它高的左边元素，即将入栈的是右边的高，计算这部分横着的体积，(i - left - 1) * (min(height[left], height[i]) - height[top])
• 407. 接雨水 II
  • 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
  • 最小堆每次找最小高度的从外往里遍历。类似Dijstra。初始化时是所有边缘处入栈

• 贪心算法。

  • 求最多需要跳几次，rightmost, end是上一次的rightmost，end变时加一。参考

• 区间

  • 求最多无重复区间数量。结束最早的那个一定会被选中。435. 无重叠区间 . 贪心。先结束点排序。参考

        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        ans = 1

        for i in range(1, n):
            if intervals[i][0] >= right:
                ans += 1
                right = intervals[i][1]