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 <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" 的描述如下图：
示例 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 <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，回车退出)
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
