12天刷题Sprint

又到面试前的突然心血来潮，开始刷题！只有12天，随命名Interview-Oriented Sprint - 12 Days Left.
也不知道算是几刷了，前面断断续续，系统不系统的刷过几次，计划每天一个主题 （2题＋一篇面筋+系统性概念熟背）。

以下主题全凭个人理解和重视程度，
1.二分查找
2.分治算法
3.贪心算法
4.回溯算法
5.链表(单链表）
6.动态规划
7.排序（快排，堆排）
8.递归（BFS，DFS）
9.栈，队列
10.双指针

BartSu 发表于 2020-10-20 10:18
好滴，后面附上题号，我想你应该想问的是反转一段链表吧，这个原题是反转链表II，但是我这个题目名称这样 ...

谢谢楼主.

不知道楼主是不是用的中文版leetcode..我的是英文版,  所以每次需要猜测对应的英文翻译然后再去搜索, 所以感觉有点难找.

10.10 二分查找 - Interview-Oriented Sprint - 11 Day Left

LC题目：4题
- x的平方根 (long) mid * mid <= x
- 0~n-1中缺失的数字 nums[mid][mid] = mid;
- 数字再排序数组中出现的次数 rightBound - leftBound + 1;
- 旋转数组的最小数字 nums[mid] 比较nums[right]

总结：
- 有序（数组) ，则考虑二分
- while循环的区间（左闭右开or双端闭）
- if检查越界

模板题：
- 寻找一个数
- 左侧边界的二分搜索
- 右侧边界的二分搜索

10.21 - 集合、Java核心类、数组操作 - Interview-Oriented Sprint - 0 Day Left

总结了一些常用的代码片段，欢迎补充。

集合
- 堆 Queue<Integer> minHeap = new  PriorityQueue<Integer>(); // 小根堆
       Queue<Integer> maxHeap = new PriorityQueue<Integer>((x, y) - > (y - x)); // 大根堆
       boolean offer(E e); E poll(); E peek(); int size();
- 栈 Deque<E> stack = new ArrayDeque<E>();
- 队列 Deque<E> queue = new ArrayDeque<E>();
           E peekLast(); E peekFirst();
           offerLast(E e); offerFirst(E e);
           E pollLast(); E pollFIrst();
- 不重复的元素 Set<E> set = new HashSet<E>();
           boolean add(E e); boolean contians(E e); boolean remove(E e); int size();
- 有序列表 List<E> list = new ArrayList<E>();
           boolean add(E e); boolean add(int index, E e);
           int remove(int index); int remove(Object e);
           E get(int index); int size();
- 键值对映射表 Map<K, V> map = new HashMap<K, V>();
           put(K key, V value); V get(K  key); boolean contains(K key);
           for (String key : map.keySet()) {
               Integer value = map.get(key);
           }
           for (Map.Entry<String, Integer> entry : map.entrySet()) {
               String key = entry.getKey();
               Integer value = entry.getValue();
           }

Java核心类
- 字符串 String
            .equals(); .equalsIgnoreCase(); // 比较
            .contains(); .startsWith(); endsWith(); //
            .indexOf(); .lastIndexOf(); // 搜索子串
            .substring(); .substring( , ); // 提取子串
            .trim(); .strip(); stripLeading(); stripTrailing(); // 去除(首尾)空白字符
            .isEmpty(); isBlank(); // 判断是否为空和空白字符串
            .replace( , ); .replaceAll(); // 替换子串
            .split(); // 分割字符串
            .join( , );  // 拼接字符串
- StringBuilder 支持链式操作
            .append(); .insert(, ); charAt(); delete(); deleteCharAt(); indexOf(); lastIndexOf();
- BigInteger 内部用一个int[]数组来模拟一个非常大的整数
            .add(); .subtract(); .multiply(); .divide(); .pow(); .longValueExact();
- Character
           .isLetter(); isDigit(); isWhiteSpace(); isUpperCase(); isLowerCase(); toUpperCase(); toLowerCase(); toString();

数组操作
- Arrays类
      .asList(); .fill(); sort(); copyOf(); copyOfRang(); .toString();

10.11 动态规划 - Interview-Oriented Sprint - 10 Days Left

LC题目： 5题
- 最长上升子序列  if(nums[j] < nums[i]) { max(dp[j]) + 1; }
- 掷骰子的n种方法 dp[d][target]+=dp[d-1][target-num]
- 剪绳子 max(dp[i], max(i-j, dp[i-j]) * j);
- 股票最大利润 dp[i] = max(dp[i-1], prices[i] - min));
- 零钱兑换 min{dp[n-coin] + 1 | coin ∈ coins}, n >0;

总结：
-存在条件：最优子结构
-一般暴力解通过穷举
-目的是求最值
-coding：状态定义、状态转移方程、初始状态、返回值
-自顶向下: 备忘录剪枝 + 递归
-自底向上：DP Table （状态压缩）+ 动态规划

面筋1：https://www.nowcoder.com/discuss ... urce_id=search_post
1. 柱状图中的最大矩形 （单调递增栈）
2. 三角形最小路径和 （动态规划）
3. 二叉树的最近公共祖先 （后序遍历DFS）

面筋1：
- 柱状图中的最大矩形 （单调递增栈）
- 三角形最小路径和 （动态规划）
- 二叉树的最近公共祖先 （后序遍历DFS）

10.12 分治算法 - Interview-Oriented Sprint - 9 Days Left

LC题目：3题
- 合并两个有序数组 mege或者从数组后面开始
- 验证IP地址 分IPV4(4个条件)和IPV6（2个条件）
- 二叉搜索树与双向链表 中序遍历dfs, prev节点, head节点

总结：
- 分解 ->解决 (触底) -> 合并(回溯)
1.分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行第归求解。
3. 将子问题的解合并成原问题的解。

模板题：
- 归并排序 sort, merge

面筋2：
- 解码方法 （动态规划）注意边界条件，最好先写全面
- 根据前序和中序重建二叉树  （前序/后序 + 中序可以确定唯一的二叉树）

10.13 滑动窗口 （双指针技巧）- Interview-Oriented Sprint - 8 Days Left

LC题目：2题
- 无重复字符的最长子串 (用set维护一个不重复窗口)
- 队列的最大值 （queue， deque）

总结：
- 如何向窗口中添加新元素
- 如何缩小窗口
- 在窗口滑动的哪个阶段更新结果

模板题：
- 滑动窗口的最大值 （单调队列）

面筋3：
- 数组中第K个元素 （partition 减治 / 堆排序排k - 1次）

模板题：
- 堆排序
- 快速排序

10.14 回溯算法 - Interview-Oriented Sprint - 7 Days Left

LC题目： 2题
- 字符串的排列
- N皇后

总结：
- 本质上是决策树的遍历问题
- 与深度优先遍历关系密切
- 路径、选择列表、结束条件

模板题：
- 全排列
- 组合
- 子集

补充内容 (2020-10-14 21:39):
技巧：
1. used数组/contains方法：排除已经选择的数字
2. start参数：（组合问题）来排除start索引前的数字