209.长度最小的子数组
此题注重理解,同时我将res一开始初始化为sums的长度加一（因为不可能为此长度）
INT32_MAX 是一个常量，代表 32 位有符号整数的最大值
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i=0,j=0;//i为起始位置，j为终止位置
int sum=0;//当前子数列总和
int sublen=0;//当前子数列长度
int res=nums.size()+1;//不可能超过这个，或int res = INT32_MAX;
for(j;j<nums.size();j++){//循环遍历指导大于等于target
sum+=nums[j];
while(sum>=target){//一旦加上新的nums[j]使得sum符合条件，则开始动态调整i
sublen=j-i+1;
res=res>sublen?sublen:res;//看看当前是否需要更新最小值
sum=sum-nums[i];//从这里开始是预判下一个
i++;
}
}
return res==nums.size()+1?0:res;
}
};
python中直接有min()函数，避免进行比较再取值：
float('inf')inf表示infinite
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
i,j=0,0#起始和终止
sum=0
res=len(nums)+1#不可能的长度，或者可以res = float('inf')
sublen=0#子长度
while j<len(nums):
sum=sum+nums[j]
while sum>=target:
sublen=j-i+1
res=min(res,sublen)#更新
sum=sum-nums[i]
i=i+1
j=j+1
if res==len(nums)+1:
return 0
else:
return res
59.螺旋矩阵II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int startx=0;
int starty=0;
int count=1;
int i=0,j=0;
int loop=n/2;
int offset=1;
vector<vector<int>> res(n,vector<int>(n,0));//二维vector，括号内第一个参数是row数，第二个参数是每行有多少个，初始化为什么（此处为0）
while(loop-->0){
for(j=starty;j<n-offset;j++){
res[startx][j]=count++;
}
for(i=startx;i<n-offset;i++){
res[i][j]=count++;
}
for(;j>starty;j--){
res[i][j]=count++;
}
for(;i>startx;i--){
res[i][j]=count++;
}
startx++;
starty++;
offset++;
}
if(n%2==1){
res[n/2][n/2]=count;
}
return res;
}
};
var generateMatrix = function(n) {
let i=0,j=0;
let startx=0,starty=0;
let count=1;
let loop=parseInt(n/2);
let mid=parseInt(n/2);
let offset=1;
let res=new Array(n).fill(0).map(()=>new Array(n).fill(0));//js创建数组还是不熟悉
//map的作用是调用回调函数
while(loop-- >0){
for(j=starty;j<n-offset;j++){
res[startx][j]=count++;
}
for(i=startx;i<n-offset;i++){
res[i][j]=count++;
}
for(;j>starty;j--){
res[i][j]=count++;
}
for(;i>startx;i--){
res[i][j]=count++;
}
startx++;
starty++;
offset++;//自己写的时候这个漏了
}
if(n%2==1){
res[mid][mid]=count;
}
return res;
};
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
startx,starty=0,0
count=1
loop,mid=n//2,n//2 #注意这里是//
nums = [[0] * n for _ in range(n)] #学会这里的构造二维数组！
#通过列表推导式，在每次循环中生成一个长度为 n 的列表 [0, 0, 0, ..., 0]，一共生成 n 行，最终形成一个 n x n 的二维矩阵。
for offset in range(1,loop+1): #python中可以用for in结构
for j in range(starty,n-offset): #range(start, stop, step),
nums[startx][j]=count
count=count+1
for i in range(startx,n-offset):
nums[i][n-offset]=count #和C++里的逻辑不一样，j无固定值，不可写成nums[i][j]=count
count+=1
#start（可选）：序列的起始位置。默认是 0。
#stop：序列的结束位置（不包括 stop 本身）。
#step（可选）：序列中数字的增量，默认为 1。可以是正数或负数。
for j in range(n-offset,starty,-1):
nums[n-offset][j]=count
count+=1
for i in range(n-offset,startx,-1):
nums[i][startx]=count
count+=1
startx+=1
starty+=1
if n%2==1:
nums[mid][mid]=count
return nums
区间和
采用暴力解法会超时，来举一个极端的例子，如果查询m次，每次查询的范围都是从0 到 n - 1。
那么该算法的时间复杂度是 O(n * m) m 是查询的次数，如果查询次数非常大的话，这个时间复杂度也是非常大的。
引入前缀和
前缀和 在涉及计算区间和的问题时非常有用！
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,a,b;
cin>>n;
vector<int> vec(n);
vector<int> p(n);//前缀和
int sump=0;
for(int i=0;i<n;i++){
cin>>vec[i];
sump+=vec[i];
p[i]=sump;
}
while(cin>>a>>b){
cout<<p[b]-p[a-1]<<endl;
}
return 0;
}
注意这样不会每次都遍历计算区间，只需要将前缀进行相减即可
#python
import sys
input = sys.stdin.read
def main():
data = input().split()
n = int(data[0]) # 第一个数是数组的大小
vec = []
p = [0] * n # 前缀和数组
sump = 0
# 构建 vec 和前缀和数组 p
for i in range(n):
vec.append(int(data[i + 1]))
sump += vec[i]
p[i] = sump
index = n + 1 # 跳过前面 n 个数字
# 处理查询部分
while index < len(data):
a = int(data[index])
b = int(data[index + 1])
index += 2
if a == 0:
print(p[b])
else:
print(p[b] - p[a - 1])
if __name__ == "__main__":
main()
对于上述的数组，如果一开始没有为数组赋值,则不能直接操作vec[i]，否则会报错index out of range
此时应使用append()函数来向数组的末尾进行增加
vec=[]
vec.append(int(data[i + 1]))
或者在一开始就对数组进行初始化，确定其长度和具体的值
vec = [0] * n # 创建一个大小为 n 的列表，初始值为 0
vec[i] = int(data[i + 1])
开发商购买土地
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int sum=0;
//为所有土地赋值，并计算所有土地的和
vector<vector<int>> field(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>field[i][j];
sum+=field[i][j];
}
}
//计算前i行土地总和
vector<int> horizental(n,0);
vector<int> horizentalCut(n,0);
int sumH;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
horizental[i]+=field[i][j];
}
sumH+=horizental[i];//这里一开始写成了horizentalCut[i]+=horizental[i];其实并没有起到累加的作用
horizentalCut[i]=sumH;
}
//计算前j列土地的总和
vector<int> vertical(m,0);
vector<int> verticalCut(m,0);
int sumV;
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
vertical[j]+=field[i][j];
}
sumV+=vertical[j];
verticalCut[j]=sumV;
}
int res=INT_MAX;
//比较横向的分割最小值
for(int i=0;i<n-1;i++){
res=min(res,abs(sum-horizentalCut[i]-horizentalCut[i]));
}
//比较纵向的分割最小值
for(int j=0;j<m-1;j++){
res=min(res,abs(sum-verticalCut[j]-verticalCut[j]));
}
cout<<res<<endl;
}
一开始写的时候没有使得前i行（或前j列）土地和起到累加的作用
标签：count,59,nums,209,res,随想录,int,vector,vec From： https://www.cnblogs.com/VickyWu/p/18435918