首页 > 其他分享 >Day2

Day2

时间:2023-07-28 22:56:42浏览次数:53  
标签:right cur nums min Day2 len left

数组专题:

leetcode: 977

暴力解法也是最开始就可以想到的方法:

def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            nums[i] *= nums[i]  
        nums.sort()
        return nums

双指针法:根据题意,给定数组为非递减数组也可以理解为一个递增的数组。在这种情况下,最大值可能是原数组(nums)最左边的值(可能是一个较小的负数),也可能是最右边的值(一个原数组内最大的正数)。所以可以使用左右指针, left = 0, right = n-1, 通过对比左右两个值的平方的大小向新定义的数组中填值。

最开始定义 res 数组时,使用的 res = [],应改为对res 的一个初始化,因为后面需要用到 res 数组中的索引信息。

def sortedSquares(nums) :
    size = len(nums) 
    left = 0 
    right = size-1 
    #res = [] 
    res = [0]*len(nums) 
    i = size - 1
    while left <= right :
        if nums[left] **2 < nums[right] ** 2 :
            res[i] = nums[right] ** 2 
            right -= 1 
        else : 
            res[i] = nums[left] **2 
            left+= 1 
        i -= 1 
    
    return res 

leetcode 209

暴力解法:刚开始看的时候这个两个for 循环也思考了很久。

def minSubArrayLen(nums, target) :
    l = len(nums) 
    #先定义一个无穷大的数
    min_len = float('inf') 
    
    for i in range(l) :
        cur_sum = 0 
        #j starts from i,从i开始慢慢更新j的值
        #如果cur_sum > target, 跳出当前循环
        #开始更新下一个i 的值,直到找到最短的子数组长度。
        for j in range(i, l) :
            cur_sum += nums[j] 
            if cur_sum >= target :
                #j-i+1为当前子数组长度,加1是因为i,j均是从0开始
                min_len = min(min_len, j-i+1) 
                break 
                #如果最后没有找到,就返回默认的0
    return min_len if min_len != float('inf') else 0 

第一层循环更新每个 i 的值的时候,第二层循环会更新 j 从当前 i 的值一直到 len(nums), 确保了最后会找到最短的子数组。

滑动窗口:不断的调节子序列的起始位置和终止位置,从而得出想要的结果。基本思想是维护一个窗口,通过移动窗口的两个边界来处理问题。使用两个指针,left and right 来扩大窗口,同时根据问题的要求调整做指针来缩小窗口。当右指针 right 扫描到字符串或数组的末尾事,算法执行完成。

本题中窗口就是满足 和大于等于 s的长度最小的连续子数组。窗口的起始位置如何移动:如果当前窗口值大于s, 窗口就要向前移动(缩小);

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for 循环的索引。

def minSubArrayLen(nums, target):
    l = len(nums) 
    left = 0
    right = 0 
    min_len = float('inf') 
    cur_sum = 0 

    while right < l :
        cur_sum += nums[right] 
        while cur_sum >= target:
            min_len = min (min_len, right-left+1) 
            #通过更新当前sum的值来改变left 的位置
            cur_sum -= nums[left]
            left += 1 
        
        right += 1 
    
    return min_len if min_len != float('inf') else 0 

对于本题的理解,我认为关键点在于cur_sum 的更新

相关阅读:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E6%80%9D%E8%B7%AF

https://cloud.tencent.com/developer/article/2294180

 

leetcode 56

code: 

def generateMatrix(n):
    if n == 0: return [] 
    res = [[0] * n for i in range(n)]
    #four bound
    left, right, up, down = 0, n-1, 0, n-1 
    #current position subscript
    #dirs[cur_d] -> how to change x, y in next direction 
    x, y = 0, 0
    #direction, right, down, left, up 
    dirs = [(0,1), (1, 0), (0, -1), (-1, 0)] 
    #current direction 
    cur_d = 0
    count = 0 
    while count != n*n: 
        res[x][y] = count + 1 
        count += 1 
        #current dir is right and arrives at right bound
        #change the move dir to the down and move the old 
        #up bound to the new up bound 
        if cur_d == 0 and y == right: 
            cur_d += 1
            up += 1 
        elif cur_d == 1 and x == down: 
            cur_d += 1 
            right -= 1 
        elif cur_d == 2 and y == left: 
            cur_d += 1 
            down -= 1 
        elif cur_d == 3 and x == up :
            cur_d += 1
            left += 1 
        cur_d %= 4 
        x += dirs[cur_d][0]
        y += dirs[cur_d][1] 
        
    return res  

