C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和

这篇具有很好参考价值的文章主要介绍了C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法

目录

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];
		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. 搜索二维矩阵

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

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

示例 1:

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法

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

示例 2:

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法

输入: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;
        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. 三角形最小路径和

给定一个三角形 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


附录

二分查找

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

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


🌟 每日一练刷题专栏 🌟

 持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

 评论,你的意见是我进步的财富!  

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法

Golang 每日一练 专栏

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法​​

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

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法​​​

Python 每日一练 专栏

C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和,刷题专栏,c语言,c++,算法文章来源地址https://www.toymoban.com/news/detail-638359.html

Java 每日一练 专栏

到了这里,关于C/C++每日一练(20230314) 移动数组元素、搜索二维矩阵、三角形最小路径和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是螺旋矩阵,使用【二维数组】这个基本的数据结构来实现 二维数组的结构特性入手 根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现,顺时针打印矩阵的顺序

    2024年02月06日
    浏览(50)
  • LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],

    2024年04月14日
    浏览(41)
  • 将一个二维数组的行元素和列元素互换,然后储存到另一个二维数组中(即进行矩阵的转置)。

    案例探究: 将一个二维数组的行元素和列元素互换, 然后储存到另一个二维数组中(即进行矩阵的转置)。 思路: 5        2        0        9                                                            5        3        10 3        7        12      6       

    2024年02月03日
    浏览(50)
  • Golang每日一练(leetDay0114) 矩阵中的最长递增路径、按要求补齐数组

    目录 329. 矩阵中的最长递增路径 Longest Increasing Path In A Matrix  🌟🌟 330. 按要求补齐数组 Patching Array  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定一个  m x n  整数矩阵  matrix  ,找出

    2024年02月12日
    浏览(47)
  • ( 数组和矩阵) 378. 有序矩阵中第 K 小的元素 ——【Leetcode每日一题】

    难度:中等 给你一个 n x n n x n n x n 矩阵 m a t r i x matrix ma t r i x ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。 你必须找到一个内存复杂度优于 O ( n 2 ) O(n^2) O ( n 2 ) 的解决方案。 示例 1:

    2024年02月14日
    浏览(57)
  • C语言-二维数组-求5*5矩阵的两条对角线之和,以及四周边界元素之和

    一.我的思路 (1)首先要用二维数组把数先存进去,再一想怎么存呢?我已经学了两种方法:第一就是进行数组初始化(比较单一),第二就是运用循环语句输入(也就是给数组赋值,求不同的数组很方便),我做的是题目中给了数组,我就采用了第一种。 (2)其次存完之后,就要想办

    2024年02月04日
    浏览(61)
  • (每日一练)MATLAB二维插值

    在前面介绍了学习MATLAB的一维插值方法,今天来学习MATLAB二维插值方法。         首先来看二维插值函数的使用格式:         其中x , y , z分别是我们给定的三个同维矩阵,x , y , z三者一 一对应构成我们需要的网格数据,x1,y1即是我们要插值点对应的坐标,z1是同维数

    2024年02月11日
    浏览(37)
  • C语言每日一练-Day1有一个3X4的矩阵,要求编程序求出其中值最大的呢个元素的值, 以及其所在的行号和列号。

     1.有一个3X4的矩阵,要求编程序求出其中值最大的呢个元素的值, 以及其所在的行号和列号。    2.将一个二维数组行和列的元素互换,存到另一个二维数组中 3.有10个地区的面积,要求对他们按小到大的顺序排序 1.for循环: for(a:b:c){         语句块 } a:起始条件   b:判断循

    2024年02月14日
    浏览(46)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

    64. 最小路径和 - 力扣(LeetCode) 描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→

    2024年04月23日
    浏览(37)
  • Python每日一练(20230506) 存在重复元素I、II、III

    目录 1. 存在重复元素 Contains Duplicate I 2. 存在重复元素 Contains Duplicate II 3. 存在重复元素 Contains Duplicate III 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个整数数组  nums  。如果任一值在数组中出现  至少两次

    2024年02月03日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包