目录

1. 存在重复元素 II

2. 外观数列

3. 最优路线

每日一练刷题专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 存在重复元素 II

给定一个整数数组和一个整数k，判断数组中是否存在两个不同的索引i和j，使得nums [i] = nums [j]，并且i和j的差的绝对值至多为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 using namespace std;class Solution{public:bool containsNearbyDuplicate(vector &nums, int k){int n = nums.size(), idx = 0;unordered_map nmap;for (int i = 0; i second second = i;}elsenmap[nums[i]] = i;}return false;}};int main(){Solution s;vector nums = {1,2,3,1};cout <

输出：

true
true
false

2. 外观数列

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

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

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

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

前五项如下：

1. 12. 113. 214. 12115. 111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

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

例如，数字字符串"3322251"的描述如下图：

示例 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
#include
#include
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 #include #include 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 91 1 1 0 0 0 0 0 00 0 1 1 1 0 0 0 00 0 0 0 1 0 0 0 00 0 0 0 1 1 0 0 00 0 0 0 0 1 1 1 10 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 #include 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 ", 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，回车退出)

每日一练刷题专栏

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

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

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

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

☸主页：https://hannyang.blog.csdn.net/

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