C/C++每日一练(20230329)
C++ 每日
2023-09-14 09:01:29 时间
目录
2. 柱状图中最大的矩形 🌟🌟🌟
3. 解数独 🌟🌟🌟
1. 求前n个素数之和
题目描述
求前n个素数的和。
例如，前5个素数是2、3、5、7、11，它们的和是28。
输入
一个整数n，1<=n<=1000。
输出
前n个素数的和
样例输入
5样例输出
28提示
第1000个素数是7919。
出处：
https://edu.csdn.net/practice/24062031
代码：
#include <iostream>
using namespace std;
int main()
{
int n, i, j, sum, a;
cin >> n;
a = 0;
i = 2;
sum = 0;
while (a < n)
{
for (j = 2; j <= i; j++)
if (i % j == 0)
break;
if (j == i)
{
sum += i;
++a;
}
++i;
}
cout << sum;
}输入输出：
5
28
1000
3682913
2. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3] 输出: 10
出处：
https://edu.csdn.net/practice/24062032
代码：
#include <stdio.h>
#include <stdlib.h>
static int largestRectangleArea(int *heights, int heightsSize)
{
int *indexes = (int*)malloc(heightsSize * sizeof(int));
int *left = (int*)malloc(heightsSize * sizeof(int));
int *right = (int*)malloc(heightsSize * sizeof(int));
int i, pos = 0;
for (i = 0; i < heightsSize; i++)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
left[i] = pos == 0 ? -1 : indexes[pos - 1];
indexes[pos++] = i;
}
pos = 0;
for (i = heightsSize - 1; i >= 0; i--)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
right[i] = pos == 0 ? heightsSize : indexes[pos - 1];
indexes[pos++] = i;
}
int max_area = 0;
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i] - 1);
max_area = area > max_area ? area : max_area;
}
return max_area;
}
int main(void)
{
int nums[] = {2, 1, 5, 6, 2, 3};
int count = sizeof(nums) / sizeof(*nums);
printf("%d\n", largestRectangleArea(nums, count));
return 0;
}输出：
10
3. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
输入：board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] 输出： [["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"], ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
出处：
https://edu.csdn.net/practice/24062033
代码：
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
void solveSudoku(vector<vector<char>> &board)
{
int size = board.size();
vector<vector<bool>> rows(size, vector<bool>(10));
vector<vector<bool>> cols(size, vector<bool>(10));
vector<vector<bool>> boxes(size, vector<bool>(10));
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (board[i][j] != '.')
{
int num = board[i][j] - '0';
int idx = i / 3 * 3 + j / 3;
rows[i][num] = true;
cols[j][num] = true;
boxes[idx][num] = true;
}
}
}
dfs(board, 0, rows, cols, boxes);
}
private:
bool valid(int num, int row, int col, int idx, vector<vector<bool>> &rows,
vector<vector<bool>> &cols, vector<vector<bool>> &boxes)
{
return !rows[row][num] && !cols[col][num] && !boxes[idx][num];
}
bool dfs(vector<vector<char>> &board, int size, vector<vector<bool>> &rows,
vector<vector<bool>> &cols, vector<vector<bool>> &boxes)
{
if (size == 9 * 9)
{
return true;
}
else
{
bool ok = false;
int row = size / 9;
int col = size % 9;
int idx = row / 3 * 3 + col / 3;
if (board[row][col] == '.')
{
for (int i = 1; i <= 9; i++)
{
if (valid(i, row, col, idx, rows, cols, boxes))
{
board[row][col] = i + '0';
rows[row][i] = true;
cols[col][i] = true;
boxes[idx][i] = true;
ok = dfs(board, size + 1, rows, cols, boxes);
if (!ok)
{
rows[row][i] = false;
cols[col][i] = false;
boxes[idx][i] = false;
board[row][col] = '.';
}
}
}
}
else
{
ok = dfs(board, size + 1, rows, cols, boxes);
}
return ok;
}
}
};
int main(void)
{
vector<vector<char>> board = {
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'}};
Solution s;
s.solveSudoku(board);
for(auto row: board){
for (auto col: row)
cout << col << " ";
cout << endl;
}
return 0;
}输出：
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 | Golang每日一练 专栏 |
 | Python每日一练 专栏 |
 | C/C++每日一练 专栏 |
 | Java每日一练 专栏 |
相关文章
- （C++）关于i++和i++的左值、右值问题
- 转--C++学习笔记（原创）
- C/C++每日一练(20230418)
- C/C++每日一练(20230417)
- C/C++每日一练(20230330)
- C/C++每日一练(20230318)
- C/C++每日一练(20230223)
- C/C++每日一练(20230222)
- C/C++每日一练(20230313)
- C/C++每日一练(20230307)
- C/C++每日一练(20230305)
- C/C++每日一练(20230304)
- C/C++基础讲解(二十三)之数据结构篇之魔王语言翻译与火车车厢重排
- 【转】三种方式在C++中调用matlab
- paip.c++ bcb string 转换操作大总结.
- CV之OpenCV：HALCON机器视觉软件简介&OpenCV的基础概念、常用案例(打开图片/摄像头/视频)、常用函数解释大全(C++/python语言)之详细攻略
- 有效的括号(C++)
- 【华为OD机试 2023】 优选核酸检测点（C++ Java JavaScript Python）
- c/c++每日面试之练习链表
- C++每日面试之算法训练 寻找数组中最大值
- C++每日面试之求数组的众数
- C++每日扎心结构体之初始化导致的一次异常崩溃。
- websocket c++ example
- VC++一文带你搞懂如何操作文件对话框（附源码）
- PAT 1124 C++版
- 【图像处理OpenCV(C++版)】——4.5 全局直方图均衡化
- 全面介绍Windows内存管理机制及C++内存分配实例