post

算法题笔记

· 21 分钟阅读 · 4339 字

目录

C++数据结构用法

通用头文件：

#include <bits/stdc++.h>

std::list::splice

在C++中，std::list 和 std::forward_list 容器提供了一个名为 splice 的成员函数。这个函数用于在常数时间内从一个列表转移元素到另一个列表，无需复制或移动元素，只是改变节点的指针。这使得 splice 特别高效，适用于需要重组列表元素时不引入额外性能开销的场景。

std::list::splice 函数有几个重载版本，允许你在不同的情况下使用。以下是一些最常用的重载形式：

  1. 将整个列表转移到另一个位置:

    cpp
Copy code
void splice(const_iterator pos, list& other);

    这个版本将 other 列表中的所有元素转移到调用者列表中 pos 位置之前。操作后 other 为空。

  2. 将来自另一个列表的单个元素转移到指定位置:

    cpp
Copy code
void splice(const_iterator pos, list& other, const_iterator it);

    这个版本只转移 other 列表中由迭代器 it 指向的单个元素到调用者列表中 pos 位置之前。

  3. 将来自另一个列表的一段元素范围转移到指定位置:

    cpp
Copy code
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);

    这个版本将 other 列表中从 first 到 last（不包括 last）的元素转移到调用者列表中 pos 位置之前。

二分查找

C++ 标准库中提供了几个用于二分查找的函数，这些函数都定义在 <algorithm> 头文件中。这些函数的前提是操作的区间必须是有序的。下面是C++中常用的几个二分查找相关的函数：

  1. std::binary_search:
    • 这个函数用来判断一个给定的值是否存在于有序序列中。
    • 函数原型通常是：bool binary_search(ForwardIt first, ForwardIt last, const T& value)
    • 返回值是一个布尔值，如果找到指定元素则返回 true，否则返回 false。
  2. std::lower_bound:
    • 用于找到一个范围内第一个不小于（大于等于）给定值的元素。
    • 函数原型：ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
    • 返回一个迭代器，指向找到的元素。如果所有元素都小于给定值，则返回 last。
  3. std::upper_bound:
    • 查找第一个大于指定值的元素。
    • 函数原型：ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
    • 返回一个迭代器，指向第一个大于指定值的元素。如果没有元素大于指定值，则返回 last。
  4. std::equal_range:
    • 同时返回 lower_bound 和 upper_bound 的结果。
    • 函数原型：pair<ForwardIt, ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& value)
    • 返回一对迭代器，第一个迭代器指向第一个不小于给定值的元素，第二个迭代器指向第一个大于给定值的元素。

Lambda 表达式

Lambda 表达式的基本语法如下：

cppCopy code[ capture_clause ] ( parameters ) -> return_type {
    function_body
}
  • capture_clause：捕获列表，定义了 Lambda 函数体外部变量的访问权限。可以捕获外部作用域中的变量，包括值捕获和引用捕获。
  • parameters：参数列表，与普通函数的参数列表相同。如果没有参数，可以省略或保留空括号 ()。
  • return_type：返回类型。在大多数情况下，Lambda 的返回类型可以被自动推导，可省略 -> return_type 部分。
  • function_body：函数体，包含了 Lambda 表达式的执行代码。

捕获模式

  • [ ]：不捕获任何外部变量。
  • [=]：以值的方式捕获外部作用域中的所有变量。
  • [&]：以引用的方式捕获外部作用域中的所有变量。
  • [var]：以值的方式捕获单个变量 var。
  • [&var]：以引用的方式捕获单个变量 var。
  • [=, &var]：以值的方式捕获所有外部变量，但 var 变量以引用方式捕获。
  • [&, var]：以引用的方式捕获所有外部变量，但 var 变量以值方式捕获。

获取字符串字串

在 C++ 中，可以使用 std::string 类的成员函数 substr 来获取字符串的子串。substr 函数返回一个字符串对象，该对象包含原字符串中指定位置开始的特定长度的字符。

substr 函数原型

substr 函数的原型如下：

cppCopy code
string substr(size_t pos = 0, size_t len = npos) const;
  • pos：一个 size_t 类型的值，表示子串开始的位置，默认值为 0。
  • len：一个 size_t 类型的值，表示子串的长度。默认值 npos 表示直到字符串的末尾。

链表&数组

可以安排的最多任务数

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。

参考：

https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/solutions/1101831/ni-ke-yi-an-pai-de-zui-duo-ren-wu-shu-mu-p7dm/?envType=study-plan-v2&envId=2024-spring-sprint-100

二分查找+贪心选择工人