感想就是编程果然是很奇妙,别人的大脑都是怎么想出来的呢???

dirs[]用来维护方向,比如当 y == right, 需要改变到同一列下一行的时候。以 n = 5 为例,第一次 y == right 是 x=0, y=4, res[x][y] = 5的时候,这个时候需要转到下一行同一列进行更新数字6。此时 对应代码 cur_d = 0,dirs[1][1] = 0, 此时 y += dirs[cur_d][1] 的值保持不变,y=4,继续在同一列上进行更新。x += dirs[cur_d][0] 的值变成 0 + 1 = 1 也就是换到下一行。以此类推完成整个更新。

相关阅读:https://leetcode.cn/problems/spiral-matrix-ii/solutions/659234/ju-zhen-bian-li-wen-ti-de-si-bu-qu-by-fu-sr5c/

标签:right,cur,nums,min,Day2,len,left
From: https://www.cnblogs.com/yuhao0451/p/17589057.html

相关文章

  • day2
    字符串API应用程序编程接口目前是JDK中提供的各种功能的Java类API帮助文档String直接赋值Stringname="AWei";创建空白字符串,不含任何内容Strings1=newstring();根据传入的字符串,创建字符串对象Strings2=newstring("点赞");根据字符数组,创建字符......
  • 7.25 day2数据结构优化dp
    战绩:100+100+20+54=374T1据lxl说是为了成绩好看加的题,难度大概cspjT1T2朴素dp然后树状数组优化一下T3赛时脑抽链,写了个dp,一直想优化dp,其实贪心就好了,过程更加简洁,优化很显然先将区间剖分成两段端点\(s_i=s_j\)相同的多条线段将区间每个点吸附到离他右边最近的一个线段......
  • 算法练习-day29
    贪心算法435.无重叠区间题意:给定一个区间的集合 intervals ,其中intervals[i]=[starti,endi] 。返回需要移除区间的最小数量,使剩余区间互不重叠 。实例:思路:本题和452.用最少数量的箭引爆气球做法非常类似,大家可以先看看我之前的文章。本题我们只需要统计重叠的区域,代码如......
  • 算法练习-day28
    贪心算法860.柠檬水找零题意:在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单bills支付的顺序)一次购买一杯。每位顾客只买一杯柠檬水,然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付5美元。注意,一开......
  • Day2 dos命令
    打开CMD的方式开始+系统+命令提示符win键+R输入cmd打开控制台(推荐使用)在任意文件夹下面,按住shift键+鼠标右键点击,在此处打开命令行窗口资源管理器的地址栏前面加上cmd空格路径 管理员方式运行选择以管理员方式运行 常用dos命令E:去盘1.#盘符切换2.#查......
  • Day2
    计算机硬件组成:CPU,主板,硬盘等装机:CPU,Memory(内存),Motherboard(主板),IO设备(input,output)冯·诺依曼结构软件定义:按照事先预定好的顺序完成特定功能组成:系统软件:windows等,​应用软件:WPS,QQ等软件:开发,软件开发​人机交互(图形化界面,命令行)常用快捷键A......
  • 算法练习-day21
    回溯算法77.组合题意:给定两个整数 n 和 k,返回范围 [1,n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。示例:   思路:本题的思想,主要是利用回溯的思想,先固定tmp插入的个数为k,当检测到tmp的大小等于k时,直接加入到我们的存储组合数组arr中,这时回溯一趟的......
  • vue-day28--对组件的理解
    学了vue之后,我们需要了解组件是什么组件的定义:实现应用中局部功能代码(css/js/html)和资源(map,map,zip)的集合 1.1模块与组件、模块化与组件化1.1.1模块理解:向外提供特定功能的 js 程序,一般就是一个 js 文件为什么:js 文件很多很复杂作用:复用 js,简化 js 的编写,提......
  • UNR #7 Day2 T1 火星式选拔题解
    放一个比赛链接先考虑打完暴力后\(k=1\)的特殊性质。当队列容量为\(1\)时,队中的人\(i\)会被第一个满足\(i\leqj\)且\(b_i\leqa_j\)的人淘汰,并且队列中的人会变成\(j\),考虑倍增加速这个过程,令\(f_{i,j}\)表示第\(i\)个人进队后淘汰过程发生\(2^j\)次后队......
  • 算法练习-day20
    二叉树669.修剪二叉搜索树题意:给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树不应该 改变保留在树中的元素的相对结构(即如果没有被移除,原有的父代子代关系都应当保留)。可以证明,存在唯一的答案 ......