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

简介: C/C++每日一练(20230420)

1. 存在重复元素 II


给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i j,使得 nums [i] = nums [j],并且 ij 的差的 绝对值 至多为 k


示例 1:

输入: nums = [1,2,3,1], k = 3

输出: true


示例 2:

输入: nums = [1,0,1,1], k = 1

输出: true


示例 3:

输入: nums = [1,2,3,1,2,3], k = 2

输出: false


出处:

https://edu.csdn.net/practice/26046521

代码:

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool containsNearbyDuplicate(vector<int> &nums, int k)
    {
        int n = nums.size(), idx = 0;
        unordered_map<int, int> nmap;
        for (int i = 0; i < n; ++i)
        {
            auto iter = nmap.find(nums[i]);
            if (iter != nmap.end())
            {
                if (i - iter->second <= k)
                    return true;
                else
                    iter->second = i;
            }
            else
                nmap[nums[i]] = i;
        }
        return false;
    }
};
int main()
{
  Solution s;
    vector<int> nums = {1,2,3,1};
  cout << (s.containsNearbyDuplicate(nums, 3) ? "true" : "false") << endl;
  nums = {1,0,1,1};
  cout << (s.containsNearbyDuplicate(nums, 1) ? "true" : "false") << endl;
  nums = {1,2,3,1,2,3};
  cout << (s.containsNearbyDuplicate(nums, 2) ? "true" : "false") << endl;
  return 0;
}

输出:

true

true

false


2. 外观数列


给定一个正整数 n ,输出外观数列的第 n 项。


「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。


你可以将其视作是由递归公式定义的数字字符串序列:


   countAndSay(1) = "1"

   countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。

前五项如下:


1.     1

2.     11

3.     21

4.     1211

5.     111221

第一项是数字 1  


描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"

描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"

描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"

描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"

要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。


例如,数字字符串 "3322251" 的描述如下图:


23bfeaec5ed390ee12e4ab4f6bd7da5a.jpeg


示例 1:

输入:n = 1

输出:"1"

解释:这是一个基本样例。


示例 2:

输入:n = 4

输出:"1211"


解释:

countAndSay(1) = "1"

countAndSay(2) = 读 "1" = 一 个 1 = "11"

countAndSay(3) = 读 "11" = 二 个 1 = "21"

countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示:

   1 <= n <= 30

以下程序实现了这一功能,请你填补空白处内容:

```c++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void parse(char *input, char *output)
{
    char *p = input;
    char *q = output;
    while (*p != '\0')
    {
        int count = 1;
        while (p[0] == p[1])
        {
            count++;
            p++;
        }
        int n = 0;
        while (count > 0)
        {
            n += count % 10;
            count /= 10;
        }
        ____________________;
        *q++ = p[0];
        p++;
    }
    *q = '\0';
}
static char *countAndSay(int n)
{
    if (n < 1)
    {
        return NULL;
    }
    char *result;
    char *prev = malloc(10000);
    char *next = malloc(10000);
    strcpy(prev, "1");
    if (n == 1)
    {
        return prev;
    }
    int i;
    for (i = 2; i <= n; i++)
    {
        if (i & 0x1)
        {
            parse(next, prev);
            result = prev;
        }
        else
        {
            parse(prev, next);
            result = next;
        }
    }
    return result;
}
int main(int argc, char **argv)
{
    if (argc != 2)
    {
        fprintf(stderr, "Usage: ./test n\n");
        exit(-1);
    }
    printf("%s\n", countAndSay(atoi(argv[1])));
    return 0;
}
```


出处:

https://edu.csdn.net/practice/26046522

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void parse(char *input, char *output)
{
    char *p = input;
    char *q = output;
    while (*p != '\0')
    {
        int count = 1;
        while (p[0] == p[1])
        {
            count++;
            p++;
        }
        int n = 0;
        while (count > 0)
        {
            n += count % 10;
            count /= 10;
        }
    while (n > 0)
    {
        *q++ = (n % 10) + '0';
        n /= 10;
    }
        *q++ = p[0];
        p++;
    }
    *q = '\0';
}
static char *countAndSay(int n)
{
    if (n < 1)
    {
        return NULL;
    }
    char *result;
    char *prev = (char*)malloc(10000);
    char *next = (char*)malloc(10000);
    strcpy(prev, "1");
    if (n == 1)
    {
        return prev;
    }
    int i;
    for (i = 2; i <= n; i++)
    {
        if (i & 0x1)
        {
            parse(next, prev);
            result = prev;
        }
        else
        {
            parse(prev, next);
            result = next;
        }
    }
    return result;
}
int main()
{
    printf("%s\n", countAndSay(1));
    printf("%s\n", countAndSay(4));
    return 0;
}

