1. 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。
出处：
https://edu.csdn.net/practice/23951838
代码1： 快慢指针
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: bool hasCycle(ListNode *head) { ListNode *faster = head; ListNode *slower = head; if (head == NULL) return false; while (faster != NULL && faster->next != NULL) { faster = faster->next->next; slower = slower->next; if (faster == slower) return true; } return false; } }; ListNode* createRingNodeList(vector<int> nums, int pos = -1) { if (nums.empty()) return nullptr; ListNode *head = new ListNode(nums[0]); ListNode *tail = head; for (int i = 1; i < nums.size(); i++) { tail->next = new ListNode(nums[i]); tail = tail->next; } if (pos >= 0) { ListNode *p = head; while (pos--) { // 找到尾指针指向的位置 p = p->next; } tail->next = p; // 构成环 } return head; } int main() { Solution s; vector<int> nums = {3,2,0,-4}; /* 不用函数的创建： ListNode *head = new ListNode(3); head->next = new ListNode(2); head->next->next = new ListNode(0); head->next->next->next = new ListNode(-4); head->next->next->next->next = head->next; */ ListNode* head = createRingNodeList(nums, 1); cout << (s.hasCycle(head) ? "true" : "false") << endl; nums = {1,2}; head = createRingNodeList(nums, 0); cout << (s.hasCycle(head) ? "true" : "false") << endl; nums = {1}; head = createRingNodeList(nums, -1); cout << (s.hasCycle(head) ? "true" : "false") << endl; return 0; }
输出：
true
true
false
代码2： 哈希表
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: bool hasCycle(ListNode *head) { unordered_set<ListNode*> s; while (head != nullptr) { if (s.count(head) != 0) { // 如果当前节点已经在哈希表中，则说明形成了环 return true; } s.insert(head); head = head->next; } return false; } }; ListNode* createRingNodeList(vector<int> nums, int pos = -1) { if (nums.empty()) return nullptr; ListNode *head = new ListNode(nums[0]); ListNode *tail = head; for (int i = 1; i < nums.size(); i++) { tail->next = new ListNode(nums[i]); tail = tail->next; } if (pos >= 0) { ListNode *p = head; while (pos--) { // 找到尾指针指向的位置 p = p->next; } tail->next = p; // 构成环 } return head; } int main() { Solution s; vector<int> nums = {3,2,0,-4}; ListNode* head = createRingNodeList(nums, 1); cout << (s.hasCycle(head) ? "true" : "false") << endl; nums = {1,2}; head = createRingNodeList(nums, 0); cout << (s.hasCycle(head) ? "true" : "false") << endl; nums = {1}; head = createRingNodeList(nums, -1); cout << (s.hasCycle(head) ? "true" : "false") << endl; return 0; }
2. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9
出处：
https://edu.csdn.net/practice/23951839
原题代码：
#include <stdio.h> #include <stdlib.h> static int uniquePaths(int m, int n) { int row, col; int *grids = (int*)malloc(m * n * sizeof(int)); for (col = 0; col < m; col++) { grids[col] = 1; } for (row = 0; row < n; row++) { grids[row * m] = 1; } for (row = 1; row < n; row++) { for (col = 1; col < m; col++) { grids[row * m + col] = grids[row * m + col - 1] + grids[(row - 1) * m + col]; } } return grids[m * n - 1]; } int main() { printf("%d\n", uniquePaths(3, 7)); printf("%d\n", uniquePaths(3, 2)); printf("%d\n", uniquePaths(7, 3)); printf("%d\n", uniquePaths(3, 3)); return 0; }
输出：
28
3
28
6
C++代码：
方法一：动态规划
可以使用动态规划来求解，定义一个二维数组 dp，其中 dp[i][j] 表示从起点 (0,0) 到达位置 (i, j) 的不同路径数目。由于机器人只能向下或向右移动，因此到达位置 (i, j) 的路径数目只能从位置 (i-1, j) 或 (i, j-1) 转移而来，即： dp[i][j]=dp[i-1][j]+dp[i][j-1]
同时，对于第一行和第一列上的位置，由于它们只能由上方或左方转移而来，因此它们的 $dp$ 值均为 1。最终，到达右下角的路径数即为 dp[m-1][n-1]。
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m; i++) { // 处理第一列的情况 dp[i][0] = 1; } for (int j = 0; j < n; j++) { // 处理第一行的情况 dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } };
方法二：组合
可以使用组合数学来求解，从起点 (0,0) 到达终点 (m-1,n-1)，需要向下走m-1步，向右走n-1 步，因此总共需要走 m+n-2 步。在这 m+n-2 步中，向下走的步数有 m-1 步，向右走的步数有 n-1 步，因此总共不同的路径总数为：
。
class Solution { public: int uniquePaths(int m, int n) { long long res = 1; for (int i = 1; i <= m-1; i++) { res = res * (n-1+i) / i; } return res; } };
方法三：递归+记忆化搜索
可以使用递归+记忆化搜索的方法来求解，定义一个二维数组 memo，其中 memo[i][j] 表示从位置 $(i,j)$ 到达右下角的不同路径数目。递归函数 dfs(i,j) 表示从位置 (i,j) 到达右下角的不同路径数目，它可以从位置 (i+1,j) 或 (i,j+1) 转移而来，即：
对于边界情况，当 i=m-1 或 j=n-1 时，位置 (i,j) 已经到达右下角，此时路径数目为1。
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> memo(m, vector<int>(n, -1)); return dfs(0, 0, m, n, memo); } int dfs(int i, int j, int m, int n, vector<vector<int>>& memo) { if (i == m-1 || j == n-1) { return 1; } if (memo[i][j] != -1) { return memo[i][j]; } int res = dfs(i+1, j, m, n, memo) + dfs(i, j+1, m, n, memo); memo[i][j] = res; return res; } };
3. 字母表位置索引
描述：从键盘输入任意一个大写英文字母，要求它在26个字母表中的位置和其后面的第四个字母
例如：程序运行
输入：B<回车>。
输出：B在第2个位置，其后面第四个字母是F。
出处：
https://edu.csdn.net/practice/23951840
代码：
#include <stdio.h> int main() { char c, c2; printf("输入:"); c = getchar(); int m = 0, n = 0; if (c >= 'A' && c <= 'z') { m = c - 'A' + 1; if (m < 23) { c2 = c + 4; n = m + 4; } } if (n > 0) printf("%c在第%d个位置,其后面第四个字母是%c\n", c, m, c2); else printf("%c在第%d个位置,其后面没有第四个字母\n", c, m); return 0; }
输入输出：
输入:B
B在第2个位置,其后面第四个字母是F
输入:V
V在第22个位置,其后面第四个字母是Z
输入:W
W在第23个位置,其后面没有第四个字母
