力扣算法每日一练

记录一下每日一个 LeetCode 算法题

注：题解大多参考官方或评论区给的答案，我只是补了补注释

# 题目

# (1170) 比较字符串最小字母出现频次

# (1171) 从链表中删去总和值为零的连续节点

# (1483) 树节点的第 K 个祖先

# (2475) 数组中不等三元组的数目

# (1375) 二进制字符串前缀一致的次数

# (1494) 并行课程

# (2481) 分割圆的最少切割次数

# (1254) 统计封闭岛屿的数目

# (18) 四数之和

# (1851) 包含每个查询的最小区间

# (143) 重排链表

# (722) 删除注释

# (23) 合并 K 个升序链表

# (2048) 下一个更大的数值平衡数

# 题解

# (1170) 比较字符串最小字母出现频次

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {

        vector<int> count(11);
        for (string& w : words){
            //统计words中每个string的最小字母出现的次数的情况，最多有10种情况，所以count的长度为11(因为使用下标从1开始)
            int req = f(w);
            //每出现一次对应的情况，将其出现次数加1
            count[req]++;
            //当f(queries[i])等于2时，那么对于words大于2的情况，都是大于f(queries[i])的
            //只需要将f(words[i]) > 2的情况全部相加，即count[3] + count[4] + .... + count[10](因为words[i].length < 10)
            //就是f(queries[i]) < f(words[i])的数量
        }
        
        int sum_len = count.size();
        vector<int> sum(11);
        for(int i = 1;i < sum_len; i++){
            //将f(words[i])的count提前计算好
            //当f(queries[i])为4时，需要计算count[5]加到count[10]
            //只需要用sum[10] - sum[5]即可
            sum[i] = sum[i - 1] + count[i];
        }

        int len = queries.size();
        vector<int> answer(len);
        for (int i = 0;i < len;i++){
            //先计算f(queries[i])
            int req = f(queries[i]);
            //将sum相减计算的最后结果存储到answer中
            answer[i] = sum[10] - sum[req];
        }

        return answer;
    }

    int f(string& str){
        //统计数
        int count = 0;
        //当前最小字母
        char cur_c = EOF;

        for (char& c : str){
            //如果c的值更小，则重新开始计算
            if (cur_c == EOF || cur_c > c){
                count = 1;
                cur_c = c;
            }
            //如果当前的最小字母和遍历到的c相同，则统计数增加
            else if (cur_c == c){
                count++;
            }
        }

        return count;
    }
};

# (1171) 从链表中删去总和值为零的连续节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        // 第一个为前缀和  第二个为链表结点
        map<int,ListNode*> map;
        int sum = 0;

        // 可以避免一些特殊情况 比如:[1,-1]
        ListNode * root = new ListNode(0, head);  
        ListNode * node;

        // 先找出具有相同前缀和的结点 把最后前缀和相同的结点保存到map中
        for(node = root;node != NULL;node = node->next)
        {
            sum += node->val;
            map[sum] = node;
        }
        
        // 对于当前节点的前缀和如果在map中被查找到有相同的（前缀和相同节点之间的节点和为0）就删除之间的所有节点
        for(node = root,sum = 0;node != NULL;node = node->next)
        {
            sum += node->val;
            if(map.find(sum) != map.end())
                node->next = map[sum]->next;
        }
        return root->next;
    }
};

# (1483) 树节点的第 K 个祖先

class TreeAncestor {
public:
    //因为至多查询5 * 10^4次，所以定义最大2^k 的k为16(2^16 = 65536 > 50000)
    constexpr static int Log = 16;
    //记录倍增的数组
    vector<vector<int>> ancestors;

