Skip to content

Latest commit

 

History

History
383 lines (330 loc) · 12.2 KB

九章强化班&高频班.md

File metadata and controls

383 lines (330 loc) · 12.2 KB
Raw

九章强化班 & 高频

  • Union-Find: Number of Islands II
  • Trie: Word Search II
  • Monotonic Stack: Largest Rectangle in Histogram
  • Find Peak Element II: 二分法深入理解
  • Number of Airplane in the sky: 扫描线经典入门题目
  • Sliding Window Maximum: Deque 滑动窗口经典题型
  • House Robber: 滚动数组优化最简单的入门。
  • Longest Increasing continuous Subsequence 2D: 记忆化搜索的经典题，此题只有记忆化搜索才能最优。
  • Coins in a Line III: 博弈问题和记忆化搜索的结合
  • Edit Distance: 双序列常考题
  • Stone-Game: 区间类DP的入门题
  • Backpack II: 有价值的背包题目才有价值

Chapter 1 - Follow Up Question

Problem

  • Sliding Window
  • Heap vs Binary Search

Template: Sliding Window

for (i = 0; i < n; i++) {
    while (j < n) {
        if (满足条件) {
            j++;
            更新j状态
        } else (不满足条件){
            break;
        }
    }
    更新i状态
}

前向型指针题目

  • 窗口类
    • Remove Nth Node From End of List
    • minimum-size-subarray-sum
    • Minimum Window Substring
    • Longest Substring with At Most K Distinct Characters
    • Longest Substring Without Repeating Characters
  • 快慢类
    • Find the Middle of Linked List
    • Linked List Cycle I, II

天地会习武要领

  • 定期停下脚步，整理同类题型
  • 解决不会做FollowUp问题
    • 属于哪一类？
    • 同类的题目有什么相似之处？
    • 他们思考的思路是怎么样的？

大纲

  • 1.透析热门IT公司中的FollowUp面试题
  • 2.数据结构（上）
    • 并查集
    • Trie 树
    • 增加线段树小视频
  • 3.数据结构（下）
    • 堆的深入理解和运用
      • 堆重要拓展
      • Median 问题拓展
      • Sliding Windows问题总结
    • 栈
      • 栈在表达式上面的运用
      • 单调栈的使用方法
    • 双端队列Deque
      • Sliding Windows问题总结
  • 4.两个指针 + 按值二分查找
    • 扫描线和堆结合拓展
  • 5.动态规划(上)
  • 6.动态规划(下)
  • 7.如何解决困难的follow up 问题

Chapter 2 Data Structure

Problem

  • 重点题
  • Number of Islands II
    • 这道题充分体现了并查集的优势
  • Implement Trie
    • 理解Trie的定义和实现
  • Word Search II
    • Trie活用比较好的例子
  • Union Find
  • Trie

Template: Union Find

public class UnionFind {
    private int[] father = null;
    int find(int x) {
        if (father[x] == x) {
            return x;
        }
        //路径压缩
        return father[x] = find(father[x]);
    }

    //合并的root老大哥, 而不是小弟
    void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }
}

Template: Trie

Chapter 3: Data Structure II

Problem

  • Heap
  • Stack
  • Monotonic Stack

Stack

  • 特性
    • 利用栈暂且保存有效信息
    • 翻转栈的运用
    • 栈优化dfs，变成非递归
  • 单调栈
    • 找每个元素左边或者右边第一个比它自身小/大的元素
      • 找左边第一个比自己小的: 单调递增
      • 找左边第一个比自己大的: 单调递减

Chapter 4: Binary Search and Line Sweep

问题

  • Binary Search
  • Binary Search on Result
  • Sweep Line (1.事件往往是以区间的形式存在 2. 区间两端代表事件的开始和结束 3. 需要排序)
  • Deque (Monotonic Deque)

Binary Search - 保留有答案的那一半

  1. Find Peak Element 只会O(n) 只会写for循环
  2. Find Peak Element 会O(log(n)) 会优化
  3. Find Peak Element II 只会O(n^2) 会优化不会举一反三
  4. Find Peak Element II 会O(nlog(n)) 会优化会举一反三
  5. Find Peak Element II 会证明是O(n) 会举一反四

Template:按答案二分

int start = 1, end = max;  //1. 找到可行解
while (start + 1 < end) { 
    int mid = start + (end - start)/2; //2.猜答案
    if (check(mid)) { //3. 检查答案
        start = mid; //4. 调整搜索范围
    } else {
        end = mid; //4. 调整搜索范围
    }
    //5.检查start, end
}

Lesson 5 Dynamic Programming I

问题

  • 重点
  • House Robber: 滚动数组优化最简单的入门。
  • Longest Increasing continuous Subsequence 2D: 记忆化搜索的经典题，此题只有记忆化搜索才能最优
  • Coins in a Line III: 博弈问题和记忆化搜索的结合
  • 滚动数组
  • 记忆化搜索

记忆化搜索

  • 动态规划的实现方式： 本质是解决了重复计算
    • 循环（从小到大递推）
    • 记忆化搜索(从大到小搜索)
      • 画搜索树
      • 万金油 - 可解决所有问题

Template：记忆化搜索 - 适合博弈型DP

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        dp[i][j] = search(i, j);
    }
}

int search(int x, int y, int[][]A) {
    if (flag[x][y] != 0) {
        return dp[x][y];
    }

    for (int i = 0; i < 4; i++) {
        nx = x + dx[i];
        ny =  y + dy[i];
        if (A[x][y] > A[nx][ny]) {
            //通过search(nx, ny, A)更新最长子序列
        }
    }
    //返回答案
}

Lesson 6 Dynamic Programming II

Lesson 7 Follow Up

Problems

  1. Subarray sum 3 follow up
  1. Continuous Subarray Sum 2 follow up
  1. Wiggle Sort 2 follow up
  1. Iterator 3 follow up (List转Stack;主函数逻辑放在HasNext里面; Next只做一次pop处理)

Follow Up 常见方式

  • 一维转二维 - 可以套相同的思路试一试
    • Find Peak Element I/II
    • Trapping Water I/II
    • Subarray Sum/Submatrix Sum
  • 数组变成循环数组
    • 循环数组小技巧
      • 方法1: 分裂
      • 方法2: 取反
      • 方法3: 原数组加倍处理,用window size=N
    • Continuous Subarray Sum
  • 题目条件加强 - 可能题目的解题方法会变化
    • Wiggle Sort I/II
  • 换马甲(变一个描述，本质不变)
    • Number of airplane on the Sky/ Meeting Room
    • BackPack Problem
  • 描述完全不一样，但是方法相同
    • 这种题目得去分析
      • 前向型指针的题目
      • Quick Sort/ Bolt Nuts Problem

高频

Chapter 1 - 简介

  • Strings Homomorphism
  • Decode Ways
  • Rectangle Overlap
  • Check Word Abbreviation

Chapter 2 - 模拟算法和字符串处理技巧

  • 系统操作模拟实现
  • 简单智力题

Chapter 3 - 基础算法和数据结构高频题 I - Map & Stack

  • 区间类问题（3题）
  • Hash 字符/字符串统计类问题（4题）
  • 栈应用问题（1题）
  • 综合应用问题（1题）

Chapter 4 - 基础算法和数据结构高频题 II - BST

  • 二分查找类问题（2题）
  • BST类问题（2题）
  • 二叉树类问题（3题）

Chapter 5 - 搜索类题目如何高效实现 - Search

  • BFS
  • DFS