目錄
1. 移動(dòng)數(shù)組中的元素
2. 搜索二維矩陣
3.?三角形最小路徑和
???每日一練刷題專(zhuān)欄???
Golang 每日一練 專(zhuān)欄
C/C++ 每日一練 ?專(zhuān)欄
Python 每日一練 專(zhuān)欄
Java 每日一練 專(zhuān)欄
1. 移動(dòng)數(shù)組中的元素
將一維數(shù)組中的元素循環(huán)左移 k 個(gè)位置
輸入：
第 1 行是一維數(shù)組元素的個(gè)數(shù) n (數(shù)組大小)
第 2 行是一個(gè)整數(shù) k , 表示移動(dòng)的位置
下面 n 行為數(shù)組的元素個(gè)數(shù)
輸出：
輸出 n 行，表示移動(dòng)后的數(shù)字
代碼：
#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];
else
a[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. 搜索二維矩陣
編寫(xiě)一個(gè)高效的算法來(lái)判斷?m x n?矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：
- 每行中的整數(shù)從左到右按升序排列。
- 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。
示例 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.lengthn == matrix[i].length1 <= 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方便，代碼比較簡(jiǎn)潔，
#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;
else
high = mid;
}
if (high == len || nums[high] != target)
return -high - 1;
else
return 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.?三角形最小路徑和
給定一個(gè)三角形?triangle?，找出自頂向下的最小路徑和。
每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn)?在這里指的是?下標(biāo)?與?上一層結(jié)點(diǎn)下標(biāo)?相同或者等于?上一層結(jié)點(diǎn)下標(biāo) + 1?的兩個(gè)結(jié)點(diǎn)。也就是說(shuō)，如果正位于當(dāng)前行的下標(biāo)?i?，那么下一步可以移動(dòng)到下一行的下標(biāo)?i?或?i + 1?。
示例 1：
輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 輸出：11 解釋?zhuān)?/strong>如下面簡(jiǎn)圖所示： 2 3 4 6 5 7 4 1 8 3 自頂向下的最小路徑和為?11（即，2?+?3?+?5?+?1?= 11）。
示例 2：
輸入：triangle = [[-10]] 輸出：-10
提示：
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-10^4 <= triangle[i][j] <= 10^4
進(jìn)階：
- 你可以只使用?
O(n)?的額外空間（n?為三角形的總行數(shù)）來(lái)解決這個(gè)問(wè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
附錄
二分查找
又稱(chēng)折半查找、二分搜索、折半搜索等，是一種在靜態(tài)查找表中查找特定元素的算法。
所謂靜態(tài)查找表，即只能對(duì)表內(nèi)的元素做查找和讀取操作，不允許插入或刪除元素。
使用二分查找算法，必須保證查找表中存放的是有序序列（升序或者降序）。
存儲(chǔ)無(wú)序序列的靜態(tài)查找表，除非先對(duì)數(shù)據(jù)進(jìn)行排序，否則不能使用二分查找算法。?
???每日一練刷題專(zhuān)欄???
??持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！
???點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動(dòng)力！?
???收藏，你的青睞是我努力的方向！?
??評(píng)論，你的意見(jiàn)是我進(jìn)步的財(cái)富！??
 |
Golang 每日一練 專(zhuān)欄 |
|
|
C/C++ 每日一練 ?專(zhuān)欄 |
|
|
Python 每日一練 專(zhuān)欄 |
|
|
Java 每日一練 專(zhuān)欄 |
??
???文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-638359.html
?到了這里，關(guān)于C/C++每日一練(20230314) 移動(dòng)數(shù)組元素、搜索二維矩陣、三角形最小路徑和的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
