【当前无排名】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/submissions/567425911/?envType=study-plan-v2&envId=dynamic-programming
缓存炸过去了

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[x]
        let maxValue = 0
        for (let index = x + 1; index < prices.length; index++) {
            const sell = prices[index];
            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

本帖最后由 wuxin0011 于 2024-9-24 21:24 编辑

本帖最后由 wuxin0011 于 2024-9-24 21:20 编辑

本帖最后由 wuxin0011 于 2024-9-24 21:14 编辑

打卡

计算右侧小于当前元素的个数

这道题如果想到相关数据结构就简单了

相关技巧

1. 离散化 这种技巧很常见 由于只关心大小 而不关心具体值，往往通过排序 + 二分查找排名 用排名排名代替具体数值，这种方式就是离散化。 查询复杂度为 log(n), 这个过程也可以预处理，用 hash 加速查找，能够优化到 O(1)，如果值不太大，在1e6范围内 可以替代因此可以用 数组代替 hash 表 查询性能为 O(1) ,数组效率常数远小于hash表 性能更优,

2. 树状数组 这题可以说专门为这个数据结构准备的 累加和查询，本题只需要统计个数，因此 每次在对应位置更新 +1 ，题目要求统计右侧小于该位置数值个数，可以从右到左遍历

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[size - 1] != a[i]) {
                a[size++] = a[i];
            }
        }
        // System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
        int[] ans = new int[n];
        Fenwick f = new Fenwick(n);
        for(int i = n - 1;i >= 0;i--) {
            int val = lowerbound(a,size,nums[i]);
            int cnt = f.sums(val - 1);
            ans[i] = 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[mid]>=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[n + 1];
            this.diff = new int[n + 1];
            this.a = a;
        }
        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public void init() {
            for (int i = 0; i < n; i++) {
                this.add(i, a[i]);
            }
        }

        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[i];
                this.diff[i] = v;
            }
            i++;
            while (i <= n) {
                tree[i] += v;
                i += lowbit(i);
            }
        }

        private int sums(int i) {
            int s = 0;
            i++;
            while (i > 0) {
                s += tree[i];
                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);
        }
    }
}

提交地址

时间复杂度为 nlog(n) [ 排序 nlog(n) + 二分查找 nlog(n) + 树状数组求和 nlog(n)]
空间复杂度为 o(n) (拷贝数组o(n) + 创建树状数组o(n) ]

用数组代替map优化后代码

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[n-1];
        max++;
        // 由于存在负数 -1e4, 因此需要 + 一个常量拓展数组 防止下标越界
        int[] map = new int[max + N];
        map[a[0] + N] = 0;
        for(int i = 1;i < n;i++) {
            if(a[size - 1] != a[i]) {
                a[size++] = a[i];
                map[a[size-1] + N] = i;
            }
        }
        // System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
        int[] ans = new int[n];
        Fenwick f = new Fenwick(n);
        for(int i = n - 1;i >= 0;i--) {
        // int val = lowerbound(a,size,nums[i]);
            int val = map[nums[i] + N];
            int cnt = f.sums(val - 1);
            ans[i] = 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[mid]>=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[n + 1];
            this.diff = new int[n + 1];
            this.a = a;
        }
        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public void init() {
            for (int i = 0; i < n; i++) {
                this.add(i, a[i]);
            }
        }

        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[i];
                this.diff[i] = v;
            }
            i++;
            while (i <= n) {
                tree[i] += v;
                i += lowbit(i);
            }
        }

        private int sums(int i) {
            int s = 0;
            i++;
            while (i > 0) {
                s += tree[i];
                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);
        }
    }
}

提交地址

时间复杂度为 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过了

var maxProfit = function (prices) {
    const dp = new Array(2).fill(0).map(() => new Array(prices.length).fill(0))
    dp[1][0] = -prices[0]
    for (let index = 1; index < prices.length; index++) {
        dp[0][index] = Math.max(dp[1][index - 1] + prices[index], dp[0][index - 1])
        dp[1][index] = Math.max(dp[1][index - 1], dp[0][index - 1] - prices[index])
    }
    return dp[0][prices.length-1]
};

李恒道

https://leetcode.cn/submissions/detail/567824388/
手续费，股票题基本会了

