C/C++每日一练(20230314)

目录

1. 移动数组中的元素

2. 搜索二维矩阵

3. 三角形最小路径和

🌟 每日一练刷题专栏 🌟

Golang 每日一练 专栏

C/C++ 每日一练 ​专栏

Python 每日一练 专栏

Java 每日一练 专栏

---

1. 移动数组中的元素

将一维数组中的元素循环左移 k 个位置

输入：

第 1 行是一维数组元素的个数 n (数组大小)

第 2 行是一个整数 k , 表示移动的位置

下面 n 行为数组的元素个数

输出：

输出 n 行，表示移动后的数字

代码：

#include <stdio.h>
#define N 10000
int main()
{int k, a[N], b[N], n, t, w, i;scanf("%d", &n);scanf("%d", &k);for (i = 0; i < n; i++)scanf("%d", &a[i]);for (i = 0; i < k % n; i++)b[i] = a[i];for (i = 0; i < n; i++){if (i < n - k % n)a[i] = a[i + k % n];elsea[i] = b[i - n + k % n];}for (i = 0; i < n; i++)printf("%d\n", a[i]);return 0;
}

输入输出：

5
3
1 2 3 4 5
4
5
1
2
3

---

2. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>static int binary_search(int *nums, int len, int target)
{int low = -1;int high = len;while (low + 1 < high){int mid = low + (high - low) / 2;if (target > nums[mid]){low = mid;}else{high = mid;}}if (high == len || nums[high] != target){return -high - 1;}else{return high;}
}static bool searchMatrix(int **matrix, int matrixRowSize, int matrixColSize, int target)
{if (matrixRowSize == 0 || matrixColSize == 0){return false;}if (target < matrix[0][0] || target > matrix[matrixRowSize - 1][matrixColSize - 1]){return false;}int row = 0;int *nums = NULL;if (matrixRowSize > 0){nums = (int*)malloc(matrixRowSize * sizeof(int));for (row = 0; row < matrixRowSize; row++){nums[row] = matrix[row][0];}row = binary_search(nums, matrixRowSize, target);if (row >= 0){return true;}else{row = -row - 1;if (row == 0){return false;}else{row--;}}}int col = binary_search(matrix[row], matrixColSize, target);return col >= 0;
}int main()
{int row = 3;int col = 4;int target = 3;int **mat = (int**)malloc(row * sizeof(int *));mat[0] = (int*)malloc(col * sizeof(int));mat[0][0] = 1;mat[0][1] = 3;mat[0][2] = 5;mat[0][3] = 7;mat[1] = (int*)malloc(col * sizeof(int));mat[1][0] = 10;mat[1][1] = 11;mat[1][2] = 16;mat[1][3] = 20;mat[2] = (int*)malloc(col * sizeof(int));mat[2][0] = 23;mat[2][1] = 30;mat[2][2] = 34;mat[2][3] = 50;printf("%s\n", searchMatrix(mat, row, col, target) ? "true" : "false");return 0;
}

输出：

true

---

改为C++ 用vector方便，代码比较简洁，

#include <bits/stdc++.h>
using namespace std;int binary_search(vector<int> nums, int len, int target)
{int low = -1;int high = len;while (low + 1 < high) {int mid = low + (high - low) / 2;if (target > nums[mid])low = mid;elsehigh = mid;}if (high == len || nums[high] != target)return -high - 1;elsereturn high;
}bool searchMatrix(vector<vector<int>> matrix, int target)
{int matrixRowSize = matrix.size();int matrixColSize = matrix.front().size();if (matrixRowSize == 0 || matrixColSize == 0)return false;if (target < matrix.front().front() || target > matrix[matrixRowSize - 1][matrixColSize - 1])return false;int row = 0;vector<int> nums(matrixRowSize);if (matrixRowSize > 0) {for (row = 0; row < matrixRowSize; row++)nums[row] = matrix[row][0];row = binary_search(nums, matrixRowSize, target);if (row < 0) {row = -row - 1;if (row != 0) row--;else return false;} else return true;}int col = binary_search(matrix[row], matrixColSize, target);return col >= 0;
}int main()
{vector<vector<int>> matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};cout << (searchMatrix(matrix, 3) ? "true" : "false") << endl;cout << (searchMatrix(matrix, 13) ? "true" : "false") << endl;return 0;
}

---

3. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

进阶：

• 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

代码：

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:int minimumTotal(vector<vector<int>> &triangle){int n = triangle.size();if (n == 0)return 0;if (n == 1)return triangle[0][0];vector<vector<int>> info(n, vector<int>(n, 0));info[0][0] = triangle[0][0];for (int i = 1; i < n; ++i){for (int j = 0; j <= i; ++j){if (j == 0)info[i][j] = triangle[i][j] + info[i - 1][j];else if (j == i)info[i][j] = triangle[i][j] + info[i - 1][j - 1];else{int temp = info[i - 1][j] > info[i - 1][j - 1] ? info[i - 1][j - 1] : info[i - 1][j];info[i][j] = temp + triangle[i][j];}}}int res = info[n - 1][0];for (int i = 0; i < n; ++i){if (info[n - 1][i] < res){res = info[n - 1][i];}}return res;}
};int main()
{Solution s;vector<vector<int>> triangle = {{2},{3,4},{6,5,7},{4,1,8,3}};cout << s.minimumTotal(triangle) << endl;triangle = {{-10}};cout << s.minimumTotal(triangle) << endl;return 0;
}

输出：

11
-10

---

附录

二分查找

又称折半查找、二分搜索、折半搜索等，是一种在静态查找表中查找特定元素的算法。
所谓静态查找表，即只能对表内的元素做查找和读取操作，不允许插入或删除元素。

使用二分查找算法，必须保证查找表中存放的是有序序列（升序或者降序）。
存储无序序列的静态查找表，除非先对数据进行排序，否则不能使用二分查找算法。 

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

	Golang 每日一练 专栏
​​	C/C++ 每日一练 ​专栏
​​​	Python 每日一练 专栏
​	Java 每日一练 专栏