本文涉及知识点
C++BFS算法
LeetCode2059. 转化数字的最小运算数
给你一个下标从 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 = [2,4,12], start = 2, goal = 12
输出：2
解释：
可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：
- 2 + 12 = 14
- 14 - 2 = 12
示例 2：
输入：nums = [3,5,7], start = 0, goal = -4
输出：2
解释：
可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：
- 0 + 3 = 3
- 3 - 7 = -4
注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。
示例 3：
输入：nums = [2,8,16], start = 0, goal = 1
输出：-1
解释：
无法将 0 转化为 1
提示：
1 <= nums.length <= 1000
-109 <= nums[i], goal <= 109
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同
BFS
BFS的状态表示：前续状态（包括start)一定在[0,1000]，后续状态（包括goal)不一定在此范围。空间复杂度：O(1000)。
BFS的后续状态：三种操作，每种操作可以选择nums的任一元素。单个状态的时间复杂度：O(m),m = nums.lenght。总时间复杂度：O(nm)
BFS的初始状态：leves[0]={start}
BFS的返回值：如果后续状态等于goal，则返回leve[i]。否则返回-1。
BFS的重复处理：leve数组出重。
代码
超时代码
哈希集合的时间复杂度是：O(7)左右，超时。
class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
unordered_set<int> neiBo[1001];
for (int i = 0; i <= 1000; i++) {
for (const auto& n : nums) {
neiBo[i].emplace(i + n);
neiBo[i].emplace(i - n);
neiBo[i].emplace(i ^ n);
}
}
vector<int> leve(1001, -1);
leve[start] = 0;
vector<int> v = { start };
for (int i = 0; i < v.size(); i++) {
for (const auto& next : neiBo[v[i]]) {
if (goal == next) { return leve[v[i]] + 1; }
if ((next >= 0) && (next <= 1000)) {
if (-1 != leve[next]) { continue; }
v.emplace_back(next);
leve[next] = leve[v[i]] + 1;
}
}
}
return -1;
}
};
单元测试
vector<int> nums;
int start, goal;
TEST_METHOD(TestMethod1)
{
nums = { 3 }, start = 2, goal = 5;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 1);
}
TEST_METHOD(TestMethod2)
{
nums = { 3 }, start = 2, goal = 1;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 1);
}
TEST_METHOD(TestMethod3)
{
nums = { 3 }, start =2, goal = -1;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 1);
}
TEST_METHOD(TestMethod4)
{
nums = { 3 }, start =2, goal = 11;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 3);
}
TEST_METHOD(TestMethod5)
{
nums = { 3 }, start = 2, goal = 22211;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, -1);
}
TEST_METHOD(TestMethod6)
{
nums = { 2,8,16 }, start =0, goal = 1;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, -1);
}
TEST_METHOD(TestMethod11)
{
nums = { 2,4,12 }, start = 2, goal = 12;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 2);
}
TEST_METHOD(TestMethod12)
{
nums = { 3,5,7 }, start = 0, goal = -4;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 2);
}
TEST_METHOD(TestMethod13)
{
nums = { 2,8,16 }, start = 0, goal = 1;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, -1);
}
TEST_METHOD(TestMethod14)
{
nums = {563, 419, -169, -106, 518, -627, 422, -50, -300, 188, -743, 54, 485, -626, 366, -675, 752, 989, -207, 915, 20, 809, 413, 823, -358, -890, -727, -850, -46, 497, 21, -59, 590, 490, -205, -864, 494, 39, -696, 582, -981, -772, 500, -12, -310, -828, -98, -313, -873, -601, -342, -814, -600, 897, 101, -589, -14, -678, 879, 176, -48, 48, -234, 972, 816, -502, 711, 938, 913, 600, -529, -513, -982, 950, 692, -31, 68, -128, -135, -654, -400, 778, -708, 855, -576, 693, 462, 906, -967, 399, -353, -809, 136, 544, 385, -758, 69, -416, -900, 659, 290, -9, 770, -770, -965, -272, 844, -792, -920, -161, -44, -840, -147, -263, 883, 909, 291, 786, -218, 585, 275, 597, 541, -199, 762, -436, -498, -177, -340, 361, 962, -113, -168, 464, 508, 666, -534, 805, -605, -99, -999, -110, -457, 969, 968, 720, -363, 524, 963, 724, -889, -93, -79, -786, 578, -812, -115, 253, -680, 755, 713, -996, 443, 987, -826, -251, 857, -369, 344, -733, 109, 152, 982, -67, -68, 47, 230, 474, 622, -888, 531, -619, 135, -613, 146, 764, -863, 18, 224, -913, 81, 584, 983, -640, 8, -520, -474, -787, 336, 286, -896, -493, -652, 937, 134, 207, -551, 527, -20, -27, 17, -620, 148, 31, 757, -84, 889, 124, 3, 534, -950, 162, 654, -766, -496, 295, 265, 421, -610, 580, 813, 685, -395, 566, 771, -519, 157, 106, 407, 672, 280, 113, -315, -298, -941, 349, -33, -635, 929, 94, -801, -921, -925, 354, 457, 825, 154, -90, -76, -432, -275, 185, 346, -414, 505, 533, 238, -646, -915, -526, 822, 164, 657, -124, 120, 530, -464, 673, -842, -919, -16, 475, 847, 591, -948, -707, -528, -817, 270, 731, 79, 632, 979, -179, -259, -410, 682, -138, 539, -117, -384, -95, 811, 595, 557, -642, 542, -43, -849, 128, 73, -57, 604, -88, -472, 836, 25, 719, 466, 444, -220, -406, 328, -195, -503, 634, -560, -230, -225, 266, -638, 367, -249, -203, 746, 4, 46, -571, -689, 327, 458, -945, -568, 451, 470, -918, -952, 482, 812, -574, -309, -351, 372, -823, -81, 888, -245, -932, 288, -448, -331, 833, 387, -719, 652, -700, -260, -594, -227, 293, 259, 151, -625, -741, -805, 384, -415, -30, -737, 615, -399, 607, 525, -327, -768, 97, 402, 100, 721, 194, 173, -603, 507, 942, 202, 52, 155, 712, 788, -151, 80, -480, 492, -289, 663, -145, -630, 273, -291, -451, -423, -499, 34, 50, -36, 376, -987, 282, -469, -483, 528, 575, -749, 96, -929, -257, 491, -928, -320, 952, 44, 829, 703, -713, 147, 851, 568, 42, 341, -938, -573, 998, 625, 688, 852, 306, -775, -756, -909, 246, -15, -852, 881, 117, 111, 975, -552, 478, 967, -181, -32, -859, -155, 800, 547, 511, 53, 985, -739, -838, -332, -240, -163, 645, -65, 150, -538, 723, 981, -154, 435, -910, 393, -431, 748, -206, -740, -401, 199, -328, 677, -258, 860, -986, 735, 516, -774, 873, 26, -157, -92, -883, 817, -133, -19, 439, -669, 390, 592, 891, 623, -83, 572, 751, 168, -870, -238, 777, -60, -676, 347, -690, 679, -74, 139, 732, 536, 115, -210, -276, 252, -341, -514, -208, 840, 709, 122, -755, -37, 509, 89, 630, -517, -881, -394, -5, 332, 311, -121, -279, -975, 342, -841, -991, 756, 299, 281, 130, 261, -224, -287, 947, -97, -711, -318, -659, 284, -685, 374, 144, 375, 322, -917, -357, 315, -466, 601, 579, -566, -979, 72, -579, 114, -614, 919, 949, -440, 1, 472, -968, 403, -636, -681, 91, -219, 633, 229, -73, -196, -367, 506, 502, -80, -361, -296, -688, -23, -385, 793, 264, -854, 893, -366, -720, -66, 882, -202, 798, -843, -256, -942, 759, -435, 714, -370, 722, -657, -934, 602, 820, -477, -762, -765, -42, 787, -706, -606, -754, -557, 255, 187, -887, 314, -816, -617, 796, 363, 294, 429, 59, 664, -243, -860, -215, 704, 689, -879, 939, -29, 132, 904, 191, 501, 769, 510, 373, -87, -352, -973, -355, 57, -322, 213, 442, -892, 772, -473, -403, -424, 396, -193, -388, 14, -701, 512, -326, -729, -992, -22, 483, 535, 741, 766, 289, 583, 680, 126, 271, -807, -253, -604, -78, 377, -378, -197, 885, 695, 546, -778, 608, -141, 552, 644, -725, 745, 647, 887, -329, -454, -228, 424, 440, -306, 210, -159, -785, 683, -180, -131, -55, 45, 310, 212, -891, 826, -182, -875, -362, -963, -391, -198, 784, 684, 853, -277, 438, -658, -127, 953, -511, 532, -354, -591, -456, -356, -944, -497, -704, 649, -512, -935, -631, -547, 781, -648, -972, 409, 627, 993, -270, 880, 190, -693, 803, 687, 667, 318, -521, -699, 914, -461, 973, 487, -235, -839, -405, -337, -592, -437, -13, -417, -226, 669, -434, -265, 480, -114, 499, -833, -231, -386, -855, 556, -811, -443, -292, 184, 991, -409, 55, -702, 948, -607, -959, 538, -549, 27, 414, -484, 570, 561, -349, -140, -831, 681, -718, 774, -564, -734, -350, -686, -912, 775, -522, -798, 808, -262, -299, 971, 924, 304, -123, -710, -790, 214, -748, -223, -446, 911, -126, 454, -662, -77, -709, -951, -868, 636, -188, 551, -695, -172, 671, -167, 716, 858, 196, -382, -142, -150, 765, 521, -1000, -449, -590, 842, -460, -714, 193, -111, -323, -961, 486, 522, 940, 729, 964, -425, 980, 338, -286, 656, 436, 871, 66, 549, -837, 391, 484, 209, 569, -698, -475, -122, -806, -501, 824, -527, -947, 791, -753, -663, 88, 776, 966, 504, 171, 145, -641, -216, 576, -556, -989, -994, -482, 810, -439, -72, -712, 221, -278, -836, -940, 526, 174, -618, -252, -344},
start = 416, goal = 372;
auto res = Solution().minimumOperations(nums, start, goal);
AssertEx(res, 1);
}
第二版
后续状态只需要考虑：[0,1000]和goal。
class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
vector<int> neiBo[1001];
for (int i = 0; i <= 1000; i++) {
vector<bool> vis(1001);
bool bGoal = false;
auto Add = [&](int cur) {
if (cur == goal) { bGoal = true; }
if ((cur < 0) || (cur > 1000)) { return; }
vis[cur] = true;
};
for (const auto& n : nums) {
Add(i + n);
Add(i - n);
Add(i ^ n);
}
for (int j = 0; j <= 1000; j++) {
if (vis[j]) { neiBo[i].emplace_back(j); }
}
if (bGoal) {
neiBo[i].emplace_back(goal);
}
}
vector<int> leve(1001, -1);
leve[start] = 0;
vector<int> v = { start };
for (int i = 0; i < v.size(); i++) {
for (const auto& next : neiBo[v[i]]) {
if (goal == next) { return leve[v[i]] + 1; }
if ((next >= 0) && (next <= 1000)) {
if (-1 != leve[next]) { continue; }
v.emplace_back(next);
leve[next] = leve[v[i]] + 1;
}
}
}
return -1;
}
};
第三版
直接用向量，不出重，反而更快了。可能重复的几率不大。出重的成本反而大于重复浪费的时间。
