1345-跳跃游戏 IV

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

  • i + 1 需满足：i + 1 < arr.length
  • i - 1 需满足：i - 1 >= 0
  • j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

**输入：** arr = [100,-23,-23,404,100,23,23,23,3,404]
**输出：** 3
**解释：** 那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

**输入：** arr = [7]
**输出：** 0
**解释：** 一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

**输入：** arr = [7,6,9,6,9,6,9,7]
**输出：** 1
**解释：** 你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

提示：

  • 1 <= arr.length <= 5 * 104
  • -108 <= arr[i] <= 108

方法一：广度优先搜索

思路

记数组 arr 的长度为 n。题目描述的数组可以抽象为一个无向图，数组元素为图的顶点，相邻下标的元素之间有一条无向边相连，所有值相同元素之间也有无向边相连。每条边的权重都为 1，即此图为无权图。求从第一个元素到最后一个元素的最少操作数，即求从第一个元素到最后一个元素的最短路径长度。求无权图两点间的最短路可以用广度优先搜索来解，时间复杂度为 O(V+E)，其中 V 为图的顶点数，E 为图的边数。

在此题中，V = n，而 E 可达 O(n^2) 数量级，按照常规方法使用广度优先搜索会超时。造成超时的主要原因是所有值相同的元素构成了一个稠密子图，普通的广度优先搜索方法会对这个稠密子图中的所有边都访问一次。但对于无权图的最短路问题，这样的访问是不必要的。在第一次访问到这个子图中的某个节点时，即会将这个子图的所有其他未在队列中的节点都放入队列。在第二次访问到这个子图中的节点时，就不需要去考虑这个子图中的其他节点了，因为所有其他节点都已经在队列中或者已经被访问过了。因此，在用广度优先搜索解决此题时，先需要找出所有的值相同的子图，用一个哈希表 idxSameValue 保存。在第一次把这个子图的所有节点放入队列后，把该子图清空，就不会重复访问该子图的其他边了。

代码

[sol1-Python3]
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
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxSameValue = defaultdict(list)
        for i, a in enumerate(arr):
            idxSameValue[a].append(i)
        visitedIndex = set()
        q = deque()
        q.append([0, 0])
        visitedIndex.add(0)
        while q:
            idx, step = q.popleft()
            if idx == len(arr) - 1:
                return step
            v = arr[idx]
            step += 1
            for i in idxSameValue[v]:
                if i not in visitedIndex:
                    visitedIndex.add(i)
                    q.append([i, step])
            del idxSameValue[v]
            if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:
                visitedIndex.add(idx + 1)
                q.append([idx+1, step])
            if idx - 1 >= 0 and (idx - 1) not in visitedIndex:
                visitedIndex.add(idx - 1)
                q.append([idx-1, step])
