def nthUglyNumber(n: int) -> int:
if n == 0:
return None
if n == 1:
return 1
# 规定dp【i】代表第i个丑数
dp = [0 for _ in range(n+1)]
dp[1] = 1
a = b = c = 1
for i in range(2,n+1):
dp[i] = min(dp[a]*2,dp[b]*3,dp[c]*5)
if dp[i] == dp[a]*2:
a += 1
if dp[i] == dp[b]*3:
b += 1
if dp[i] == dp[c]*5:
c += 1
return dp[-1]
m = len(s)
n = len(p)
# dp[i][j]表示s长度为i,p长度为j时,s与p是否匹配,因为是从长度为0开始的,所以这里dp的长度为【m+1】【n+1】
dp = [[False for _ in range(n+1)] for __ in range(m+1)]
# 初始化
dp[0][0] = True
# 注意两个地方,
# 1、dp中的索引是指长度,所以在对应到字符串中的时候都要减一,
# 2、for循环遍历的是dp中的索引,所以右边界要加1
for _ in range(2,n+1):
if p[_-1] == '*':
dp[0][_] =dp[0][_-2]
for i in range(1,m+1):
for j in range(1,n+1):
if p[j-1] != "*":
if s[i-1] == p[j-1] or p[j-1] == ".":
dp[i][j] = dp[i-1][j-1]
else:
# 如果和*前一个值不相等(而且不是".")最好的情况就是让*=0——不对前面的时进行重复,那就是和*往前两个的值进行比较
if p[j-2] != s[i-1] and p[j-2] != ".":
dp[i][j] = dp[i][j-2]
else:
#匹配0个or匹配1个or匹配多个
dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
return dp[-1][-1]
class Solution {
public int calculateMinimumHP(int[][] g) {
int n = g.length, m = g[0].length;
int[][] f = new int[n+1][m+1];
for (int i = 0; i <= n; i++) Arrays.fill(f[i], 0x3f3f3f3f);
f[n][m-1] = f[n-1][m] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
f[i][j] = Math.max(1, Math.min(f[i+1][j], f[i][j+1]) - g[i][j]);
}
}
return f[0][0];
}
}
class Solution {
public int rob(int[] nums) {
int[] f = new int[nums.length + 1];
f[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
f[i] = Math.max(f[i-1], f[i-2]+nums[i-1]);
}
return f[nums.length];
}
}
class Solution {
public int trap(int[] height) {
int sum = 0;
int maxId = 0;
for (int i = 1; i < height.length; i++)
if (height[i] > height[maxId]) maxId = i;
int lmax = 0;
for (int i = 0; i < maxId; i++) {
if (lmax <= height[i]) lmax = height[i];
else sum += (lmax - height[i]);
}
int rmax = 0;
for (int i = height.length - 1; i > maxId; i--) {
if (rmax <= height[i]) rmax = height[i];
else sum += (rmax - height[i]);
}
return sum;
}
}
class Solution {
public double[] dicesProbability(int n) {
double[][] f = new double[n + 1][6 * n + 1];
for (int i = 1; i <= 6; i++) f[1][i] = 1.0 / 6;
for (int i = 1; i < n; i++) {
for (int j = i; j <= 6 * i; j++) {
for (int k = 1; k <= 6; k++) {
f[i + 1][j + k] += f[i][j] / 6;
}
}
}
double[] ans = new double[5 * n + 1];
for (int i = n, j = 0; i <= 6 * n; i++, j++) {
ans[j] = f[n][i];
}
return ans;
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n < 2) return n;
// 队列, 存储最长子字符串
int[] q = new int[n];
int hh = 0, tt = -1;
// 可能不全是小写英文字符, 用map(吐槽一下Java的Map不咋好用)
Map pos = new HashMap();
int max = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
// 查找这个字符上一次出现的位置
int oldP = pos.getOrDefault(c, -1);
// 如果存好的子串包含了上一次出现的s[i], 则s[i]及之前都要舍弃
while (hh <= tt && oldP >= q[hh]) hh++;
// 把当前字符放进字串
q[++tt] = i;
// 更新最大长度
max = Math.max(max, q[tt] - q[hh] + 1);
// 更新s[i]上一次出现的位置
pos.put(c, i);
}
return max;
}
}
更简单的写法
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
for(int i = 0; i < 128; i++) last[i] = -1;
int n = s.length(), max = 0, st = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
st = Math.max(st, last[c] + 1);
max = Math.max(max, i - st + 1);
last[c] = i;
}
return max;
}
}
class Solution {
public int maxValue(int[][] g) {
if (g.length == 0 || g[0].length == 0) return 0;
int n = g.length, m = g[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) continue;
if (i == 0) g[i][j] += g[i][j - 1];
else if (j == 0) g[i][j] += g[i - 1][j];
else g[i][j] += Math.max(g[i][j-1], g[i-1][j]);
}
}
return g[n-1][m-1];
}
}
// 寻找 max(prices[j] - prices[i]) [j > i]
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int min = prices[0];
int ans = 0;
for (int num : prices) {
ans = Math.max(ans, num - min);
min = Math.min(min, num);
}
return ans;
}
}
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] f = new int[n];
f[0] = nums[0];
int max = f[0];
for (int i = 1; i < n; i++) {
f[i] = Math.max(0, f[i - 1]) + nums[i];
max = Math.max(max, f[i]);
}
return max;
}
}
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0)
return new int[0];
int n = matrix.length, m = matrix[0].length;
int[] ans = new int[n * m];
boolean[][] vis = new boolean[n][m];
int x = 0, y = 0;
ans[0] = matrix[0][0];
vis[x][y] = true;
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int d = 0;
for (int i = 1; i < n * m; i++) {
int nx = x + dx[d], ny = y + dy[d];
while (!(nx >= 0 && nx < n &&
ny >= 0 && ny < m && !vis[nx][ny])) {
d = (d + 1) % 4;
nx = x + dx[d]; ny = y + dy[d];
}
x = nx; y = ny;
vis[x][y] = true;
ans[i] = matrix[x][y];
}
return ans;
}
}
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int n = matrix.length, m = matrix[0].length;
int i = 0, j = m - 1;
while (i < n && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] > target) j--;
else i++;
}
return false;
}
}
class Solution {
public int numWays(int n) {
if (n < 2) return 1;
int a = 1, b = 1;
while (n-- > 1) {
int t = a;
a = b;
b += t;
if (b >= 1000000007) b -= 1000000007;
}
return b;
}
}
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1;
while (n-- > 1) {
int t = a;
a = b;
b += t;
if (b >= 1000000007) b -= 1000000007;
}
return b;
}
}
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: TreeNode, target: int) -> list[list[int]]:
result = []
temp = []
def dfs(node):
if not node:
return
temp.append(node.val)
if sum(temp) == target and not node.right and not node.left:
# 这里不可以直接将temp append到result中,后面temp的改变会使result也改变
result.append([_ for _ in temp])
dfs(node.left)
dfs(node.right)
# 回溯时消除上一个节点的元素
temp.pop(-1)
dfs(root)
return result
# 优化:将target设成动态的new_target -= node.val,来避免每次遍历都需要对temp求和,这样到遍历到叶子节点的时候,如果new_target==0,说明满足temp=target
def pathSum1(self, root: TreeNode, target: int) -> list[list[int]]:
result = []
temp = []
def dfs(node, new_target):
if not node:
return
temp.append(node.val)
new_target -= node.val
if not node.right and not node.left and new_target == 0:
result.append([_ for _ in temp])
dfs(node.left, new_target)
dfs(node.right, new_target)
temp.pop(-1)
dfs(root, target)
return result
class Solution:
def __init__(self):
# 这里用set存放标记
self.invisitedList = set()
self.m = 0
self.n = 0
self.k = 0
def movingCount(self, m, n, k):
self.m = m
self.n = n
# self.invisitedList = [[False for _ in range(n)] for __ in range(m)]
self.k = k
res = self.dsf(0,0)
return res
def dsf(self,i,j):
# 越界,已标记,大于k
if i < 0 or i >= self.m or j < 0 or j >= self.n or (i,j) in self.invisitedList or self.sum(i,j) > self.k:
return 0
self.invisitedList.add((i,j))
return 1 + self.dsf(i,j+1) + self.dsf(i+1,j) + self.dsf(i,j-1) + self.dsf(i-1,j)
def sum(self,x,y):
if x // 10:
sum1 = x // 10 + x % 10
else:
sum1 = x
if y // 10:
sum2 = y // 10 + y % 10
else:
sum2 = y
return sum2 + sum1
class Solution:
def __init__(self):
self.n = 0
self.m = 0
# self.visitedList = []
def exist(self, board: list[list[str]], word: str) -> bool:
self.n = len(board)
self.m = len(board[0])
# self.visitedList = [[False for _ in range(self.m)] for __ in range(self.n)]
# 用两层for循环固定单词的第一个值
for i in range(self.n):
for j in range(self.m):
if self.dfs(board,i,j,word,0):
return True
return False
def dfs(self,board,i,j,word,k):
'''
深度优先遍历
Args:
board:
i,j:定位board的索引
word:
k: 固定word中的第k个元素
'''
# 终止条件
# 不越界,未走过,值相等
# if i < 0 or i >= self.n or j < 0 or j >= self.m or self.visitedList[i][j] or board[i][j] != word[k]:
# 这里由于在原list中进行标记
if i < 0 or i >= self.n or j < 0 or j >= self.m or board[i][j] != word[k]:
return False
if k == len(word)-1:
return True
# 对已经走过的路径进行标注
# self.visitedList[i][j] = True
# 也可以不使用一个专门的二维列表标记路径,而是直接在原列表中将这个元素改成一个不可能是答案的数来作为标记
board[i][j] = '~~~'
# 遍历每个阶段的可选解集合(规定方向是右,下,左,上)
res = self.dfs(board,i,j+1,word,k+1) or self.dfs(board,i+1,j,word,k+1) or self.dfs(board,i,j-1,word,k+1) or self.dfs(board,i-1,j,word,k+1)
# 回溯,需要去掉原来走过的路径的标记
# self.visitedList[i][j] = False
# 如果不用布尔list标记路径,在回溯时,就需要恢复原列表中的该元素,这里能等于word【k】是因为能够回溯说明之前这个位置的值是对的
board[i][j] = word[k]
return res
class Solution {
public int movingCount(int n, int m, int k) {
if (k == 0) return 1;
int[] r = new int[n], c = new int[m];
for (int i = 0; i < n; i++) {
int t = i;
while (t > 0) {
r[i] += t % 10;
t /= 10;
}
}
for (int i = 0; i < m; i++) {
int t = i;
while (t > 0) {
c[i] += t % 10;
t /= 10;
}
}
int[] dx = {0, 1}, dy = {1, 0};
boolean[][] vis = new boolean[n][m];
Queue<int[]> q = new LinkedList<>();
int sum = 1;
q.add(new int[]{0, 0});
vis[0][0] = true;
while (!q.isEmpty()) {
int[] p = q.poll();
for (int i = 0; i < 2; i++) {
int x = p[0] + dx[i], y = p[1] + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && r[x] + c[y] <= k) {
vis[x][y] = true;
q.add(new int[]{x, y});
sum++;
}
}
}
return sum;
}
}
class Solution {
public int reversePairs(int[] nums) {
return sort(nums, 0, nums.length - 1);
}
private int sort(int[] a, int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
int sum = sort(a, l, mid) + sort(a, mid + 1, r);
int i = l, j = mid + 1;
int[] tmp = new int[r - l + 1];
int idx = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[idx++] = a[i++];
else {
sum += (mid + 1 - i);
tmp[idx++] = a[j++];
}
}
while (i <= mid) tmp[idx++] = a[i++];
while (j <= r) tmp[idx++] = a[j++];
idx = 0;
for (int k = l; k <= r; k++, idx++)
a[k] = tmp[idx];
return sum;
}
}
已完成阅读
打卡
gitee项目仓库地址:https://gitee.com/supermalow/from-zero-to-one
打卡
70 没有 懂
打卡
逆向DP
二维DP 和 字符串DP的典型题
背包变式
终于会一道
双指针,巧妙避开DP
DP一生之敌
真的难,又是能看一下午的一道题目
真的难
双指针
更简单的写法
和LeetCode 64. 最小路径和 同理,最小值改为最大值即可
迭代
DP,类比杨辉三角
DP
数学公式,只会背过…..
原地变换(给每个元素找家)
恶心题,考验基本功
二分
同理斐波那契
迭代
利用矩阵,需要注意取模精度
打卡
无重复的全排列 DFS
DFS
BFS
回溯
一个大根堆存 <= 中位数,一个小根堆存 > 中位数
归并排序