判断能否完成k个任务：取最小的k个task，最大的k个工人，从大到小遍历task，如果最大的工人/最小的嗑药工人可以完成该task则删掉这个工人并继续遍历，否则不能完成

二分查找能够完成的最大k

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int m=tasks.size(), n=workers.size();
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int up=min(m, n), l=0, r=up;
        while(l<=r) {
            int mid=l+(r-l)/2;
            if(ifCanFinish(tasks, workers, pills, strength, mid)) {
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }

        return l-1;
    }
private:
    bool ifCanFinish(vector<int>& tasks, vector<int>& workers, int pills, int strength, int taskNum) {
        if(taskNum==0) return true;
        int m=tasks.size(), n=workers.size();
        multiset<int> ws;
        for(int i=n-1; i>=n-taskNum; --i) ws.insert(workers[i]);

        for(int i=taskNum-1; i>=0; --i) {
            int curTask=tasks[i];
            if(*prev(ws.end())>=curTask) ws.erase(prev(ws.end()));
            else {
                if(pills==0) return false;
                auto it=ws.lower_bound(curTask-strength);
                if(it==ws.end()) return false;
                --pills;
                ws.erase(it);
            }
        }
        return true;
    }
};

优化：使用双端队列维护嗑药能完成任务的工人来代替有序集合中的查找过程

计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

数据结构：树状数组，可使插入和范围查询的时间复杂度均为O(logN)

节点i的父节点：i+LowestBit(i)

节点i的左兄弟节点：i-LowestBit(i)

参考：

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/324892/ji-suan-you-ce-xiao-yu-dang-qian-yuan-su-de-ge-s-7/?envType=study-plan-v2&envId=2024-spring-sprint-100

https://blog.csdn.net/TheWayForDream/article/details/118436732

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size());
        vector<int> a;

        a.assign(nums.begin(), nums.end());
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());

        vector<int> c(a.size()+1, 0);
        for(int i=(int)nums.size()-1; i>=0; --i) {
            int id = lower_bound(a.begin(), a.end(), nums[i]) - a.begin() + 1;
            int curAns=0, curId=id-1;
            while(curId>0) {
                curAns += c[curId];
                curId -= lowestBit(curId);
            }
            ans[i] = curAns;

            curId = id;
            while(curId<c.size()) {
                c[curId] += 1;
                curId += lowestBit(curId);
            }
        }

        return ans;
    }
private:
    int lowestBit(int num) {
        return num & (-num);
    }
};

方法2：归并排序

去重方法：对索引排序

最小区间

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

贪心+最小堆，对于取出的k个数的最小值，其余k-1个数在对应的列表中为大于该最小值的第一个数（贪心）；

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k=nums.size();
        vector<int> ans(2, 0);
        if(k==0) return ans;

        vector<int> ptrs(k, 0);
        priority_queue<int, vector<int>, greater<int>> pq;
        int maxNum=INT_MIN;
        for(int i=0; i<k; ++i) {
            maxNum = max(maxNum, nums[i][ptrs[i]]);
            pq.push(nums[i][ptrs[i]]);
        }
        ans[0]=pq.top();
        ans[1]=maxNum;

        while(true) {
            int tmp=pq.top();
            while(!pq.empty() && pq.top()==tmp) pq.pop();
            
            bool endC=false;
            for(int i=0; i<k; ++i) {
                if(nums[i][ptrs[i]]==tmp) {
                    ptrs[i]++;
                    if(ptrs[i]>=nums[i].size()) {
                        endC=true;
                        break;
                    }
                    maxNum = max(maxNum, nums[i][ptrs[i]]);
                    pq.push(nums[i][ptrs[i]]);
                }
            }
            if(endC) break;

            int minNum=pq.top();
            if(maxNum-minNum<ans[1]-ans[0]) {
                ans={minNum, maxNum};
            }
        }

        return ans;
    }
};

改进：最小堆中存储数组索引，省去内循环：

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int rangeLeft = 0, rangeRight = INT_MAX;
        int size = nums.size();
        vector<int> next(size);
        
        auto cmp = [&](const int& u, const int& v) {
            return nums[u][next[u]] > nums[v][next[v]];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        int minValue = 0, maxValue = INT_MIN;
        for (int i = 0; i < size; ++i) {
            pq.emplace(i);
            maxValue = max(maxValue, nums[i][0]);
        }

        while (true) {
            int row = pq.top();
            pq.pop();
            minValue = nums[row][next[row]];
            if (maxValue - minValue < rangeRight - rangeLeft) {
                rangeLeft = minValue;
                rangeRight = maxValue;
            }
            if (next[row] == nums[row].size() - 1) {
                break;
            }
            ++next[row];
            maxValue = max(maxValue, nums[row][next[row]]);
            pq.emplace(row);
        }

        return {rangeLeft, rangeRight};
    }
};

