草庐IT

代码随想录-数组篇

ydssx 2023-03-28 原文

上次刷没刷完整,和李哥做字节的题感觉先前刷的题白刷了,故打算从头到尾完整走一遍。

二分法

1-1.二分查找

力扣题目链接

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r = 0,len(nums)-1
        while l < r:
            mid = l + r + 1 >> 1
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid 
        if nums[l] == target:
            return l
        return -1

RE了一次,原因是r的右侧初始化写成了len(nums)

1-2.搜索插入位置

力扣题目链接

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 1e4
  • -1e4 <= nums[i] <= 1e4
  • nums 为 无重复元素 的 升序 排列数组
  • -1e4 <= target <= 1e4

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l,r = 0,len(nums)-1
        while l<r:
            mid = l + r + 1 >> 1
            if nums[mid] < target:
                l = mid
            else:
                r = mid - 1
        if nums[l] < target:
            return l + 1        
        return l

一直WA,两个板子

第一个板子就是找第一个小于target值的位置,所以位置不能取到外面

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l,r = 0,len(nums)
        while l<r:
            mid = l + r >> 1
            if nums[mid] >= target:
                r = mid 
            else:
                l = mid + 1
        return l

这里和上面不一样,这里可以取到数组外面,我们找到的是第一个大于等于target的位置,所以可能取到len(nums)

总结:务必考虑清楚找到的是什么,然后敲定范围

1-3.在排序数组中查找元素的第一个和最后一个位置

力扣链接

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 <= nums.length <= 1e5
  • -1e9 <= nums[i] <= 1e9
  • nums 是一个非递减数组
  • -1e9 <= target <= 1e9

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left,right = -1,-1
        if len(nums) == 0:
            return [-1,-1]
        l,r = 0,len(nums) - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        if nums[l] == target:
            left = l
        l,r = 0,len(nums) - 1
        while l < r:
            mid = l + r + 1 >> 1
            if nums[mid] <= target:
                l = mid
            else:
                r = mid - 1
        if nums[l] == target:
            right = l
        return [left,right]

一次AC了,但存在两个编写时的问题

一是一开始left和right搞反了,上面是>=,所以是第一个大于等于target的位置,所以是左侧。相反下面的为右侧。

二是 nums = [], target = 0 RE了,特判一下

1-4.x 的平方根

力扣链接

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 2^31 - 1

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        if x <= 3: return 1
        l,r = 1, x // 2
        while l < r:
            mid = l + r + 1 >> 1
            if mid * mid > x:
                r = mid - 1
            else:
                l = mid
        return l
            

一次AC了,可能就是要考虑是大于x时才是不可能的完全不可能的情况,平方根乘起来必然<=target

1-5.有效的完全平方数

力扣链接

给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false

进阶:不要使用任何内置的库函数,如 sqrt

示例 1:

输入:num = 16
输出:true

示例 2:

输入:num = 14
输出:false

提示:

1 <= num <= 2^31 - 1


class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l,r = 1,num//2
        while l < r:
            mid = l + r + 1>> 1
            if mid * mid <= num:
                l = mid
            else:
                r = mid - 1
        if l * l == num:
            return True
        return False

一次AC了,就是上一题

双指针

快慢指针,首尾指针

2-1.移除元素

27. 移除元素 - 力扣(LeetCode)

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

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

一次AC了,但是注意注释部分,由于只需要保留前面一部分,并且只会以r指针作为判断,所以只需要交换一次

2-2.删除排序数组中的重复项

26. 删除有序数组中的重复项 - 力扣(LeetCode)

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的相对顺序 应该保持一致

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k

不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被 通过。

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按 升序 排列

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        s,t = 0,1
        while t < len(nums):
            if nums[s] != nums[t]:
                s += 1
                nums[s] = nums[t]
            t += 1
        return s + 1

一次AC,但是要注意s,t的初始化,其中较快的t指针如果和较慢的s指针说指向的值不相等的话,就将s指针的下一个位置的值赋新值

2-3.移动零

283. 移动零 - 力扣(LeetCode)

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

进阶:你能尽量减少完成的操作次数吗?


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        s,t = 0,0
        while t < len(nums):
            if nums[t] != 0:
                nums[s],nums[t] = nums[t],nums[s]
                s += 1
            t += 1
        return 

将第一题的target指定为0

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        s,t = 0,0
        while t < len(nums):
            if nums[t] != 0:
                nums[s] = nums[t]
                s += 1
            t += 1
        for i in range(s,len(nums)):
            nums[i] = 0
        return 

优化就是第一题加上将后面无用部分直接赋值为0

2-4.比较含退格的字符串

844. 比较含退格的字符串 - 力扣(LeetCode)

给定 st 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true# 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

示例 1:

输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。

示例 2:

输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。

示例 3:

输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。

提示:

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶:

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?