    TreeAncestor(int n, vector<int>& parent) {
        //创建一个二维vector容器，并初始化值为-1，赋值给ancestors
        ancestors = vector<vector<int>>(n, vector<int>(Log, -1));
        //先将ancestors[i][0]是parent[i]的父节点;
        for (int i = 0; i < n; i++) {
            ancestors[i][0] = parent[i];
        }

        //计算倍增，并将其存储到ancestors
        for (int j = 1; j < Log; j++) {
            for (int i = 0; i < n; i++) {
                if (ancestors[i][j - 1] != -1) {
                    //对于ancestors[i]向上跳跃[j]步，相当于ancestors[i]向上跳跃[j-1]步(即跳跃到ancestors[i][j - 1])
                    //然后将ancestors[i][j - 1]再向上跳[j - 1]次(即ancestors[ancestors[i][j - 1]][j - 1])
                    ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
                }
            }
        }            
    }

    int getKthAncestor(int node, int k) {
        for (int j = 0; j < Log; j++) {
            //将k右移j位，例如：对于9，其二进制为1001右移1位，变为100，也就是4，再右移1位，变成10，也就是2
            if ((k >> j) & 1) {
                //&:与操作，例如：对于9，其二进制为1001，对于1，其二进制为0001
                //          1001
                //          0001
                //取&结果为:0001    1&1 = 1, (1 & 0) = (0 & 0) = 0;

                //令node = 其跳跃到的父节点
                node = ancestors[node][j];
                if (node == -1) {//如果node=-1，说明倍增时没有赋值到，也就是其父节点为空
                    return -1;
                }
            }
        }
        //返回结果
        return node;
    }
};


/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

# (2475) 数组中不等三元组的数目

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        //使用不排序map处理nums数组，
        unordered_map<int, int> temp;
        int length = nums.size();
        for (int i = 0;i < length;i++){
            //将nums[i]作为key，记录其出现次数
            temp[nums[i]]++;
        }
        
        //对于该题，数组元素的相对顺序并不影响结果，例如4,4,2,4,3
        //其答案为(0,2,3),(1,2,4),(2,3,4)共3种结果
        //将其排序为2,3,4,4,4
        //其答案为(0,1,2),(0,1,3),(0,1,4)同样3种结果
        //而且对于其中相同的元素4来说，假设先前元素的个数为t，当前元素个数为v
        //则有t * v * (n - t - v)个三元组符合要求
        //例如对于1,1,3,3,3,5,5,5
        //如果是3，显然0和1是两(t)种i组成,2,3,4是三(v)种j组成,5,6,7是三(n - t - v)种k组成
        //所以对于3有2*3*3种情况符合题目要求

        //answer记录答案，pre记录计算过的key值的出现次数
        int answer = 0, pre = 0;
        for(unordered_map<int, int>::iterator it = temp.begin();it != temp.end();it++){
            //用record记录删去已经计算过的key值的出现次数，和当前循环key值出现次数，剩余的数字的个数
            int record = length - pre - it->second;
            //元组数累计
            answer += pre * it->second * record;
            //将当前循环的key值出现次数累计到pre中
            pre += it->second;
        }
        
        return answer;
    }
};

# (1375) 二进制字符串前缀一致的次数

class Solution {
public:
    int numTimesAllBlue(vector<int>& flips) {
        //maxe为字符串最靠右的1
        int length = flips.size(), count = 0, maxe = 0;
        for (int i = 0; i < length; i++) {
            //要让[1, i+1]的范围都为1，说明此时最靠右的1的位置正好等于变1操作的步数
            //若最靠右的1的位置大于已经操作的步数，说明在最靠右的1的位置之前，还存在着没有改成变成1的0

            //取已操作过的flips中的最大值，记作已被操作过的最靠右的1的位置
            maxe = max(maxe, flips[i]);
            //比较，如果恰好相等，说明符合题目要求
            if (i + 1 == maxe)
                count++;
        }
        return count;
    }
};

# (1494) 并行课程