[sol1-Java]
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
class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> idxSameValue = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < arr.length; i++) {
            idxSameValue.putIfAbsent(arr[i], new ArrayList<Integer>());
            idxSameValue.get(arr[i]).add(i);
        }
        Set<Integer> visitedIndex = new HashSet<Integer>();
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{0, 0});
        visitedIndex.add(0);
        while (!queue.isEmpty()) {
            int[] idxStep = queue.poll();
            int idx = idxStep[0], step = idxStep[1];
            if (idx == arr.length - 1) {
                return step;
            }
            int v = arr[idx];
            step++;
            if (idxSameValue.containsKey(v)) {
                for (int i : idxSameValue.get(v)) {
                    if (visitedIndex.add(i)) {
                        queue.offer(new int[]{i, step});
                    }
                }
                idxSameValue.remove(v);
            }
            if (idx + 1 < arr.length && visitedIndex.add(idx + 1)) {
                queue.offer(new int[]{idx + 1, step});
            }
            if (idx - 1 >= 0 && visitedIndex.add(idx - 1)) {
                queue.offer(new int[]{idx - 1, step});
            }
        }
        return -1;
    }
}
[sol1-C#]
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
public class Solution {
    public int MinJumps(int[] arr) {
        Dictionary<int, IList<int>> idxSameValue = new Dictionary<int, IList<int>>();
        for (int i = 0; i < arr.Length; i++) {
            if (!idxSameValue.ContainsKey(arr[i])) {
                idxSameValue.Add(arr[i], new List<int>());
            }
            idxSameValue[arr[i]].Add(i);
        }
        ISet<int> visitedIndex = new HashSet<int>();
        Queue<int[]> queue = new Queue<int[]>();
        queue.Enqueue(new int[]{0, 0});
        visitedIndex.Add(0);
        while (queue.Count > 0) {
            int[] idxStep = queue.Dequeue();
            int idx = idxStep[0], step = idxStep[1];
            if (idx == arr.Length - 1) {
                return step;
            }
            int v = arr[idx];
            step++;
            if (idxSameValue.ContainsKey(v)) {
                foreach (int i in idxSameValue[v]) {
                    if (visitedIndex.Add(i)) {
                        queue.Enqueue(new int[]{i, step});
                    }
                }
                idxSameValue.Remove(v);
            }
            if (idx + 1 < arr.Length && visitedIndex.Add(idx + 1)) {
                queue.Enqueue(new int[]{idx + 1, step});
            }
            if (idx - 1 >= 0 && visitedIndex.Add(idx - 1)) {
                queue.Enqueue(new int[]{idx - 1, step});
            }
        }
        return 0;
    }
}
[sol1-C++]
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
class Solution {
public:
    int minJumps(vector<int>& arr) {
        unordered_map<int, vector<int>> idxSameValue;
        for (int i = 0; i < arr.size(); i++) {
            idxSameValue[arr[i]].push_back(i);
        }
        unordered_set<int> visitedIndex;
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        visitedIndex.emplace(0);
        while (!q.empty()) {
            auto [idx, step] = q.front();
            q.pop();
            if (idx == arr.size() - 1) {
                return step;
            }
            int v = arr[idx];
            step++;
            if (idxSameValue.count(v)) {
                for (auto & i : idxSameValue[v]) {
                    if (!visitedIndex.count(i)) {
                        visitedIndex.emplace(i);
                        q.emplace(i, step);
                    }
                }
                idxSameValue.erase(v);
            }
            if (idx + 1 < arr.size() && !visitedIndex.count(idx + 1)) {
                visitedIndex.emplace(idx + 1);
                q.emplace(idx + 1, step);
            }
            if (idx - 1 >= 0 && !visitedIndex.count(idx - 1)) {
                visitedIndex.emplace(idx - 1);
                q.emplace(idx - 1, step);
            }
        }
        return -1;
    }
};
[sol1-C]
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
typedef struct IdxHashEntry {
    int key;               
    struct ListNode * head;
    UT_hash_handle hh;         
}IdxHashEntry;

typedef struct SetHashEntry {
    int key; 
    UT_hash_handle hh;         
}SetHashEntry;

typedef struct Pair {
    int idx;
    int step;
}Pair;

void hashAddIdxItem(struct IdxHashEntry **obj, int key, int val) {
    struct IdxHashEntry *pEntry = NULL;
    struct ListNode * node = (struct ListNode *)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;

    HASH_FIND(hh, *obj, &key, sizeof(key), pEntry);
    if (NULL == pEntry) {
        pEntry = (struct IdxHashEntry *)malloc(sizeof(struct IdxHashEntry));
        pEntry->key = key;
        pEntry->head = node;
        HASH_ADD(hh, *obj, key, sizeof(int), pEntry);
    } else {
        node->next = pEntry->head;
        pEntry->head = node;
    }
} 

struct IdxHashEntry *hashFindIdxItem(struct IdxHashEntry **obj, int key)
{
    struct IdxHashEntry *pEntry = NULL;
    HASH_FIND(hh, *obj, &key, sizeof(int), pEntry);
    return pEntry;
}

void hashFreeIdxAll(struct IdxHashEntry **obj)
{
    struct IdxHashEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, *obj, curr, next)
    {
        HASH_DEL(*obj, curr);  
        free(curr);      
    }
}