class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s = list(s)
        t = list(t)
        i, j = 0, 0
        while j < len(s):
            s[i] = s[j]
            if s[j] == '#':
                if i <= 1:
                    i = -1
                else:
                    i -= 2
            i += 1
            j += 1
        k, j = 0, 0
        while j < len(t):
            t[k] = t[j]
            if t[j] == '#':
                if k <= 1:
                    k = -1
                else:
                    k -= 2
            k += 1
            j += 1
        if i != k:
            return False
        # print(s,t)
        for n in range(k):
            if s[n] != t[n]:
                return False
        return True

WA了两次,一开始考虑在原始字符串上替换实现,但是python字符串不可变,故实际上不满足。

拆分字符串使用list(s)即可

WA两次的原因:

第一没有考虑倒退“过猛”的情况

"y#fo##f" "y#f#o##f"

第二个字符串由于连续两个#,

if i > 0: i -= 2

会退的太厉害

修改之后还是WA了,原因是修改成

if i <= 1: i = 0
else:  i -= 2

这样其实是倒退不足我们后面i必然会+1,所以要多退1个位置

进阶写法:

从后向前遍历,在每个字符串上指定一个遍历指针和一个回退计数值

【双指针】比较含退格的字符串

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        a, b = len(s) - 1, len(t) - 1
        sb,tb = 0,0
        while a >= 0 or b >= 0 :
            while a >= 0:
                if s[a] == '#':
                    sb += 1
                    a -= 1
                else:
                    if sb > 0:
                        sb -= 1
                        a -= 1
                    else:
                        break
            while b >= 0:
                if t[b] == '#':
                    tb += 1
                    b -= 1
                else:
                    if tb > 0:
                        tb -= 1
                        b -= 1
                    else:
                        break
            # 都结束了
            if a < 0 and b < 0:
                return True
            # 都没结束
            if a >= 0 and b >= 0 and s[a] != t[b]:
                return False
            # 一个结束了一个没结束
            if (a >= 0 and b < 0) or (a < 0 and b >= 0):
                return False
            a -= 1
            b -= 1
        # 长度不一样长
        if a >= 0 or b >= 0:
            return False
        return True

WA了两次

第一次是

"bbbextm"
"bbb#extm"

缺少最后长度不同情况下的判断

第二次是

"nzp#o#g"
"b#nzp#o#g"

将最外层循环的or写成了and,使得较长的串无法完全遍历

2-5.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

示例 2:

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶:

请你设计时间复杂度为 O(n) 的算法解决本问题


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        res = []
        i, j = 0, len(nums) - 1
        while i <= j:
            if nums[i] * nums[i] < nums[j] * nums[j]:
                res.append(nums[j] * nums[j])
                j -= 1
            else:
                res.append(nums[i] * nums[i])
                i += 1
        return res[::-1]

一次AC了

要注意是先从大到小插入,中间可能为较小的值。从小到大不行,可能中间的平方比两边小

[-7,-3,2,3,11]

2-6.长度最小的子数组

209. 长度最小的子数组 - 力扣(LeetCode)

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

进阶:

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。


涉及连续子数组的问题,我们通常有两种思路:一是滑动窗口、二是前缀和。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l, r = 0, 0
        s = nums[0]
        res = 0
        while r < len(nums):
            while s < target:
                r += 1
                if r == len(nums):
                    break
                s += nums[r]
            while s >= target:
                if res == 0:
                    res = r - l + 1
                else:
                    res = min(res, r - l + 1)
                s -= nums[l]
                if l == r:
                    break
                l += 1
         
        return res

WA了两次,主要是看错了题目,题目要求是>=target即可,看成了==target

在对指针做加减时务必留意是否是用变换后的值进行诸如求和之类的计算

上面写的非常膈应,优化如下:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        l, r = 0, 0
        s = 0
        res = len(nums) + 1
        while r < len(nums):
            s += nums[r]
            while s >= target:
                res = min(res, r - l + 1)
                s -= nums[l]
                l += 1
            r += 1
        if res == len(nums) + 1:
            return 0
        return res

参考官解的简洁写法

首先是优化了res的判断,将它置为长度+1,这是永远不可能出现的情况

接着是循环,设置初始和s为0,每次循环必然加上一次nums[r],去掉一个小于target的判断,我们只用考虑>=的情况,由于r每次都+1,可以遍历完全部可能的情况。

进阶:

利用 nums[i] 的数据范围为1 ~ 10^5,可知前缀和数组满足单调递增。??待补

滑动窗口形式的双指针(前后指针)

2-7.水果成篮

904. 水果成篮 - 力扣(LeetCode)

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:

输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。

示例 2:

输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 3:

输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

示例 4:

输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。

提示:

  • 1 <= fruits.length <= 10^5
  • 0 <= fruits[i] < fruits.length

不会

转换题意:

给定一个序列,求的是长度最长的,最多只包含两个不同元素的区间的长度

使用双指针,首先明确两个指针的定义

i为较快的那个指针,j为距离i最远的那个使得区间仅包含两个不同元素的指针。