var maxProfit = function (prices, fee) {
  const dp = new Array(2).fill(0);
  dp[0]=new Array(prices.length).fill(0);
  dp[1]=new Array(prices.length).fill(0);
  //0啥也没买
  //1买入了股票
  dp[1][0] = -prices[0];
  for (let index = 1; index < prices.length; index++) {
    dp[1][index] = Math.max(dp[1][index - 1], dp[0][index - 1] - prices[index]);
    dp[0][index] = Math.max(
      dp[0][index - 1],
      dp[1][index - 1] + prices[index] - fee
    );
  }
  return dp[0][prices.length - 1];
};

李恒道

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/submissions/567880494/?envType=study-plan-v2&envId=dynamic-programming
dp全写对了
但是边界问题错了
还是要练
呜呜呜

var maxProfit = function (prices) {
    const dp = new Array(4).fill(0).map(() => new Array(prices.length).fill(0))
    dp[0][0] = -prices[0]
    dp[2][0] =  -prices[0]
    for (let index = 1; index < prices.length; index++) {
        dp[0][index] = Math.max(dp[0][index - 1], -prices[index])
        dp[1][index] = Math.max(dp[1][index - 1], dp[0][index - 1] + prices[index])
        dp[2][index] = Math.max(dp[2][index - 1], dp[1][index - 1] - prices[index])
        dp[3][index] = Math.max(dp[3][index - 1], dp[2][index - 1] + prices[index])
    }
    return dp[3].pop()
};

李恒道

热烈欢迎新朋友加入油猴中文网！ 🎉🥳

❤️ 亲爱的朋友，你好呀～👋 我是油猴中文网的李恒道，另外一个管理员是王一之。你在社区遇到的疑问都可以发帖或者私信我们💌。

🌟 油玩手册 📚

🔍 寻找脚本

你可以在脚本站中找到你需要的脚本，也可以在问答互助中进行提问💬。

📄 发布脚本

如果你想把脚本发布在论坛中，你需要先发布在脚本站中，然后再在油猴脚本板块中绑定发布📢。

🐟 日常闲逛

日常摸鱼你也可以通过搜索与首页找到你需要和想发布的内容🔍。

🌟 试试下面的操作，让大家更好地认识你👥：

完善个人信息

• 设置个人签名 点我修改签名 🖊️
• 设置一个吸引人的头像 点我修改头像 📸

🌟 其它链接 📌

• 总版规地址： 点击这里 📃
• 脚本站审查规则： 点击这里 🔍
• 回帖/回复/发帖通知 点击这里 💌

祝你在油猴中文网玩得开心！❤️🥳

李恒道

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/submissions/567956875/?envType=study-plan-v2&envId=dynamic-programming
困难题，秒了！

var maxProfit = function (k, prices) {
    const dp = new Array(k * 2).fill(0).map(() => new Array(prices.length).fill(0))
    dp[0][0] = -prices[0]
    let kIndex = 0;
    while (kIndex < k * 2 - 1) {
        dp[kIndex][0] = -prices[0]
        kIndex += 2;
    }

    for (let index = 1; index < prices.length; index++) {
        dp[0][index] = Math.max(dp[0][index - 1], -prices[index])
        dp[1][index] = Math.max(dp[1][index - 1], dp[0][index - 1] + prices[index])
        let kIndex = 2;
        while (kIndex < k * 2 - 1) {
            dp[kIndex][index] = Math.max(dp[kIndex][index - 1], dp[kIndex-1][index - 1] - prices[index])
            dp[kIndex + 1][index] = Math.max(dp[kIndex + 1][index - 1], dp[kIndex][index - 1] + prices[index])
            kIndex += 2;
        }
    }
    return dp[dp.length-1].pop()
};

李恒道

https://leetcode.cn/problems/unique-binary-search-trees/submissions/568254598/?envType=study-plan-v2&envId=dynamic-programming
缓存dfs秒了！

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
我说怎么感觉不对劲...

var generateTrees = function (n) {
    const cache = new Map()
    const generateTree = (left, right) => {
        if (left > right) {
            return [null]
        }
        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

func sum(num1 int, num2 int) int {
    return num1+num2
}