存在重复元素II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

滑动窗口+哈希集合，非常巧妙

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> um;
        for(int i=0; i<nums.size(); ++i) {
            if(um.find(nums[i])!=um.end() && i-um[nums[i]]<=k) return true;
            um[nums[i]]=i;
        }

        return false;
    }
};

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

滑动窗口法

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1=headA, *p2=headB;
        while(p1!=p2) {
            p1 = p1? p1->next : headB;
            p2 = p2? p2->next : headA;
        }
        return p1;
    }
};

旋转字符串

class Solution {
public:
    string dynamicPassword(string password, int target) {
        return password.substr(target, password.size()) + password.substr(0, target);
    }
};

三次翻转

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

字符串转整数

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意：

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
class Solution {
public:
    int myAtoi(string str) {
        int len=str.size(), i=0;
        int symbol = 1;
        long long ans=0;
        while(str[i]==' ') ++i;
        if(str[i]=='-'){
            symbol = -1;
            ++i;
        }
        else if(str[i]=='+') ++i;
        while(isdigit(str[i])){
            ans = ans*10 + (str[i]-'0');
            if(symbol==1 && ans>INT_MAX) return INT_MAX;
            if(symbol==-1 && -ans<INT_MIN) return INT_MIN;
            ++i;
        }

        return symbol*ans;
    }
};

复杂链表的复制

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        Node *cur=head;
        while(cur) {
            Node *copyNode = new Node(cur->val);
            copyNode->next = cur->next;
            cur->next = copyNode;
            cur = copyNode->next;
        }

        Node *ans=head->next;
        cur = head;
        while(cur) {
            cur->next->random = cur->random? cur->random->next : nullptr;
            cur = cur->next->next;
        }

        cur = head;
        Node *copyNode;
        while(cur) {
            copyNode = cur->next;
            cur->next = copyNode->next;
            copyNode->next = copyNode->next? copyNode->next->next:nullptr;
            cur = cur->next;
        }

        return ans;
    }
};

统计目标成绩的出现次数

二分查找，上下边界

class Solution {
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int countTarget(vector<int>& scores, int target) {
        int leftIdx = binarySearch(scores, target, true);
        int rightIdx = binarySearch(scores, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < scores.size() && scores[leftIdx] == target && scores[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }
};

点名

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

二分查找

特殊情况：最后一名学生缺席

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0, j = records.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(records[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
};

库存余量最少的 cnt 个商品余量

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

快速排序+哨兵选择

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        if (cnt >= stock.size()) return stock;
        return quickSort(stock, cnt, 0, stock.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& stock, int cnt, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && stock[j] >= stock[l]) j--;
            while (i < j && stock[i] <= stock[l]) i++;
            swap(stock[i], stock[j]);
        }
        swap(stock[i], stock[l]);
        if (i > cnt) return quickSort(stock, cnt, l, i - 1);
        if (i < cnt) return quickSort(stock, cnt, i + 1, r);
        vector<int> res;
        res.assign(stock.begin(), stock.begin() + cnt);
        return res;
    }
};

数据流中的中位数

使用最小、最大堆

坑：容器.size()是无符号long

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        maxH.push(INT_MIN);
        minH.push(INT_MAX);
    }
    
    void addNum(int num) {
        if(num<=maxH.top()) {
            maxH.push(num);
        }
        else {
            minH.push(num);
        }
        if(maxH.size()>minH.size()+1) {
            minH.push(maxH.top());
            maxH.pop();
        }
        if(minH.size()>maxH.size()+1) {
            maxH.push(minH.top());
            minH.pop();
        }

        return;
    }
    
    double findMedian() {
        if(maxH.size()!=minH.size()) return maxH.size()>minH.size()? maxH.top() : minH.top();
        return (minH.top()+maxH.top())/2.0;

    }
private:
    priority_queue<int> maxH;
    priority_queue<int, vector<int>, greater<int>> minH;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

文物朝代判断

展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否连续（如遇未知朝代可算作连续情况）。

无重复，最大朝代-最小朝代<5

哈希集合

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        unordered_set<int> repeat;
        int ma = 0, mi = 14;
        for(int place : places) {
            if(place == 0) continue; // 跳过未知朝代
            ma = max(ma, place); // 最大编号朝代
            mi = min(mi, place); // 最小编号朝代
            if(repeat.find(place) != repeat.end()) return false; // 若有重复，提前返回 false
            repeat.insert(place); // 添加此朝代至 Set
        }
        return ma - mi < 5; // 最大编号朝代 - 最小编号朝代 < 5 则连续
    }
};

