繼續(xù)每天補一個纸厉，最好能加快進度趕上正常的TAT系吭，可惜基礎不夠牢，邊學邊做
滑動窗口和雙指針的條件颗品，包括滑動窗口的移動要求要清楚
209.長度最小的子數組
題目描述：
給定一個含有 n 個正整數的數組和一個正整數 target 肯尺。
找出該數組中滿足其總和大于等于 target 的長度最小的子數組[nums_l, nums_(l+1), ..., nums_(r-1), nums_r]沃缘，并返回其長度。如果不存在符合條件的子數組则吟，返回 0 槐臀。
思路整理：
- 雙指針法
利用sum計算總和，比較和target的大小氓仲，沒超過target水慨，則右指針繼續(xù)移動，超過target敬扛，則左指針移動收縮
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
left, sums = 0, 0
minlen = float('inf')
for right in range(len(nums)):
sums += nums[right]
while sums >= target:
# 用判斷條件來控制left移動
minlen = min(minlen,right - left + 1) # 確保right指針已經指向了下個元素
sums -= nums[left]
left += 1
return minlen if minlen != float('inf') else 0
2.暴力法
暴力法相當于使用兩層for循環(huán)晰洒，第一層取不同的數組起點，第二層取不同的數組終點啥箭，來求解最符合要求的數組谍珊，比較麻煩。
59.螺旋矩陣II
題目：
給你一個正整數 n 急侥，生成一個包含 1 到 n^2 所有元素砌滞，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
思路整理：
- 雙循環(huán)：我理解的核心是兩個缆巧，一個是保證每次排列邊的時候計算法則要保持一致布持，放置四條邊時個數之類的保持一致豌拙，不然算法計算上會有可能產生沖突陕悬；二是第一層循環(huán)采用的是
offset，通過n - offset來控制每層循環(huán)縮小按傅，最后再判斷為奇數的情況看是否需要填充最后一個數捉超。
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, mid = n // 2, n // 2
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, starty, -1):
nums[n - offset][i] = count
count += 1
# 從下到上（下閉上開）唯绍，注意方向
for i in range(n - offset, startx, -1):
nums[i][starty] = count
count += 1
startx += 1
starty += 1
if n % 2 != 0:
nums[mid][mid] = count
return nums
- 定義四個邊界：
分別對上下左右四個點的位置進行定義拼岳，這樣條件從正方形框逐步縮小變成了每條邊的指針位置，優(yōu)勢是不用單獨考慮中間那個位置
class Solution(object):
def generateMatrix(self, n):
if n <= 0:
return []
# 初始化 n x n 矩陣
matrix = [[0]*n for _ in range(n)]
# 初始化邊界和起始值
top, bottom, left, right = 0, n-1, 0, n-1
num = 1
while top <= bottom and left <= right:
# 從左到右填充上邊界
for i in range(left, right + 1):
matrix[top][i] = num
num += 1
top += 1
# 從上到下填充右邊界
for i in range(top, bottom + 1):
matrix[i][right] = num
num += 1
right -= 1
# 從右到左填充下邊界
for i in range(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
bottom -= 1
# 從下到上填充左邊界
for i in range(bottom, top - 1, -1):
matrix[i][left] = num
num += 1
left += 1
return matrix
區(qū)間和
題目：
給定一個整數數組 Array况芒，請計算該數組在每個指定區(qū)間內元素的總和惜纸。
思路整理：
通過利用p存儲累計和，讀取a和b時通過p(b) - p(a - 1)獲得該區(qū)間和绝骚。
import sys
input = sys.stdin.read
def main():
data = input().split()
index = 0
n = int(data[index])
index += 1
vec = []
for i in range(n):
vec.append(int(data[index + i]))
index += n
p = [0] * n
count = 0
for v in range(n):
count += vec[v]
p[v] = count
results = []
while index < len(data):
a = int(data[index]) # 注意如何提取的a和b
b = int(data[index + 1])
index += 2
if 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()
開發(fā)商購買土地
題目描述：
在一個城市區(qū)域內耐版，被劃分成了n * m個連續(xù)的區(qū)塊，每個區(qū)塊都擁有不同的權值压汪，代表著其土地價值粪牲。目前，有兩家開發(fā)公司止剖，A 公司和 B 公司腺阳，希望購買這個城市區(qū)域的土地落君。
現在，需要將這個城市區(qū)域的所有區(qū)塊分配給 A 公司和 B 公司亭引。
然而绎速，由于城市規(guī)劃的限制，只允許將區(qū)域按橫向或縱向劃分成兩個子區(qū)域焙蚓，而且每個子區(qū)域都必須包含一個或多個區(qū)塊朝氓。
為了確保公平競爭，你需要找到一種分配方式主届，使得 A 公司和 B 公司各自的子區(qū)域內的土地總價值之差最小赵哲。
注意：區(qū)塊不可再分。
輸入輸出示例：
【輸入描述】
· 第一行輸入兩個正整數君丁，代表 n 和 m枫夺。
· 接下來的 n 行，每行輸出 m 個正整數绘闷。
【輸出描述】
· 請輸出一個整數橡庞，代表兩個子區(qū)域內土地總價值之間的最小差距。
【輸入示例】
3 3
1 2 3
2 1 3
1 2 3
【輸出示例】
0
【提示信息】
· 如果將區(qū)域按照如下方式劃分：
1 2 | 3
2 1 | 3
1 2 | 3
兩個子區(qū)域內土地總價值之間的最小差距可以達到 0印蔗。
【數據范圍】：
·1 <= n, m <= 100扒最；
·n 和 m 不同時為 1。
思路整理：
分別計算每一行和每一列的和华嘹，類似前綴和的思路來比較吧趣，如果兩塊土地差距最小，嘖單邊的土地價值應該盡可能接近總和的一半耙厚。
def main():
import sys
input = sys.stdin.read
data = input().split()
n,m = int(data[0]),int(data[1])
vec = []
index = 2
horizontal = []
for i in range(n):
row = []
sums = 0
for j in range(m):
num = int(data[index])
index += 1
sums += num
row.append(num)
vec.append(row)
horizontal.append(sums)
total_sum = sum(horizontal)
vertical = [0] * m
for j in range(m):
for i in range(n):
vertical[j] += vec[i][j]
result = float('inf')
horizontalCut = 0
for i in range(n):
horizontalCut += horizontal[i]
result = min(result, abs(total_sum - 2*horizontalCut))
verticalCut = 0
for j in range(m):
verticalCut += vertical[j]
result = min(result, abs(total_sum - 2*verticalCut))
print(result)
if __name__ == "__main__":
main()
官方還提供了一個方案强挫，在計算完行列結果即開始進行比較，對整個過程略微優(yōu)化薛躬。
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
n = int(data[idx])
idx += 1
m = int(data[idx])
idx += 1
sum = 0
vec = []
for i in range(n):
row = []
for j in range(m):
num = int(data[idx])
idx += 1
row.append(num)
sum += num
vec.append(row)
result = float('inf')
count = 0
# 行切分
for i in range(n):
for j in range(m):
count += vec[i][j]
# 遍歷到行末尾時候開始統(tǒng)計
if j == m - 1:
result = min(result, abs(sum - 2 * count))
count = 0
# 列切分
for j in range(m):
for i in range(n):
count += vec[i][j]
# 遍歷到列末尾時候開始統(tǒng)計
if i == n - 1:
result = min(result, abs(sum - 2 * count))
print(result)
if __name__ == "__main__":
main()
