算法刷题总结 (一) 数组

算法刷题总结 (一) 数组,第1张

算法总结1 数组 一、数组1.1、二分查找1.1.1、原题1.1.2、方法1.1.3、相似题型 1.2、双指针法1.2.1、原题1.2.2、方法1.2.3、相似题型 1.3、滑动窗口1.3.1、原题1.3.2、方法1.3.3、相似题型 1.4、过程模拟1.4.1、原题1.4.2、方法1.4.3、相似题型 参考

一、数组

本文章为数组的基础算法部分,相似题型汇总: 数组经典题型


1.1、二分查找 1.1.1、原题

力扣题目链接

二分查找的条件:

有序无重复元素
1.1.2、方法

根据区间的定义做边界处理。

想象有一个区间,该区间会随着二分而缩小范围,同时改变其左右闭边界([left, right])。不断二分该区间,比较mid与target的大小而选择二分区间其一。

def search(li, target):
	# 定义左右闭区间
	left, right = 0, len(li)-1
	# 二分迭代,比较中值和target,不断调整边界缩小范围。
	# 当left>target左右交错时遍历完成退出循环。
	while left<=right:
		# 中值
		mid = (left+right)//2
		# 有下面这种写法,这里 m>>n 为 m//(2**n), 即 mid = left + (right-left)//2
		# mid = left + (right-left)>>1
		# 若中值大于目标值
		if li[mid]>target:
			# 将查找区间右半部分去掉,即right替换成中值左边一位
			right = mid-1
		elif li[mid]<target:
			# 将查找区间左半部分去掉,即left替换成中值右边一位
			left = mid +1
		# 其他情况中值等于目标值,直接返回即可
		else:
			return mid
	# 前面 left > right 退出循环,说明列表整个遍历后找不到目标值,则返回 -1
	return -1

注意这里每次划分都不包括mid的值。

1.1.3、相似题型

35.搜索插入位置
34.在排序数组中查找元素的第一个和最后一个位置
69.x的平方根
367.有效的完全平方数



1.2、双指针法 1.2.1、原题

力扣题目链接
元素的删除:
注意这里为原地操作,也就是原址操作。也就是在原列表的上进行的所有操作。
这里就要注意某些函数方法会产生新的地址,一般无返回值的函数为原址操作,有返回值的为新址操作:
比如:
list.remove()无返回值,原址操作,改变原list,而不会产生新的list。
sorted(list)有返回值,新址操作,不改变原list,会产生新的list。


1.2.2、方法

1.一般解法,遍历一次列表:
思路:使用nums[:]创建一个新的list,遍历这个新的list,每次遇到val就删除原list等于val的值,这样就不会造成删除过程中index位移而错过连续的重复元素。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in nums[:]:
            if i == val:
                nums.remove(i)
        return len(nums)

2.高级解法,快慢指针:
设定两个指针,快指针每次都往前移动一个索引,慢指针只有当快指针的值不等于val时,将它的值赋予给慢指针此刻的索引,再往后移动一格

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fastIndex = 0
        slowIndex = 0
        while fastIndex <len(nums):
            if nums[fastIndex]!=val:
                nums[slowIndex] = nums[fastIndex]
                slowIndex += 1
            fastIndex += 1
        return slowIndex



1.2.3、相似题型

26.删除排序数组中的重复项
283.移动零
844.比较含退格的字符串
977.有序数组的平方



1.3、滑动窗口 1.3.1、原题

力扣题目链接


1.3.2、方法

1.一般解法,暴力破解:
思路:因为是该子序列是连续的,所以定义起始点和结束点,以区间内的和和长度进行比较。因为是暴力求解,会遍历list,所以该解法遇到较长的list会超时。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    	# 先定义一个无限大长度,后续更新变小,因为要找到最小连续子序列
        lengt_h = float(inf)
        # 先定义起始位置
        for i in range(len(nums)):
        	# 每个起始位置定义一个和,保存起始和结尾区间的值,用于比较target
            su_m = 0
            # 结尾的位置
            for j in range(i, len(nums)):
            	# 区间求和
                su_m = sum(nums[i:j+1])
                # 满足和大于等于target的条件就比较长度
                # 这里主要比较的是不同起始位置产生的区间长度
                # 因为同一起始位置,往后遍历长度只会越长,第一次满足条件则直接break
                # 后续的满足条件的区间必然会越来越大
                if su_m>=target:
                    length = j-i+1
                    # 比较原长度与目前长度的大小,小则替换,大则保留原始
                    lengt_h = lengt_h if lengt_h<length else length
                    break
            # 长度已经为1了,最小了,直接结束
            if lengt_h == 1:
                break
        return 0 if lengt_h == float(inf) else lengt_h

2.滑动窗口:
暴力破解定义了两个循环,分别代表了起始和结尾位置。
所以滑动窗口更加简化,只使用一个循环,动态维持一个起点到结尾的动态窗口,而这个循环表示结尾索引。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        lengt_h = float(inf)
        su_m = 0
        # 滑动窗口的起始索引
        ind = 0
        # 滑动窗口的结尾
        for i in range(len(nums)):
        	# 结尾索引,从0开始不断遍历,不断求和
        	# 后续只改变起始位置,来动态改变区间长度和求和的值
            su_m+=nums[i]
            # 小于target时,起始点不变,不断扩展结尾点,增加和的值和长度
            # 一旦大于等于target,试图缩小窗口,窗口缩小,则要减去相应索引位置的值
            while su_m>=target:
            	# 保留最小的长度到lengt_h
                lengt_h = min(lengt_h, i-ind+1)
                # 减去起始位置的索引的值,去缩小长度
                su_m -= nums[ind]
                # 起始索引后移
                ind += 1
        # 找不到即长度为无限大,则输出0
        return 0 if lengt_h == float(inf) else lengt_h

滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

1.3.3、相似题型

904.水果成篮
76.最小覆盖子串



1.4、过程模拟 1.4.1、原题

力扣题目链接


1.4.2、方法

找规律,每一圈为一层,不断向内缩减

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0]*n for _ in range(n)]
        # 起始点
        startx, starty = 0, 0
        # loop循环次数,循环几圈
        # mid中间点的坐标,一般为奇数才使用到,因为中间的点不算一个圈
        loop, mid = n//2, n//2
        # 计数点 1-n
        count = 1
        
        # 每循环一层,偏移量加一
        for offset in range(1, loop+1):
            # 从左至右,左闭右开
            for i in range(starty, n-offset):
                nums[startx][i] = count
                count += 1
            # 从上至下,上闭下开
            for i in range(startx, n-offset):
                nums[i][n-offset] = count
                count += 1
            # 从右至左,右闭左开
            for i in range(n-offset, startx,-1):
                nums[n-offset][i] = count
                count += 1
            # 从下至上,下闭上开
            for i in range(n-offset, starty, -1):
                nums[i][starty] = count
                count += 1
            startx += 1
            starty += 1
            
        if n%2!=0:
            nums[mid][mid] = count
        return nums

1.4.3、相似题型

54.螺旋矩阵
剑指Offer 29.顺时针打印矩阵



参考

数组经典题型

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/web/2990407.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-09-23
下一篇2022-09-23

随机推荐

  • 微博评论怎么删除 微博评论删除方法

    这个问题我遇到过,所以我会。我把删除的具体方法和流程放在下面,希望能帮助到你。1.打开微博我的个人页面,选择【微博】进入,如图所示:2.然后点击需要删除评论的微博进入,如图所示:3.选择自己需要删除的评论,如图所示:4.点击【删除】,如图所

  • 花椒树木材可以做什么?

    花椒是我们日常生活当中经常会用到的一味调味品,但是花椒除了能够做调味品,花椒还有没有其它的用途呢?尤其是花椒的木材有什么用处呢?这里科学兴农就和大家看一下关于花椒木材的用途。花椒的小知识花椒这种调味品相信很多朋友都喜欢,不过也有一部分朋友

    2023-02-03
    100
  • “饮歌”是什么意思?

    意思:1、饮歌是广东话,就是最喜欢的歌,是自己最熟最会唱最擅长的歌的意思。2、《饮歌》是著名歌手twins演唱的一首歌,收录专辑《magic》。《饮歌》创作来源于林夕希望歌曲成为人们的饮歌,也希望人们能在时代与金曲之中,失去并成长。扩展

    2023-02-03
    100
  • 八珍是哪八珍?

    八珍是人参、白术、白茯苓、当归、川芎、白芍药、熟地黄、甘草。主治气血两虚证。面色苍白或萎黄,头晕耳眩,四肢倦怠,气短懒言,心悸怔忡,饮食减少,舌淡苔薄白,脉细弱或虚大无力。清代八珍其一是“参翅八珍”“参翅八珍”中海产品占半数。指参(海

    2023-02-03
    100
  • 马克斯和莫里茨(Max &amp; Moritz)

    这是我最喜欢的黑面包了,一个叫马克斯,一个叫莫里茨,它们基本一样,里面都有各种五谷杂粮,但是各自含的内容又稍有不同,至于具体的区别我还没搞懂,下次吃的时候再具体考察下,然后做后续报道。 那你一定好奇,那这次我究竟想说什么呢? 不知道

    2023-02-03
    100
  • 求《大侠沈胜衣大侠沈胜衣(1983)》百度云无删减完整版在线观看,狄龙主演的

    链接: https:pan.baidu.coms1tu03ytFo1501vDmhSGxvJg提取码: 3fnb《大侠沈胜衣 大侠沈胜衣》导演: 楚原编剧: 秦雨主演: 狄龙、井莉、欧阳佩珊、谷峰、顾冠忠类型: 动作、悬疑制片国家

    2023-02-03
    200
  • 568A和568B的区别

    一、排线顺序不同1、568A:568A的排线顺序为白绿、绿、白橙、蓝、白蓝、橙、白棕、棕。2、568B:568B的排线顺序为白橙、橙、白绿、蓝、白蓝、绿、白棕、棕。二、应用不同1、568A:568A主要应用于交叉线。2、568B:

    2023-02-03
    200
  • 天气38度什么概念

    天气38度属于高温天气。中国气象学上,气温在35℃以上时可称为“高温天气”,如果连续几天最高气温都超过35℃时,即可称作“高温热浪”天气。一般来说,高温通常有两种情况,一种是气温高而湿度小的干热性高温;另一种是气温高、湿度大的闷热性高温,称

  • 新能源包括哪些能源?

    新能源的各种形式都是直接或者间接地来自于太阳或地球内部伸出所产生的热能。包括了太阳能、风能、生物质能、地热能、核聚变能、水能和海洋能以及由可再生能源衍生出来的生物燃料和氢所产生的能量。也可以说,新能源包括各种可再生能源和核能。相对于传统能源

    2023-02-03
    200

发表评论

登录后才能评论

评论列表(0条)

    保存