文件组合

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：

  • 每种组合按照文件编号 升序 排列；
  • 不同组合按照第一个文件编号 升序 排列。
class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        int left=1, right=2, tmp=3;
        vector<vector<int>> ans;
        while(left<right) {
            if(tmp<target) tmp+=(++right);
            else if(tmp>target) tmp-=(left++);
            else {
                vector<int> line;
                for(int i=left; i<=right; ++i) {
                    line.push_back(i);
                }
                ans.push_back(line);
                tmp+=(++right);
            }
        }

        return ans;
    }
};

查找和最小的K对数字

自定义优先级队列

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };

        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> ans;   
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < min(k, m); i++) {
            pq.emplace(i, 0);
        }
        while (k-- > 0 && !pq.empty()) {
            auto [x, y] = pq.top(); 
            pq.pop();
            ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
            if (y + 1 < n) {
                pq.emplace(x, y + 1);
            }
        }

        return ans;
    }
};

删除有序数组的重复项

你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

快慢指针法，快指针与上一个元素比较时可能被慢指针覆盖，因此需要用新的变量保存当前重复值

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int cur=0, select=0, count=0, curnum;
        while(cur<nums.size()) {
            if(count==0) {
                nums[select] = nums[cur];
                curnum = nums[cur];
                ++cur;
                ++select;
                ++count;
            }
            else if(count==1) {
                nums[select] = nums[cur];
                if(nums[cur] == curnum) {
                    count++;
                }
                else {
                    curnum = nums[cur];
                }
                ++cur;
                ++select;
            }
            else if(count==2) {
                while(cur<nums.size() && nums[cur]==curnum) ++cur;
                count = 0;
            }
        }
        return select;
    }
};

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

要求时间复杂度nlog(n)，空间复杂度1

方法：自底向上归并排序

个人代码：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return nullptr;
        int len = 0;
        ListNode* cur = head;
        while(cur) {
            cur = cur->next;
            ++len;
        }

        int subLen = 1;
        ListNode* dummyHead = new ListNode(-1, head);
        for(;subLen<=len-1; subLen<<=1) {
            ListNode *pre=dummyHead, *a, *b;
            while(pre->next) {
                a = pre->next;
                b = pre->next;
                for(int i=0; i<subLen; ++i) {
                    if(!b) break;
                    b = b->next;
                }
                ListNode *nextN = b;
                for(int i=0; i<subLen; ++i) {
                    if(!nextN) break;
                    nextN = nextN->next;
                }

                int cntA=0, cntB=0;
                for(int i=0; i<2*subLen; ++i) {
                    if(!a && !b || cntA==subLen && !b) break;
                    if(cntA==subLen || (cntB<subLen && b && b->val<a->val)) {
                        pre->next = b;
                        pre = pre->next;
                        b = b->next;
                        cntB++;
                    }
                    else {
                        pre->next = a;
                        pre = pre->next;
                        a = a->next;
                        cntA++;
                    }
                }
                pre->next = nextN;
            }
        }

        return dummyHead->next;
    }
};

分割链表，代码更易读：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 合并两个子链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummyHead(0);
    ListNode* ptr = &dummyHead;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            ptr->next = l1;
            l1 = l1->next;
        } else {
            ptr->next = l2;
            l2 = l2->next;
        }
        ptr = ptr->next;
    }
    ptr->next = l1 ? l1 : l2;
    return dummyHead.next;
}

// 自底向上归并排序
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    // 计算链表长度
    ListNode* cur = head;
    int length = 0;
    while (cur) {
        length++;
        cur = cur->next;
    }

    ListNode dummyHead(0);
    dummyHead.next = head;
    ListNode *left, *right, *tail;
    for (int size = 1; size < length; size <<= 1) {
        cur = dummyHead.next; // 每次大循环后重新开始
        tail = &dummyHead;
        while (cur) {
            left = cur;
            right = split(left, size); // 分割得到右半部分的开始
            cur = split(right, size); // 更新cur为下一对要合并链表的开始
            tail = merge(left, right, tail); // 合并链表，并更新tail
        }
    }
    return dummyHead.next;
}

// 分割链表函数，返回第二部分链表的头节点
ListNode* split(ListNode* head, int n) {
    while (--n && head) {
        head = head->next;
    }
    ListNode* rest = head ? head->next : nullptr;
    if (head) head->next = nullptr;
    return rest;
}

