https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/submissions/567425911/?envType=study-plan-v2&envId=dynamic-programming
缓存炸过去了
```js
var maxProfit = function (prices) {
const cache=new Map()
const dfs = (x) => {
if(cache.has(x)){
return cache.get(x)
}
if (x >= prices.length) {
return 0
}
const buy = prices
let maxValue = 0
for (let index = x + 1; index < prices.length; index++) {
const sell = prices;
if (sell <= buy) {
continue;
}
maxValue = Math.max(maxValue, dfs(index + 2) + (sell - buy))
}
maxValue = Math.max(maxValue, dfs(x + 1))
cache.set(x,maxValue)
return maxValue
}
return dfs(0)
};
```
本帖最后由 wuxin0011 于 2024-9-24 21:24 编辑
> 本帖最后由 wuxin0011 于 2024-9-24 21:20 编辑
> 本帖最后由 wuxin0011 于 2024-9-24 21:14 编辑
打卡
[计算右侧小于当前元素的个数](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/)
这道题如果想到相关数据结构就简单了
### 相关技巧
1.**离散化** 这种技巧很常见 由于只关心大小 而不关心具体值，往往通过排序 + 二分查找排名 用排名排名代替具体数值，这种方式就是离散化。 查询复杂度为 log(n), 这个过程也可以预处理，用 hash 加速查找，能够优化到 O(1)，如果值不太大，在1e6范围内可以替代因此可以用 数组代替 hash 表 查询性能为 O(1) ,数组效率常数远小于hash表 性能更优,
2.**树状数组** 这题可以说专门为这个数据结构准备的 累加和查询，本题只需要统计个数，因此 每次在对应位置更新 +1 ，题目要求统计右侧小于该位置数值个数，可以从右到左遍历
```java
class Solution {
public List<Integer> countSmaller(int[] nums) {
int[] a = Arrays.copyOf(nums,nums.length);
Arrays.sort(a);
int size = 1;
int n = a.length;
for(int i = 1;i < n;i++) {
if(a != a) {
a = a;
}
}
// System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
int[] ans = new int;
Fenwick f = new Fenwick(n);
for(int i = n - 1;i >= 0;i--) {
int val = lowerbound(a,size,nums);
int cnt = f.sums(val - 1);
ans = cnt;
f.add(val,1);
}
List<Integer> ls = new ArrayList<>();
for(int val : ans) ls.add(val);
return ls;
}
public static int lowerbound(int[] a,int size,int t) {
int l = 0,r = size - 1;
while(l <= r) {
int mid = l + ((r - l)>> 1);
if(a>=t)r = mid - 1;
else l = mid + 1;
}
return l;
}
public static class Fenwick {
int n;
int[] tree, diff, a;
public Fenwick(int[] a) {
this.n = a.length;
this.tree = new int;
this.diff = new int;
this.a = a;
}
public Fenwick(int n) {
this.n = n;
this.tree = new int;
}
public void init() {
for (int i = 0; i < n; i++) {
this.add(i, a);
}
}
public int lowbit(int i) {
return i & -i;
}
public void add(int i, int val) {
int v = val;
if (diff != null) {
v = val - this.diff;
this.diff = v;
}
i++;
while (i <= n) {
tree += v;
i += lowbit(i);
}
}
private int sums(int i) {
int s = 0;
i++;
while (i > 0) {
s += tree;
i -= lowbit(i);
}
return s;
}
public int sums(int l, int r) {
if (l < 0 || r > n || l > r) {
return 0;
}
return sums(r) - sums(l - 1);
}
}
}
```
[提交地址](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/submissions/567699694/)
时间复杂度为 nlog(n) [ 排序 nlog(n) + 二分查找 nlog(n) + 树状数组求和 nlog(n)]
空间复杂度为 o(n) (拷贝数组o(n) + 创建树状数组o(n) ]
> 用数组代替map优化后代码
```java
class Solution {
static int N = (int)1e4 + 10;
public List<Integer> countSmaller(int[] nums) {
int[] a = Arrays.copyOf(nums,nums.length);
Arrays.sort(a);
int size = 1;
int n = a.length;
int max = a;
max++;
// 由于存在负数 -1e4, 因此需要 + 一个常量拓展数组 防止下标越界
int[] map = new int;
map + N] = 0;
for(int i = 1;i < n;i++) {
if(a != a) {
a = a;
map + N] = i;
}
}
// System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
int[] ans = new int;
Fenwick f = new Fenwick(n);
for(int i = n - 1;i >= 0;i--) {
// int val = lowerbound(a,size,nums);
int val = map + N];
int cnt = f.sums(val - 1);
ans = cnt;
f.add(val,1);
}
List<Integer> ls = new ArrayList<>();
for(int val : ans) ls.add(val);
return ls;
}
public static int lowerbound(int[] a,int size,int t) {
int l = 0,r = size - 1;
while(l <= r) {
int mid = l + ((r - l)>> 1);
if(a>=t)r = mid - 1;
else l = mid + 1;
}
return l;
}
public static class Fenwick {
int n;
int[] tree, diff, a;
public Fenwick(int[] a) {
this.n = a.length;
this.tree = new int;
this.diff = new int;
this.a = a;
}
public Fenwick(int n) {
this.n = n;
this.tree = new int;
}
public void init() {
for (int i = 0; i < n; i++) {
this.add(i, a);
}
}
public int lowbit(int i) {
return i & -i;
}
public void add(int i, int val) {
int v = val;
if (diff != null) {
v = val - this.diff;
this.diff = v;
}
i++;
while (i <= n) {
tree += v;
i += lowbit(i);
}
}
private int sums(int i) {
int s = 0;
i++;
while (i > 0) {
s += tree;
i -= lowbit(i);
}
return s;
}
public int sums(int l, int r) {
if (l < 0 || r > n || l > r) {
return 0;
}
return sums(r) - sums(l - 1);
}
}
}
```
[提交地址](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/submissions/567747776/)
时间复杂度为 nlog(n) [ 排序 nlog(n) + 查找 o(1) + 树状数组求和 nlog(n)]
空间复杂度为 o(max + 1e4 + 10) (拷贝数组o(n) + 创建树状数组o(n) ] max为数组最大值
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
dp过了
```js
var maxProfit = function (prices) {
const dp = new Array(2).fill(0).map(() => new Array(prices.length).fill(0))
dp = -prices
for (let index = 1; index < prices.length; index++) {
dp = Math.max(dp + prices, dp)
dp = Math.max(dp, dp - prices)
}
return dp
};
```
https://leetcode.cn/submissions/detail/567824388/
手续费，股票题基本会了
```js
var maxProfit = function (prices, fee) {
const dp = new Array(2).fill(0);
dp=new Array(prices.length).fill(0);
dp=new Array(prices.length).fill(0);
//0啥也没买
//1买入了股票
dp = -prices;
for (let index = 1; index < prices.length; index++) {
dp = Math.max(dp, dp - prices);
dp = Math.max(
dp,
dp + prices - fee
);
}
return dp;
};
```
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/submissions/567880494/?envType=study-plan-v2&envId=dynamic-programming
dp全写对了
但是边界问题错了
还是要练
呜呜呜
```js
var maxProfit = function (prices) {
const dp = new Array(4).fill(0).map(() => new Array(prices.length).fill(0))
dp = -prices
dp =-prices
for (let index = 1; index < prices.length; index++) {
dp = Math.max(dp, -prices)
dp = Math.max(dp, dp + prices)
dp = Math.max(dp, dp - prices)
dp = Math.max(dp, dp + prices)
}
return dp.pop()
};
```
# 热烈欢迎新朋友加入油猴中文网！ 🎉🥳
❤️ 亲爱的朋友，你好呀～👋 我是油猴中文网的[**李恒道**](https://bbs.tampermonkey.net.cn/?2)，另外一个管理员是[**王一之**](https://bbs.tampermonkey.net.cn/?4)。你在社区遇到的疑问都可以发帖或者私信我们💌。
## 🌟 油玩手册 📚
#### 🔍 寻找脚本
你可以在[**脚本站**](https://scriptcat.org/search)中找到你需要的脚本，也可以在[**问答互助**](https://bbs.tampermonkey.net.cn/forum-77-1.html)中进行提问💬。
#### 📄 发布脚本
如果你想把脚本发布在论坛中，你需要先发布在[**脚本站**](https://scriptcat.org/search)中，然后再在[**油猴脚本**](https://bbs.tampermonkey.net.cn/forum.php?gid=1)板块中绑定发布📢。
#### 🐟 日常闲逛
日常摸鱼你也可以通过[**搜索**](https://bbs.tampermonkey.net.cn/plugin.php?id=codfrm_recommend%3Asearch&keyword=&searchsubmit=true)与[**首页**](https://bbs.tampermonkey.net.cn/)找到你需要和想发布的内容🔍。
## 🌟 试试下面的操作，让大家更好地认识你👥：
**完善个人信息**
- 设置个人签名 [点我修改签名](https://bbs.tampermonkey.net.cn/home.php?mod=spacecp&ac=profile&op=info) 🖊️
- 设置一个吸引人的头像 [点我修改头像](https://bbs.tampermonkey.net.cn/home.php?mod=spacecp&ac=avatar) 📸
## 🌟 其它链接 📌
- **总版规地址：** [点击这里](https://bbs.tampermonkey.net.cn/thread-9-1-1.html) 📃
- **脚本站审查规则：** [点击这里](https://bbs.tampermonkey.net.cn/thread-3036-1-1.html) 🔍
- **回帖/回复/发帖通知** [点击这里](https://bbs.tampermonkey.net.cn/thread-5104-1-1.html) 💌
祝你在油猴中文网玩得开心！❤️🥳
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/submissions/567956875/?envType=study-plan-v2&envId=dynamic-programming
困难题，秒了！
```js
var maxProfit = function (k, prices) {
const dp = new Array(k * 2).fill(0).map(() => new Array(prices.length).fill(0))
dp = -prices
let kIndex = 0;
while (kIndex < k * 2 - 1) {
dp = -prices
kIndex += 2;
}
for (let index = 1; index < prices.length; index++) {
dp = Math.max(dp, -prices)
dp = Math.max(dp, dp + prices)
let kIndex = 2;
while (kIndex < k * 2 - 1) {
dp = Math.max(dp, dp - prices)
dp = Math.max(dp, dp + prices)
kIndex += 2;
}
}
return dp.pop()
};
```
https://leetcode.cn/problems/unique-binary-search-trees/submissions/568254598/?envType=study-plan-v2&envId=dynamic-programming
缓存dfs秒了！
```js
var numTrees = function (n) {
const cache = new Map()
const generateTree = (pos, left, right) => {
const flag = `${pos} ${left} ${right}`
if (cache.has(flag)) {
return cache.get(flag)
}
let leftNum = 0;
for (let index = left; index < pos; index++) {
leftNum += generateTree(index, left, pos - 1)
}
leftNum = leftNum == 0 ? 1 : leftNum
let rightNum = 0;
for (let index = pos + 1; index <= right; index++) {
rightNum += generateTree(index, pos + 1, right)
}
rightNum = rightNum == 0 ? 1 : rightNum
cache.set(flag, leftNum * rightNum)
return leftNum * rightNum
}
let result = 0;
for (let index = 1; index <= n; index++) {
result += generateTree(index, 1, n)
}
return result
};
```
https://leetcode.cn/problems/unique-binary-search-trees-ii/submissions/568289029/?envType=study-plan-v2&envId=dynamic-programming
看了上道的解
我以为：掏dp
实际：dfs
我说怎么感觉不对劲...
```js
var generateTrees = function (n) {
const cache = new Map()
const generateTree = (left, right) => {
if (left > right) {
return
}
const flag = `${left} ${right}`
if (cache.has(flag)) {
return cache.get(flag)
}
let result = []
for (let index = left; index <= right; index++) {
let leftNum = generateTree(left, index - 1)
let rightNum = generateTree(index + 1, right)
for (const leftItem of leftNum) {
for (const rightItem of rightNum) {
result.push({
val: index,
left: leftItem,
right: rightItem
})
}
}
}
cache.set(flag, result)
return result
}
return generateTree(1, n)
};
```
https://leetcode.cn/problems/add-two-integers/?envType=study-plan-v2&envId=primers-list
水一道练练go
```go
func sum(num1 int, num2 int) int {
return num1+num2
}
```