扬中网站建设价格,360首页,电商代运营公司十强,重庆网站制作工作室目录
1. 移动数组中的元素
2. 搜索二维矩阵
3. 三角形最小路径和
#x1f31f; 每日一练刷题专栏 #x1f31f;
Golang 每日一练 专栏
C/C 每日一练 专栏
Python 每日一练 专栏
Java 每日一练 专栏 1. 移动数组中的元素
将一维数组中的元素循环左移 k 个位置
输入…
目录
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.lengthn matrix[i].length1 m, n 100-10^4 matrix[i][j], target 10^4
代码
#include stdio.h
#include stdlib.h
#include stdbool.hstatic 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(vectorint 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(vectorvectorint 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;vectorint 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()
{vectorvectorint 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 200triangle[0].length 1triangle[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(vectorvectorint triangle){int n triangle.size();if (n 0)return 0;if (n 1)return triangle[0][0];vectorvectorint info(n, vectorint(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;vectorvectorint 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 每日一练 专栏
