2181. 合并零之间的节点 - 力扣（LeetCode）
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。head 。
解题思路
双指针
1° 分别定义指针low，high指向头节点和头节点的下一节点，保持“一定一动”
2° 移动high指针，当high指针指向不为0时，将指向的节点值累加到当前low节点中
3° 当high指针指向0且当前节点不为最后一个节点时，满足合并条件。令low->next = high即可
4° 遍历结束，将指针low指向空
代码实现
struct ListNode* mergeNodes(struct ListNode* head){
struct ListNode *low = head;
struct ListNode *high = head->next;
while(high){
if(high->next != NULL && high->val == 0){
low->next = high;
low = low->next;
}
low->val += high->val;
high = high->next;
}
low->next = NULL;
return head;
}950. 按递增顺序显示卡牌 - 力扣（LeetCode）
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：
- 从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
- 如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
- 如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。
返回能以递增顺序显示卡牌的牌组顺序。答案中的第一张牌被认为处于牌堆顶部。
解题思路
模拟
1° 假设刚开始一副牌放在桌上，题干的意思是：从牌堆顶拿走一张牌，若牌堆中还有牌，则把牌堆顶的那张牌放在牌堆底。直到拿走所有的牌。最后手中的牌是单调递减的（就是手上垒了一堆牌，牌堆顶是最大的）。
2° 我们不妨将逆置上述步骤，也就是：现在我们手上有一副单调递减的牌，先把桌上的牌堆底的那张牌抽出来放到牌堆顶，然后再把手上的首张牌放到桌上的牌堆顶，重复以上两步，直到手上的牌放完为止。
代码实现
int cmp(const void* a, const void* b){
return *(int*)b - *(int*)a;
}
// 桌上的牌堆底的牌抽出来放到牌堆顶
void converse(int* ret, int q){
if (q == 0) {
return;
}
int temp = ret[q - 1];
for (int i = q - 1; i > 0; i--) {
ret[i] = ret[i - 1];
}
ret[0] = temp;
return;
}
// 把手上的首张牌放到桌上的牌堆顶
void set(int* ret, int q, int tag){
for (int i = q - 1; i > 0; i--) {
ret[i] = ret[i - 1];
}
ret[0] = tag;
return;
}
int* deckRevealedIncreasing(int* deck, int deckSize, int* returnSize){
// 使用qsort函数使数组单调递减，模拟手上的递减牌
qsort(deck, deckSize, sizeof(int), cmp);
int* ret = (int*)malloc(deckSize * sizeof(int));
memset(ret, 0, deckSize * sizeof(int));
int q = 0;
for (int i = 0; i < deckSize; i++) {
converse(ret, q);
q++;
set(ret, q, deck[i]);
}
*returnSize = q;
return ret;
}1997. 访问完所有房间的第一天 - 力扣（LeetCode）
你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：
- 假设某一天，你访问
i号房间。 - 如果算上本次访问，访问
i号房间的次数为 奇数 ，那么 第二天 需要访问nextVisit[i]所指定的房间，其中0 <= nextVisit[i] <= i。 - 如果算上本次访问，访问
i号房间的次数为 偶数 ，那么 第二天 需要访问(i + 1) mod n号房间。
请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。
解题思路
贪心、dp
1° 定义一个二维数组记录奇数/偶数次访问房间的次数。第一次（第0天）访问0号房间的次序是0，第二次（第一天）访问0号房间的次序是1，即：dp[0][0] = 0，dp[0][1] = 1
2° 据题意可知只有当第偶数次访问到某个房间时，才可以前进，如果是第奇数次访问，则必然是回退到当前房间的左边（0 <= nextVisit[i] <= i）
3° 由此，第一次访问i号房间，等于第二次访问i-1号房间的次数再加1，即 dp[i][0] = dp[i-1][1] + 1。那么第二次访问i号房间的次数呢？
4° ①首先要有第一次访问i号房间，+dp[i][0] ②第一次访问i号房间后，要回退到nextVisit[i]号房间，即 +1 ③然后从nextVisit[i]号房间再一次访问到i号房间，即dp[i][0]-dp[nextVisit[i][0]]，那么为什么会是[i][0]，nextVisit[i][0]呢？
5° 因为当我们第二次到达i号房间的过程，也就是说，之前已经来过一次了（似乎有点废话），那么这就意味着前边的房间都已经访问过了偶数次，再次回退时，则到达nextVisit[i]号房间又是奇数次。此时再从nextVisit[i]号房间前进到i号房间，其实就等价于，从第一次访问nextVisit[i]号房间到第一次访问i号房间之间的次数差。
6° 得到 dp[i][1] = 2*dp[i][0] - dp[nextVisit[i]][0] + 1
6° 由状态转移方程，当第一次访问到最后一个房间时，直接返回它即可。这个过程中不要忘记并模上m。注意！可能会出现负数，必须加上m再模m。
代码实现
int firstDayBeenInAllRooms(int* nextVisit, int nextVisitSize) {
int m = 1e9+7;
int n = nextVisitSize;
long long dp[n][2];
memset(dp, 0, sizeof(dp));
dp[0][0] = 0, dp[0][1] = 1;
for(int i = 1; i < n; i++){
dp[i][0] = (dp[i-1][1] + 1 + m) % m;
dp[i][1] = (2*dp[i][0] - dp[nextVisit[i]][0] + 1 + m) % m;
}
return dp[n-1][0];
}