// O(n^2)，稳定，从后往前遍历时发现逆序即立刻交换 void bubbleSort(vector<int> &ivec){ int len = ivec.size(); for(int i = 0; i < len; ++i) for(int j = 0; j < len - i - 1; ++j) if(ivec[j] > ivec[j + 1]) swap(ivec[j], ivec[j + 1]); }

// O(n^2)，不稳定，第i次遍历时，选择下标[i, n)中数值最小的数放在i处 void selectionSort(vector<int> &ivec){ int len = ivec.size(); for(int i = 0; i < len; ++i){ int minIdx = i; for(int j = i + 1; j < len; ++j) if(ivec[j] < ivec[i]) minIdx = j; swap(ivec[i], ivec[minIdx]); } }

// O(n^2)，稳定，遍历第i个数时，一直将它往前交换直到不再比前一个数更大 void insertionSort(vector<int> &ivec){ for(int i = 1; i < ivec.size(); ++i){ int j = i - 1; while(j >= 0 && ivec[j + 1] < ivec[j]) swap(ivec[j + 1], ivec[j]),	--j; } }

// O(nlogn)，稳定，不断分成更小的数组进行归并 void merge(vector<int> &ivec, int low, int mid, int high){ vector<int> helper; int L = low, R = mid + 1; while(L <= mid && R <= high) ivec[L] < ivec[R] ? helper.push_back(ivec[L++]) : helper.push_back(ivec[R++]); while(L <= mid) helper.push_back(ivec[L++]); while(R <= high) helper.push_back(ivec[R++]); for(int i = low; i <= high; ++i) ivec[i] = helper[i - low]; } void mergeSort(vector<int> &ivec, int low, int high){ if(low >= high) return; int mid = (high - low) / 2 + low; mergeSort(ivec, low, mid); mergeSort(ivec, mid + 1, high); merge(ivec, low, mid, high); } // 排序入口 void mergeSort(vector<int> &ivec){ mergeSort(ivec, 0, ivec.size() - 1); }

//O(nlogn)，不稳定，找到第i个数，使[0,i)中均比它小且(i,n)中均比它大，再对[0,i)和(i,n)进行快排 void quickSort(vector<int> &ivec, int low, int high){ if(low >= high) return; // 找到pivot_value满足上述条件 int pivot_value = ivec[low]; int pivot = low; for(int i = low + 1; i <= high; ++i) if(ivec[i] < pivot_value){ ++pivot; swap(ivec[i], ivec[pivot]);	} swap(ivec[low], ivec[pivot]); // 对[i,pivot),(pivot, n)继续快排 quickSort(ivec, low, pivot - 1); quickSort(ivec, pivot + 1, high); } // 排序入口 void quickSort(vector<int> &ivec){ quickSort(ivec, 0, ivec.size() - 1); }

// 自己网上找资料看吧 void heapDown(vector<int> &ivec, int beg, int end){// 调整 ivec[beg...end] 使之满足大顶堆要求 for(int cur = beg, child = beg * 2 + 1; child <= end; cur = child, child = child * 2 + 1){ if(child < end && ivec[child] < ivec[child + 1]) ++child; if(ivec[cur] > ivec[child])// 调整父节点和子节点的关系 break; else swap(ivec[cur], ivec[child]); } } // 排序入口 void heapSort(vector<int> &ivec){ // 构造大顶堆 for(int i = ivec.size() / 2 - 1; i >= 0; --i) heapDown(ivec, i, ivec.size() - 1); // 交换堆顶元素，并再次调整为大顶堆 for(int i = ivec.size() - 1; i > 0; --i){ swap(ivec[0], ivec[i]); heapDown(ivec, 0, i - 1); } }

// 思路1：利用堆排序，第K次弹出大顶堆的堆顶即为第K大的元素。其中heapDown函数见堆排序 int findKthLargest(vector<int>& nums, int k) { // 构造大顶堆 for(int i = nums.size() / 2 - 1; i >= 0; --i) heapDown(nums, i, nums.size() - 1); // 前k-1次换到数组末尾后，堆顶nums[0]即为第k大 int cnt = 0; while(++cnt < k){// 注意：条件 (++cnt < k) 进行 k-1 次操作， (cnt++ < k) 进行 k 次操作 swap(nums[0], nums[nums.size() - cnt]); heapDown(nums, 0, nums.size() - cnt - 1); } return nums[0]; // k-1次操作之后的堆顶即为第k大的元素 } // 思路2：利用快速排序，找到第k-1个枢点，此时0~k-1是最小的k个值 // 枢点pivot<k => 搜索[pivot+1, high]。 枢点pivot>k => 搜索[left, pivot-1] // 此方法的渐进时间复杂度理论上是log(n)

// 思路：在归并排序的过程中对逆序对进行统计 int InversePairs(vector<int> nums) { int cnt = 0; mergeCount(nums, 0, nums.size() - 1, cnt); return cnt; } void mergeCount(vector<int> &nums, int left, int right, int &cnt){ if(left >= right) return; int mid = (right - left) / 2 + left; mergeCount(nums, left, mid, cnt); mergeCount(nums, mid + 1, right, cnt); merge(nums, left, mid, right, cnt); } void merge(vector<int> &nums, int left, int mid, int right, int &cnt){ vector<int> tmp; int l = left, r = mid + 1; while(l <= mid && r <= right) if(nums[l] <= nums[r]) tmp.push_back(nums[l++]); else{ cnt = (cnt + mid - l + 1) % 1000000007; tmp.push_back(nums[r++]); } while(l <= mid) tmp.push_back(nums[l++]); while(r <= right) tmp.push_back(nums[r++]); for(int i = left; i <= right; ++i) nums[i] = tmp[i - left]; }

// 思路1: 先进行排序，然后交换1-2, 3-4, 5-6 ==> O(nlogn) void wiggleSort(vector<int> &nums) { sort(nums.begin(), nums.end()); if(nums.size() <= 2) return; for(int i = 2; i < nums.size(); i += 2) swap(nums[i], nums[i - 1]); } // 思路：由题意的，下标为奇数的大于等于两侧，下标为偶数的小于等于两侧，不满足的话将该数与左侧交换即可 O(n) void wiggleSort(vector<int> &nums){ if(nums.size() <= 1) return; for(int i = 1; i < nums.size(); ++i) if((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) swap(nums[i], nums[i - 1]); }

// 思路：先进行排序，不能交换相互挨着的两个数，可能相等 //	将排序后的数组分为前后两半，分别从前半部分和后半部分取出最后一个数，可以保证不等 void wiggleSort(vector<int>& nums) { vector<int> temp = nums; sort(temp.begin(), temp.end()); // left_back取中间，right_back取末尾 int left_back = (nums.size() % 2 == 1) ? nums.size() / 2 : nums.size() / 2 - 1; int right_back = nums.size() - 1; for(int i = 0; i < nums.size(); ++i) nums[i] = (i % 2 == 0) ? temp[left_back--] : temp[right_back--]; }

int mySqrt(int x) { if(x <= 1) return x; int low = 1, high = x; while(low <= high){ int mid = (high - low) / 2 + low; if(x / mid == mid) return mid; else if(x / mid < mid) high = mid - 1; else low = mid + 1; } return high; }

bool isPerfectSquare(int num) { if(num < 1) return false; int low = 1, high = num; while(low <= high){ int mid = (high - low) / 2 + low; if(num / mid == mid && num % mid == 0) return true; else if(num / mid < mid) high = mid - 1; else low = mid + 1; } return false; }

int arrangeCoins(int n) { if(n < 1) return 0; int low = 1, high = n; while(low <= high){ int mid = (high - low) / 2 + low; long long total = (mid + 1) * (long long)mid / 2; if(total == n) return mid; else if(total < n) low = mid + 1; else high = mid - 1; } return high; }

// 思路：对x依次做1,2,4,...次幂，得到x, x*x, x*x*x*x，直到指数次数为不大于n的最大值 // 保存x*x*x*x...，并从n中减去该指数次数 // 重复操作，将所有x*x...连续乘起来即为所求 double myPow(double x, int n) { bool sign = n < 0; long long exp = abs((long long)n); // 先转化为longlong再abs，防止出现n=INT_MIN double res = 1.0; while(exp > 0){ long long e = 1;// 指数 1 -> 2 -> 4 ... double mul = x; // 结果 x -> x*x -> x*x*x*x ... while((e*2) < exp){ // 直到e*2仍小于exp e = e << 1; mul = mul * mul; } exp -= e; res *= mul; } return sign ? 1.0/res : res; }

// 思路：二分搜索num+0.5，num-0.5的位置，它们区间内个数即为所求 int biSearch(const vector<int> &data, double num){ // 对数组data = 1 2 3a 3b 3c 4 4 5 // num = 2.5 -> 返回2所在下标 // num = 3.5 -> 返回3c所在下标 int low = 0, high = data.size() - 1; while(low <= high){ int mid = (high - low) / 2 + low; if(data[mid] < num) low = mid + 1; else high = mid - 1; } return high; } int GetNumberOfK(vector<int> data ,int k) { return biSearch(data, k + 0.5) - biSearch(data, k - 0.5); }

// 思路：采用二分查找法，left = 0, right = nums.size() - 1为起点 // nums[mid] < nums[mid + 1]，局部上升，右侧必然有峰值 (注意，mid+1必然是存在的, mid-1不一定) // nums[mid] > nums[mid + 1]，局部下降，左侧必然有峰值 int findPeakElement(vector<int>& nums) { int left = 0, right = nums.size() - 1; while(left < right){ int mid = (right - left) / 2 + left; if(nums[mid] < nums[mid + 1])// 是否取等，后面if-else-都需要仔细调整 left = mid + 1; else right = mid; } return right; }

// 思路：从左下角、或者右上角开始，进行二分搜索 bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int i = matrix.size() - 1, j = 0; while(i >= 0 && j < matrix[0].size()) if(matrix[i][j] == target) return true; else if(matrix[i][j] < target) ++j; else --i; return false; }

// 思路：从胃口最小的孩子开始，从最小的饼干开始喂直到能满足为止 int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int cnt = 0; int i = 0, j = 0; // 从胃口最小的孩子喂饼干，从最小的饼干开始喂 while(i < g.size() && j < s.size()){ if(g[i] <= s[j]){ ++cnt; ++i; ++j; }else ++j; } return cnt; }

// 思路：左往右依次射箭，每次保证引爆最多的气球 int findMinArrowShots(vector<vector<int>>& points) { if(points.size() <= 1) return points.size(); sort(points.begin(), points.end()); int cnt = 1; int rightEdge = points[0][1]; // 第一个圆右侧为右边界 for(int idx = 1; idx < points.size(); ++idx){ // 圆在边界内，需更新边界为它们右侧的较小值 if(points[idx][0] <= rightEdge) rightEdge = min(rightEdge, points[idx][1]); // 圆不在边界内，引爆气球++cnt，并更新右边界为新的右侧值 else{ ++cnt; rightEdge = points[idx][1]; } } return cnt; }

// 思路： // 步骤1. 先每个人发一颗糖果 // 步骤2. 从左往右遍历，i比i-1表现好就在i-1基础上+1糖果 // 步骤3. 从右往左遍历，i比i+1表现好就在i+1基础上+1糖果（需判断已有糖果是否已经比i+1多） int candy(vector<int>& ratings) { vector<int> candies(ratings.size(), 1); for(int i = 1; i < candies.size(); ++i) if(ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1; for(int i = candies.size() - 2; i >= 0; --i) if(ratings[i] > ratings[i + 1]) candies[i] = max(candies[i], candies[i + 1] + 1); return accumulate(candies.begin(), candies.end(), 0); }

// 思路：只要p[i] > p[i - 1]，就在i-1买入并在i卖出。某天既买入又卖出可视为没有做任何操作 int maxProfit(vector<int>& prices) { if(prices.size() <= 1) return 0; int prof = 0; for(int i = 1; i < prices.size(); ++i) prof += (prices[i] > prices[i - 1]) ? prices[i] - prices[i - 1] : 0; return prof; }

// 思路：直接遍历，满足条件就种下。注意两类特殊情况和花坛两端 bool canPlaceFlowers(vector<int>& bed, int n) { int seeds = 0; if(n == 0) return true; if(bed.size() == 1) return bed[0] == 0; if(bed.size() >= 2 && bed[0] == 0 && bed[1] == 0){ ++seeds; bed[0] = 1; } for(int i = 1; i < bed.size() - 1; ++i) if(bed[i - 1] == 0 && bed[i] == 0 && bed[i + 1] == 0){ ++seeds; bed[i] = 1; } if(bed.size() >= 2 && bed[bed.size() - 2] == 0 && bed.back() == 0) ++seeds; return seeds >= n; }