void hashAddSetItem(struct SetHashEntry **obj, int key) {
    struct SetHashEntry *pEntry = NULL;
    HASH_FIND(hh, *obj, &key, sizeof(key), pEntry);
    if (pEntry == NULL) {
        pEntry = malloc(sizeof(struct SetHashEntry));
        pEntry->key = key;
        HASH_ADD(hh, *obj, key, sizeof(int), pEntry);
    }
} 

struct SetHashEntry *hashFindSetItem(struct SetHashEntry **obj, int key)
{
    struct SetHashEntry *pEntry = NULL;
    HASH_FIND(hh, *obj, &key, sizeof(int), pEntry);
    return pEntry;
}

void hashFreeSetAll(struct SetHashEntry **obj)
{
    struct SetHashEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, *obj, curr, next)
    {
        HASH_DEL(*obj, curr);  
        free(curr);      
    }
}

int minJumps(int* arr, int arrSize){
    struct IdxHashEntry * idxSameValue = NULL;
    for (int i = 0; i < arrSize; i++) {
        hashAddIdxItem(&idxSameValue, arr[i], i);
    }
    
    struct SetHashEntry * visitedIndex = NULL;
    struct Pair * queue = (struct Pair *)malloc(sizeof(struct Pair) * arrSize * 2);
    int head = 0;
    int tail = 0;
    queue[tail].idx = 0;
    queue[tail].step = 0;
    tail++;
    hashAddSetItem(&visitedIndex, 0);
    while (head != tail) {
        int idx = queue[head].idx;
        int step = queue[head].step;
        head++;
        if (idx + 1 == arrSize) {
            hashFreeIdxAll(&idxSameValue);
            hashFreeSetAll(&visitedIndex);
            free(queue);
            return step;
        }
        int v = arr[idx];
        step++;
        struct IdxHashEntry * pEntry = hashFindIdxItem(&idxSameValue, v);
        if (NULL != pEntry) {
            for (struct ListNode * node = pEntry->head; node; node = node->next) {
                if (NULL == hashFindSetItem(&visitedIndex, node->val)) {
                    hashAddSetItem(&visitedIndex, node->val);
                    queue[tail].idx = node->val;
                    queue[tail].step = step;
                    tail++;
                }
            }
            HASH_DEL(idxSameValue, pEntry);
        }
        if (idx + 1 < arrSize && NULL == hashFindSetItem(&visitedIndex, idx + 1)) {
            hashAddSetItem(&visitedIndex, idx + 1);
            queue[tail].idx = idx + 1;
            queue[tail].step = step;
            tail++;
        }
        if (idx - 1 >= 0 && NULL == hashFindSetItem(&visitedIndex, idx - 1)) {
            hashAddSetItem(&visitedIndex, idx - 1);
            queue[tail].idx = idx - 1;
            queue[tail].step = step;
            tail++;
        }
    }
    hashFreeIdxAll(&idxSameValue);
    hashFreeSetAll(&visitedIndex);
    free(queue);
    return -1;
}
[sol1-Golang]
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
func minJumps(arr []int) int {
    n := len(arr)
    idx := map[int][]int{}
    for i, v := range arr {
        idx[v] = append(idx[v], i)
    }
    vis := map[int]bool{0: true}
    type pair struct{ idx, step int }
    q := []pair{ {} }
    for {
        p := q[0]
        q = q[1:]
        i, step := p.idx, p.step
        if i == n-1 {
            return step
        }
        for _, j := range idx[arr[i]] {
            if !vis[j] {
                vis[j] = true
                q = append(q, pair{j, step + 1})
            }
        }
        delete(idx, arr[i])
        if !vis[i+1] {
            vis[i+1] = true
            q = append(q, pair{i + 1, step + 1})
        }
        if i > 0 && !vis[i-1] {
            vis[i-1] = true
            q = append(q, pair{i - 1, step + 1})
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 arr 的长度。每个元素最多只进入队列一次，最多被判断是否需要进入队列三次。

  • 空间复杂度：O(n)，其中 n 为数组 arr 的长度。队列，哈希表和哈希集合均最多存储 n 个元素。

 Comments
On this page
1345-跳跃游戏 IV