leetcode

数据结构与算法API

一维数组

1. 排序
2. 哈希表
3. 二分查找
4. 动态规划，相邻的关系
5. 转换成0-1背包问题：容量，价值，装与不装
6. 转换成完全背包问题：物品数量不限
7. 滑动窗口
8. 双指针

栈的应用

1. 括号匹配
2. 单调栈

动态规划

1. 相邻的关系 => 一层循环
2. 遍历扫描 => 两层循环

二叉树

1. 递归遍历写法

2. 非递归遍历写法

   // 前序遍历
   public void preorderTraversal(TreeNode root){
       TreeNode cur = root;
       Deque<TreeNode> stack = new ArrayDeque<>();
       while(cur != null || !stack.isEmpty()){
           while(cur != null){
               // do something here
               stack.push(cur);
               cur = cur.left;
           }
           cur = stack.pop();
           cur = cur.right;
       }
   }
   
   // 中序遍历
   public void inorderTraversal(TreeNode root){
       TreeNode cur = root;
       Deque<TreeNode> stack = new ArrayDeque<>();
       while(cur != null || !stack.isEmpty()){
           while(cur != null){
               stack.push(cur);
               cur = cur.left;
           }
           cur = stack.pop();
           // do something here
           cur = cur.right;
       }
   }
   
   // 后序遍历
   public void postorderTraversal(TreeNode root){
       TreeNode cur = root;
       TreeNode pre = null;
       Deque<TreeNode> stack = new ArrayDeque<>();
       while(cur != null || !stack.isEmpty()){
           while(cur != null){
               stack.push(cur);
               cur = cur.left;
           }
           cur = stack.peek();
           if(cur.right != null && cur.right != pre){
               cur = cur.right;
           }
           else{
               stack.pop();
               // do something here
               pre = cur;
               cur = null;
           }
       }
   }

排序

// 快排
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end){
        if(start < end){
            int mid = partition(nums, start, end);
            quickSort(nums, start, mid - 1);
            quickSort(nums, mid + 1, end);
        }
    }

    public int partition(int[] nums, int start, int end){
        int rdm = new Random().nextInt(end - start + 1) + start;
        swap(nums, rdm, end);
        int small = start - 1;
        for(int i = start; i < end; i++){
            if(nums[i] < nums[end]){
                small++;
                swap(nums, small, i);
            }
        }
        small++;
        swap(nums, small, end);
        return small;
    }

    public void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

// 堆排
class Solution {
    public int[] sortArray(int[] nums) {
        int[] ans = Arrays.copyOf(nums, nums.length);
        heapSort(nums, ans, 0, nums.length - 1);
        return ans;
    }

    public void heapSort(int[] nums, int[] ans, int start, int end) { 
        if (start < end) {
            int mid = (end + start) / 2;
            heapSort(ans, nums, start, mid);
            heapSort(ans, nums, mid + 1, end);
            merge(nums, ans, start, mid, end);
        }
    }

    public void merge(int[] nums, int[] ans, int start, int mid, int end) {
        int cnt = start, p = start, q = mid + 1;
        while (p <= mid && q <= end) {
            if (nums[p] < nums[q]) {
                ans[cnt++] = nums[p];
                p++;
            } else {
                ans[cnt++] = nums[q];
                q++;
            }
        }
        while (p <= mid) ans[cnt++] = nums[p++];
        while (q <= end) ans[cnt++] = nums[q++];
    }
}

字符串处理

1. 动态规划：子问题，状态，选择，初始条件，状态转移方程，边界条件细节

字符串搜索

区间问题

单源最短路径

1. 迪杰斯特拉算法：贪心更新当前最短距离

• 最小堆更新边 O($mlogm$)
• 遍历点 O($n^2+m$)