// 思路：对逆序的数对进行计数，同时需要确认是否可以修正 // 找到nums[i] > nums[i + 1]的位置，再对nums[i] or nums[i + 1]进行更改 bool checkPossibility(vector<int>& nums) { int cnt = 0; for(int i = 0; i < nums.size() - 1; ++i) if(nums[i] > nums[i + 1]){ ++cnt; // 优先考虑更改nums[i]为它能接受的最小值，即nums[i - 1] if(i == 0) continue; if(nums[i - 1] <= nums[i + 1]) nums[i] = nums[i - 1];// 2 4(i) 2 5 => 改4为2 else nums[i + 1] = nums[i];// 3 4(i) 2 5 => 不能改4 } return cnt <= 1; }

// 思路：直接比对每一个字母即可 bool isSubsequence(string s, string t) { if(s.empty()) return true; int p = 0; for(const auto &c:t) if(s[p] == c) if(++p == s.size()) return true; return false; }

// 思路: 第一遍遍历得到每个字母最后出现的位置map // 第二遍通过left,right指示区间，cur指示当前遍历到的位置 //	使用right = max(map[s[cur]], right)扩张右侧边界 //	cur==right时说明区间内的字母未出现在其它区域 vector<int> partitionLabels(string str) { map<char, int> map; for(int i = 0; i < str.size(); ++i) map[str[i]] = i; int left = 0, right = map[str[0]], cur = 0; vector<int> res; while(right < str.size()){ right = max(right, map[str[cur]]);// 更新右边界 if(right == cur){ // 此时[left,right]之间的字母未出现在其它位置 res.push_back(right - left + 1); left = right + 1; right = (cur < str.size() - 1) ? map[str[cur + 1]] : str.size(); } ++cur; } return res; }

// 思路： // 将所有区间从小到大排序 // 选择第一个区间右端点作为界限，不断向右扩展其势力范围内的其它区间 vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size() <= 1) return intervals; sort(intervals.begin(), intervals.end()); vector<vector<int>> res; auto tmp = intervals[0]; for(int i = 1; i < intervals.size(); ++i){ if(intervals[i][0] <= tmp[1]) tmp[1] = max(tmp[1], intervals[i][1]); else{ res.push_back(tmp); tmp = intervals[i]; } } res.push_back(it0);// 最后一个tmp由于没有进入到for循环中的else语句，需要额外加入到res中 return res; }

// 思路 // 将所有人(h,k)按身高h降序，k升序进行排列得 [7,0],[7,1],[6,1],[5,0],[5,2],[4,4] // 此时所有人前面的人均不低于它，只需将(hi,ki)往前swap直到ki = i为止 bool comp(const vector<int> &p1, const vector<int> &p2){ return p1[0] > p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort(people.begin(), people.end(), comp); for(int i = 0; i < people.size(); ++i) for(int k = i; k > people[k][1]; --k) swap(people[k], people[k - 1]); return people; }

// 思路：统计每个任务出现次数，假设为AAAABBBBCCC,n=3 // 放A: |A---|A---|A---|A  // 放B：|AB--|AB--|AB--|AB => 执行时间 = (4 - 1) * (n + 1) + 2 // 放C：|ABC-|ABC-|ABC-|AB 其中4是最多的次数，2是最多次数的任务 // 另外，当出现AAABBBCCDD,n=2时，总能通过尽量稀疏分布使得不需要等待时间 // 放A：|A--|A--|A--| // 放B: |AB-|AB-|AB-| // 放C：|ABC|AB-|ABC|	(这里是关键) // 放D：|ABC|ABD|ABC|D int leastInterval(vector<char>& tasks, int n) { vector<int> stat(26, 0); for(const auto &c:tasks) ++stat[c - 'A']; sort(stat.begin(), stat.end()); int max_task = stat[25], max_cnt = 0; for(const auto &cnt:stat) max_cnt += cnt == stat[25] ? 1 : 0; int time = (max_task - 1) * (n + 1) + max_cnt; time = time > tasks.size() ? time : tasks.size(); return time; }

// 思路:首先每行翻转，保证第一位是1, 1000 > 0111 // 然后第二列开始，每列翻转保证该列1数量比0多 void reverseRow(vector<vector<int>> &A, int row){ for(auto &c:A[row]) c ^= 1; } void reverseCol(vector<vector<int>> &A, int col){ for(int i = 0; i < A.size(); ++i) A[i][col] ^= 1; } int matrixScore(vector<vector<int>>& A) { if(A.empty() || A[0].empty()) return 0; // 每行变换，保证每行第一位是1 for(int row = 0; row < A.size(); ++row) if(A[row][0] == 0) reverseRow(A, row); // 列变换，保证每列1数量比0多 for(int col = 1; col < A[0].size(); ++col){ int ones = 0, zeros = 0; for(int i = 0; i < A.size(); ++i) A[i][col] == 0 ? ++ones : ++zeros; if(ones > zeros) reverseCol(A, col); } int sum = 0;// 计算最终结果 for(const auto &row:A){ int sum_row = 0; for(const auto &i:row) sum_row = (sum_row << 1) + i;// 移位运算符优先级很低，需要打上括号 sum += sum_row; } return sum; }

// 计算每个车到达终点的所花时间, 并将车队按起始位置进行排序 // 从最后一个车开始开始遍历, 时间比最后一个车还短的车必然是同一个车队 int carFleet(int target, vector<int>& position, vector<int>& speed) { vector<pair<int,double>> times; // 每辆车到达终点花费的时间 for(int i = 0; i < position.size(); ++i) times.push_back({position[i], (target - position[i]) * 1.0 / speed[i]}); sort(times.begin(), times.end()); int count = 0, idx = times.size() - 1; while(idx >= 0){ ++count; // 车队+1 double t = times[idx].second; // 最后一个车的花费的时间 --idx; while(idx >= 0 && times[idx].second <= t) --idx; // 跳过所有花费时间比最后一个车还短的 } return count; }

// 思路：两个下标分别指向首、尾，同时向中间靠拢以搜索两数 vector<int> twoSum(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left <= right){ int sum = nums[left] + nums[right]; if(sum == target) return { left + 1, right + 1 }; else if(sum < target) ++left; else --right; } return {0,0};// 题目必有解，不会执行到这里，但没有这句话无法通过编译 }

