48days强训——day4
第一题：dd爱框框
链接：dd爱框框
题目描述 读入n，xn，xn，x,给出nnn个数a[1],a[2],……,a[n]a[1],a[2],……,a[n]a[1],a[2],……,a[n],求最小的区间[l,r][l,r][l,r]，使a[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥x，若存在相同长度区间，输出lll最小的那个 输入描述: 第一行两个数，n(1≤n≤10000000),x(1≤x≤10000) 第二行n个数a[i](1≤a[i]≤1000) 输出描述: 输出符合条件l,r(保证有解) 示例1 输入 10 20 1 1 6 10 9 3 3 5 3 7 输出 3 5
思路：这道题本质就是一道简单的滑动窗口。模拟注意细节即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
int left = 0, right = 0, begin = -1, sum = 0, ret = 0x3f3f3f3f;
while (right < n)
{
sum += arr[right];
while (sum >= x)
{
if (ret > right - left + 1)
{
ret = min(ret, right - left + 1);
begin = left;
}
sum -=arr[left++];
}
right++;
}
cout << begin+1 << " "<< begin + ret;
return 0;
}第二题：单词搜索
描述 给出一个二维字符数组和一个单词，判断单词是否在数组中出现， 单词由相邻单元格的字母连接而成，相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。 数据范围： 0 < 行长度 <= 100 0 < 列长度 <= 100 0 < 单词长度 <= 1000 例如： 给出的数组为["XYZE","SFZS","XDEE"]时， 对应的二维字符数组为：
若单词为"XYZZED"时，应该返回 true， 也即：
若单词为"SEE"时，应该返回 true， 也即： 若单词为"XYZY"时，应该返回 false。
示例1 输入： ["XYZE","SFZS","XDEE"],"XYZZED" 返回值： true 示例2 输入： ["XYZE","SFZS","XDEE"],"SEE" 返回值： true 示例3 输入： ["XYZE","SFZS","XDEE"],"XYZY" 返回值： false
题解： 深度优先搜索（DFS）在二维字符网格中查找单词。从每个起点出发，递归检查相邻单元格是否匹配单词的下一个字符，避免重复访问。若匹配到单词末尾则返回true。
代码：
#include <queue>
class Solution
{
public:
int m,n;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool vis[101][101] = {0};
bool dfs(vector<string>& board, string word,int a,int b,int pos)
{
if(pos == word.size()-1) return true;
vis[a][b] = true;
for(int i = 0; i < 4;i++)
{
int x = a + dx[i],y = b + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m &&!vis[x][y] && board[x][y] == word[pos + 1])
{
if(dfs(board,word,x,y,pos+1) == true) return true;
}
}
vis[a][b] = false;
return false;
}
bool exist(vector<string>& board, string word)
{
m = board[0].size(),n = board.size();
for(int i = 0;i < n;i++)
{
for(int j = 0; j < m;j++)
{
if(board[i][j] == word[0])
{
if(dfs(board,word,i,j,0) == true) return true;
}
}
}
return false;
}
};第三题：杨辉三角
描述 KiKi知道什么叫杨辉三角之后对杨辉三角产生了浓厚的兴趣，他想知道杨辉三角的前n行，请编程帮他解答。杨辉三角，本质上是二项式(a+b)的n次方展开后各项的系数排成的三角形。其性质包括：每行的端点数为1， 一个数也为1；每个数等于它左上方和上方的两数之和。 输入描述： 第一行包含一个整数数n。 (1≤n≤30) 输出描述： 包含n行，为杨辉三角的前n行，每个数输出域宽为5。 示例1 输入： 6 复输出： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
题解：进行模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int dp[31][31];
int main()
{
int n;
cin >> n;
dp[1][1] = 1;
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
cout << setw(5) << dp[i][j];
//printf("%5d", dp[i][j]);
}
printf("\n");
}
return 0;
}总结：
setw函数用于设置输出流的字段宽度，只影响下一个输出项，之后恢复默认宽度（0）。
腾讯云开发者