// 更新的合并函数，返回合并后链表的尾部
ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head) {
    ListNode* cur = head;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    while (cur->next) cur = cur->next; // 移动到合并后链表的尾部
    return cur;
}

// 主函数用于演示
int main() {
    // 示例：创建并排序链表
    // 注意：具体的创建链表过程在此略过，假设有一个链表head
    ListNode* sorted = sortList(head);
    // 打印排序后的链表...
    return 0;
}

移掉K位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

维护一个单调非增栈，栈中元素为保留的数字

class Solution {
public:
    string removeKdigits(string num, int k) {
        deque<char> dq;
        dq.push_back(num[0]);
        int delCnt=0, curIndex=1;
        while(curIndex<num.size()) {
            while(!dq.empty() && num[curIndex]<dq.back() && delCnt<k) {
                delCnt++;
                dq.pop_back();
            }
            dq.push_back(num[curIndex]);
            curIndex++;
        }
        while(delCnt<k) {
            delCnt++;
            dq.pop_back();
        }

        string ans;
        while(!dq.empty() && dq.front()=='0') dq.pop_front();
        while(!dq.empty()) {
            ans += dq.front();
            dq.pop_front();
        }

        return ans.size()==0? "0":ans;
    }
};

二叉树

二叉树的最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

二叉树数组索引+层序遍历

细节：无符号整型保存索引值，避免了溢出问题

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res = 1;
        vector<pair<TreeNode *, unsigned long long>> arr;
        arr.emplace_back(root, 1L);
        while (!arr.empty()) {
            vector<pair<TreeNode *, unsigned long long>> tmp;
            for (auto &[node, index] : arr) {
                if (node->left) {
                    tmp.emplace_back(node->left, index * 2);
                }
                if (node->right) {
                    tmp.emplace_back(node->right, index * 2 + 1);
                }
            }
            res = max(res, arr.back().second - arr[0].second + 1);
            arr = move(tmp);
        }
        return res;
    }
};

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

递归

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return recur(root, LONG_MIN, LONG_MAX);
    }
private:
    bool recur(TreeNode *node, long leftRoot, long rightRoot) {
        if(node==nullptr) return true;
        if(node->val>=rightRoot || node->val<=leftRoot) return false;
        return recur(node->left, leftRoot, node->val) && recur(node->right, node->val, rightRoot);
    }
};

中序遍历，即二叉搜索树的中序遍历一定是升序排列

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};

层序遍历，每层为一行

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root != NULL) que.push(root);
        while(!que.empty()) {
            vector<int> tmp;
            for(int i = que.size(); i > 0; --i) {
                root = que.front();
                que.pop();
                tmp.push_back(root->val);
                if(root->left != NULL) que.push(root->left);
                if(root->right != NULL) que.push(root->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

翻转二叉树

递归算法

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode *tmp=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(tmp);

        return root;
    }
};

辅助栈

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        stack<TreeNode*> stack;
        stack.push(root);
        while (!stack.empty())
        {
            TreeNode* node = stack.top();
            stack.pop();
            if (node->left != nullptr) stack.push(node->left);
            if (node->right != nullptr) stack.push(node->right);
            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;
        }
        return root;
    }
};

二叉树最近公共祖先

dfs+回溯

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left && right) return root;
        if(left==nullptr) return right;
        if(right==nullptr) return left;
        return nullptr;
    }
};

推理二叉树

通过前序遍历和中序遍历构建二叉树

个人方法：

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        int p=0, i1=0, i2=inorder.size();
        return recur(preorder, inorder, p, i1, i2);
    }
private:
    TreeNode* recur(vector<int>& preorder, vector<int>& inorder, int &p, int i1, int i2) {
        if(i1>=i2 || p>=preorder.size()) return nullptr;
        TreeNode* cur = new TreeNode(preorder[p]);
        int mid=0;
        for(int j=i1; j<i2; ++j) {
            if(preorder[p]==inorder[j]) {
                mid=j;
                break;
            }
        }
        ++p;
        cur->left=recur(preorder, inorder, p, i1, mid);
        cur->right=recur(preorder, inorder, p, mid+1, i2);
        return cur;
    }
};

k神，使用哈希表快速定位索引：

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            hmap[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> hmap;
    TreeNode* recur(int root, int left, int right) { 
        if(left > right) return nullptr;                        // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);          // 建立根节点
        int i = hmap[preorder[root]];                           // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                            // 回溯返回根节点
    }
};

验证二叉搜索树的后序遍历序列

k神，辅助单调栈，从后往前遍历

