赞
踩
题目: https://leetcode.cn/contest/weekly-contest-320/
题解来源于灵神:
视频学习:【力扣周赛 320】动态规划的思考步骤
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
ans, a, c = 0, 0, len(nums)
for b in Counter(nums).values():
c -= b
ans += a * b * c
a += b
return ans
二叉搜索树的性质:中序遍历就是有序的数组
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
a = []
def dfs(root):
if root is None: return
dfs(root.left)
a.append(root.val)
dfs(root.right)
dfs(root)
ans = []
for x in queries:
j = bisect_right(a, x) # >
minv = a[j - 1] if j else -1
j = bisect_left(a, x) # >=
maxv = a[j] if j < len(a) else -1
ans.append([minv, maxv])
return ans
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
g = [[] for _ in range(len(roads) + 1)]
for x, y in roads:
g[x].append(y)
g[y].append(x)
ans = 0
def dfs(x: int, fa: int) -> int:
size = 1
for y in g[x]:
if y != fa:
size += dfs(y, x)
if x:
nonlocal ans # nonlocal声明的变量不是局部变量,也不是全局变量,而是外部嵌套函数内的变量。【上一层的变量?】
ans += (size + seats - 1) // seats # 上取整公式
return size
dfs(0, -1)
return ans
动态规划解题经验:
经典DP,好好学习如何写出 动态规划 ,然后再考虑优化
考虑最后一步发生了什么【或者说,最后一步状态如何更新? + 状态转移 条件】
例如:f[i][j] : 前i个字符,分成j段
第i个 是构成最后一段的最后一个字符,满足一下状态转移 条件:
- s[i]非质数,s[i + 1]是质数【下一段开头】, 最后一段长度>= minLength
- f[i][j] += f[j’][j - 1], i - j’ >= minLength
初始值:f[0][0] = 1, ans = f[n][k]再考虑 优化 代码…
from: https://leetcode.cn/problems/number-of-beautiful-partitions/solutions/1981337/by-tsreaper-t3ge/
根据状态转移写出, O ( n 3 ) O(n ^ 3) O(n3) ,超时
class Solution {
public:
bool prime(char c){
return c == '2' || c == '3' || c == '5' || c == '7';
}
int beautifulPartitions(string s, int k, int minLength) {
if(!prime(s[0])) return 0;
int mod = 1e9 + 7;
int n = s.size();
long long f[n + 1][k + 1];
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1;i <= n;i ++ ){
// 判断第 i 个字符能否成为一段的结尾
if( i >= minLength && !prime(s[i - 1]) && (i == n || prime(s[i])) ) // 下标从1开始
{
for(int j = 1; j <= k;j ++ ){
for(int p = 0; p <= i - minLength; p ++ ){ // 这里p最小=0
f[i][j] = (f[i][j] + f[p][j - 1]) % mod;
}
}
}
}
return f[n][k];
}
};
前缀和优化 一重循环, O ( n 2 ) O(n ^ 2) O(n2)
class Solution {
public:
bool prime(char c){
return c == '2' || c == '3' || c == '5' || c == '7';
}
int beautifulPartitions(string s, int k, int minLength) {
if(!prime(s[0])) return 0;
int mod = 1e9 + 7;
int n = s.size();
long long f[n + 1][k + 1];
long long g[n + 1][k + 1];
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
f[0][0] = 1;
g[0][0] = 1;
for(int i = 1;i <= n;i ++ ){
// 判断第 i 个字符能否成为一段的结尾:s[i]不是质数,s[i + 1]是质数(下一段开头)【由于下标从1开始,所以-1】
if( i >= minLength && !prime(s[i - 1]) && (i == n || prime(s[i])) ) // 下标从1开始
{
for(int j = 1; j <= k;j ++ ){
// for(int p = 0; p <= i - minLength; p ++ ){ // 这里p最小=0
// f[i][j] = (f[i][j] + f[p][j - 1]) % mod;
// }
// 用前缀和优化 这一段循环, f[i][j] 求的是 [0, i-minLength][j - 1] 这一段和
f[i][j] = g[i - minLength][j - 1];
}
}
// 维护前缀和
for(int j = 0; j <= k;j ++ ) g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
}
return f[n][k];
}
};
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。