const set<char> sc = { 'a','e','i','o','u' }; string reverseVowels(string s) { int left = 0, right = s.size() - 1; while(left <= right){ while(left < s.size() && sc.count(tolower(s[left])) == 0) ++left;// 左往右定位到元音 while(right >= 0 && sc.count(tolower(s[right])) == 0) --right;// 右往左定位到元音 if(left <= right) swap(s[left++], s[right--]); } return s; }

bool judgeSquareSum(int c) { long long left = 0, right = sqrt(c); while(left <= right){ long long num = left * left + right * right; if(num < c) ++left; else if(num > c) --right; else if(num == c) return true; } return false; }

// 思路：定位到第一个非回文的位置，刨除左字母或右字母后验证剩余部分是否为回文串 bool valid(const string &s, int left, int right){ while(left <= right) if(s[left++] != s[right--]) return false; return true; } bool validPalindrome(string s) { int left = 0, right = s.size() - 1; while(left <= right){ if(s[left] != s[right])// 定位后验证 return valid(s, left + 1, right) || valid(s, left, right - 1); ++left; --right; } return true; }

// 思路：从num1的m+n-1位置处往前填充数字 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int idx = m + n - 1; int p1 = m - 1, p2 = n - 1; while(idx >= 0) if(p1 >= 0 && p2 >= 0){ // 在num1,nums2中都还有未融合的数才进行 nums1[idx--] = max(nums1[p1], nums2[p2]); nums1[p1] > nums2[p2] ? --p1 : --p2; }else break; // p2>=0说明nums2中存在数没融合，将它放到nums1中； p1>=0，此时nums1中已经排好无需再管 while(p2 >= 0) nums1[idx--] = nums2[p2--]; }

// 与leetcode.88类似，不过这里从前往后填充 void moveZeroes(vector<int>& nums) { int p1 = 0, p2 = 0; while(p2 < nums.size()){ if(nums[p2] != 0) nums[p1++] = nums[p2]; ++p2; } while(p1 < nums.size()) nums[p1++] = 0; } // 写得更紧凑一些 void moveZeros(vector<int> &nums){ int p = 0; for(auto num:nums) if(num != 0) nums[p++] = num; while(p < nums.size()) nums[p++] = 0; }

// 思路：快慢指针，快指针先走n次，然后快、慢一起走，快指针到达nullptr时慢指针即倒数第n个 // 注意：题目保证n有效，即1 <= n <= 总节点数 ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *fast = head, *slow = head; int cnt = 0; while(cnt++ < n) fast = fast->next; // n == 总节点数，倒数第n个节点即头结点 if(fast == nullptr){ ListNode *tmp_head = head->next; delete head; return tmp_head; } // 其余情况：条件fast->next != nullptr可将slow定位到待删节点前一个 // 条件fast != nullptr可将slow定位到待删节点。 注意区分使用 while(fast->next != nullptr){ fast = fast->next; slow = slow->next; } auto tmp = slow->next->next; delete slow->next; slow->next = tmp; return head; }

// 思路：快慢指针法，若有环则必然在某个点相遇 // 另外：也可以用set或者map对已出现的节点进行记录，需要额外空间O(n) bool hasCycle(ListNode *head) { ListNode *fast = head, *slow = head; while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(fast == slow) return true; } return false; }

// __a__.______ b a,b,c分为为各段长度 // c \_____* <---- 快慢指针相遇点 // 若有环，快慢指针在图中 * 处相遇，存在关系 fast = a+b+(b+c)*k = 2*slow =2*(a+b), k为快指针圈数 // 解得： a = (b + c)*(k - 1) + c // 即：从头结点和相遇点分别出发，必然在入口节点相遇 ListNode* EntryNodeOfLoop(ListNode* head){ ListNode* fast = head, *slow = head; while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(slow == fast){// 在*相遇 fast = head;// fast从头出发，slow从相遇点出发，一次跳一格 while(fast != slow){ fast = fast->next; slow = slow->next; } return fast;// 入口接单相遇后返回fast或slow都可以 } } return nullptr; }

// 思路：用left, right表示无重复字符的窗口，用一个map记录right之前所有字符最后出现的位置loc // 依次遍历每个字符的位置作为右端right，判断s[right]最后出现的位置是否在[left, right]内 int lengthOfLongestSubstring(string s) { int left = 0, maxLen = 0; map<char, int> loc; // 记录已遍历字符最后出现的位置 for(int right = 0; right < s.size(); ++right){ if(loc.count(s[right]) > 0 && loc[s[right]] >= left)// 判断 left = loc[s[right]] + 1; loc[s[right]] = right; maxLen = max(maxLen, right - left + 1); } return maxLen; }

// 思路:为字典里每个字符串分配一个指针idx, 表示该字符串已经匹配到了idx // 遍历给定字符串str每个字母c，看c是否能与字典中字符串target_s[idx]进行匹配，匹配则idx+1 // 遍历完成后，看字典中每个字符串的idx==target_s.size()与否，相等则表示已匹配到 string findLongestWord(string str, vector<string>& vs) { unordered_map<string, int> dict; for(const auto &item:vs) dict[item] = 0;// 分配指针 for(const auto &c:str) // 比对 for(auto &m:dict) // 注意，这里一定要 auto &，否则更改后不会作用到m上 if(c == m.first[m.second]) ++m.second; string res = ""; int maxLen = 0; for(const auto &m:dict) if(m.second == m.first.size()){ // 匹配成功的 if(m.first.size() > maxLen){ res = m.first; maxLen = m.first.size(); }else if(m.first.size() == maxLen) res = res < m.first ? res : m.first; // 字典序更小的 } return res; }

// 思路：由于nums中全都是正数，因此可以使用双指针 int numSubarrayProductLessThanK(vector<int>& nums, int k) { if(nums.empty() || k == 0) return 0; int prod = 1; int left = 0, right = 0; int cnt = 0; while(right < nums.size()){ prod *= nums[right]; while(left <= right && prod >= k){ prod /= nums[left]; ++left; } cnt += prod < k ? right - left + 1 : 0; ++right; } return cnt; }

// 注意：返回结果是每一层的节点作为一个vector，所有层再作为一个vector vector<vector<int>> levelOrder(TreeNode* root) { if(root == nullptr) return {}; vector<vector<int>> res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int cnt = q.size(); // 每层的节点数量 vector<int> level_nums; while(cnt-- > 0){ auto tmp = q.front(); q.pop(); level_nums.push_back(tmp->val); if(tmp->left != nullptr) q.push(tmp->left); if(tmp->right != nullptr) q.push(tmp->right); } res.push_back(level_nums); } return res; } // 如果整体返回一个 vector<int>，则写法如下： vector<int> levelOrder(TreeNode* root) { if(root == nullptr) return {}; vector<int> res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ auto tmp = q.front(); q.pop(); res.push_back(tmp->val); if(tmp->left != nullptr) q.push(tmp->left); if(tmp->right != nullptr) q.push(tmp->right); } return res; }

// 递归法，递归不需要借助queue bool isSymmetric(TreeNode* root) { if(root == nullptr) return true; return check(root->left, root->right); } bool check(TreeNode* l, TreeNode *r){ if(l == nullptr && r == nullptr) return true; if(l == nullptr || r == nullptr || l->val != r->val) return false; return check(l->left, r->right) && check(r->left, l->right); } // 迭代法，借助queue实现 bool isSymmetric(TreeNode* root) { if(root == nullptr) return true; queue<TreeNode*> ql; queue<TreeNode*> qr; ql.push(root->left); qr.push(root->right); while(!ql.empty() && !qr.empty()){ auto l = ql.front(); auto r = qr.front(); ql.pop(); qr.pop(); if(l == nullptr && r == nullptr) continue; if(l == nullptr || r == nullptr || l->val != r->val) return false; ql.push(l->left); qr.push(r->right); ql.push(l->right); qr.push(r->left); } return true; }

// 对beginword里的每一个字母，将它替换为26个字母（26个搜索方向），若替换后存在于wordList中，则可以作为下一层 // 示例1的搜索变换过程为 [hit] -> [hot] -> [dot, lot] -> [dog, log] -> [cog] int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); if(dict.count(endWord) == 0) // 词典中必然存在endWord才能转换 return 0; dict.erase(beginWord); queue<string> q; // 一般使用queue辅助广度优先搜索 q.push(beginWord); int level = 1; // beginWord算一层 while(!q.empty()){ int node_num = q.size();// 该层的节点数 while(node_num-- > 0){// 遍历该层的所有节点 string node = q.front(); q.pop(); if(node == endWord) return level; for(int i = 0; i < node.size(); ++i){// 对每个字母 char node_i = node[i]; for(char c = 'a'; c < 'z'; ++c){// 26个搜索方向，即替换为a-z node[i] = c; if(dict.count(node) > 0){ q.push(node); dict.erase(node); // 剔除该节点，防止后面再次搜索到 } } node[i] = node_i; } } ++level; } return 0; // 遍历到这说明没搜索到 }

// 思路：gird(i,j)=1，岛屿+1，同时删除岛屿连通的陆地->上下左右四个方向 int numIslands(vector<vector<char>>& islands) { if(islands.empty() || islands[0].empty()) return 0; int num = 0; for(int i = 0; i < islands.size(); ++i) for(int j = 0; j < islands[0].size(); ++j) if(islands[i][j] == '1') ++num, dfs(islands, i, j); return num; } void dfs(vector<vector<char>> &islands, int i, int j){ // 超出边界，或者(i,j)是水域，直接返回 if(i < 0 || i > islands.size() - 1 || j < 0 || j > islands[0].size() - 1 || islands[i][j] == '0') return; // 删除陆地和它上下左右四个方向上的陆地 islands[i][j] = '0'; dfs(islands, i - 1, j); dfs(islands, i + 1, j); dfs(islands, i, j - 1); dfs(islands, i, j + 1); }

// 思路：分别从(i,j)出发寻找最大的岛屿 int maxAreaOfIsland(vector<vector<int>>& grid) { if(grid.empty() || grid[0].empty()) return 0; int maxArea = 0; for(int i = 0; i < grid.size(); ++i) for(int j = 0; j < grid[0].size(); ++j) maxArea = max(maxArea, dfs(grid, i, j)); return maxArea; } int dfs(vector<vector<int>> &grid, int i, int j){ // 超出边界，或(i,j)是水域，直接返回0 if(i < 0 || i > grid.size() - 1 || j < 0 || j > grid[0].size() - 1 || grid[i][j] == 0) return 0; // 将该岛屿改成水域，同时向东南西北四个方向搜索存在的陆地 grid[i][j] = 0; return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1); }

// 思路：类似leetcode.200岛屿数量 // 此题中，M(i,j)=1，朋友圈+1，同时删除(i,j)的所有朋友关系 // 注意：朋友关系具有传递性，需要删除 i 行和 j 列上的所有关系。不同于leetcode.200中向上下左右四个方向删陆地 int findCircleNum(vector<vector<int>>& M) { if(M.empty() || M[0].empty()) return 0; int circles = 0; for(int i = 0; i < M.size(); ++i) for(int j = 0; j < M[0].size(); ++j) if(M[i][j] == 1) ++circles, dfs(M, i, j); return circles; } void dfs(vector<vector<int>> &M, int i, int j){ // 超出搜索范围或者没有关系，直接返回 if(i < 0 || i > M.size() - 1 || j < 0 || j > M[0].size() - 1 || M[i][j] == 0) return; // 删除所有朋友关系 M[i][j] = 0; for(int row = 0; row < M.size(); ++row) dfs(M, row, j); for(int col = 0; col < M[0].size(); ++col) dfs(M, i, col); }

// 思路：反向思维，先从边界开始进行dfs，将与边界接壤的区域该为 * // 然后遍历所有元素，将O该为X，将*改为O void solve(vector<vector<char>>& board) { if(board.empty() || board[0].empty()) return; // 左右边界 for(int row = 0; row < board.size(); ++row){ dfs(board, row, 0); dfs(board, row, board[0].size() - 1); } // 上下边界 for(int col = 0; col < board[0].size(); ++col){ dfs(board, 0, col); dfs(board, board.size() - 1, col); } for(auto &rows:board) for(auto &ele:rows) ele = ele == 'O' ? 'X' : ele == '*' ? 'O' : ele; } void dfs(vector<vector<char>> &board, int i, int j){ if(i < 0 || i > board.size() - 1 || j < 0 || j > board[0].size() - 1 || board[i][j] != 'O') return;// 超出边界或者不是'O'，直接返回 board[i][j] = '*'; dfs(board, i - 1, j); dfs(board, i + 1, j); dfs(board, i, j - 1); dfs(board, i, j + 1); }

// 思路：太平洋的水低到高流，能流到的地图为m1，大西洋的水从低到高流，能流到的地图为m2。则m1和m2的重合部分即为所求 vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) { if(matrix.empty() || matrix[0].empty()) return {}; vector<vector<bool>> pac(matrix.size(), vector<bool>(matrix[0].size(), false)); vector<vector<bool>> atl(matrix.size(), vector<bool>(matrix[0].size(), false)); // 从太平洋沿岸出发，即左列和上行 for(int i = 0; i < matrix.size(); ++i) dfs(matrix, i, 0, pac); for(int j = 0; j < matrix[0].size(); ++j) dfs(matrix, 0, j, pac); // 从大西洋沿岸出发，即右列和下行 for(int i = 0; i < matrix.size(); ++i) dfs(matrix, i, matrix[0].size() - 1, atl); for(int j = 0; j < matrix[0].size(); ++j) dfs(matrix, matrix.size() - 1, j, atl); vector<vector<int>> res; for(int i = 0; i < matrix.size(); ++i) for(int j = 0; j < matrix[0].size(); ++j) if(pac[i][j] == true && atl[i][j] == true) res.push_back({i,j}); return res; } void dfs(const vector<vector<int>> &matrix, int i, int j, vector<vector<bool>> &map){ if(map[i][j] == true) return;// 到达曾到达过的区域则直接返回，防止两个点高度相同时陷入死循环 map[i][j] = true; if(i > 0 && matrix[i - 1][j] >= matrix[i][j]) dfs(matrix, i - 1, j, map); if(i < matrix.size() - 1 && matrix[i + 1][j] >= matrix[i][j]) dfs(matrix, i + 1, j, map); if(j > 0 && matrix[i][j - 1] >= matrix[i][j]) dfs(matrix, i, j - 1, map); if(j < matrix[0].size() - 1 && matrix[i][j + 1] >= matrix[i][j]) dfs(matrix, i, j + 1, map); }

vector<vector<int>> dirs = { {-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1} }; vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { if(board[click[0]][click[1]] == 'M'){ board[click[0]][click[1]] = 'X'; return board; } bfs(board, click[0], click[1]); return board; } void bfs(vector<vector<char>> &board, int row, int col){ // 搜索board[row][col]八个方向的炸弹数量 int bombs = 0; for(auto &dir:dirs){ int new_row = row + dir[0], new_col = col + dir[1]; if(new_row < 0 || new_col < 0 || new_row >= board.size() || new_col >= board[0].size()) continue; bombs += board[new_row][new_col] == 'M' ? 1 : 0; } board[row][col] = bombs == 0 ? 'B' : char(48 + bombs); // 附近没有雷，才对八个方向进行搜索 if(board[row][col] == 'B') for(auto &dir:dirs){ int new_row = row + dir[0], new_col = col + dir[1]; if(new_row < 0 || new_col < 0 || new_row >= board.size() || new_col >= board[0].size()) continue; if(board[new_row][new_col] == 'E') // 该方向是空格才搜索 bfs(board, new_row, new_col); } } 

vector<string> binaryTreePaths(TreeNode* root) { if(root == nullptr) return {}; vector<string> res; dfs(root, "", res); return res; } void dfs(TreeNode* root, string prefix, vector<string> &res){ if(root->left == nullptr && root->right == nullptr){// 到达叶节点 res.push_back(prefix + to_string(root->val)); return; } if(root->left != nullptr) dfs(root->left, prefix + to_string(root->val) + "->", res); if(root->right != nullptr) dfs(root->right, prefix + to_string(root->val) + "->", res); }

int sumNumbers(TreeNode* root) { if(root == nullptr) return 0; long long res = 0; if(dfs(root, 0, res)) return INT_MAX; return res; } // 返回true表示已超过了INT_MAX，停止dfs bool dfs(TreeNode *root, long long prefix, long long &res){ if(root->left == nullptr && root->right == nullptr){ res += prefix * 10 + root->val; return res > INT_MAX ? true : false; } prefix = prefix * 10 + root->val; if(prefix > INT_MAX) return true; if(root->left != nullptr && dfs(root->left, prefix, res)) return true; if(root->right != nullptr && dfs(root->right, prefix, res)) return true; return false; }

// 思路：DFS-先序遍历（右侧开始），某层最先达到的节点即为该层最右侧的节点 vector<int> rightSideView(TreeNode* root) { if(root == nullptr) return {}; vector<int> res; preorder(root, 0, res); return res; } void preorder(TreeNode *root, int level, vector<int> &nums){ if(root == nullptr) return; if(nums.size() == level) nums.push_back(root->val); preorder(root->right, level + 1, nums); preorder(root->left, level + 1, nums); } // 此题也可使用BFS做，即层次遍历，每层最后一个节点放入vector中即可 // 注：树的前、中、后序遍历均是深度优先搜索

int maxPathSum(TreeNode* root) { int maxSum = INT_MIN; dfs(root, maxSum); return maxSum; } int dfs(TreeNode *root, int &maxSum){ if(root == nullptr) return 0; // 求左、右子树的最大单边路径和,若为负数则直接置0，刨除负数节点 int leftSum = max(dfs(root->left, maxSum), 0); int rightSum = max(dfs(root->right, maxSum), 0); // 更新最大路径和, 必然为(左+根+右, maxSum)中的较大值 maxSum = max(maxSum, leftSum + rightSum + root->val); // 返回左、右子树路径和较大值 + 本节点的值，作为以root为根往下的最大单边路径和 return max(leftSum, rightSum) + root->val; }

int movingCount(int threshold, int rows, int cols){ vector<vector<bool>> grid(rows, vector<bool>(cols, false)); dfs(grid, 0, 0, threshold);// 只需从(0,0)出发开始dfs int sum = 0; for(const auto &row:grid) sum += accumulate(row.begin(), row.end(), 0); return threshold < 0 ? 0 : sum; } void dfs(vector<vector<bool>> &grid, int i, int j, const int &thresh){ if(i < 0 || i > grid.size() - 1 || j < 0 || j > grid[0].size() - 1 || grid[i][j] == true || decbitsum(i, j) > thresh) return; grid[i][j] = true; dfs(grid, i - 1, j, thresh); dfs(grid, i + 1, j, thresh); dfs(grid, i, j - 1, thresh); dfs(grid, i, j + 1, thresh); } int decbitsum(int i, int j){ int sum = 0; while(i != 0){ sum += i % 10; i /= 10; } while(j != 0){ sum += j % 10; j /= 10; } return sum; }

vector<string> letterCombinations(string digits) { if(digits.empty()) return {}; string s; // 用于保存在dfs过程中的遍历记录 vector<string> res; backtracking(digits, 0, s, res); return res; } vector<string> phones = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void backtracking(const string &digits, int idx, string &prefix, vector<string> &res){ if(idx == digits.size()){ res.push_back(prefix); return; } for(const auto &c:phones[digits[idx] - '0']){ prefix.push_back(c); backtracking(digits, idx + 1, prefix, res); prefix.pop_back(); // 进行下次遍历前，将此次的影响消除 } }

bool exist(vector<vector<char>>& board, string word) { if(word.empty()) return true; if(board.empty() || board[0].empty()) return false; for(int i = 0; i < board.size(); ++i) for(int j = 0; j < board[0].size(); ++j) if(backtracking(board, word, 0, i, j)) return true; return false; } bool backtracking(vector<vector<char>> &board, const string &word, int idx, int i, int j){ // 超出搜索边界，或者(i,j)处的字母与word[idx]不等，直接返回 if(i < 0 || i > board.size() - 1 || j < 0 || j > board[0].size() - 1 || idx > word.size() - 1 || board[i][j] != word[idx]) return false; // 搜索到了，返回true if(idx == word.size() - 1 && board[i][j] == word[idx]) return true; char c_backup = board[i][j]; board[i][j] = '*'; // 已访问标记，防止再次访问 // 向上下左右四个方向搜索 if(backtracking(board, word, idx + 1, i + 1, j) || backtracking(board, word, idx + 1, i - 1, j) || backtracking(board, word, idx + 1, i, j + 1) || backtracking(board, word, idx + 1, i, j - 1)) return true; board[i][j] = c_backup; // 未搜索到，需要恢复(i,j)处的字母 return false; }

vector<string> restoreIpAddresses(string s) { if(s.size() <= 3) return {}; vector<string> res; backtracking(res, s, "", 0); return res; } void backtracking(vector<string> &res, string s, string prefix, int cnt){ if(cnt == 3){ // 已经经历了3次分割，只需进行最后一次分割 if(isValid(s)) res.push_back(prefix + s); return; } for(int i = 1; i <= 3; ++i)// 分割出1-3位判断有效性 if(i <= s.size() && isValid(s.substr(0, i))) backtracking(res, s.substr(i), prefix + s.substr(0, i) + ".", cnt + 1); } bool isValid(string s){ if(s.empty() || s.size() > 3) return false; if(s[0] == '0')// 首位为0，则必然只有一位 return s.size() == 1; else // 只需数值<=255即可 return stoi(s) <= 255; }

vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; permute(res, nums, 0); return res; } void permute(vector<vector<int>> &res, vector<int> &nums, int idx){ if(idx == nums.size() - 1){ res.push_back(nums); return; } for(int i = idx; i < nums.size(); ++i){ swap(nums[i], nums[idx]); permute(res, nums, idx + 1); swap(nums[i], nums[idx]); } }

// 只需将leetcode.46中的vector<vector<int>> res ===>>> set<vector<int>> res; vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res;// 改动 permute(res, nums, 0); return vector<vector<int>> (res.begin(), res.end());// 改动 } void permute(set<vector<int>> &res, vector<int> &nums, int idx){ if(idx == nums.size() - 1){ res.insert(nums); // 改动 return; } for(int i = idx; i < nums.size(); ++i){ swap(nums[i], nums[idx]); permute(res, nums, idx + 1); swap(nums[i], nums[idx]); } }

vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; vector<int> nums; backtracking(n, k, res, nums, 0); return res; } void backtracking(const int &n, const int &k, vector<vector<int>> &res, vector<int> &nums, int last_int){ if(nums.size() == k){ res.push_back(nums); return; } // 从上一次放入nums的数的后一位开始放 for(int i = last_int + 1; i <= n; ++i){ nums.push_back(i); backtracking(n, k, res, nums, i); nums.pop_back(); } }

vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); set<vector<int>> res; vector<int> nums; backtracking(candidates, target, res, nums, 0); return vector<vector<int>> (res.begin(), res.end()); } void backtracking(const vector<int> &cdd, int t, set<vector<int>> &res, vector<int> &nums, int idx){ if(t <= 0){ // 注意这里的条件 if(t == 0) res.insert(nums); return; } for(int i = idx; i < cdd.size(); ++i){ nums.push_back(cdd[i]); backtracking(cdd, t - cdd[i], res, nums, i); nums.pop_back(); } }

// 在leetcode.39的基础上改动一个小地方 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); set<vector<int>> res; vector<int> nums; backtracking(candidates, target, res, nums, 0); return vector<vector<int>> (res.begin(), res.end()); } void backtracking(const vector<int> &cdd, int t, set<vector<int>> &res, vector<int> &nums, int idx){ if(t <= 0){ if(t == 0) res.insert(nums); return; } for(int i = idx; i < cdd.size(); ++i){ nums.push_back(cdd[i]); backtracking(cdd, t - cdd[i], res, nums, i + 1); // 改动：下一层遍历从i+1开始 nums.pop_back(); } }

vector<vector<int>> subsets(vector<int>& nums) { set<vector<int>> res; vector<int> subset; backtracking(nums, res, subset, 0); return vector<vector<int>> (res.begin(), res.end()); } void backtracking(const vector<int> &nums, set<vector<int>> &res, vector<int> &subset, int idx){ res.insert(subset); // 不放入nums[i]的情况 for(int i = idx; i < nums.size(); ++i){ subset.push_back(nums[i]); backtracking(nums, res, subset, i + 1); // 放入nums[i]的情况 subset.pop_back(); } }

// 与leetcode.78基本一模一样，唯一改动的是需要进行排序 // 因为 [1,2,2]和[2,1,2]是同一子集，却是不同的vector，在res.insert(subset)时会被重复插入 vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end());// 唯一改动的地方 set<vector<int>> res; vector<int> subset; backtracking(nums, res, subset, 0); return vector<vector<int>> (res.begin(), res.end()); } void backtracking(const vector<int> &nums, set<vector<int>> &res, vector<int> &subset, int idx){ res.insert(subset); for(int i = idx; i < nums.size(); ++i){ subset.push_back(nums[i]); backtracking(nums, res, subset, i + 1); subset.pop_back(); } }

// 思路：与leetcode.90子集II类似，只需要改动两个地方：1.保证子集尺寸>=2才放入res, 2. 保证子集是递增子序列 vector<vector<int>> findSubsequences(vector<int>& nums) { set<vector<int>> res; vector<int> subset; backtracking(nums, res, subset, 0); return vector<vector<int>> (res.begin(), res.end()); } void backtracking(const vector<int> &nums, set<vector<int>> &res, vector<int> &subset, int idx){ if(subset.size() >= 2)// 改动1. 保证子集尺寸>=2才放入res res.insert(subset); for(int i = idx; i < nums.size(); ++i) if(subset.empty() || nums[i] >= subset.back()){// 改动2. 保证子集是递增子序列 subset.push_back(nums[i]); backtracking(nums, res, subset, i + 1); subset.pop_back(); } }

vector<vector<string>> partition(string s) { vector<string> strs; vector<vector<string>> res; backtracking(res, strs, s, 0); return res; } void backtracking(vector<vector<string>> &res, vector<string> &strs, const string &s, int idx){ if(idx == s.size()){ res.push_back(strs); return; } for(int i = idx; i < s.size(); ++i) if(isPalindrome(s, idx, i)){ strs.push_back(s.substr(idx, i - idx + 1)); backtracking(res, strs, s, i + 1); strs.pop_back(); } } bool isPalindrome(const string &s, int left, int right){ while(left <= right) if(s[left++] != s[right--]) return false; return true; }

void solveSudoku(vector<vector<char>>& board) { // rowc[i][c]表示第i行存在多少个字符c, colc[j][c]表示第j行字符c数量 // subc[k][c]表示第k个3x3子区域存在多少个字符c vector<map<char,int>> rowc(9, map<char,int>()); vector<map<char,int>> colc(9, map<char,int>()); vector<map<char,int>> subc(9, map<char,int>()); // 统计board中每行每列各个字符的数量 for(int i = 0; i < 9; ++i) for(int j = 0; j < 9; ++j) if(board[i][j] != '.'){ int k = i / 3 * 3 + j / 3; // (i,j)与第k个3x3子区域的关系 char c = board[i][j]; ++rowc[i][c]; ++colc[j][c]; ++subc[k][c]; } // 直接从(0,0)开始求解 backtracking(board, 0, 0, rowc, colc, subc); } // 从左到右、从上到下求解 bool backtracking(vector<vector<char>> &board, int i, int j, vector<map<char,int>> &rowc, vector<map<char,int>> &colc, vector<map<char,int>> &subc){ // 结束条件：已经求解到最后一行的下一行，说明前面的9x9已经求解完毕 if(i == 9 && j == 0) return true; // (i,j)已求解，对下一格求解 if(board[i][j] != '.') if( (j != 8 && backtracking(board, i, j + 1, rowc, colc, subc)) ||(j == 8 && backtracking(board, i + 1, 0, rowc, colc, subc))) return true; // (i,j)未求解，对本格求解 if(board[i][j] == '.') for(char c = '1'; c <= '9'; ++c) if(rowc[i][c] < 1 && colc[j][c] < 1 && subc[i/3*3+j/3][c] < 1){ ++rowc[i][c]; ++colc[j][c]; ++subc[i/3*3+j/3][c]; board[i][j] = c; if( (j != 8 && backtracking(board, i, j + 1, rowc, colc, subc)) ||(j == 8 && backtracking(board, i + 1, 0, rowc, colc, subc))) return true; --rowc[i][c]; --colc[j][c]; --subc[i/3*3+j/3][c]; board[i][j] = '.'; } return false; }

bool canPartitionKSubsets(vector<int>& nums, int k) { int sum = 0, maxnum = INT_MIN; for(const auto &num:nums) sum += num, maxnum = max(maxnum, num); if(nums.size() < k || sum % k != 0 || maxnum > sum / k) return false; vector<bool> used(nums.size(), false); return backtracking(nums, used, k, sum / k, 0, 0); } bool backtracking(vector<int> &nums, vector<bool> &used, int k, int tarSum, int curSum, int idx){ if(k == 0) // 已经搜索到了k个子集 return true; if(curSum == tarSum) // 搜索下一个子集 return backtracking(nums, used, k - 1, tarSum, 0, 0); for(int i = idx; i < nums.size(); ++i) // 这里如果每次都从0开始搜索则会超时, 从idx开始 if(used[i] == false && curSum + nums[i] <= tarSum){ used[i] = true; if(backtracking(nums, used, k, tarSum, curSum + nums[i], i + 1)) return true; used[i] = false; } return false; }

// 分而治之的思想 vector<int> diffWaysToCompute(string s) { vector<int> res; for(int i = 0; i < s.size(); ++i) if(s[i] == '+' || s[i] == '-' || s[i] == '*')// 以s[i]为节点，分为左、右子串进行处理 for(auto intl:diffWaysToCompute(s.substr(0, i))) for(auto intr:diffWaysToCompute(s.substr(i + 1))){ if(s[i] == '+') res.push_back(intl + intr); else if(s[i] == '-') res.push_back(intl - intr); else if(s[i] == '*') res.push_back(intl * intr); } // res为空，说明s中不存在 +/-/* 运算符，直接将其转换为整数即可 if(res.empty()) res.push_back(stoi(s)); return res; }

vector<string> addOperators(string num, int target) { vector<string> res; div_conq(num, target, 0, 0, "", res); return res; } void div_conq(string num, int target, long last, long cur, string out, vector<string>& res) { if(num.size() == 0 && cur == target){ res.push_back(out); return; } // 分成左右两半进行操作 for(int i = 1; i <= num.size(); ++i){ string left = num.substr(0, i); string right = num.substr(i); if(left.size() > 1 && left[0] == '0') return; // +-* 三种运算符分别进行操作 if(out.size() > 0){ div_conq(right, target, stoll(left), cur + stoll(left), out + "+" + left, res); div_conq(right, target, -stoll(left), cur - stoll(left), out + "-" + left, res); div_conq(right, target, last * stoll(left), cur - last + last * stoll(left), out + "*" + left, res); // 对于乘法2-3*5，上次操作中已经得到 cur = 2-3 = -1, last = -3 // 因此此次操作应为 cur - last + last * 5 = -1 - (-3) + (-3) * 5 = 2 - 3 * 5 }else div_conq(right, target, stoll(left), stoll(left), left, res); } }

int integerBreak(int n) { vector<int> dp(n + 1, 0); // dp[i] = integerBreak(i) dp[1] = 1; // dp[1] = integerBreak(1) = 1 // 将 i 拆分为 j, i - j两个数之和 for(int i = 2; i <= n; ++i) for(int j = 1; j < i; ++j){ dp[i] = max(dp[i], j * (i - j)); dp[i] = max(dp[i], dp[j] * (i - j)); dp[i] = max(dp[i], dp[j] * dp[i - j]); } return dp.back(); } // 另解：拆分出尽量多的3即可 // 5 -> 3 * 2 = 6 8 -> 3 * 3 * 2 = 18	11 -> 3 * 3 * 3 * 2 = 54 // 6 -> 3 * 3 = 9 9 -> 3 * 3 * 3 = 27	12 -> 3 * 3 * 3 * 3 = 81 // 7 -> 3 * 4 = 12 10-> 3 * 3 * 4 = 36	13 -> 3 * 3 * 3 * 4 = 108 int integerBreak(int n){ if(n <= 3) return n - 1; int res = 1; while(n > 4){ res *= 3; n -= 3; } return res * n; }

int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for(int i = 0; i <= n; ++i) for(int j = 0; i + j * j <= n; ++j) dp[i + j * j] = min(dp[i + j * j], dp[i] + 1); // 注意j的遍历方式，dp[i]可以保证了不为INT_MAX，进而避免INT_MAX+1 return dp.back(); } // 四平方和定理：任意数字必然能表示为四个数的平方和（可能有零） // 1. 预处理n/4直到无法除尽 // 2. n % 8 == 7, 则n必然是4个数的平方和 // 3. 确认n是否能表示为两个数平方和（可能有零），以此确认是3个数还是2个数的平方和 int numSquares(int n){ while(n % 4 == 0) n /= 4; if(n % 8 == 7) return 4; for(int a = 0; a * a <= n; ++a){ int b = sqrt(n - a * a); if(b * b + a * a == n) return (a > 0) + (b > 0); } return 3; }

int numDecodings(string s) { vector<int> dp(s.size() + 1, 0); // dp[i]表示前i个字母可解码的数量 dp[0] = 1; for(int i = 1; i < dp.size(); ++i){ // "1|23|45" dp[1] = 1, "23"可解码 => dp[3] += dp[1] = 1 if(i >= 2 && s[i - 2] != '0' && stoi(s.substr(i - 2, 2)) <= 26) dp[i] += dp[i - 2]; // "12|3|45" dp[2] = 3, "2"可解码 => dp[3] += dp[2] => 1 + 3 = 4  if(s[i - 1] != '0') dp[i] += dp[i - 1]; } return dp.back(); }

// 第一行和第一列每个位置都只能有一种方法 // 除此之外每个位置都可以有两个方向(左侧or上侧)到达 int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int> (n, 1)); for(int row = 1; row < m; ++row) for(int col = 1; col < n; ++col) dp[row][col] = dp[row - 1][col] + dp[row][col - 1];// 左侧或者上侧来到[row][col] return dp.back().back(); } // 优化空间，前m-1行是不必要的空间消耗 int uniquePaths(int m, int n){ vector<int> dp(n, 1); for(int row = 1; row < m; ++row) for(int col = 1; col < n; ++col) dp[col] = dp[col - 1] + dp[col]; return dp.back(); }

// 在leetcode.62的基础上加个判断 int uniquePathsWithObstacles(vector<vector<int>>& obs) { vector<long long> dp(obs[0].size(), 0); if(obs[0][0] == 1 || obs.back().back() == 1) // 起点终点堵死就没必要继续了 return 0; // 第一行 dp[0] = 1; for(int col = 1; col < obs[0].size(); ++col) dp[col] = obs[0][col] == 1 ? 0 : dp[col - 1]; // 其它行 for(int row = 1; row < obs.size(); ++row){ if(obs[row][0] == 1) dp[0] = 0; for(int col = 1; col < obs[0].size(); ++col) dp[col] = obs[row][col] == 1 ? 0 : dp[col] + dp[col - 1]; } return dp.back() > INT_MAX ? INT_MAX : dp.back(); }

// 与leetcode.62类似，除了第一行和第一列只有一个方向可达外，其余点均有两个方向可达 int minPathSum(vector<vector<int>>& grid) { if(grid.empty() || grid[0].empty()) return 0; // 第一行只能左侧来，因此第一行的每一列都是左列数字加上本身的数字 for(int col = 1; col < grid[0].size(); ++col) grid[0][col] += grid[0][col - 1]; // 其他行 for(int row = 1; row < grid.size(); ++row){ grid[row][0] += grid[row - 1][0]; // 每行的第一列，必然从上一行来 for(int col = 1; col < grid[0].size(); ++col) // 其他列，两个方向来 grid[row][col] += min(grid[row - 1][col], grid[row][col - 1]); } return grid.back().back(); }

// dp(n) - n阶楼梯的爬法数量 // dp(n) = dp(n - 1) + dp(n - 2) - 可以从n-2跨两步，或从n-1跨一步到达n int climbStairs(int n) { vector<int> dp(n + 1, 0); // dp[i] - i阶楼梯的爬法数量 dp[0] = 1; dp[1] = 1; for(int i = 2; i < dp.size(); ++i) dp[i] = dp[i - 1] + dp[i - 2]; return dp.back(); } // 优化空间：通过llast,last替代dp[i - 2], dp[i - 1]，写成函数迭代的形式 int climbStairs(int n){ int llast = 0, last = 1; int cnt = 0; while(cnt++ < n){ int cur = llast + last; llast = last;// 注意，这两句话 last = cur;// 不能交换顺序 } return last; }

// dp[n] = dp[n - 1] + dp[n - 2] + ... + dp[1] // dp[n - 1] = dp[n - 2] + ... + dp[1] // 状态转移方程： dp[n] = 2 * dp[n - 1] = 2^n*dp[0] = 2 ^ n int jumpFloorII(int n) { if(n <= 0) return 1; int res = 1, cnt = 1; while(cnt++ < n)	res *= 2; return res; }

// 与leetcode.70爬楼梯类似 // 两种方法爬到i层，1. 从i-1层爬上来，花费dp[i-1]+cost[i-1] 2. 从i-2层爬上来，花费dp[i-2]+cost[i-2] int minCostClimbingStairs(vector<int>& cost) { vector<int> dp(cost.size() + 1, 0); // dp[i]爬到前i层时的最小花费 for(int i = 2; i < dp.size(); ++i) dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); return dp.back(); }

// dp[i] - 前i家能抢到的最大值，两种情况：抢第i家，或者不抢第i家 // dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) int rob(vector<int>& nums) { if(nums.size() <= 1) return nums.empty() ? 0 : nums[0]; vector<int> dp(nums.size(), 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for(int i = 2; i < nums.size(); ++i) dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); return dp.back(); } // 优化空间，通过llast,last替代dp[i - 2], dp[i - 1] int rob(vector<int> &nums){ if(nums.size() <= 1) return nums.empty() ? 0 : nums[0]; int llast = nums[0], last = max(nums[0], nums[1]); for(int i = 2; i < nums.size(); ++i){ int cur = max(last, llast + nums[i]); llast = last; last = cur; } return last; }

// 从第0家开始抢，最后一家不能抢 => nums[0...n-1] // 从第1家开始抢，最后一家可以抢 => nums[1...n] int rob(vector<int>& nums) { if(nums.size() <= 1) return nums.empty() ? 0 : nums[0]; return max(rob(nums, 1, nums.size() - 1), rob(nums, 0, nums.size() - 2)); } int rob(const vector<int> &nums, int left, int right){ if(right == left) return nums[left]; int llast = nums[left], last = max(nums[left], nums[left + 1]); for(int i = left + 2; i <= right; ++i){ int cur = max(last, llast + nums[i]); llast = last; last = cur; } return last; }

// 思路：动态规划中的斐波那契数列，假设二进制位数不大于k的无连续1的非负整数位f(k) // k = 5时，二进制数为00000-11111，可分为00000-01111 和 10000-10111(11开头的连续两个1，不算在内) // 则00000-01111表示f(4), 10000-10111就是f(3), 因此有f(5) = f(4) + f(3) // 先求得1位，2位，3位，...，32位的二进制数不存在连续1的个数 // 再对十进制不超过num的数进行计数即可 int findIntegers(int num) { vector<int> fib(32, 0); fib[0] = 1; // 1位的只有 0 fib[1] = 2; // 2位的则有 01, 10 for(int i = 2; i <= 31; ++i) fib[i] = fib[i - 1] + fib[i - 2]; int bit_num = 31; bool last_bit = false; int res = 0; while(bit_num >= 0){// 如：对100110, 考察<=100000, 100的数中分别有多少个不存在连续1的数 if(num & (1 << bit_num)){ res += fib[bit_num]; if(last_bit == true) // 连续两个1, 返回。如100110中的110，因为两个1，比他小的都不满足 return res; last_bit = true; }else last_bit = false; --bit_num; } return res + 1; // 遍历到了这里，说明小于num中没有连续的11, num也应该算在内 }

// dp[i] = max(dp[k] + 1) s.t. k < i && nums[k] < nums[i] // dp[i] 表示以nums[i]结尾的最长递增子序列，nums[i]必然包含在子序列中 int lengthOfLIS(vector<int>& nums) { if(nums.size() <= 1) return nums.empty() ? 0 : 1; vector<int> dp(nums.size(), 1);// 每个数本身算入其中一个 for(int i = 1; i < dp.size(); ++i) for(int k = 0; k < i; ++k) if(nums[k] < nums[i]) dp[i] = max(dp[i], dp[k] + 1); return *max_element(dp.begin(), dp.end()); // 这里需要注意，最大长度不一定出现在dp.back() } // 没明白原理的二分法，建立一个vector<int> ends = {nums[0]}; // 遍历nums, 如果num<ends.front(), 直接替换；如果num>ends.back()，直接压入（非替换） // 如果num < ends.back(),则在ends中查找不小于num的最小数，并将其替换 // 最后ends的长度即为所求（注意此时ends只是长度吻合，其中的数并不是目标上升子序列） int lengthOfLIS(vector<int> &nums){ if(nums.empty()) return 0; vector<int> ends = { nums[0] }; for(int i = 1; i < nums.size(); ++i) if(nums[i] < ends[0]) ends[0] = nums[i]; else if(nums[i] > ends.back()) ends.push_back(nums[i]); else{ int left = 0, right = ends.size(); while(left < right){ int mid = (right - left) / 2 + left; if(ends[mid] < nums[i]) left = mid + 1; else right = mid; } ends[right] = nums[i]; } return ends.size(); }

int wiggleMaxLength(vector<int>& nums) { if(nums.size() <= 1) return nums.size(); vector<int> p(nums.size(), 1); // p[i] 表示 nums[0...i] 中首先往上摆的最长子序列长度 vector<int> q(nums.size(), 1); // q[i] 表示 nums[0...i] 中首先往下摆的最长子序列长度 for(int i = 1; i < nums.size(); ++i) for(int j = 0; j < i; ++j) if(nums[i] > nums[j]) // nums[i] 相比于 nums[j] 向上摆 p[i] = max(p[i], q[j] + 1); // q[j]是往下摆，因此下一次就往上摆到达到达nums[j] else if(nums[i] < nums[j]) // nums[i] 相比于 nums[j] 向下摆 q[i] = max(q[i], p[j] + 1); return max(q.back(), p.back()); } // O(n)，使用贪心思想，用p,q来记录上述两个状态，一遍遍历即可(不知道为什么可以一遍遍历) int wiggleMaxLength(vector<int> &nums){ if(nums.size() <= 1) return nums.size(); int p = 1, q = 1; for(int i = 1; i < nums.size(); ++i) if(nums[i] > nums[i - 1]) // 往上摆 p = q + 1; else if(nums[i] < nums[i - 1]) // 往下摆 q = p + 1; return max(p, q); }

// dp[i][j] - S1中前i项和S2中前j项的最长公共长度。根据S1[i]与S2[j]是否相等有两种情况 // S1[i] == S2[j], 则dp[i][j] = dp[i - 1][j - 1] + 1 // S1[i] != S2[j], dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) int maxCommonLength(const string &s1, const string &s2){ if(s1.empty() || s2.empty()) return 0; vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1, 0)); for(int i = 1; i <= s1.size(); ++i) for(int j = 1; j <= s2.size(); ++j) if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); return dp.back().back(); } // 优化空间 int minDistance(const string &s1, const string &s2){ if(s1.empty() || word2.s2()) return 0; vector<int> dp(s2.size() + 1, 0); vector<int> last_dp(s2.size() + 1, 0); for(int i = 1; i <= s1.size(); ++i){ for(int j = 1; j <= s2.size(); ++j) if(s1[i - 1] == s2[j - 1]) dp[j] = last_dp[j - 1] + 1;// dp[i - 1][j - 1]可能已被更新掉，因此用last_dp保存状态 else dp[j] = max(dp[j - 1], dp[j]); last_dp = dp; } return dp.back(); }

// 思路：找到两个字符串的最长公共子串的大小maxlen, 则需要删除字符的数量为： // word1.size() + word2.size() - 2 * maxLen int minDistance(string word1, string word2) { if(word1.empty() || word2.empty()) return word1.empty() ? word2.size() : word1.size(); vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0)); for(int i = 1; i <= word1.size(); ++i) for(int j = 1; j <= word2.size(); ++j) if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); return word1.size() + word2.size() - 2 * dp.back().back(); } // 优化空间同上一题

// dp[i][j] - s1前i项和s2前j项的最小ASCII删除和，分两种情况 // s1[i] == s2[j], 不用删除，则dp[i][j] = dp[i - 1][j - 1] // s1[i] != s2[j], 需要删除，可以删除s1[i],也可以删除s2[j] // 看删除后哪个更小 => dp[i][j] = min(s1[i] + dp[i - 1][j], s2[j] + dp[i][j - 1]) int minimumDeleteSum(string s1, string s2) { vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0)); // 第一行，dp[0][j], 表示s2前j个字母变为空字符的ASCII数。第一列同理 for(int j = 1; j <= s2.size(); ++j) dp[0][j] = dp[0][j - 1] + int(s2[j - 1]); for(int i = 1; i <= s1.size(); ++i) dp[i][0] = dp[i - 1][0] + int(s1[i - 1]); for(int i = 1; i <= s1.size(); ++i) for(int j = 1; j <= s2.size(); ++j) if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]); return dp.back().back(); } // 优化空间 int minimumDeleteSum(string s1, string s2){ vector<int> dp(s2.size() + 1, 0); vector<int> last_dp(s2.size() + 1, 0); for(int j = 1; j <= s2.size(); ++j) dp[j] = dp[j - 1] + int(s2[j - 1]); last_dp = dp; for(int i = 1; i <= s1.size(); ++i){ dp[0] = dp[0] + int(s1[i - 1]); for(int j = 1; j <= s2.size(); ++j) if(s1[i - 1] == s2[j - 1]) dp[j] = last_dp[j - 1]; // 只有这里需要用上一次的状态（即二维dp时该处的左上角） else dp[j] = min(dp[j] + int(s1[i - 1]), dp[j - 1] + int(s2[j - 1])); last_dp = dp; } return dp.back(); }

// ∅ a b c d	当 s1[i] != s2[j]时，分三种情况可以从s1->s2 // ∅ 0 1 2 3 4	操作a. s1[i]处插入字符s[j]使之相等，则比较s1[i + 1], s2[j]即可 // b 1 1 1 2 3	操作b. s1[i]处的字符删除，直接比较s1[i],s1[j + 1]即可 // b 2 2 1 2 3	操作c. s1[i]处的字符变为s[j]处的字符，则比较s1[i + 1], s2[j + 1]即可 // c 3 3 2 1 2	☆这三种操作分别对应的 dp[i][j] 的左侧、上侧、左上侧 + 1，看哪种操作更少 //  // 对比[最长公共子序列]问题，该问题和本问题类似。区别在于： // [最长公共子序列]： //	允许操作a,b(删除)，不允许c(修改), 对应的是 dp[i][j] 的左侧、上侧 + 1， 而没有左上侧 + 1 // [编辑距离]： //允许操作a,b,c，因此是左侧、上侧、左上侧 + 1, 并看哪种更少 int minDistance(string s1, string s2) { vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0)); for(int j = 1; j <= s2.size(); ++j) dp[0][j] = j; for(int i = 1; i <= s1.size(); ++i) dp[i][0] = i; for(int i = 1; i <= s1.size(); ++i) for(int j = 1; j <= s2.size(); ++j) if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; return dp.back().back(); } // 优化空间，同前面几个题

// dp[i][j] - A中以第i项结尾子数组，和B中以第j项结尾子数组的最长公共长度，根据A[i]，B[j]是否相等分两种情况 // A[i] == B[j], 则dp[i][j] = dp[i - 1][j - 1] + 1 // A[i] != B[j], dp[i][j] = 0 int findLength(vector<int>& A, vector<int>& B) { vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0)); int maxLen = 0; for(int i = 1; i <= A.size(); ++i) for(int j = 1; j <= B.size(); ++j) if(A[i - 1] == B[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; maxLen = max(maxLen, dp[i][j]); }else dp[i][j] = 0; return maxLen; } // 优化空间 int findLength(vector<int> &A, vector<int> &B){ vector<int> dp(B.size() + 1, 0); int maxLen = 0; for(int i = 1; i <= A.size(); ++i) for(int j = B.size(); j >= 1; --j) // 注意，这里必须从后往前遍历 if(A[i - 1] == B[j - 1]){ // ↓ dp[j] = dp[j - 1] + 1; // dp[j]需要使用前一个，前一个却可能已经更新过了 maxLen = max(maxLen, dp[j]); }else dp[j] = 0; return maxLen; }

// 思路：使用curSum,maxSum记录当前区间、最大区间和 int maxSubArray(vector<int>& nums) { if(nums.empty()) return 0; int maxSum = INT_MIN; int curSum = 0; for(const auto &num:nums){// curSum + num < num 时，说明curSum对区间和为负增益效果 curSum = max(num, curSum + num); // 因此直接让num为当前的区间（区间内只含一个数） maxSum = max(curSum, maxSum); } return maxSum; }

// 思路：与leetcode.53最大子序和类似，区别在于53求的是i~j, 本题可以为i~j, 也可以为0~i + j~n // 对于 i~j 的情况：直接沿用leetcode.53中的解法 // 对于 0~i + j~n 的情况：可以求最小子序和, sum-最小子序和即为环形子数组的最大和 // 判断两种情况谁的结果更大即可 int maxSubarraySumCircular(vector<int>& A) { if(A.empty()) return 0; // i~j 的情况 int maxSum = INT_MIN; int curSum = 0; bool all_minus = true; for(const auto &num:A){ curSum = max(num, curSum + num); maxSum = max(curSum, maxSum); if(num > 0) all_minus = false; } if(all_minus == true)// 对于所有数均为负数时，minSum == sum return maxSum;// 此时sum - minSum必然为0, 因此需要返回A中最大值, 即maxSum // 0~i + j~n 的情况 int sum = 0; // 保存A的所有元素和 int minSum = INT_MAX; curSum = 0; for(const auto &num:A){ curSum = min(num, curSum + num); minSum = min(curSum, minSum); sum += num; } return max(maxSum, sum - minSum);// 取 }

// 思路：dp[i] - A[i]结尾的子区间的数量（注意，A[i]） // 因此，A[i] - A[i - 1] == A[i - 1] - A[i - 2], 则dp[i] = dp[i - 1] + 1 // 0 1 2 3 4 5 9 10 // dp[2] = 1, 等差数列为 0 1 2 // dp[3] = 2, 等差数列为 1 2 3, 0 1 2 3 // dp[4] = 3, 登差数列为 2 3 4, 1 2 3 4, 0 1 2 3 4 // dp[5] = 4, 等差数列为 3 4 5, 2 3 4 5, 1 2 3 4 5, 0 1 2 3 4 5 // dp[6] = dp[7] = 0 int numberOfArithmeticSlices(vector<int>& A) { if(A.size() <= 2) return 0; vector<int> dp(A.size(), 0); for(int i = 2; i < A.size(); ++i) if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) dp[i] = dp[i - 1] + 1; return accumulate(dp.begin(), dp.end(), 0); } // 优化空间 int numberOfArithmeticSlices(vector<int> &A){ if(A.size() <= 2) return 0; int dp = 0, sum = 0; for(int i = 2; i < A.size(); ++i) if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) dp += 1, sum += dp; else dp = 0; return sum; }

// 思路：sums保存累加和，则区间[i...j]的和为sums[j] - sums[i - 1] (包含i在内) class NumArray { private: vector<int> sums; public: NumArray(vector<int>& nums) { int sum = 0; for(auto num:nums){ sum += num; sums.push_back(sum); } } int sumRange(int i, int j) { return i == 0 ? sums[j] : sums[j] - sums[i - 1]; } };

// 思路：受leetcode.303启发, 建立累加数组sums, 其中sums[i] = nums[0] + ... + nums[i] // 则区间(i, j]的和为sums[j] - sums[i]. 为使(i, j]区间和为 target, 问题转化为: // 在区间和sums[0] ··· sums[j - 1]中，是否存在k使得sums[j]-sums[k]为target，存在多少个? // 为提高效率，使用哈希表ordered_map保存sum出现的次数 int subarraySum(vector<int>& nums, int target) { if(nums.empty()) return 0; unordered_map<int, int> map; map[0] = 1; // 这里map[0]=1是为了保证区间[0, i]也能计算 int cur_sum = 0, cnt = 0; // ↓ 举个栗子，比如对 nums = 2,3,10 target = 5 for(int i = 0; i < nums.size(); ++i){ // ↓ 如果不加入map[0] = 2, 则遍历到3时: cur_sum += nums[i]; // ↓ sum = 5, map = { 2:1 }, cur_sum - target = 0 if(map.count(cur_sum - target) > 0) // ↓ 此时map中没有0这一项, 没法统计 2 + 3 这一项 cnt += map[cur_sum - target]; // 这里 ++map[cur_sum]; } return cnt; }

// 思路：解法同leetcode.560完全相同 int numSubarraysWithSum(vector<int>& nums, int target) { if(nums.empty()) return 0; unordered_map<int, int> map; map[0] = 1; int cur_sum = 0, cnt = 0; for(int i = 0; i < nums.size(); ++i){ cur_sum += nums[i]; if(map.count(cur_sum - target) > 0) cnt += map[cur_sum - target]; ++map[cur_sum]; } return cnt; }

// 思路：和leetcode.560思路相同，使用累加和，需要改动一些地方 // 改动1. 对累加和 % target. 在这样的情况下假设区间 [i, j] 的和为target的倍数 // 则有：sums[i] + n * target = sums[j] => sums[j] % sums[j] = sums[i] % target // 即当出现两个累加和相同时，则可确定存在区间和为target的倍数 // 改动2. 为了保证区间长度 > 1, 可用unordered_map保存每个累加和第一次出现的位置 bool checkSubarraySum(vector<int>& nums, int target) { if(nums.size() <= 1) return false; unordered_map<int, int> map; map[0] = -1; int cur_sum = 0; for(int i = 0; i < nums.size(); ++i){ cur_sum += nums[i]; // 累加和 if(target != 0) cur_sum %= target; // 改动1, 让区间和为0 ... target - 1 if(map.count(cur_sum) > 0){ // 存在该累加和 if(i - map[cur_sum] > 1)// 且区间长度 > 1 return true; }else map[cur_sum] = i; // 改动2. 保存第一个出现该累加和的位置 } return false; }

// 思路：使用两个个数组dp1, dp2, 分别表示以nums[i]结尾的最大乘积、最小乘积，再通过maxprod记录最大乘积 // 则： dp1[i] 必然从 dp1[i - 1]*nums[i], dp2[i - 1]*nums[i], nums[i] 中选择最大的一个 // dp2[i] 必然从 ...选择最小的一个 // maxprod = max(maxprod, dp1[i]); int maxProduct(vector<int>& nums) { int maxprod = nums[0]; vector<int> dp1(nums.size(), 0), dp2(nums.size(), 0); dp1[0] = nums[0]; dp2[0] = nums[0]; for(int i = 1; i < nums.size(); ++i){ dp1[i] = max(nums[i], max(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i])); dp2[i] = min(nums[i], min(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i])); maxprod = max(maxprod, dp1[i]); } return maxprod; } // 优化空间 int maxProduct(vector<int> &nums){ int maxprod = nums[0]; int dp1 = nums[0], last_dp1 = dp1;// 使用last_dp1保存上一次的状态 int dp2 = nums[0], last_dp2 = dp2; for(int i = 1; i < nums.size(); ++i){ dp1 = max(nums[i], max(last_dp1 * nums[i], last_dp2 * nums[i])); dp2 = min(nums[i], min(last_dp1 * nums[i], last_dp2 * nums[i])); maxprod = max(maxprod, dp1); last_dp1 = dp1; last_dp2 = dp2; } return maxprod; }

// 思路：由于nums中全都是正数，因此可以使用双指针，而非动态规划，注意区别 int numSubarrayProductLessThanK(vector<int>& nums, int target) { if(target <= 0 || nums.empty()) return 0; int left = 0, right = 0; int prod = 1; int cnt = 0; while(right < nums.size()){ prod *= nums[right]; while(left <= right && prod >= target) prod /= nums[left++]; cnt += prod < target ? right - left + 1 : 0; ++right; } return cnt; }

// 思路：动态规划，dp[i][j] - 前i件物品体积不超过j的最大价值 // 假设第i件物品的体积为vol, 价值为val. 则改件物品有两种选项： // 1. 放入背包, 则dp[i][j] = dp[i - 1][j - vol] + val // 2. 不放入背包, 则dp[i][j] = dp[i - 1][j] // 两者取较大的 ===> dp[i][j] = max(dp[i - 1][j - vol] + val, dp[i - 1][j]) // V为背包容量, volumes和values分别为每件物品的体积和价值 int knapsack(const int V, const vector<int> &volumes, const vector<int> &values){ if(V <= 0 || volumes.size() <= 0)// 确保背包有容积、存在需要放入背包的物体 return 0; int num = volumes.size();// 物品数量为num vector<vector<int>> dp(num, vector<int>(V + 1, 0)); // 第0件物品: 在背包容积vol >= volumes[0]时，可以将第0件物品放入背包 for(int vol = 0; vol <= V; ++vol) dp[0][vol] = (vol >= volumes[0]) ? values[0] : 0; // 第1, 2, 3, ..., num-1件物品，使用上述通项公式 for(int i = 1; i < num; ++i) for(int vol = 0; vol <= V; ++vol) if(vol >= volumes[i]) // 背包容积vol >= 物品体积时, 尝试放入该物品 dp[i][vol] = max(dp[i - 1][vol], dp[i - 1][vol - volumes[i]] + values[i]); else // 背包容积vol < 物品体积时, 必然不放入该物品 dp[i][vol] = dp[i - 1][vol]; return dp.back().back(); } // 空间优化, 因为对dp是一行一行进行操作, 所以dp可以直接使用一维数组 int knapsack1(const int V, const vector<int> &volumes, const vector<int> &values){ if(V <= 0 || volumes.size() <= 0) return 0; int num = volumes.size(); vector<int> dp(V + 1, 0); // 第0件物品 for(int vol = 0; vol <= V; ++vol) dp[vol] = (vol >= volumes[0]) ? values[0] : 0; // 第1,2,...,num-1件物品 for(int i = 1; i < num; ++i) for(int vol = V; vol >= volumes[i]; --vol)// 必须从大到小遍历, 防止小到大遍历时使用已更改数据 dp[vol] = max(dp[vol], dp[vol - volumes[i]] + values[i]); return dp.back(); }

// 思路：0-1背包, 背包容量为sum/2, 物品只存在重量属性, 挑选物品恰好装满背包 // dp[i][j] - 下标0~i的数,是否存在某个子集使其总重量为j, 递推关系为 // dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] bool canPartition1(vector<int> &nums){ int sum = accumulate(nums.begin(), nums.end(), 0); if(nums.size() <= 1 || sum % 2 == 1) return false; int V = sum / 2; vector<vector<bool>> dp(nums.size(), vector<bool>(V + 1, 0)); dp[0][0] = true; // 不放入第0件物品 dp[0][nums[0]] = true; // 要放入第0件物品 for(int i = 1; i < nums.size(); ++i) for(int vol = 0; vol <= V; ++vol) if(vol >= nums[i]) // 背包容积 >= 物品体积, 尝试放入物体 dp[i][vol] = dp[i - 1][vol] || dp[i - 1][vol - nums[i]]; else // 背包容积 < 物品体积，必然不放入物体 dp[i][vol] = dp[i - 1][vol]; return dp.back().back(); } // 优化空间, 同时根据可以提前结束节省时间 bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if(nums.size() <= 1 || sum % 2 == 1) return false; int V = sum / 2; vector<bool> dp(V + 1, false); dp[0] = true; // 不放入任何物品 for(const auto &num:nums) for(int vol = V; vol >= num; --vol){ // 必须从大到小遍历, 防止小到大使用了已更改数据 dp[vol] = dp[vol] || dp[vol - num]; if(dp.back()) // 已找到, 提前结束 return true; } return dp.back(); }

// 思路1: 可以使用0-1背包的变种, 此题中为多个背包, 物品1种属性,解法比较复杂 // 思路2: 直接使用backtracking方法 bool canPartitionKSubsets(vector<int>& nums, int k) { int sum = 0, maxnum = INT_MIN; for(const auto &num:nums) sum += num, maxnum = max(maxnum, num); if(nums.size() < k || sum % k != 0 || maxnum > sum / k) return false; vector<bool> used(nums.size(), false); return backtracking(nums, used, k, sum / k, 0, 0); } bool backtracking(vector<int> &nums, vector<bool> &used, int k, int tarSum, int curSum, int idx){ if(k == 0) // 已经搜索到了k个子集 return true; if(curSum == tarSum) // 搜索下一个子集 return backtracking(nums, used, k - 1, tarSum, 0, 0); for(int i = idx; i < nums.size(); ++i) // 这里如果每次都从0开始搜索则会超时, 从idx开始 if(used[i] == false && curSum + nums[i] <= tarSum){ used[i] = true; if(backtracking(nums, used, k, tarSum, curSum + nums[i], i + 1)) return true; used[i] = false; } return false; }

// 思路：假设其中符号为+的数的和为P, 符号为-的数的和为N, P + N = nums的和 // P - N = S => 两边都加上sum => (P + N) + (P - N) = S + sum => P = (S + sum) / 2 // 转化：是否存在nums的子集, 使其和为(S + sum) / 2, 这样的子集有多少个? // dp[j] - 子集和为j的子集个数, dp[j] = dp[j] + dp[j - nums[i]] int findTargetSumWays(vector<int>& nums, int S) { int sum = accumulate(nums.begin(), nums.end(), 0); if(sum < S || (sum + S) % 2 != 0) return 0; int N = (sum + S) / 2; vector<int> dp(N + 1, 0); dp[0] = 1; // 空集的和为0, 一种情况 for(const auto &num:nums) for(int vol = N; vol >= num; --vol) // 必须从大到小遍历, 防止小到大使用了已更改数据 dp[vol] = dp[vol] + dp[vol - num]; return dp.back(); }

// 思路：与leetcode.416类似, 视为0-1背包, 每种物品只有一种属性 // 转化为：背包的大小为字符串长度, 是否存在一个物品的子集恰好装满背包, 且每种物品都是无限的 // dp[i] - 前i个字符是否能被拆分为wordDict中的单词, 递推关系为dp[i] = dp[i] || dp[i - word.size()] bool wordBreak(string s, vector<string>& wordDict) { vector<bool> dp(s.size() + 1, false); dp[0] = true; for(int i = 1; i <= s.size(); ++i) for(const auto &word:wordDict) if(word.size() <= i && s.substr(i - word.size(), word.size()) == word) dp[i] = dp[i] || dp[i - word.size()]; return dp.back(); }

// 和leetcode.139单词拆分类似，是一个0-1背包问题，每种物品无限多 int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for(int i = 1; i < dp.size(); ++i) for(const auto &coin:coins) if(coin <= i && dp[i - coin] != INT_MAX) dp[i] = min(dp[i], dp[i - coin] + 1); return dp.back() == INT_MAX ? -1 : dp.back(); }

// 思路：又双叒叕是每种物品无限多的0-1背包问题 int combinationSum4(vector<int>& nums, int target) { vector<unsigned long long> dp(target + 1, 0); dp[0] = 1; for(int i = 1; i < dp.size(); ++i) for(const auto &num:nums) if(num <= i) dp[i] += dp[i - num]; return dp.back(); } // 存在负数时：TODO

// 思路1:直接使用回溯backtracking方法，但是会超时，写在这里做下参考 vector<string> wordBreak(string s, vector<string>& wordDict) { vector<string> res; string sbroken; backtracking(s, res, sbroken, wordDict, 0); return res; } void backtracking(const string &s, vector<string> &res, string sbroken, vector<string> &wordDict, int idx){ if(idx == s.size()){ res.push_back(sbroken); return; } for(const auto &word:wordDict) if(word.size() + idx <= s.size() && s.substr(idx, word.size()) == word){ string tmp = sbroken; sbroken += sbroken.empty() ? word : (" " + word); backtracking(s, res, sbroken, wordDict, idx + word.size()); sbroken = tmp; } } // 思路2:使用动态规划，unordered_map<string, vector<string>> 记录s的拆分结果 vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_map<string, vector<string>> map; map[""] = {""}; // 这里初始化空串的拆分方式，肥肠重要！！ dynamicProg(s, wordDict, map); return map[s]; } void dynamicProg(string s, vector<string> &wordDict, unordered_map<string, vector<string>> &map){ if(map.count(s) > 0 || s.empty()) // s已被拆分过或为空，直接返回，不用拆分 return; vector<string> res; for(const auto &word:wordDict) if(s.substr(0, word.size()) == word){ // s可拆分为word + 后半部分 dynamicProg(s.substr(word.size()), wordDict, map); // 继续拆分后半 auto brokens = map[s.substr(word.size())]; // 将word和后半部分的拆分组合起来 for(auto broken:brokens) res.push_back(word + (broken.empty() ? "" : " ") + broken); } map[s] = res; // s的拆分结果放入map备用 }

// 思路1：与leetcode.139单词拆分基本一样，只需要对words中的每个词调用单词拆分函数即可 // 这一思路很容易超时 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { if(words.size() <= 1) return {}; vector<string> res; unordered_set<string> wordsets(words.begin(), words.end()); for(const auto &s:words){ wordsets.erase(s); // 不能拆分为自己 vector<bool> dp(s.size() + 1, false); dp[0] = true; for(int i = 1; i <= s.size(); ++i){ for(int j = 0; j < i; ++j) if(dp[j] == true && wordsets.count(s.substr(j, i - j)) > 0) dp[i] = true; if(dp.back() == true){ // 找到后提前截止 res.push_back(s); wordsets.insert(s); break; } } wordsets.insert(s); // 没找到也要将该词复原 } return res; } // 思路二：使用前缀树 // TODO: 写完数据结构中的树再来解这个题

// 思路：多维背包为题，每个物品都有两类属性，0、1的数量，两类属性的背包容量为m、n，最多能放多少个物品 int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for(const auto &s:strs){ int zeros = 0, ones = 0; for(const auto &c:s) c == '0' ? ++zeros : ++ones;// 统计属性 for(int i = m; i >= zeros; --i)// 必须大到小遍历，防止小到大使用已更改数据 for(int j = n; j >= ones; --j) dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1); } return dp.back().back(); }

// 思路：动态规划 // local[i][j] - 到达第i天最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润, 此为局部最大值 // global[i][j] - 到达第i天最多可进行j次交易的最大利润，此为全局最大值 // 局部最大：前一天少交易一次的全局最优加上>0的差值,和前一天的局部最后加差值(不在前一天卖，而在这一天卖)，取大值 // 全局最大：比较当天的局部最优，对比前一天的全局最优，两者取较大值 //	local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff) //	global[i][j] = max(local[i][j], global[i - 1][j]) int maxProfit1(vector<int>& prices) { if(prices.empty()) return 0; vector<vector<int>> global(prices.size(), vector<int>(2 + 1, 0)); vector<vector<int>> local(prices.size(), vector<int>(2 + 1, 0)); for(int i = 1; i < prices.size(); ++i){ int diff = prices[i] - prices[i - 1]; for(int j = 1; j <= 2; ++j){ local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff); global[i][j] = max(local[i][j], global[i - 1][j]); } } return global.back().back(); } // 优化空间 int maxProfit(vector<int> &prices){ if(prices.empty()) return 0; vector<int> global(2 + 1, 0); vector<int> local(2 + 1, 0); for(int i = 1; i < prices.size(); ++i){ int diff = prices[i] - prices[i - 1]; for(int j = 2; j >= 1; --j){ // 必须从大到小遍历，防止小到大使用已更新数据 local[j] = max(global[j - 1] + max(0, diff), local[j] + diff); global[j] = max(local[j], global[j]); } } return global.back(); }

// 思路：同leetcode.123买卖股票最佳时机III完全类似 int maxProfit(int k, vector<int>& prices) { if(prices.size() <= 1) return 0; // 可交易的次数大于股票数量，可以随意进行买卖，此题退化为leetcode.122买卖股票最佳时机II if(k >= prices.size()){ int prof = 0; for(int i = 1; i < prices.size(); ++i) prof += (prices[i] - prices[i - 1] >= 0) ? prices[i] - prices[i - 1] : 0; return prof; } vector<vector<int>> local(prices.size(), vector<int>(k + 1, 0)); vector<vector<int>> global(prices.size(), vector<int>(k + 1, 0)); for(int i = 1; i < prices.size(); ++i){ int diff = prices[i] - prices[i - 1]; for(int j = 1; j <= k; ++j){ local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff); global[i][j] = max(local[i][j], global[i - 1][j]); } } return global.back().back(); } // 空间优化，同leetcode.123完全类似

// 动态规划的思想： // sell[i] - 第i天结束后，手里没有股票，获得的最大收益 // hold[i] - 第i天结束后，手里持有股票，获得的最大收益 // 对sell[i], 当天啥也没干(sell[i - 1]), 当天卖出昨天持有的股票(hold[i - 1], price[i])，取较大值。 // sell[i] = max(sell[i - 1], hold[i - 1] + price[i]) ,	由于当天结束手里没有股票，因此当天不可能买入。 // 对hold[i], 当天啥也没干(hold[i - 1]), 当天买入了股票(sell[i - 2] - price[i])，取较大值。 // hold[i] = max(hold[i - 1], sell[i - 2] - price[i]), 由于当天结束手里持有股票，因此当天不可能卖出 int maxProfit(vector<int>& prices) { if(prices.size() <= 1) return 0; vector<int> sell(prices.size(), INT_MIN); vector<int> hold(prices.size(), INT_MIN); sell[0] = 0; // 第0天卖出股票，收益为0 hold[0] = -prices[0]; // 第0天买入股票，收益为-prices[0] sell[1] = max(sell[0], hold[0] + prices[1]); hold[1] = max(hold[0], 0 - prices[1]); for(int i = 2; i < prices.size(); ++i){ sell[i] = max(sell[i - 1], hold[i - 1] + prices[i]); hold[i] = max(hold[i - 1], sell[i - 2] - prices[i]); } return sell.back(); }

// 动态规划: dp[i] - 十进制i的二进制表示中1的个数 // n & (n - 1) 用来去除n的最低位上的1，因此该结果恰好比n少一个二进制1 ==>> dp[n] = dp[n & (n - 1)] + 1 // n = 1100 // n - 1 = 1011 // n & (n - 1) = 1000 vector<int> countBits(int num) { vector<int> dp(num + 1, 0); for(int i = 1; i <= num; ++i) dp[i] = dp[i & (i - 1)] + 1; return dp; }

// 思路1:动态规划法O(n^2), 类似暴力求解 int findLongestChain1(vector<vector<int>> &pairs){ sort(pairs.begin(), pairs.end()); vector<int> dp(pairs.size(), 1); for(int i = 0; i < pairs.size(); ++i) for(int j = 0; j < i; ++j) if(pairs[j][1] < pairs[i][0]) dp[i] = max(dp[i], dp[j] + 1); return *max_element(dp.begin(), dp.end()); } // 思路2:贪心算法O(nlogn)，按照第二个数字小到大排序，最小的压入栈， // 遍历每个数对，数对第一个数比栈顶数对的第二个数大即将其入栈,遍历完成后栈的大小即为所求 int findLongestChain(vector<vector<int>>& pairs) { if(pairs.empty()) return 0; sort(pairs.begin(), pairs.end(), comp); stack<vector<int>> st; st.push(pairs[0]); for(int i = 1; i < pairs.size(); ++i) if(st.top()[1] < pairs[i][0]) st.push(pairs[i]); return st.size(); } bool comp(vector<int> p1, vector<int> p2){ return p1[1] < p2[1]; }

// 动态规划，dp[i] - i个A最少可有多少次操作 int minSteps(int n) { vector<int> dp(n + 1, INT_MAX); dp[1] = 0; // 1个字符，无需操作，本身就有 // 复制前i个字符(1次操作), 粘贴若干次 for(int i = 1; i < dp.size(); ++i) for(int paste = 1; i + paste * i < dp.size(); ++paste) dp[i + paste * i] = min(dp[i + paste * i], dp[i] + 1 + paste); return dp.back(); }

// 找到一个质数a，可以将小于n的a的倍数全部刨除 int countPrimes(int n) { if(n <= 1) return 0; vector<int> primes(n, true); int cnt = 0; for(int i = 2; i < primes.size(); ++i){ if(primes[i] == false)// 该数不是质数，不用理会 continue; ++cnt;// 该数是质数，计数+1，并将该质数的倍数全部排除在外 for(int multi = 2; multi*i < n; ++multi) primes[multi * i] = false; } return cnt; }

bool isUgly(int num) { if(num <= 0) return false; while(num % 2 == 0) // 排除质因子2 num /= 2; while(num % 3 == 0) // 排除质因子3 num /= 3; while(num % 5 == 0) // 排除质因子5 num /= 5; return num == 1; }

// 质因子| 1倍 2倍 3倍 4倍 5倍  // 2 | 2 4 6 8 10	由质因子个1/2/3/4...倍即可生成丑数序列 // 3 | 3 6 9 12 15 // 5 | 5 10 15 20 25 int nthUglyNumber(int n) { vector<int> uglys = {1};// 初始化，第一个丑数是1 int p2 = 0, p3 = 0, p5 = 0; while(uglys.size() < n){ // 对uglys={1}, 下一个丑数必然是1*2, 1*3, 1*5的较小值，得到uglys={1,2} // 对uglys={1,2}, 下一个丑数必然是2*2, 1*3, 1*5的较小值，得到uglys={1,2,3} // 对uglys={1,2,3}, 下一个丑数必然是2*2, 2*3, 1*5的较小值，得到uglys={1,2,3,4} 以此类推 int nextUgly = min(uglys[p2]*2, min(uglys[p3]*3, uglys[p5]*5)); if(nextUgly == uglys[p2]*2)// 如果下一个丑数是uglys[p2]*2，则将下标p2右移一格. 下面同理 ++p2; if(nextUgly == uglys[p3]*3) ++p3; if(nextUgly == uglys[p5]*5) ++p5; uglys.push_back(nextUgly);// 下一个丑数放入丑数数组里 } return uglys.back(); }

// 思路：本题和leetcode.264丑数的解法完全一致 int nthSuperUglyNumber(int n, vector<int>& primes) { vector<int> uglys = {1}; vector<int> idxs(primes.size(), 0); while(uglys.size() < n){ int nextUgly = INT_MAX; for(int i = 0; i < idxs.size(); ++i) nextUgly = min(nextUgly, uglys[idxs[i]] * primes[i]); for(int i = 0; i < idxs.size(); ++i) if(nextUgly == uglys[idxs[i]] * primes[i]) ++idxs[i]; uglys.push_back(nextUgly); } return uglys.back(); }

int gcd(int a, int b){// a、b谁大谁小没有要求 return (a % b == 0) ? b : gcd(b, a % b); } int gcd(int a, int b){// 和上一个两者等价 return b == 0 ? a : gcd(b, a % b); }

int lcm(int a, int b){ return a * b / gcd(a, b); }

// 本质上是求最大公约数, 得到 gcd = gcd_func(p, q) // 水平方向走了 w = p / gcd 格, 竖直方向走了 h = q / gcd 格 // 根据 w 和 q 的奇偶性判断哪个接收器接收 int mirrorReflection(int p, int q) { int gcd = gcd_func(p, q); int w = p / gcd, h = q / gcd; if((w % 2 == 1) && (h % 2 == 0)) // 横向走了奇数格, 纵向走了偶数格 return 0; if((w % 2 == 1) && (h % 2 == 1)) // 横向走了奇数格, 纵向走了奇数格 return 1; if((w % 2 == 0) && (h % 2 == 1)) // 横向走了偶数个, 纵向走了奇数格 return 2; return -1; // 不可能横向偶数个, 纵向偶数格, 因为保证有解 } // 函数：求最大公约数 int gcd_func(int a, int b){ return b == 0 ? a : gcd_func(b, a % b); }

// 100 = 2 * 7^2 + 0 * 7^1 + 2 * 7^0 string convertToBase7(int num) { if(num == 0) return "0"; string res; bool sign = num < 0; num = num > 0 ? num : -num; while(num > 0){ res = to_string(num % 7) + res; num /= 7; } return sign ? ("-" + res) : res; }

// 思路：本题是26进制转换的一个变种，要肥肠注意与普通的26进制的区别 // 比如7进制，每一位上可能出现的数是 0，1，2，3，4，5，6 // 再比如普通的26进制，每一位上可能出现的数是 0，1，2，...，24，25 // 但是，本题是26进制转换的一个变种，每一位上可能出现的数数 1，2，3，...，24，25，26，要肥肠注意 string convertToTitle(int n) { string res; while(n > 0){ n -= 1;// 关键点 res = table[n % 26] + res; n /= 26; } return res; } vector<string> table = { "A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z" };

int titleToNumber(string s) { long long res = 0; for(int i = 0; i < s.size(); ++i){ res *= 26; res += s[i] - 'A' + 1; } return res > INT_MAX ? INT_MAX : res;; }

// 思路：转化为无符号之后再进制转换 string toHex(int num) { if(num == 0) return "0"; unsigned int n = num; string res; while(n != 0){ res = table[n % 16] + res; n /= 16; } return res; } vector<string> table = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};

// 思路：数字n是(n-1)进制下的11，(n-1)进制是好进制，因此最小好进制必然为k=[2,n-1], 可用二分法 // k进制，共m位1，则有关系式 // n = 1 + k + k^2 + ... + k^(m - 1) = (1 - k^m) / (1 - k) >= k^(m - 1) => k <= n^(1-m) // k >= 2, 则有m <= 1 + logn/logk <= 1 + logn/log2 // 为使位数m更大，可让 m 从 1+logn/log2 -> 2进行遍历，遍历过程中二分搜索进制k string smallestGoodBase(string n) { unsigned long long num = stol(n); for(int m = log(num) / log(2) + 1; m >= 2; --m){ // 搜索位数m int k_left = 2, k_right = pow(num, 1.0 / (m - 1)) + 1; // 搜索进制k while(k_left <= k_right){ int k_mid = (k_right - k_left) / 2 + k_left; unsigned long long sum = 0; for(int i = 0; i < m; ++i) sum = sum * k_mid + 1; if(sum == num) return to_string(k_mid); else if(sum < num) k_left = k_mid + 1; else k_right = k_mid - 1; } } return to_string(num - 1); // n-1进制的11 }

// 没什么难度，就是需要考虑的情况过多 string validIPAddress(string IP) { vector<int> seg; // 分割符 . : 的位置 for(int i = 0; i < IP.size(); ++i) if(IP[i] == '.' || IP[i] == ':') seg.push_back(i); if(seg.size() == 3){ // IPv4, 3个 . for(auto c:IP) if(!(isdigit(c) || c == '.')) return "Neither"; string ad1 = IP.substr(0, seg[0]); string ad2 = IP.substr(seg[0] + 1, seg[1] - seg[0] - 1); string ad3 = IP.substr(seg[1] + 1, seg[2] - seg[1] - 1); string ad4 = IP.substr(seg[2] + 1); if(ad1.empty() || ad1.size() > 3 || stoi(ad1) > 255 || (ad1[0] == '0' && ad1.size() > 1) || ad2.empty() || ad2.size() > 3 || stoi(ad2) > 255 || (ad2[0] == '0' && ad2.size() > 1) || ad3.empty() || ad3.size() > 3 || stoi(ad3) > 255 || (ad3[0] == '0' && ad3.size() > 1) || ad4.empty() || ad4.size() > 4 || stoi(ad4) > 255 || (ad4[0] == '0' && ad4.size() > 1)) return "Neither"; else return "IPv4"; }else if(seg.size() == 7){ // IPv6, 7个 : string ad1 = IP.substr(0, seg[0]); if(ad1.empty() || hex2dec(ad1) > 65535 || ad1.size() > 4) return "Neither"; for(int i = 0; i < seg.size() - 1; ++i){ string ad = IP.substr(seg[i] + 1, seg[i + 1] - seg[i] - 1); if(ad.empty() || hex2dec(ad) > 65535 || ad.size() > 4) return "Neither"; } string ad8 = IP.substr(seg[6] + 1); if(ad8.empty() || hex2dec(ad8) > 65535 || ad8.size() > 4) return "Neither"; return "IPv6"; }else // 分割符号数量不对 return "Neither"; return ""; } int hex2dec(string s){ int res = 0; for(int i = 0; i < s.size(); ++i) if(isdigit(s[i])) res = res * 16 + s[i] - '0'; else if(isalpha(s[i])){ if(tolower(s[i]) > 'f') return 65536; res = res * 16 + (tolower(s[i]) - 'a' + 10); }else return 65536; return res; }