节点的右子树元素必须小于该节点的父节点

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        int root=INT_MAX;
        stack<int> s;

        for(int j=postorder.size()-1; j>=0; --j) {
            if(postorder[j]>=root) return false;
            while(!s.empty() && postorder[j]<s.top()) {
                root = s.top();
                s.pop();
            }
            s.push(postorder[j]);
        }

        return true;
    }
};

DFS&BFS

字母迷宫

比较粗暴的dfs算法

注意容器类型传递要使用引用，双层循环因子初始化问题

二维数组初始化，利用构造函数

class Solution {
public:
    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        vector<vector<bool>> path(grid.size(), vector<bool>(grid[0].size(), false));

        for(int i=0;i<grid.size();++i) {
            for(int j=0;j<grid[0].size();++j) {
                if(ifMatched(grid, target, path, i, j, 0)) return true;
            }
        }

        return false;
    }
private:
    bool ifMatched(vector<vector<char>>& grid, string &target, vector<vector<bool>> &path, int i, int j, int p){
        if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || path[i][j]) return false;

        if(grid[i][j]==target[p] && p==target.size()-1) return true;
        if(grid[i][j]==target[p]){
            path[i][j] = true;
            if(ifMatched(grid, target, path, i+1, j, p+1) || ifMatched(grid, target, path, i-1, j, p+1) || ifMatched(grid, target, path, i, j+1, p+1)
             || ifMatched(grid, target, path, i, j-1, p+1)) return true;
            path[i][j] = false;
            return false;
        }

        return false;

    }
};

衣橱整理

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

bfs

class Solution {
    // 计算 x 的数位之和
    int get(int x) {
        int res=0;
        for (; x; x /= 10) {
            res += x % 10;
        }
        return res;
    }
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        if (!cnt) return 1;
        queue<pair<int,int> > Q;
        // 向右和向下的方向数组
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        vector<vector<int> > vis(m, vector<int>(n, 0));
        Q.push(make_pair(0, 0));
        vis[0][0] = 1;
        int ans = 1;
        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > cnt) continue;
                Q.push(make_pair(tx, ty));
                vis[tx][ty] = 1;
                ans++;
            }
        }
        return ans;
    }
};

动态规划

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

dp

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails; // 存储各个长度递增子序列的末尾元素

    for (int num : nums) {
        // 使用 binary search 找到 num 在 tails 中的位置
        auto it = std::lower_bound(tails.begin(), tails.end(), num);

        // 如果 num 大于 tails 中的所有元素，添加到 tails 末尾
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            // 否则更新 tails 中的元素
            *it = num;
        }
    }

    return tails.size(); // tails 的大小即为最长递增子序列的长度
}

二分优化

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails; // 存储各个长度递增子序列的末尾元素

    for (int num : nums) {
        // 使用 binary search 找到 num 在 tails 中的位置
        auto it = std::lower_bound(tails.begin(), tails.end(), num);

        // 如果 num 大于 tails 中的所有元素，添加到 tails 末尾
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            // 否则更新 tails 中的元素
            *it = num;
        }
    }

    return tails.size(); // tails 的大小即为最长递增子序列的长度
}

精妙之处就在于： 遍历nums拿出来的比我当前tail尾部更小的数，我遇见了就把它换进来，要是后续不能让这些稍小（相较于tail数组的尾部）的变成更长的子序列，那就超不过原先的，我也没有任何损失，但如果长度能超过之前的这些，我前面已经替换完了，随时准备着和你后面的组成更长的，只需要你来加到尾部就ok了

给定一个数组和value，需要求其中连续的子数组的和等于value，返回符合条件的子数组的数量

dp题，没看出来。。。

使用前缀和

int subarraySumEqualsK(std::vector<int>& nums, int k) {
    int count = 0;
    int sum = 0; // 当前的前缀和
    std::unordered_map<int, int> prefixSums; // 前缀和 -> 该前缀和出现的次数
    prefixSums[0] = 1; // 初始化，和为0的前缀和出现1次（即没有元素的情况）

    for (int num : nums) {
        sum += num; // 更新当前的前缀和
        // 查找当前前缀和减去k的值是否存在于前缀和中
        if (prefixSums.find(sum - k) != prefixSums.end()) {
            count += prefixSums[sum - k]; // 如果存在，增加对应的子数组计数
        }
        // 更新当前前缀和的计数
        prefixSums[sum]++;
    }

    return count;
}

丑数

注意重复情况

