1. 约分
编写程序，要求用户输入一个分数，然后将其约分为最简式。如：
输入一个分数：8/12
最简分式：2/3
代码：
#include <stdio.h> #include <stdlib.h> int main() { int a, b, x, y, c; printf("输入一个分式："); scanf("%d/%d", &a, &b); if (a < b) { x = b; y = a; } else { x = a; y = b; } c = x % y; while (c) { x = y; y = c; c = x % y; } if (b / y != 1) printf("最简分式为：%d/%d", a / y, b / y); else printf("最简分式为：%d", a / y); return 0; }
输入输出：
输入一个分式：8/12
最简分式为：2/3
2. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
提示：
1 <= tokens.length <= 10^4
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int evalRPN(vector<string> &tokens) { stack<int> num; for (int i = 0; i < tokens.size(); ++i) { if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") { int j; int a = num.top(); num.pop(); int b = num.top(); num.pop(); if (tokens[i] == "+") j = b + a; else if (tokens[i] == "-") j = b - a; else if (tokens[i] == "*") j = b * a; else j = b / a; num.push(j); } else { num.push(stoi(tokens[i])); } } return num.top(); } }; int main() { Solution s; vector<string> tokens = {"2","1","+","3","*"}; cout << s.evalRPN(tokens) << endl; tokens = {"4","13","5","/","+"}; cout << s.evalRPN(tokens) << endl; tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"}; cout << s.evalRPN(tokens) << endl; return 0; }
输出：
9
6
22
3. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 10^4]内 -10^5 <= Node.val <= 10^5pos的值为-1或者链表中的一个有效索引
代码：
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow, *fast, *p; slow = fast = p = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { while (p != slow) { p = p->next; slow = slow->next; } return p; } } return nullptr; } }; ListNode* cycleLinkedList(vector<int>& nums, size_t pos) { if (nums.empty() || (int)pos == -1) return NULL; ListNode *head = new ListNode(nums[0]); ListNode *rear = head; ListNode *cyclePos = head; for (size_t i = 1; i < nums.size(); ++i) { rear->next = new ListNode(nums[i]); rear = rear->next; if (i == pos) cyclePos = rear; } if (cyclePos) rear->next = cyclePos; return head; } string LList2String(ListNode* head, int nodes = 10) { ListNode* curNode = head; int size = 0; string res = "["; while (curNode != NULL && size < nodes) { res += size++ > 0 ? "," : ""; res += to_string(curNode->val); curNode = curNode->next; } return res + "]"; } int main() { Solution s; vector<int> nums = {3,2,0,-4}; ListNode* head = cycleLinkedList(nums, 1); cout << LList2String(head) << endl; ListNode* ring = s.detectCycle(head); cout << LList2String(ring) << endl; nums = {1,2,3}; head = cycleLinkedList(nums, 0); cout << LList2String(head) << endl; ring = s.detectCycle(head); cout << LList2String(ring, 12) << endl; return 0; }
输出：
[3,2,0,-4,2,0,-4,2,0,-4]
[2,0,-4,2,0,-4,2,0,-4,2]
[1,2,3,1,2,3,1,2,3,1]
[1,2,3,1,2,3,1,2,3,1,2,3]
说明：
创建带环单链表：
ListNode* cycleLinkedList(vector<int>& nums, size_t pos)
遍历带环单链表：
因为遍历无限循环，所以设置默认遍历前10个节点：
string LList2String(ListNode* head, int nodes = 10)
