八股文
记录准备过的八股文
前后缀分解
思路一个prefix数组 一个 suffix 数组
在idx = i处可以使用prefix 和 suffix的一些性质,比如乘积,或者在i上左边的最小值,右边的最小值
本质是为了快速的在当前i上能够利用信息避免重复计算
题目初见使用在了leetcode 368 周赛 Q2:
元素和最小的山形三元组 II1234567891011121314151617181920212223class Solution { public int minimumSum(int[] nums) { int n = nums.length; int[] leftMin = new int[n]; int[] rightMin = new int[n]; leftMin[0] = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { leftMin[i] = Math.min(leftMin[i - 1], nums[i - 1]); } ...
摩尔投票
摩尔投票!
Re:从1500分开始的竞赛生活
记录下为了周赛的难度练习
最长公共子序列
对于两个字符串求子序列的问题,都是用两个指针 i 和 j 分别在两个字符串上移动,大概率是动态规划思路。
labuladong-最长公共子序列
相关题目1143. 最长公共子序列
583. 两个字符串的删除操作
712. 两个字符串的最小ASCII删除和
思路定义dp(s1, i, s2, j)为s1[i...] 和 s2[j...]的最长公共子序列长度
goal: dp(s1, 0, s2, 0) 从零开始的最长公共子序列长度
base case: i == len(s1) 或 j == len(s2) 由于相当于没有string,所以最长公共子序列长度为0
状态转移:
在选的情况下,即charAt[i] == charAt[j]时,状态转移:
在不选的情况下可以从三种情况转移:
但是其实只有情况一和情况二,因为情况三被情况一cover了
1143. 最长公共子序列模板题
代码:
自顶向下的递归解法:
123456789101112131415161718192021222324252627282930class Solution { String text1, tex ...
排序
涉及排序解法的题目集合
Basic-Calculator-Topics
基础计算器专题类问题
数组
涉及数组的题目集合
DataBricks
记录下databricks的面试
最小生成树 - Minimum Spanning Tree - MST
了解一下最小生成树