//答案看不懂，直接复制过来了
class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
        vector<int> dp(1 << n, INT_MAX);
        vector<int> need(1 << n, 0);
        for (auto& edge : relations) {
            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1);
        }
        dp[0] = 0;
        for (int i = 1; i < (1 << n); ++i) {
            need[i] = need[i & (i - 1)] | need[i & (-i)];
            if ((need[i] | i) != i) { // i 中有任意一门课程的前置课程没有完成学习
                continue;
            }
            int valid = i ^ need[i]; // 当前学期可以进行学习的课程集合
            if (__builtin_popcount(valid) <= k) { // 如果个数小于 k，则可以全部学习，不再枚举子集
                dp[i] = min(dp[i], dp[i ^ valid] + 1);
            } else { // 否则枚举当前学期需要进行学习的课程集合
                for (int sub = valid; sub; sub = (sub - 1) & valid) {
                    if (__builtin_popcount(sub) <= k) {
                        dp[i] = min(dp[i], dp[i ^ sub] + 1);
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

# (2481) 分割圆的最少切割次数

//纯简单题，没啥好说的，记得考虑n == 1的特殊情况就行
class Solution {
public:
    int numberOfCuts(int n) {
        if(n == 1)
            return 0;
        if(n % 2 == 0){
            return n / 2;
        }
        return n;
    }
};

# (1254) 统计封闭岛屿的数目

//没看懂0.o
class Solution {
public:
    static constexpr int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
                
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    queue<pair<int,int>> qu;
                    grid[i][j] = 1;
                    bool closed = true;

                    qu.push(make_pair(i, j));
                    while (!qu.empty()) {
                        auto [cx, cy] = qu.front();
                        qu.pop();
                        if (cx == 0 || cy == 0 || cx == m - 1 || cy == n - 1) {
                            closed = false;
                        }
                        for (int i = 0; i < 4; i++) {
                            int nx = cx + dir[i][0];
                            int ny = cy + dir[i][1];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                                grid[nx][ny] = 1;
                                qu.emplace(nx, ny);
                            }
                        }
                    }
                    if (closed) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

# (18) 四数之和

//在解决四数之和问题前，我们先来解决其前置题目，三数之和。
//三数之和,给你一个nums数组，判断其中是否有三个数的和为0，将所有三个数和为0的数组返回，答案中不能包含重复的三元组。

/*该题目要求答案三元组不能重复，因此不能单纯的使用三重循环暴力求解。因为如果数组nums[] = {0, 0, 0, 0, 0, ...}时，那么就会得到O(N ^ 3)个三元组，然后需要再对其去重，这样的开销显然非常大。
		重新思考重复三元组，可以发现，假设有a,b,c三个数符合要求，那么就会有三元组{a, b, c}, {b, a, c}, {c, a, b}...等三元组符合要求，其实也就是a,b,c三个数的排列组合，应该会有6种(A33 = 3!)，如果对其进行限制，从第一个数到第三个数的大小应当是逐渐变大的，那么就能够剔除到5种排列组合，仅保留一种。例如对于-2 + -1 + 3 = 0，要求三元组从小到大，那么只有{-2，-1，3}是符合要求的。所以在获取答案之前，可以将nums数组进行排序，以便于操作。
		但这样会导致{0, 0, 0}三元组等于0的情况被排除，也就是重复数三元组会被意外排除。
		为了避免意外排除需要的答案，所以仅限制为a <= b <= c，但这样仍然无法解决nums[] = {0, 0, 0, 0}，即重复数的问题，这个问题可以通过if判断重复数，然后跳过循环来解决。
		到这里便完成了这个问题的解答，下面给出代码：
		*/
class Solution {
public:
	std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
		
		//对nums数组进行排序
		sort(nums.begin(), nums.end());
		int len = nums.size();
		//用于存储答案
		std::vector<std::vector<int>> ans;
		for (int a = 0; a < len - 2; a++) {
			//如果nums[a]和上一个数相同，即重复数，那么跳过重复数
			if (a == 0 || nums[a] != nums[a - 1]) {
				for (int b = a + 1; b < len - 1; b++) {
					//如果nums[b]和上一个数相同，即重复数，那么跳过重复数
					if (b == a + 1 || nums[b] != nums[b - 1]) {
						for (int c = b + 1; c < len; c++) {
							//如果nums[c]和上一个数相同，即重复数，那么跳过重复数
							if (c == b + 1 || nums[c] != nums[c - 1]) {
								//检查是否有nums[a]+nums[b]+nums[c] == 0
								if (nums[a] + nums[b] + nums[c] == 0) {
									//如果有，将其加入到答案中
									ans.push_back({ nums[a], nums[b], nums[c] });
								}
							}
						}
					}
				}
			}
		}
		return ans;
	}
};

/*但是该解法使用的三重循环就是一个非常复杂的算法，其时间开销十分巨大(O(n^3)，这个算法力扣直接给报超时)
所以继续对该算法进行优化。

可以发现对于a+b+c==0，如果固定了a和b，那么c也就是确定了，当三重循环找到了c后，应该就可以直接结束了，因为c是唯一确定的。
然后改变b，将b向后移动为b'，可以确定b'一定大于b，那么对于a+b'+c'=0，可以确定唯一的c'，并且可以断言，c'一定是小于c的(因为b增大了，那么c就要减小)。
因此便可以想到：
1.假设同时取左指针left指向b，右指针right指向c，将b固定，如果a+b+c > 0，只要将right左移，减小c的值即可
2.当找到唯一确定的c之后，那么b的left指针就可以右移，即把b变为b'了，然后重复上一操作寻找c'即可
3.当right与left重合时，判断就结束了
这个过程有些类似于快速排序。
下面是代码实现：
*/
class Solution {
public:
	std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
		//排序nums数组
		sort(nums.begin(), nums.end());
		int len = nums.size();
		//用于存储答案
		std::vector<std::vector<int>> ans;
		for (int a = 0; a < len - 2; a++) {
			//对于a去除重复数
			if (a > 0 && nums[a] == nums[a - 1])
				continue;
			//定义右标
			int right = len - 1;
			//此for循环用于枚举b
			for (int left = a + 1; left < len - 1; left++) {
				//对于b去除重复数
				if (left > a + 1 && nums[left] == nums[left - 1])
					continue;
				//保证left在right的左侧，然后寻找符合要求的c
				while (left < right && nums[a] + nums[left] + nums[right] > 0)
					right--;
				//当左指针与右指针相等时，左指针继续右移，此时b>c，不符合要求的a<=b<=c，所以直接退出循环即可
				if (left == right)
					break;
				if (nums[a] + nums[left] + nums[right] == 0)
					//如果找到匹配的三元组，那么就将其存入答案
					ans.push_back({ nums[a], nums[left], nums[right] });
			}
		}
		return ans;
	}
};
//这样改进后时间复杂度就变为了O(n^2)

//理解了三数之和的  排序+双指针  解决方法后，再回来看四数之和的解决方案
//其方法与三数和类似，首先考虑四重循环，然后将c和d的循环用双指针变为单重循环，这样便可以实现一个时间复杂度为O(n^3)的算法
class Solution {
public:
	std::vector<std::vector<int>> threeSum(std::vector<int>& nums, int target) {
		//排序nums数组
		sort(nums.begin(), nums.end());
		int len = nums.size();
		//用于存储答案
		std::vector<std::vector<int>> ans;
		for (int a = 0; a < len - 3; a++) {
			//对于a去除重复数
			if (a > 0 && nums[a] == nums[a - 1])
				continue;
			for (int b = a + 1; b < len - 2; b++) {
				//对于b去除重复数
				if (b > a + 1 && nums[b] == nums[b - 1])
					continue;

				//定义右标
				int right = len - 1;
				//此for循环用于枚举c
				for (int left = b + 1; left < len - 1; left++) {
					//对于c去除重复数
					if (left > b + 1 && nums[left] == nums[left - 1])
						continue;
					//保证left在right的左侧，然后寻找符合要求的d
					//下面强转为long，因为力扣的测试中有输入{1000000000,1000000000,1000000000,1000000000}的例子，相加时会超出int范围。
					while (left < right && (long) nums[a] + nums[b] + nums[left] + nums[right] > target)
						right--;
					//当左指针与右指针相等时，左指针继续右移，此时b>c，不符合要求的a<=b<=c，所以直接退出循环即可
					if (left == right)
						break;
					if ((long) nums[a] + nums[b] + nums[left] + nums[right] == target)
						//如果找到匹配的三元组，那么就将其存入答案
						ans.push_back({ nums[a], nums[b], nums[left], nums[right] });
				}
			}
		}
		return ans;
	}
};
//在所有C++提交中击败了20.18%的用户，我人都懵了，果然还是菜，大佬太多了

# (1851) 包含每个查询的最小区间

class Solution {
public:
	std::vector<int> minInterval(std::vector<std::vector<int>>& intervals, std::vector<int>& queries) {
		//创建辅助数组qindex用来存储排序后的queries数组
		std::vector<int> qindex(queries.size());
		//初始化qindex，将其内部全部赋0
		iota(qindex.begin(), qindex.end(), 0);

		//使用lambda表达式(匿名函数)，将升序排序后的queries数组赋给qindex
		sort(qindex.begin(), qindex.end(), [&](int i, int j)->bool {
			return queries[i] < queries[j];
			});

		//使用lambda表达式(匿名函数)，按照interval的左值升序排序intervals数组
		sort(intervals.begin(), intervals.end(), [](const std::vector<int>& it1, const std::vector<int>& it2)->bool {
			return it1[0] < it2[0];
			});

		//创建优先队列pq
		std::priority_queue<std::vector<int>> pq;
		//创建答案数组ans
		std::vector<int> ans(queries.size(), -1);
		int i = 0;
		//遍历qindex
		for (auto qi : qindex) {
			//1.当i等于intervals的长度或者lefti > queries[j]，停止循环
			while (i < intervals.size() && intervals[i][0] <= queries[qi]) {
				//l为intervals区间长度
				int l = intervals[i][1] - intervals[i][0] + 1;
				//将intervals的区间存入优先队列，其优先级按照区间长度进行降序排序，所以对l取反存入
				pq.push({ -l, intervals[i][0], intervals[i][1] });
				i++;
			}
			//优先队列不为空时，并且优先队列中优先级最高的intervals区间右值小于queries，那么将其排除
			while (!pq.empty() && pq.top()[2] < queries[qi]) {
				pq.pop();
			}
			//此时剩余的优先队列中优先级最高的就是所求区间，将其存入的区间长度取反即可
			if (!pq.empty()) {
				ans[qi] = -pq.top()[0];
			}
		}
		
		return ans;
	}
};

# (143) 重排链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        //如果是空链表，直接返回即可
        if (head == nullptr){
            return;
        }
        
        //创建vector容器存储链表，使用线性表可以随机读写的特性去操作链表
        vector<ListNode *> vec;
        ListNode *node = head;
        while (node != nullptr){
            //emplace_back是C++11新增的，其作用与push_back相同，但相较于push_back
            //emplace_back直接使用拷贝将值拷贝到容器末尾
            //而push_back则是先将值拷贝出来，然后再把拷贝好的值移动到容器末尾
            //相较而言，emplace_back有更高的性能，因此更推荐使用emplace_back
            //但考虑到兼容性，也可以在一些场景使用push_back
            vec.emplace_back(node);
            node = node->next;
        }

        //i，j双指针，一个正向读一个反向读，修改链表
        int i = 0, j = vec.size() - 1;
        while (i < j){
            vec[i]->next = vec[j];
            i++;
            if (i == j){
                break;
            }
            vec[j]->next = vec[i];
            j--;
        }
        vec[i]->next = nullptr;
    }
};