时间复杂度较高的算法：优先级队列

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n==0) return -1;
        vector<int> dp;
        dp.push_back(1);
        int p2=0, p3=0, p5=0;
        for(int i=1; i<n; ++i) {
            int v2=dp[p2]*2, v3=dp[p3]*3, v5=dp[p5]*5;
            int cur = min(v2, min(v3, v5));
            dp.push_back(cur);
            if(cur==v2) ++p2;
            if(cur==v3) ++p3;
            if(cur==v5) ++p5;
        }
        return dp[n-1];
    }
};

统计结果概率

经典动态规划

class Solution {
public:
    vector<double> statisticsProbability(int num) {
        vector<double> dp(6, 1/6.0);
        for(int i=2; i<=num; ++i) {
            vector<double> tmp(5*num+1, 0);
            for(int j=0; j<5*num+1; ++j) {
                for(int k=min(j, int(dp.size())-1); k>=max(0, j-5); --k) {
                    tmp[j]+=dp[k]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }
};

按规则统计计算结果

为了深入了解这些生物群体的生态特征，你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据，其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB，该数组为基于数组 arrayA 中的数据计算得出的结果，其中 arrayB[i] 表示将第 i 个生物群体的数量从总体中排除后的其他数量的乘积。

本质还是dp

前缀积+后缀积

class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        vector<int> ans(arrayA.size(), 1);
        int tmp=1;
        for(int i=1; i<arrayA.size(); ++i) {
            tmp*=arrayA[i-1];
            ans[i] = tmp;
        }

        tmp=1;
        for(int i=arrayA.size()-2; i>=0; --i) {
            tmp*=arrayA[i+1];
            ans[i] *= tmp;
        }

        return ans;
    }
};

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

动态规划+哈希集合

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dic;
        for(auto ele : wordDict) {
            dic.insert(ele);
        }

        vector<bool> dp(s.size(), false);
        for(int i=0; i<s.size(); ++i) {
            for(int j=0; j<i; ++j) {
                if(dp[j] && dic.find(s.substr(j+1, i-j))!=dic.end()) {
                    dp[i]=true;
                    break;
                }
            }
            if(dic.find(s.substr(0, i+1))!=dic.end()) {
                dp[i]=true;
            }
        }

        return dp[s.size()-1];
        
    }
};

分治

交易逆序对总数

统计一个数组逆序对的总数

归并排序法，分治思想

class Solution {
public:
    int reversePairs(vector<int>& record) {
        ans = 0;
        assist.resize(record.size());
        recur(record, 0, record.size()-1);
        return ans;
    }
private:
    int ans;
    vector<int> assist;
    void recur(vector<int>& record, int left, int right) {
        if(right<=left) return;

        int mid = left + (right-left)/2;
        recur(record, left, mid);
        recur(record, mid+1, right);

        int i=left, j=mid+1;
        for(int k=left; k<=right; ++k) {
            if(i>mid) {
                assist[k] = record[j++];
            }
            else if(j>right || record[i]<=record[j]) {
                assist[k] = record[i++];
            }
            else {
                assist[k] = record[j++];
                ans += mid-i+1;
            }
        }
        copy(assist.begin()+left, assist.begin()+right+1, record.begin()+left);

        return;
    }
};

拼接最大数

给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。

请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。

返回代表答案的长度为 k 的数组。

示例 1：

输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
输出：[9,8,6,5,3]

示例 2：

输入：nums1 = [6,7], nums2 = [6,0,4], k = 5
输出：[6,7,6,0,4]

示例 3：

输入：nums1 = [3,9], nums2 = [8,9], k = 3
输出：[9,8,9]

高难题，单调栈+分治，合并操作实现

cpp是真不好写

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ans;
        int min_k = k - min(k, (int)nums2.size()), max_k = min(k, (int)nums1.size());
        for(int i=min_k; i<=max_k; ++i) {
            vector<int> a1 = maxOfOne(nums1, i);
            vector<int> a2 = maxOfOne(nums2, k-i);
            vector<int> merged = merge(a1, a2);
            ans = greatorV(ans, merged);
        }

        return ans;
    }
