Skip to content

Latest commit

 

History

History
358 lines (300 loc) · 8.83 KB

算法小抄 读书笔记.md

File metadata and controls

358 lines (300 loc) · 8.83 KB
Raw

算法小抄 读书笔记

一、动态规划解题套路框架

dp[0][0][...] = base case;
for 状态1 in 状态1的所有值
	for 状态2 in 状态2的所有值
		for ...
			dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...)
graph LR
暴力递归 --> 状态转移方程 --> 带备忘录的递归算法 --> dp数组的迭代算法 --> 状态压缩
Loading

二、回溯算法解题套路框架

var result = []
fun backtrack(路径, 选择列表) {
    if(满足选择条件) {
    	result.add(路径)
    	return    
    }
    
    for 选择 in 选择列表 {
        // 做选择
        将该选择从选择列表中移除
        路径.add(选择)
        backtrack(路径, 选择列表)
        // 撤销选择
        路径.remove(选择)
        将该选择恢复到选择列表
    }
}

解题步骤：

  1. 判断当前情况是否非法，如果非法就立即返回。
  2. 当前情况是否已经满足递归条件，如果是就将当前结果保存起来并返回。
  3. 当前情况下，遍历所有可能出现的情况并进行下一步的尝试。
  4. 递归完毕后，立即回溯，回溯的方法就是取消前一步的选择（尝试）。

三、BFS 算法套路框架

广度优先搜索。把一些问题抽象成图，从一个点开始，向四周扩散。本质就是求一些最近距离。

int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start);
    visited.add(start);
    int step = 0;
    
    while(q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
    	for(int i = 0; i < sz; i++) {
            Node cur = q.poll();
            if(cur is target) {
                return step;
            }
            /* 将 cur 的相邻节点加入队列 */
            for(Node x : cur.adj()) { // cur 为相邻节点
                if(x not in visited) {
                    q.offer(x);
                 	visited.add(x);
                }
            }
        }
        /* 划重点：在这里更新步数 */
        step++;
    }
}

四、双指针技巧套路框架

快慢指针：链表中是否含有环、环的起始位置（快慢指针后，同速前进）、中点、倒数第 k 个元素。

左右指针常用算法：二分搜索、两数之和、反转数组、滑动窗口算法（左右快慢指针的应用）。

// 二分搜索框架
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            ...
        } else if(nums[mid] < target) {
            left = ...
        } else if(nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

二分搜索：

// 最基本：
right = nums.length - 1;
[left, right] // 搜索区间
while(left <= right) // 循环区间，其实也就是上面所谓搜索区间
left = mid + 1; right = mid - 1;

// 只需要找到一个 target 的索引即可
nums[mid] == target //返回
// 寻找左侧边界
right = nums.length;
[left, right);
 while(left <= right);
 left = mid + 1 和 right = mid
 nums[mid] == target 不要立即返回，而要收缩右侧边界以锁定左侧边界 
 
// 寻找右侧边界的二分搜索
right = nums.length;
[left, right);
 while(left <= right);
 left = mid + 1 和 right = mid
 
//因为需找到 target 的最左侧索引
//所以当 nums[mid] == target 时不要立即返回
//而要收缩右侧边界以锁定左侧边界 
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid - 1;
        } else if(nums[mid] == target) {
            return mid;
        }
    }
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target || nums[mid] == target) {
            right = mid - 1;
        }
    }
    
    // 检查 left 越界情况
    if(left >= nums.length || nums[left] != target) {
        return -1;
    }
    
    return left;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target || nums[mid] == target) {
            right = mid - 1;
        }
    }
    
    // 检查 left 越界情况
    if(left >= nums.length || nums[left] != target) {
        return -1;
    }
    
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target || nums[mid] == target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid - 1;
        }
    }
    
    // 检查 right 越界情况
    if(right < 0 || nums[right] != target) {
        return -1;
    }
    
    return right;
}

五、滑动窗口算法

int left = 0, right = 0;

while(right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while(window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}
/* 滑动窗口算法框架 */
void slidingWindow(String s, String t) {
    Map<Char, Int> need, window;
    for(char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    while(right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...
        
        // 判断左侧窗口是否要收缩
        while(window needs shrink){
            char d = s[left];
            // 左移窗口
            left++
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

六、LRU 缓存淘汰算法

  • 为什么是双向链表，而不是单链表？：需要删除动作，删除一个节点不仅要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接找到查找前驱，保证操作的时间复杂度为 O(1)。
  • 为什么要在链表中同事存储 key 和 val，而不是只存储 val？：当缓存容量已满，不仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。

七、单调队列

八、回文串

寻找回文串的核心思想就是从中心向两端扩展：

string palindrome(string& s, int l, int r) {
    // 防止索引越界
    while(l >= 0 && r < s.size() && s[l] == s[r]) {
        // 向两边展开
        l--; r++;
    }
    return s.substr(l + 1, r - l - 1);
}

bool isPalindrome(string s) {
    int left = 0, right = s.length - 1;
    while(left < right) {
        if(s[left] != s[right])
            return false;
    }
    
    return true
}
// 链表反转算法
ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while(cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

九、单调栈

int[] nextGreaterElement(int[] nums) {
    int[] ans = new int[nums.length];
    Stack<Integer> s = new Stack<>();
    for(int i = nums.size - 1; i >= 0; i--) {
        while(!s.isEmpty() && s.peek() <= nums[i]) {
            s.pop();
        }
        ans[i] = s.isEmpty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return ans;
}
	/*
     * 快速排序
     *
     * 参数说明: 
     *     a -- 待排序的数组
     *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    public static void quickSort(int[] a, int l, int r) {

        if (l < r) {
            int i,j,x;

            i = l;
            j = r;
            x = a[i]; // flag
            while (i < j) {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quickSort(a, l, i-1); /* 递归调用 */
            quickSort(a, i+1, r); /* 递归调用 */
        }
    }