这次的题感觉还是挺简单的，前两道题半小时做完了，第三道题用DFS栈溢出（不懂剪枝没做够？），最后一道题只剩半小时不够时间了，还是只做出来两道题，排名2206 / 4181

5914. 值相等的最小索引 [EASY]

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

x mod y 表示 x 除以 y 的 余数 。

示例 1：

输入：nums = [0,1,2]
输出：0
解释：
i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
所有下标都满足 i mod 10 == nums[i] ，所以返回最小下标 0

示例 2：
输入：nums = [4,3,2,1]
输出：2
解释：
i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 唯一一个满足 i mod 10 == nums[i] 的下标

示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9,0]
输出：-1
解释：不存在满足 i mod 10 == nums[i] 的下标
示例 4：

输入：nums = [2,1,3,5,2]
输出：1
解释：1 是唯一一个满足 i mod 10 == nums[i] 的下标

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* 
审题：
没啥好说的，过于简单还让我多审了两次题
*/
class Solution {
public:
    int smallestEqual(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (i % 10 == nums[i]) {
                return i;
            }
        }
        return -1;
    }
};

5915. 找出临界点之间的最小和最大距离 [MEDIUM]

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。

示例 1：
输入：head = [3,1]
输出：[-1,-1]
解释：链表 [3,1] 中不存在临界点。

示例 2：
输入：head = [5,3,1,2,5,1,2]
输出：[1,3]
解释：存在三个临界点：

