力扣每日一练(24-1-20)

这篇具有很好参考价值的文章主要介绍了力扣每日一练(24-1-20)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣每日一练(24-1-20),leetcode,算法,职场和发展

 

      大脑里的第一想法是排列组合,直接给出超级准确的最优解。

        但不适用,hhh

        只要连续的n个元素大于或者等于target就可以了

        题目比自己想象的要好解决

        解法是使用滑动窗口算法。这个算法的基本思想是维护一个窗口,使得窗口内的元素总和大于等于目标值,然后尝试缩小窗口以找到最小的满足条件的子数组。

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        start = 0
        end = 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == n + 1 else ans

C#

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        int ans = n + 1;
        int start = 0;
        int end = 0;
        int total = 0;
        while (end < n) {
            total += nums[end];
            while (total >= target) {
                ans = Math.Min(ans, end - start + 1);
                total -= nums[start];
                start++;
            }
            end++;
        }
        return ans == n + 1 ? 0 : ans;
    }
}

        解法的时间复杂度是O(n),因为每个元素最多被访问两次。

二分查找法

        在这个问题中,O(n)的滑动窗口解法已经是最优解法,因为它只需要遍历一次数组。然而,如果你想要实现一个O(n log n)的解法,你可以使用二分查找的方法。这种方法的基本思想是先计算累积和数组,然后对每个累积和,使用二分查找找到最小的索引j,使得sum[j] - sum[i] >= target。

        以下是这个方法的Python实现:文章来源地址https://www.toymoban.com/news/detail-811381.html

Python

import bisect

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        sums = [0] * (n + 1)
        for i in range(1, n + 1):
            sums[i] = sums[i - 1] + nums[i - 1]
        for i in range(1, n + 1):
            to_find = target + sums[i - 1]
            bound = bisect.bisect_left(sums, to_find)
            if bound != len(sums):
                ans = min(ans, bound - (i - 1))
        return 0 if ans == n + 1 else ans

C#

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        int ans = n + 1;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int to_find = target + sums[i - 1];
            int bound = Array.BinarySearch(sums, to_find);
            if (bound < 0) {
                bound = ~bound;
            }
            if (bound <= n) {
                ans = Math.Min(ans, bound - (i - 1));
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}

到了这里,关于力扣每日一练(24-1-20)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣、每日一练:回文数

    给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1: 输入:x = 121 输出:true 示例 2: 输入:x = -121 输出:false 解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是

    2024年02月11日
    浏览(39)
  • 力扣、每日一练:爬楼梯

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例 1: 输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2: 输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1 阶 + 1 阶

    2024年02月11日
    浏览(48)
  • 60.每日一练:回文数(力扣)

    目录 问题描述 代码解决以及思想  解法(一) 知识点 解法(二) 在C++中,你可以使用标准库提供的函数来将整数转换为字符串。 使用 std::to_string() 函数:

    2024年02月11日
    浏览(35)
  • CSDN编程题-每日一练(2023-08-24)

    时间限制:1000ms内存限制:256M 题目描述: 给定整数n。 计算公式: n i-1 ∑ ∑ [gcd(i + j, i - j) = 1] i=1 j=1 输入描述: 输入整数n。(1=n=1e6) 输出描述: 输出答案 🚩 示例: ✔️ 示例1 : 输入 233 输出 11065 🔔 解题思路: 首先#x

    2024年02月11日
    浏览(59)
  • 数据结构:力扣OJ题(每日一练)

    目录 题一:环形链表 思路一: 题二:复制带随机指针的链表  思路一: 本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵! 给定一个链表的头节点   head  ,返回链表开始入环的第一个节点。  如果链表无环,则返回  null 。 如果链表中有某个节

    2024年02月12日
    浏览(45)
  • 数据结构:力扣OJ题(每日一练)

    示例:         初始化: 初始化队列Q1,Q2; 入栈: 先将要入栈的数据放入为空的队列中,都为空时,放入Q1; 出栈: 当要出栈时,将Q1的数据出列n-1个,此时的Q1就是栈要出栈的数据(每次出栈都进行一次第三步将为不为空的队列数据放n-1个到为空队列中)); 获取栈顶元

    2024年02月12日
    浏览(41)
  • “三指针法“合并两个有序数组(力扣每日一练)

            我的第一想法确实是:先合并数组,再排序,搞完。         哈哈哈,想那么多干嘛,目的达成了就好了。 力扣官方题解是双指针: 还有糕手: Python: C#:       总结         可以称之为\\\"三指针\\\" 方法,因为我们同时使用了三个指针(p1、p2 和 p)来操作和遍历两

    2024年02月02日
    浏览(41)
  • 2023-08-24力扣每日一题

    链接: 1267. 统计参与通信的服务器 题意: 同行同列可以发生通信,求能发生通信的机器数量 解: 标记每行/每列的机器个数即可 实际代码: 限制: m == grid.length n == grid[i].length 1 = m = 250 1 = n = 250 grid[i][j] == 0 or 1

    2024年02月11日
    浏览(46)
  • CSDN编程题-每日一练(2023-08-20)

    时间限制:1000ms内存限制:256M 题目描述: 给定一已排序的正整数组成的数组,求需要在中间至少插入多少个数才能将其补全成为一等差数列。 “在中间插入”的意思是:不能在第一个数之前,或最后一个数之后插入数。 输入描述: 仅有一行输入,即已排序的正整数数组

    2024年02月12日
    浏览(41)
  • C语言每日一练 —— 第20天:位运算

      今天主要内容是聊一聊二进制和位运算。   对应视频教程如下:位运算视频教程。   我们在学习 光天化日学C语言(06)- 进制转换入门 的时候,曾经提到过二进制。   二进制就是逢二进一,计算机中的存储采用的就是二进制。在计算机中,非零即一。   例如

    2024年02月07日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包