private:
    vector<int> maxOfOne(vector<int>& nums, int k) {
        if(k==0) return {};
        vector<int> ans(k);
        stack<int> s;
        int cnt=0, pop_num=nums.size()-k;
        for(auto ele : nums) {
            while(cnt<pop_num && !s.empty() && ele>s.top()) {
                s.pop();
                cnt++;
            }
            s.push(ele);
        }
        while(cnt<pop_num) {
            s.pop();
            cnt++;
        }

        for(int i=k-1; i>=0; --i) {
            ans[i] = s.top();
            s.pop();
        }
        cout<<"k="<<k<<endl;
        copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, " "));
        cout<<endl;
        return ans;
    }

    vector<int> merge(vector<int>& a1, vector<int>& a2) {
        int len1=a1.size(), len2=a2.size();
        vector<int> ans;

        int p1=0, p2=0;
        while(p1<len1 || p2<len2) {
            if(p1==len1) {
                ans.push_back(a2[p2]);
                ++p2;
            }
            else if(p2==len2) {
                ans.push_back(a1[p1]);
                ++p1;
            }
            else if(a1[p1]>a2[p2]) {
                ans.push_back(a1[p1]);
                ++p1;
            }
            else if(a1[p1]<a2[p2]){
                ans.push_back(a2[p2]);
                ++p2;
            }
            else {
                bool flag = whichBigger(a1, a2, p1, p2);
                if(flag) {
                    ans.push_back(a1[p1]);
                    ++p1;
                }
                else {
                    ans.push_back(a2[p2]);
                    ++p2;
                }
            }
        } 
        return ans;
    }

    bool whichBigger(vector<int>& a1, vector<int>& a2, int p1, int p2) {
        int cur = a1[p1];
        while(p1<a1.size() && p2<a2.size()) {
            if(a1[p1]>a2[p2]) return true;
            if(a1[p1]<a2[p2]) return false;
            ++p1;
            ++p2;
        }

        if(p1==a1.size()) return false;
        else return true;
    }

    vector<int> greatorV(vector<int>& a1, vector<int>& a2) {
        if(a1.size()==0) return a2;
        int len = a1.size();
        for(int i=0; i<len; ++i) {
            if(a1[i]>a2[i]) return a1;
            if(a1[i]<a2[i]) return a2;
        }

        return a1;
    }



};

位运算&数学

位运算求和

暴力法（个人）

class Solution {
public:
    int encryptionCalculate(int dataA, int dataB) {
        int ans = 0, curFlag = 1, carryFlag = 0;
        while(curFlag!=0) {
            ans |= ((dataA^dataB^carryFlag)&curFlag);
            if((dataA&curFlag)&&(dataB&curFlag) || (dataA&curFlag)&&(carryFlag&curFlag) || (dataB&curFlag)&&(carryFlag&curFlag)) {
                carryFlag = (curFlag<<1)&(-1);
            }
            else carryFlag = 0;
            curFlag<<=1;
        }
        return ans;
    }
};

k神，和=非进位和+进位

循环知道进位=0

class Solution {
public:
    int encryptionCalculate(int dataA, int dataB) {
        while(dataB != 0)
        {
            int c = (unsigned int)(dataA & dataB) << 1;
            dataA ^= dataB;
            dataB = c;
        }
        return dataA;
    }
};

撞色搭配

求元素成对出现的数组中唯二不成对的元素

异或运算性质：x^x=0；

不成对元素x, y必有一位不同

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        if(sockets.empty()) exit(1);
        int val1 = 0;
        for(int i=0; i<sockets.size(); ++i) {
            val1 ^= sockets[i];
        }

        int m = 1, flag = val1&m;
        while(flag==0) {
            m<<=1;
            flag = val1&m;
        }

        int valx=0, valy=0;
        for(int i=0; i<sockets.size(); ++i) {
            if(flag&sockets[i]) {
                valx ^= sockets[i];
            }
            else {
                valy ^= sockets[i];
            }
        }

        vector<int> ans = {valx, valy};
        return ans;
    }
};

撞色搭配2

求元素成三出现的数组中唯一出现的元素

位运算+有限状态机

成三出现的元素同一位和模3为0

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int ones = 0, twos = 0;
        for(int action : actions){
            ones = ones ^ action & ~twos;
            twos = twos ^ action & ~ones;
        }
        return ones;
    }
};

砍竹子2

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

数学+快速幂

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        long mod = 1000000007;
        if(bamboo_len<=3) return bamboo_len-1;
        int a = bamboo_len/3, b = bamboo_len%3, pow;
        long ans;
        if(b==2) {
            pow = a;
            ans = 2;
        }
        else if(b==1) {
            pow = a-1;
            ans = 4;
        }
        else {
            pow = a;
            ans = 1;
        }

        long x=3;
        while(pow>0) {
            if(pow%2==1) ans = (ans*x)%mod;
            x = (x*x)%mod;
            pow/=2;
        }
        
        return ans;
    }
};

破冰游戏

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

约瑟夫环问题，数学+dp

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        int ans = 0;
        for(int i=1; i<=num; ++i) {
            ans = (ans+target)%i;
        }

        return ans;
    }
};