• [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
• [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
• [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
  第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
  第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。

示例 3：
输入：head = [1,3,2,2,3,2,2,2,7]
输出：[3,3]
解释：存在两个临界点：

• [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
• [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
  最小和最大距离都存在于第二个节点和第五个节点之间。
  因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
  注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。

示例 4：
输入：head = [2,3,3,2]
输出：[-1,-1]
解释：链表 [2,3,3,2] 中不存在临界点。

提示：
链表中节点的数量在范围 [2, 105] 内
1 <= Node.val <= 105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/*
审题：这题先把极值点找出来，标记下坐标（这个过程保证坐标有序），然后最远的肯定是第一个和最后一个，
遍历下坐标点，找出距离最近的，输出即可
*/
/**
 * 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:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int> result(2, 0);
        vector<int> pointIndex;
        auto node = head;
        int preNodeVal = -1;
        int index = 0;
        while (node->next) {
            // cout << index << ", " << node->val << endl;
            if (node == head) {
            } else if (node->val > node->next->val && node->val > preNodeVal) {
                // 极大值
                pointIndex.push_back(index);
            } else if (node->val < node->next->val && node->val < preNodeVal) {
                // 极小值
                pointIndex.push_back(index);
            }
            preNodeVal = node->val;
            node = node->next;
            ++index;
        }
        // for (auto& point : pointIndex) {
        //     cout << pointIndex.size() << " : " << point << ", ";
        // }
        // cout << endl;
        if (pointIndex.size() < 2) {
            result[0] = -1;
            result[1] = -1;
            return result;
        }
        int minDistance = 100000;
        int maxDistance = pointIndex.back() - pointIndex[0];
        if (pointIndex.size() == 2) {
            result[0] = maxDistance;
            result[1] = maxDistance;
            return result;
        }
        for (auto i = 1; i < pointIndex.size(); i++) {
            if (pointIndex[i] - pointIndex[i - 1] < minDistance) {
                minDistance = pointIndex[i] - pointIndex[i - 1];
            }
        }
        result[0] = minDistance;
        result[1] = maxDistance;
        return result;
    }
};

5916. 转化数字的最小运算数 [MEDIUM]

给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。

整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：

如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：

x + nums[i]
x - nums[i]
x ^ nums[i]（按位异或 XOR）
注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。

返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。

示例 1：
输入：nums = [1,3], start = 6, goal = 4
输出：2
解释：
可以按 6 → 7 → 4 的转化路径进行，只需执行下述 2 次运算：

• 6 ^ 1 = 7
• 7 ^ 3 = 4

示例 2：
输入：nums = [2,4,12], start = 2, goal = 12
输出：2
解释：
可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：

• 2 + 12 = 14
• 14 - 2 = 12

示例 3：
输入：nums = [3,5,7], start = 0, goal = -4
输出：2
解释：
可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：

• 0 + 3 = 3
• 3 - 7 = -4
  注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。

示例 4：
输入：nums = [2,8,16], start = 0, goal = 1
输出：-1
解释：
无法将 0 转化为 1

示例 5：
输入：nums = [1], start = 0, goal = 3
输出：3
解释：
可以按 0 → 1 → 2 → 3 的转化路径进行，只需执行下述 3 次运算：

• 0 + 1 = 1
• 1 + 1 = 2
• 2 + 1 = 3

提示：
1 <= nums.length <= 1000
-109 <= nums[i], goal <= 109
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

审题：看着就像DFS可以做出来的题，加了操作数大于已知最小退出、出现过数字退出这两个剪枝策略都没用，看讨论要用BFS

// stack-overflow
class Solution {
public:
    long long minOpt_ = INT_MAX;
    void dfs(const vector<int>& nums, int x, int goal, int operation, vector<int>& asMap) {
        if (x == goal) {
            if (operation < minOpt_) {
                minOpt_ = operation;
            } 
            return;
        }
        if (x < 0 || x > 1000 || operation >= minOpt_ || asMap[x]) {
            return;
        }
        asMap[x]++;
        for (size_t i = 0; i < nums.size(); ++i) {
            // add
            dfs(nums, x + nums[i], goal, operation + 1, asMap);
            // minus
            dfs(nums, x - nums[i], goal, operation + 1, asMap);
            // xor
            dfs(nums, x ^ nums[i], goal, operation + 1, asMap);
        }
    }
    
    int minimumOperations(vector<int>& nums, int start, int goal) {
        vector<int> asMap(1000, 0);
        dfs(nums, start, goal, 0, asMap);
        return minOpt_ == INT_MAX ? -1 : minOpt_;
    }
};

5917. 同源字符串检测 [HARD]

原字符串由小写字母组成，可以按下述步骤编码：

任意将其 分割 为由若干 非空 子字符串组成的一个 序列 。
任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。
重新 顺次连接 序列，得到编码后的字符串。
例如，编码 “abcdefghijklmnop” 的一种方法可以描述为：

将原字符串分割得到一个序列：[“ab”, “cdefghijklmn”, “o”, “p”] 。
选出其中第二个和第三个元素并分别替换为它们自身的长度。序列变为 [“ab”, “12”, “1”, “p”] 。
重新顺次连接序列中的元素，得到编码后的字符串：”ab121p” 。
给你两个编码后的字符串 s1 和 s2 ，由小写英文字母和数字 1-9 组成。如果存在能够同时编码得到 s1 和 s2 原字符串，返回 true ；否则，返回 false。

注意：生成的测试用例满足 s1 和 s2 中连续数字数不超过 3 。

示例 1：
输入：s1 = “internationalization”, s2 = “i18n”
输出：true
解释：”internationalization” 可以作为原字符串

• “internationalization”
  -> 分割： [“internationalization”]
  -> 不替换任何元素
  -> 连接： “internationalization”，得到 s1
• “internationalization”
  -> 分割： [“i”, “nternationalizatio”, “n”]
  -> 替换： [“i”, “18”, “n”]
  -> 连接： “i18n”，得到 s2

示例 2：
输入：s1 = “l123e”, s2 = “44”
输出：true
解释：”leetcode” 可以作为原字符串

• “leetcode”
  -> 分割： [“l”, “e”, “et”, “cod”, “e”]
  -> 替换： [“l”, “1”, “2”, “3”, “e”]
  -> 连接： “l123e”，得到 s1
• “leetcode”
  -> 分割： [“leet”, “code”]
  -> 替换： [“4”, “4”]
  -> 连接： “44”，得到 s2

示例 3：
输入：s1 = “a5b”, s2 = “c5b”
输出：false
解释：不存在这样的原字符串

• 编码为 s1 的字符串必须以字母 ‘a’ 开头
• 编码为 s2 的字符串必须以字母 ‘c’ 开头
• 示例 4：
  输入：s1 = “112s”, s2 = “g841”
  输出：true
  解释：”gaaaaaaaaaaaas” 可以作为原字符串
• “gaaaaaaaaaaaas”
  -> 分割： [“g”, “aaaaaaaaaaaa”, “s”]
  -> 替换： [“1”, “12”, “s”]
  -> 连接： “112s”，得到 s1
• “gaaaaaaaaaaaas”
  -> 分割： [“g”, “aaaaaaaa”, “aaaa”, “s”]
  -> 替换： [“g”, “8”, “4”, “1”]
  -> 连接 “g841”，得到 s2

示例 5：
输入：s1 = “ab”, s2 = “a2”
输出：false
解释：不存在这样的原字符串

• 编码为 s1 的字符串由两个字母组成
• 编码为 s2 的字符串由三个字母组成

提示：

1 <= s1.length, s2.length <= 40
s1 和 s2 仅由数字 1-9 和小写英文字母组成
s1 和 s2 中连续数字数不超过 3

1

审题：第三题卡太久了，这题只留了半小时不到，知道做不完还是写一下，我的想法就是先把字符串分割，然后排列组合成多种，再遍历这两个s1和s2的所有组合，只写完了字符串分割(c++真难搞)。虽然后面的排列组合和比较估计也很难写，看答案应该是用动态规划，待续。。。