使用双指针时要证明其单调性,反证法百试不厌。如果i往后移动到i',j往前移动是j',那么在i时就应该是j',矛盾。

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        i, j = 0, 0
        cnt = collections.defaultdict(int)
        s = 0
        res = 0
        while i < len(fruits):
            cnt[fruits[i]] += 1
            if cnt[fruits[i]] == 1:
                s += 1
            while s > 2:
                cnt[fruits[j]] -= 1
                if cnt[fruits[j]] == 0:
                    s -= 1
                j += 1
            res = max(res, i - j + 1)
            i += 1
        return res

可以看到写法与上一题的基本一致,先写后面指针的变化,再根据根据条件判断前面指针的变动

2-8.最小覆盖子串

76. 最小覆盖子串 - 力扣(LeetCode)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

注意:

对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"

示例 2:

输入:s = "a", t = "a"
输出:"a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

提示:

  • 1 <= s.length, t.length <= 10^5
  • s 和 t 由英文字母组成

进阶:你能设计一个在 o(n) 时间内解决此问题的算法吗?


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = collections.defaultdict(int)
        res = collections.defaultdict(int)
        for a in t:
            cnt[a] += 1
        n = len(t)
        m = 0
        i, j = 0, 0
        ans = ''
        while i < len(s):
            res[s[i]] += 1
            if cnt[s[i]] >= res[s[i]]:
                # 有效增加
                m += 1
            while j <= i and res[s[j]] > cnt[s[j]]:
                res[s[j]] -= 1
                j += 1
            if m == n:
                if len(ans) > (i - j + 1) or ans == '':
                    ans = s[j: i + 1]
            i += 1
        return ans

写不出来

和上面几题一个思路,就是如何知道使用hash,如何判定两个hash相同

首先用两个hash相对来说比较方便

其次是判断的话由于我们固定了一个hash表,另一个待比较的hash表在超过这个固定hash的值时我们可以认为他是无效的。

最后是j如何前进,我们的j位置多余时才能前进,也就时hash值比固定的多的时候

需要注意的是j变化需要设置j <= i,否则RE

i的更新我们可以认定为必然更新。

模拟

3-1.螺旋矩阵 II

59. 螺旋矩阵 II - 力扣(LeetCode)

给你一个正整数 n ,生成一个包含 1n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1
输出:[[1]]

提示:

  • 1 <= n <= 20

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0 for i in range(n)] for i in range(n)]
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        i, j = 0, 0
        cnt = 1
        index = 0
        while cnt <= n * n:
            ans[i][j] = cnt
            ti = i + dx[index]
            tj = j + dy[index]
            if ti >= 0 and ti < n and tj >= 0 and tj < n and ans[ti][tj] == 0:
                i = ti
                j = tj
            else:
                index = (index + 1) % 4
                i += dx[index]
                j += dy[index]
            cnt += 1
        return ans

一次AC了,要注意向右是y变换,向下是x变换

边界判断不妨先假设成立,在判断是否成立,不成立再修改

3-2.螺旋矩阵

54. 螺旋矩阵 - 力扣(LeetCode)

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

class Solution:

    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0 for i in range(n)] for i in range(n)]
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]  
        i, j = 0, 0
        cnt = 1
        index = 0
        while cnt <= n * n:
            ans[i][j] = cnt
            ti = i + dx[index]
            tj = j + dy[index]
            if ti >= 0 and ti < n and tj >= 0 and tj < n and ans[ti][tj] == 0:
                i = ti
                j = tj
            else:
                index = (index + 1) % 4
                i += dx[index]
                j += dy[index]
            cnt += 1
        return ans

一次AC,与上题反过来

小结

可以看出二分和滑动窗口多半是套路

纯双指针需要考虑使用什么样的指针

模拟题考虑怎么模拟

有关代码随想录-数组篇的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组,我需要根据最早的事件循环打印。在这种情况下,我需要打印付款和维护日期,如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询,用于查找maintenance和payment项目(非排他性查询),并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 如何在 buildr 项目中使用 Ruby 代码? - 2

    如何在buildr项目中使用Ruby?我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序,我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/),但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻,因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  3. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容?我基本上想做类似numbers.slice(0,3)的事情,但要删除切片中的数组项。嗯...嗯,我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组,我们在StackOverflow上找到一

  4. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中,它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  5. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值,但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗?ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值,你可以这样做:values=@input[x]

  6. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名,我的程序将对其进行迭代。在我之前使用的bash脚本中,我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是,我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  7. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加?这是我的解决方案,但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  8. ruby - 如果指定键的值在数组中相同,如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同,我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  9. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序,它接受一个给定的数组,然后将其显示为一个列表,我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了,但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情,但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem,我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点? 最佳答案 我不知道这是否是您正在寻找的,但也许您可以使用我的想法。由于我没有关于您要完成的工作

  10. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码,但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如,我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码?我知道在pry中我可以执行类似show-methodmethod的操作,但我如何才能对Rails框架中的方法执行此操作?您对我如何更好地理解Gem及其API有什么建议吗?仅仅阅读源代码似乎真的很难,尤其是对于框架。谢谢! 最佳答案 Ru

随机推荐