# (722) 删除注释

class Solution {
public:
    vector<string> removeComments(vector<string>& source) {
        //答案
        vector<string> res;
        //中间变量new_line
        string new_line = "";
        //用布尔变量in_block来标记现在是否在块注释中
        bool in_block = false;
        //遍历source
        for (auto& line : source) {
            //遍历source中的string
            for (int i = 0; i < line.size(); i++) {
                if (in_block) {
                    //如果现在在块注释中，进行如下判断：
                    //如果下一个字符不大于字符串长度(为了避免读取*/时，使用i+1越界)，并且接下来的两个字符是*/
                    if (i + 1 < line.size() && line[i] == '*' && line[i + 1] == '/') {
                        //那么退出块注释状态，将in_block设置为false
                        in_block = false;
                        i++;
                    }
                } else {
                    //如果不在块注释内，进行如下判断：
                    //如果下一个字符不大于字符串长度(为了避免读取/*时，使用i+1越界)，并且接下来的两个字符是/*
                    if (i + 1 < line.size() && line[i] == '/' && line[i + 1] == '*') {
                        //那么进去块注释状态，将in_block设置为true
                        in_block = true;
                        i++;
                    } else if (i + 1 < line.size() && line[i] == '/' && line[i + 1] == '/') {
                        //或者接下来的两个字符是//，那么直接结束该行即可
                        break;
                    } else {
                        //如果既不是块注释也不是行注释，那么把该字符加入到new_line当中
                        new_line += line[i];
                    }
                }
            }
            //当一行字符遍历结束时，如果此时不在块注释内，并且new_line不为空，将其加入到答案里
            if (!in_block && new_line != "") {
                res.push_back(new_line);
                //重置new_line
                new_line = "";
            }
        }
        return res;
    }
};

