刷算法题-数组-02

04-长度最小的子数组

链接：209. 长度最小的子数组 - 力扣（LeetCode）

1. 题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

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

提示：

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

1. 思路

思路1：双for遍历每一个子序列，看看谁最小

思路2：滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果，也算是双指针吧

• left：只有当加起来的和大于等于target时往后移动
• right：一直往后遍历就行

1. 代码

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""left = 0# 存储和的大小，>=target的最小序列的长度cur_sum = 0min_len = float("inf")for right in range(len(nums)):cur_sum += nums[right]while cur_sum >= target: # 满足要求的情况，记录这个最小的长度，left一直往右边移动min_len = min(min_len, right - left + 1)cur_sum -= nums[left]left += 1return min_len if min_len != float("inf") else 0

05-螺旋矩阵Ⅱ

链接：59. 螺旋矩阵 II - 力扣（LeetCode）

1. 题目描述：

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

示例:

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

1. 思路：

模拟填充过程即可，考察对代码的掌控能力，按照顺序填充，注意区间

1. 代码：

class Solution(object):def generateMatrix(self, n):""":type n: int:rtype: List[List[int]]"""# 定义要返回的数组nums = [[0] * n for _ in range(n)]startx, starty = 0, 0  # 定义每轮循环一个圈的起始位置loop = n // 2  # 定义循环次数，例如n=3，就是循环1次mid = n // 2  # 矩阵中间的位置是多少，例如n=3，中间的位置就是(1,1)count = 1  # 用来给矩阵的每个位置赋值的# 循环次数为loopfor offset in range(1, loop + 1): # 偏移量从1开始，每循环一层叠加1for i in range(starty, n - offset): # 从左至右，左闭右开nums[startx][i] = countcount += 1for i in range(startx, n - offset): # 从上至下nums[i][n - offset] = countcount += 1for i in range(n - offset, starty, -1):  # 从右至左nums[n - offset][i] = countcount += 1for i in range(n - offset, startx, -1):  # 从下至上nums[i][starty] = countcount += 1# 更新起始点startx += 1starty += 1if n % 2 != 0: # n为奇数的时候，填充中间的值nums[mid][mid] = n **2return nums

06-区间和（学一下输入）

链接：58. 区间和（第九期模拟笔试）

1. 题目描述：

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

1. 思路:

思路1：每次输入的时候，计算哪个区间的和就行了，缺点是，每次输入需要大量的元素查询遍历，速度慢，属于暴力解法

思路2：用前缀和，单独用一个数组存储和，每次算区间和的时候，可以一下子算出结果来，不需要遍历

1. 代码：

import sys
input = sys.stdin.readdef main():data = input().split()index = 0n = int(data[index])  # 获取第一个数index += 1vec = []for i in range(n):  # 获取所有的数字vec.append(int(data[index + i]))index += n # index往后移动# 定义数组pp = [0] * npresum = 0for i in range(n):presum += vec[i]p[i] = presumresults = []while index < len(data):   # 看看还有没有数，如果有，那就是一个a，一个ba = int(data[index])b = int(data[index + 1])index += 2if a == 0:sum_value = p[b]else:sum_value = p[b] - p[a - 1]results.append(sum_value)for result in results:print(result)if __name__ == "__main__":main()

07-开发商购买土地

链接：44. 开发商购买土地（第五期模拟笔试）

1. 描述：

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

1. 思路：

最好的方法还是用那个前缀和，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。

1. 代码：

def main():import sysinput = sys.stdin.readdata = input().split()idx = 0n = int(data[idx])idx += 1m = int(data[idx])idx += 1sum = 0vec = []# 构建二维矩阵vec，和所有元素的和for i in range(n):row = []for j in range(m):num = int(data[idx])idx += 1row.append(num)sum += numvec.append(row)# 统计横向，计算每一行元素的和horizontal = [0] * nfor i in range(n):for j in range(m):horizontal[i] += vec[i][j]# 统计纵向，计算每一列元素的和vertical = [0] * mfor j in range(m):for i in range(n):vertical[j] += vec[i][j]# 寻找最小切割差值# 初始化一个极大值作为最小差值，先存储result = float('inf')# 从第0行开始，逐步累加每行的和到horizontalCut。# 每次累加后，计算当前切割线上下两部分的差值：abs(sum - 2 * horizontalCut)。horizontalCut = 0for i in range(n):horizontalCut += horizontal[i]result = min(result, abs(sum - 2 * horizontalCut))verticalCut = 0for j in range(m):verticalCut += vertical[j]result = min(result, abs(sum - 2 * verticalCut))print(result)if __name__ == "__main__":main()

08-有多少小于当前数字的数字

链接：1365. 有多少小于当前数字的数字 - 力扣（LeetCode）

1. 题目描述：

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

• 输入：nums = [8,1,2,2,3]
• 输出：[4,0,1,1,3]
• 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
  对于 nums[1]=1 不存在比它小的数字。
  对于 nums[2]=2 存在一个比它小的数字：（1）。
  对于 nums[3]=2 存在一个比它小的数字：（1）。
  对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

• 输入：nums = [6,5,4,8]
• 输出：[2,1,0,3]

示例 3：

• 输入：nums = [7,7,7,7]
• 输出：[0,0,0,0]

1. 思路：

思路1：双for暴力解法，时间复杂度高

思路2：先排序，排完序后，对应的索引就是有几个数字比自己小了。然后用一个哈希表存储，哈希表用数组，索引代表数字，值代表小于他的个数。然后重建一个数组，数组填写最后的结果

1. 代码：

class Solution(object):def smallerNumbersThanCurrent(self, nums):""":type nums: List[int]:rtype: List[int]"""sorted_nums = sorted(nums)hash_lst = [0] * 101# 填写hash数组，索引表示数字，值表示有几个比他小的，注意这里从后往前，存储前面的小于这个数字的数for i in range(len(sorted_nums)-1, -1, -1):hash_lst[sorted_nums[i]] = ifor i in range(len(nums)):nums[i] = hash_lst[nums[i]]return nums