【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数)

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

57. 插入区间

https://leetcode.cn/problems/insert-interval/
【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题
提示:
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5

当前区间与要加入的新区间之间的关系只有两种可能:相交或者不相交。

如果相交,将两者结合即可。
如果不相交,判断新加入的区间是否在当前区间之前,如果是,就先加入答案。

遍历一遍之后,如果没有处理过新加入的区间,就说明新区间应该加在最后。

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) return new int[][]{newInterval};
        List<int[]> ans = new ArrayList<>();
        int s = newInterval[0], e = newInterval[1];
        boolean f = false;
        for (int[] interval: intervals) {
            int a = interval[0], b = interval[1];
            // 和 newInterval 相交
            if (b >= s && a <= e) {
                f = true;
                a = Math.min(a, s);
                b = Math.max(b, e);
            }

            // 不相交 newInterval 在此区间之前
            if (a > e) {
                 if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < s) {
                    ans.add(newInterval);
                    f = true;
                }
            }

            if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < a) ans.add(new int[]{a, b});
            else ans.get(ans.size() - 1)[1] = b;
        }
        // 如果没有处理过 newInterval
        if (!f) ans.add(newInterval);
        return ans.toArray(new int[ans.size()][2]);
    }
}

823. 带因子的二叉树

https://leetcode.cn/problems/binary-trees-with-factors/
【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题
提示:
1 <= arr.length <= 1000
2 <= arr[i] <= 10^9
arr 中的所有值 互不相同

解法——递推

将元素排序之后,从小到大依次处理各个数值作为根节点时的二叉树数量。

class Solution {
    final long MOD = (long)1e9 + 7;

    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        long ans = 0;
        Map<Integer, Long> m = new HashMap<>();         // 存储每个数字作为根节点时的二叉树数量
        for (int i = 0; i < n; ++i) {
            long cnt = 1;
            for (int j = 0; j < i; ++j) {               // 枚举儿子节点
                if (arr[i] % arr[j] == 0 && m.containsKey(arr[i] / arr[j])) {
                    cnt = (cnt + m.get(arr[j]) * m.get(arr[i] / arr[j])) % MOD;
                }
            }
            ans = (ans + cnt) % MOD;
            m.put(arr[i], cnt);
        }
        return (int)ans;
    }
}

1654. 到家的最少跳跃次数(BFS,🚹最远距离上界的证明)

https://leetcode.cn/problems/minimum-jumps-to-reach-home/description/
【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题

提示:
1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden 中所有位置互不相同。
位置 x 不在 forbidden 中。

可以证明,一定可以在[0, max(f + a + b, x + b)] 的下标范围内找到最优解,其中 f 是最远进制点的坐标。
因为 f, a, b, x <= 2000,故搜索范围不会超过 6000。(证明略,我也没整明白)

用 bfs 计算最短路。

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> s = new HashSet<>();
        for (int v: forbidden) s.add(v);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 1});       // 将起点放入队列
        final int N = 6000;
        boolean[][] vis = new boolean[N][2];
        vis[0][1] = true;
        for (int ans = 0; !q.isEmpty(); ++ans) {
            for (int t = q.size(); t > 0; --t) {
                int[] p = q.poll();
                int i = p[0], k = p[1];
                // 到达了目的地,直接返回答案
                if (i == x) return ans;

                List<int[]> nxt = new ArrayList<>();
                nxt.add(new int[]{i + a, 1});
                // 如果上一步 不是向后跳,那么这一步可以向后跳
                if ((k & 1) == 1) nxt.add(new int[]{i - b, 0});
                for (int[] e: nxt) {
                    int j = e[0];
                    k = e[1];
                    if (j >= 0 && j < N && !s.contains(j) && !vis[j][k]) {
                        q.offer(new int[]{j, k});
                        vis[j][k] = true;
                    }
                }
            }
        }
        return -1;
    }
}

1761. 一个图中连通三元组的最小度数

https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/

【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题

提示:
2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。

构造邻接表,枚举每一个三元组。

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        int[] cnt = new int[n + 1];
        int[][] isC = new int[n + 1][n + 1];
        for (int[] edge: edges) {
            int x = edge[0], y = edge[1];
            isC[x][y] = 1;
            isC[y][x] = 1;
            cnt[x]++;
            cnt[y]++;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (isC[i][j] == 0) continue;
                for (int k = j + 1; k <= n; ++k) {
                    if (isC[j][k] == 0 || isC[i][k] == 0) continue;
                    ans = Math.min(ans, cnt[i] + cnt[j] + cnt[k] - 6);
                }
            }
        }
        return ans != Integer.MAX_VALUE? ans: -1;
    }
}

2240. 买钢笔和铅笔的方案数

https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/

【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题

提示:
1 <= total, cost1, cost2 <= 10^6

解法1——完全背包

套用完全背包模板,对dp数组求和即可。

class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long[] dp = new long[total + 1];
        dp[0] = 1;
        for (int j = cost1; j <= total; ++j) dp[j] += dp[j - cost1];
        for (int j = cost2; j <= total; ++j) dp[j] += dp[j - cost2];
        long ans = 0;
        for (long d: dp) ans += d;
        return ans;
    }
}

解法2——枚举买了几支钢笔(推荐解法)

通过枚举购买钢笔的数量,计算此时可以购买铅笔的数量,+1即是购买此时数量钢笔时,购买铅笔的方案数。