# (23) 合并 K 个升序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//方法1：顺序合并
class Solution {
public:
    //合并a,b两个链表
    ListNode* mergeTwoLists(ListNode *a, ListNode *b){
        //如果a链表为空，或者b链表为空
        //如果a为空返回b，如果b为空返回a
        if ((!a) || (!b)) return a ? a : b;

        //声明ans的头节点head，与指向ans链表结尾的tail指针
        //使用aPtr和bPtr来操作a链表和b链表
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        
        //只要aPtr或者bPtr任意一个指向空，那么就结束循环
        while (aPtr && bPtr){
            //如果aPtr的值更小，那么将aPtr的节点赋给tail的next，并向后继续读a链表
            if (aPtr->val < bPtr->val){
                tail->next = aPtr;
                aPtr = aPtr->next;
            }
            else{
                //如果bPtr的更小，那么将bPtr的节点赋给tail的next，并向后继续读b链表
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            //更新tail
            tail = tail->next;
        }

        //循环结束后，a链表为空或者b链表为空，将不为空的链表剩余部分归入ans
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (int i = 0;i < lists.size();i++){
            //从前往后将ans链表和lists[i]看作两个链表的合并逐个调用mergeTwoLists
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

//方法2：分治合并
class Solution {
public:
    //合并a,b两个链表
    ListNode* mergeTwoLists(ListNode *a, ListNode *b){
        //如果a链表为空，或者b链表为空
        //如果a为空返回b，如果b为空返回a
        if ((!a) || (!b)) return a ? a : b;

        //声明ans的头节点head，与指向ans链表结尾的tail指针
        //使用aPtr和bPtr来操作a链表和b链表
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        
        //只要aPtr或者bPtr任意一个指向空，那么就结束循环
        while (aPtr && bPtr){
            //如果aPtr的值更小，那么将aPtr的节点赋给tail的next，并向后继续读a链表
            if (aPtr->val < bPtr->val){
                tail->next = aPtr;
                aPtr = aPtr->next;
            }
            else{
                //如果bPtr的更小，那么将bPtr的节点赋给tail的next，并向后继续读b链表
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            //更新tail
            tail = tail->next;
        }

        //循环结束后，a链表为空或者b链表为空，将不为空的链表剩余部分归入ans
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector<ListNode*> &lists, int l, int r){
        //使用左右指针与取中值，将链表组分为左半部分与右半部分，然后将二者作为整体进行递归归并
        //不停的左右划分，直到左右部分仅剩一个链表，则返回其本身即可
        //或者剩余两个链表，那么使用mergeTwoLists将其合并为一个链表并返回
        //最后收束归并链表组
        if (l == r) return lists[l];
        //如果左值已经超过右值，那么返回空即可
        if (l > r)return nullptr;
        //(l + r) >> 1即(l + r) / 2
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

# (2048) 下一个更大的数值平衡数

#include<iostream>
#include<map>
#include<algorithm>

class Solution {
public:
    int nextBeautifulNumber(int n) {
        using namespace std;
        //用于记录某个数的出现次数
        map<int, int> m;
        int i = ++n;

        while (true) {
            //flag用于标记是否找到平衡数，结束循环
            bool flag = true;
            //temp用于标记某一位数字是否出现过
            map<int, bool> temp;
            while (i > 0) { 
                //如果出现0，说明该数字不符合要求（因为0的出现次数已经为1，不可能满足出现次数为0的要求）
                if (i % 10 == 0) {
                    flag = false;
                    break;
                }
                
                //如果某数是第一次出现
                if (temp[i % 10] == false) {
                    //则将该数设置为已经出现过
                    temp[i % 10] = true;
                    //并将该数对应的map[]设置为需要出现的次数
                    m[i % 10] = i % 10 - 1;
                }
                else {
                    //如果该数已经出现过，则将其对应的map[] 需要出现的次数减1
                    m[i % 10]--;
                }
                i /= 10;
            }

            for (int j = n; j > 0; j /= 10) {
                //遍历map，如果均为0说明出现次数匹配，如果不为0，则说明有数字的出现次数不对，把flag调成false
                if (m[j % 10] != 0) {
                    flag = false;
                    break;
                }
            }
            //根据flag返回查找到的平衡数
            if (flag)
                return n;
            n++;
            i = n;
        }
    }
};

int main() {
    using namespace std;
    Solution s;
    //遍历题目给出的n的范围（0 <= n <= 1000000)
    for (int i = 0; i < 1000000; i++) {
        i = s.nextBeautifulNumber(i);
        cout << i << endl;
    }
    
	return 0;
}

//通过上述算法计算出所有结果的可能，然后使用vector存储，用二分查找获取结果并返回，如下：
class Solution {
public:
    const vector<int> balance {
        1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444,
        14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332,
        33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555,
        122333, 123233, 123323, 123332, 132233, 132323, 132332,
        133223, 133232, 133322, 155555, 212333, 213233, 213323,
        213332, 221333, 223133, 223313, 223331, 224444, 231233,
        231323, 231332, 232133, 232313, 232331, 233123, 233132,
        233213, 233231, 233312, 233321, 242444, 244244, 244424,
        244442, 312233, 312323, 312332, 313223, 313232, 313322,
        321233, 321323, 321332, 322133, 322313, 322331, 323123,
        323132, 323213, 323231, 323312, 323321, 331223, 331232,
        331322, 332123, 332132, 332213, 332231, 332312, 332321,
        333122, 333212, 333221, 422444, 424244, 424424, 424442,
        442244, 442424, 442442, 444224, 444242, 444422, 515555,
        551555, 555155, 555515, 555551, 666666, 1224444
    };

    int nextBeautifulNumber(int n) {
        return *upper_bound(balance.begin(), balance.end(), n);
    }
};