2059. 转化数字的最小运算数-队列+广度优先遍历

2059. 转化数字的最小运算数-队列+广度优先遍历

给你一个下标从 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）
1
2
3

注意，你可以按任意顺序使用每个 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

这题也是很典型的一个题目，解题代码如下：

int minimumOperations(int* nums, int numsSize, int start, int goal){
   int x[1001];
   int step=0;
   for(int i=0;i<1001;i++){
       x[i]=0;
   }
   x[start]=1;
   int store[1001];
   int rear=1,front=0;
   store[0]=start;

   while(1){
       step++;
       int prerear=rear;
       while(prerear!=front){
           int x_t=store[front++];
          
           for(int i=0;i<numsSize;i++){
              if(x_t+nums[i]==goal){
                       return step;
                   }
               if(0<=x_t+nums[i]&&x_t+nums[i]<=1000&&x[x_t+nums[i]]==0){
                  
                   x[x_t+nums[i]]=1;
                   store[rear++]=x_t+nums[i];
                   
               }
                 if(x_t-nums[i]==goal){
                       return step;
                   }
               if(0<=x_t-nums[i]&&x_t-nums[i]<=1000&&x[x_t-nums[i]]==0){
                   
                   x[x_t-nums[i]]=1;
                   store[rear++]=x_t-nums[i];
                   
               }
                 if((x_t^nums[i])==goal){
                       return step;
                   }
             
               if(0<=(x_t^nums[i])&&(x_t^nums[i])<=1000&&x[x_t^nums[i]]==0){
                   
                   x[(x_t^nums[i])]=1;
                   store[rear++]=(x_t^nums[i]);
                   
               }
              
               
           }

       }
    //   printf("||%d %d ",rear,front);
       if(rear==front){
           break;
       }

   }

   return -1;
   


}
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
63
64
65