class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long ans = 0;
        for (int i = 0; i * cost1 <= total; ++i) {
            ans += (total - i * cost1) / cost2 + 1;
        }
        return ans;
    }
}

2511. 最多可以摧毁的敌人城堡数目

https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/?envType=daily-question&envId=2023-09-02

【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题

提示:
1 <= forts.length <= 1000
-1 <= forts[i] <= 1

解法——一次遍历

题目要求是计算 1 和 -1 之间的 0 的最大数量。

一次遍历,遍历的过程中记录上一个 1 或 -1 出现的位置即可。

class Solution {
    public int captureForts(int[] forts) {
        int lastId = 0, ans = 0;
        for (int i = 0; i < forts.length; ++i) {
            if (forts[i] == -1 || forts[i] == 1) {
                if (forts[i] + forts[lastId] == 0) ans = Math.max(ans, i - lastId - 1);
                lastId = i;
            }
        }
        return ans;
    }
}

1921. 消灭怪物的最大数量(贪心)

https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/

【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数),算法刷题记录,leetcode,算法,BFS,每日一题

提示:
n == dist.length == speed.length
1 <= n <= 10^5
1 <= dist[i], speed[i] <= 10^5

先计算时间,再按时间排序。
贪心的先消灭快要到达城市的怪兽。文章来源地址https://www.toymoban.com/news/detail-701176.html

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        int[] t = new int[n];
        for (int i = 0; i < n; ++i) {
            t[i] = (dist[i] + speed[i] - 1) / speed[i]; // 向上取整
        }
        Arrays.sort(t);
        for (int i = 0; i < n; ++i) {
            if (t[i] <= i) return i;
        }
        return n;
    }
}

到了这里,关于【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-08-28 LeetCode每日一题(插入区间)

    点击跳转到题目位置 给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 10 4 interval

    2024年02月11日
    浏览(46)
  • 2023-07-28 LeetCode每日一题(并行课程 III)

    点击跳转到题目位置 给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 relations[j] = [prevCourse j , nextCourse j ] ,表示课程 prevCoursej 必须在课程 nextCourse j 之前 完成(先修课的关系)。同时给你一个下标从 0 开始的整数数组 time ,其

    2024年02月15日
    浏览(47)
  • 【LeetCode每日一题合集】2023.7.3-2023.7.9

    445. 两数相加 II 这道题目考察的实际知识点是高精度加法。更多关于高精度计算的内容参见:【算法基础】1.4 高精度(模拟大数运算:整数加减乘除) 2679. 矩阵中的和 读懂题意,每次操作会删去每一行中的当前最大值,同时将这些行最大值中的最大值加入最后的分数。 为了

    2024年02月13日
    浏览(56)
  • 【LeetCode - 每日一题】2594. 修车的最少时间(23.09.07)

    给定每个师傅修车的时间和需要修的车辆总数,计算修理所有汽车需要的最少时间。 师傅可以同时修车。 看到题目没有任何头绪,直接查看题解。 至于为什么用二分做呢,讨论区有个友友这么说到: 对于修理时间 t t t 来说: 若 t t t 时间内可以修理完所有车,则大于等于

    2024年02月09日
    浏览(51)
  • leetcode每日一题——45.跳跃游戏II(面试经典150题)

    45. 跳跃游戏 II - 力扣(LeetCode) 给定一个长度为 n 的 0 索引 整数数组 nums。 初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:   0 = j = nums[i]     i + j n 返回到达 nums[n - 1] 的最小跳跃次数

    2024年02月13日
    浏览(40)
  • 每日一题leetcode--使循环数组所有元素相等的最少秒数

    相当于扩散,每个数可以一次可以扩散到左右让其一样,问最少多少次可以让整个数组都变成一样的数 使用枚举,先将所有信息存到hash表中,然后逐一进行枚举,计算时间长短用看下图  考虑到环形数组,可以把首项+n放到最后,这样for循环就相当于前后可以联通 贴一张别

    2024年02月12日
    浏览(47)
  • 【LeetCode每日一题】2809. 使数组和小于等于 x 的最少时间

    2024-1-19 2809. 使数组和小于等于 x 的最少时间 思路: 获取两个列表的长度n,并初始化一个二维数组f,用于存储最优解。 定义一个二维数组nums,用于存储输入的两个列表中的元素,并按照第二列元素进行排序。 使用动态规划的方法,通过遍历nums数组,计算最优解。其中,

    2024年01月21日
    浏览(48)
  • 【力扣每日一题】2023.8.28 插入区间

    目录 题目: 示例: 分析: 代码: 和昨天的题大差不差,我们仍然是有一堆区间,题目给我们一个新的区间,要我们把新区间插入到原本的区间数组里,并且能合并的要合并。 我们可以直接把新区间放入数组里,接着执行昨天的代码即可,一行都不用改,甚至形参名字都是

    2024年02月10日
    浏览(43)
  • 【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)

    2024-1-11 2645. 构造有效字符串的最少插入数 方法一:计算组数 1.用count统计,能构成几组abc 2.如果当前字符大于之前字符,说明还在组内,不更新 3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新 4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数

    2024年01月17日
    浏览(58)
  • LeetCode 每日一题 2023/7/10-2023/7/16

    记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 7/10 16. 最接近的三数之和 排序 先确定一个最小数 双指针确定之后两个数 7/11 1911. 最大子序列交替和 dp dp[i][0/1] 表示第i个数坐标为偶数或奇数的最大交替和 dp[i][0]=max(dp[i-1][0],dp[i-1][1

    2024年02月16日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包