CONTENTS
- LeetCode 166. 分数到小数（中等）
- LeetCode 167. 两数之和 II - 输入有序数组（中等）
- LeetCode 168. Excel 表列名称（简单）
- LeetCode 169. 多数元素（简单）
LeetCode 166. 分数到小数（中等）
【题目描述】
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回任意一个 。
对于所有给定的输入，保证答案字符串的长度小于 1 0 4 10^4 104。
【示例 1】
输入：numerator = 1, denominator = 2
输出："0.5"
【示例 2】
输入：numerator = 2, denominator = 1
输出："2"
【示例 3】
输入：numerator = 4, denominator = 333
输出："0.(012)"
【提示】
− 2 31 < = n u m e r a t o r , d e n o m i n a t o r < = 2 31 − 1 -2^{31} <= numerator, denominator <= 2^{31} - 1 −231<=numerator,denominator<=231−1
d e n o m i n a t o r ≠ 0 denominator \ne 0 denominator=0
【分析】
模拟高精度除法，如果在除的过程中重复出现了某个余数说明存在循环，可以用哈希表维护余数值及其所在的位数。
需要注意本题答案可能会爆 int，例如 − 2 31 / − 1 = 2 31 -2^{31} / -1 = 2^{31} −231/−1=231。
【代码】
class Solution {
public:string fractionToDecimal(int numerator, int denominator) {long long x = numerator, y = denominator;string res = "";unordered_map<int, int> st; // 余数及其对应的位数if ((x < 0) ^ (y < 0) && x) res += '-'; // 只有其中一个数为负数结果才为负，注意被除数可能为 0x = abs(x), y = abs(y);res += to_string(x / y), x %= y;while (x) {if (st.empty()) res += '.';st[x] = res.size(); // 记录每一位小数的位置x *= 10;res += to_string(x / y);x %= y; // 余数if (st.count(x)) { // 存在循环res.insert(res.begin() + st[x], '(');res.push_back(')');break;}}return res;}
};
LeetCode 167. 两数之和 II - 输入有序数组（中等）
【题目描述】
给你一个下标从 1 开始的整数数组 numbers，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2]，则 1 <= index1 < index2 <= numbers.length。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
【示例 1】
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
【示例 2】
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
【示例 3】
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
【提示】
2 < = n u m b e r s . l e n g t h < = 3 ∗ 1 0 4 2 <= numbers.length <= 3 * 10^4 2<=numbers.length<=3∗104
− 1000 < = n u m b e r s [ i ] < = 1000 -1000 <= numbers[i] <= 1000 −1000<=numbers[i]<=1000
numbers 按非递减顺序排列
− 1000 < = t a r g e t < = 1000 -1000 <= target <= 1000 −1000<=target<=1000
仅存在一个有效答案
【分析】
本题是双指针算法中的一道经典题（AcWing 800. 数组元素的目标和），我们用指针 i i i 从前往后遍历，对于每个 i i i，从右往左找到第一个满足 a i + a j ≤ t a r g e t a_i + a_j \le target ai+aj≤target 的指针 j j j，如果相等说明找到答案，否则 j j j 的左右都不可能是答案。
在遍历 i i i 的时候，当 i i i 向右移动到 i ′ i' i′ 时，其对应的 j ′ j' j′ 一定在 j j j 左边，如果在右边，那么通过 i ′ + j ′ ≤ t a r g e t i' + j' \le target i′+j′≤target 能够推导出 i + j ′ ≤ t a r g e t i + j' \le target i+j′≤target，这样 i i i 对应的 j j j 位置就产生了矛盾。因此 i i i 在往后走的时候 j j j 只能往左走，时间复杂度为 O ( n ) O(n) O(n)。
注意本题保证一定有解，如果可能无解需要在 while 和 if 的判断条件中加上 i < j。
【代码】
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {for (int i = 0, j = numbers.size() - 1; i < j; i++) {while (numbers[i] + numbers[j] > target) j--;if (numbers[i] + numbers[j] == target) return {i + 1, j + 1};}return {-1, -1}; // 一定不会执行}
};
LeetCode 168. Excel 表列名称（简单）
【题目描述】
给你一个整数 columnNumber，返回它在 Excel 表中相对应的列名称。
例如：
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
【示例 1】
输入：columnNumber = 1
输出："A"
【示例 2】
输入：columnNumber = 28
输出："AB"
【示例 3】
输入：columnNumber = 701
输出："ZY"
【示例 4】
输入：columnNumber = 2147483647
输出："FXSHRXW"
【提示】
1 < = c o l u m n N u m b e r < = 2 31 − 1 1 <= columnNumber <= 2^{31} - 1 1<=columnNumber<=231−1
【分析】
本题是个简单的找规律题，首先将 A ~ Z 看成 0 ~ 25，那么如果这个数在这个区间内就很容易映射。如果这个数大于 25 如何映射？只需要逐位判断即可，注意本题的编号从 1 开始，因此映射前需要先将当前值减一，直接来看个例子，假如 columnNumber = 701：
- 首先将当前值减一，然后求出第一位：
700 % 26 = 24 = 'Y'，将当前值除以 26：700 /= 26 = 26； - 继续将当前值减一，然后求出第二位：
25 % 26 = 25 = 'Z'，将当前值除以 26：25 /= 26 = 0； - 值变为 0，说明已求出每一位，最后结果即为
ZY。
【代码】
class Solution {
public:string convertToTitle(int columnNumber) {string res;while (columnNumber--) {res += columnNumber % 26 + 'A';columnNumber /= 26;}return string(res.rbegin(), res.rend());}
};
LeetCode 169. 多数元素（简单）
【题目描述】
给定一个大小为 n n n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n / 2 ⌋ \lfloor n / 2 \rfloor ⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
【示例 1】
输入：nums = [3,2,3]
输出：3
【示例 2】
输入：nums = [2,2,1,1,1,2,2]
输出：2
【提示】
n = = n u m s . l e n g t h n == nums.length n==nums.length
1 < = n < = 5 ∗ 1 0 4 1 <= n <= 5 * 10^4 1<=n<=5∗104
− 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 −109<=nums[i]<=109
【分析】
本题是个非常经典的题目，需要求出数组中出现次数比其他所有数加起来都多的那个数，最优解法不容易想出来，代码很简单但是思路很具有跳跃性。
解法是从前往后扫描，在扫描的过程中维护两个变量， r r r 表示当前存的数（可以理解为库存）， c c c 表示当前存的数的剩余数量。假设当前枚举的数为 x x x，若 x = r x = r x=r，则将 c c c 加一（当前数的库存多了一个），否则将 c c c 减一（取一个库存的数与 x x x 抵消），若 c c c 为零则将 r r r 设为 x x x，将 c c c 设为 1。扫描完最后 r r r 一定是那个最多的数。
因为只有两个数不同才会消耗库存，最多的那个数才有可能把其他所有数消耗完，并且其他所有数的数量还没有最多的那个数多，因此最后最多的那个数一定会剩余。
【代码】
class Solution {
public:int majorityElement(vector<int>& nums) {int r = 0, c = 0;for (int x: nums) {if (!c) r = x, c = 1;else if (x == r) c++;else c--;}return r;}
};