输出:

1

1211


3. 最优路线


题目描述

探险队要穿越泥潭,必须选择可踩踏的落脚点。可是泥潭面积很大,落脚点又实在少得可怜,一不小心就会深陷泥潭而无法脱身。侦查员费尽周折才从老乡手里弄到了一份地图,图中标出了落脚点的位置,而且令人震惊的是:泥潭只有一条穿越路线,且对于 n×m 的地图,路线长度为 n+m-1!请编程为探险队找出穿越路线。


输入描述

两个整数 n 和 m,表示泥潭的长和宽。下面 n 行 m 列表示地形(0 表示泥潭,1 表示落脚点)

输出描述

用坐标表示穿越路线,坐标之间用 > 分隔

样例输入

6 9
1 1 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1


样例输出

(1,1)>(1,2)>(1,3)>(2,3)>(2,4)>(2,5)>(3,5)>(4,5)>(4,6)>(5,6)>(5,7)>(5,8)>(5,9)>(6,9)


出处:

https://edu.csdn.net/practice/26046523

代码:

#include <stdio.h>
#include <string.h>
const int N = 101;
int map[N][N];
int n, m;
struct point
{
    int l, r;
} node[N];
int ans;
void DFS(int x, int y)
{
    if (x == n && y == m)
    {
        for (int i = 1; i < ans; i++)
            printf("(%d,%d)>", node[i].l, node[i].r);
        printf("(%d,%d)\n", x, y);
    }
    else
    {
        if (map[x][y] == 1 && x <= n && y <= m)
        {
            node[ans].l = x;
            node[ans].r = y;
            ans++;
            DFS(x + 1, y);
            DFS(x, y + 1);
        }
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        ans = 1;
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &map[i][j]);
        DFS(1, 1);
    }
    return 0;
}


输出:

6 9 ↙

1 1 1 0 0 0 0 0 0↙

0 0 1 1 1 0 0 0 0↙

0 0 0 0 1 0 0 0 0↙

0 0 0 0 1 1 0 0 0↙

0 0 0 0 0 1 1 1 1↙

0 0 0 0 0 0 0 0 1↙

(1,1)>(1,2)>(1,3)>(2,3)>(2,4)>(2,5)>(3,5)>(4,5)>(4,6)>(5,6)>(5,7)>(5,8)>(5,9)>(6,9)

^Z↙ (输入Ctrl+Z,回车退出)


目录
相关文章
|
6月前
|
Linux 监控 Ubuntu
Linux 终端操作命令(1)
Linux 终端操作命令(1)
98 1
Linux 终端操作命令(1)
|
6月前
|
算法 Java Go
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
47 1
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
|
6月前
|
Linux 监控 Shell
Linux 终端命令之文件浏览(4) head, tail
Linux 终端命令之文件浏览(4) head, tail
58 0
Linux 终端命令之文件浏览(4) head, tail
|
6月前
|
Shell Linux 机器学习/深度学习
Linux 终端操作命令(3)内部命令用法
Linux 终端操作命令(3)内部命令用法
88 0
Linux 终端操作命令(3)内部命令用法
|
6月前
|
Python Linux Ubuntu
Linux系统部署Python语言开发运行环境
Linux系统部署Python语言开发运行环境
220 0
Linux系统部署Python语言开发运行环境
|
6月前
|
Go Unix 开发者
Go语言time库,时间和日期相关的操作方法
Go语言time库,时间和日期相关的操作方法
101 0
Go语言time库,时间和日期相关的操作方法
|
6月前
|
C++ 存储 Serverless
力扣C++|一题多解之数学题专场(2)
力扣C++|一题多解之数学题专场(2)
49 0
力扣C++|一题多解之数学题专场(2)
|
6月前
|
Go 机器学习/深度学习 Rust
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
87 0
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
|
6月前
|
Java Go C++
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
64 0
Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列
|
6月前
|
Java Go C++
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort
57 0
Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort