ARST打卡第167周[167/521]

 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

func arrayNesting(nums []int) int {
	// 在准备先写暴力算法的时候，在想状态标记每次修改应该比较麻烦
	// 然后想到如果一个数字已经遍历过了，那么它在那个嵌套里面的值就一直是那个值
	// 然后其他的数字看到了之前的嵌套环的话，那么就是直接把自身的cnt步数直接加上原来的环中的数
	// invalid array length sz. 数组只能用常量声明
	// var cnt [sz]int
	cnt := make([]int, len(nums))
	ans := 0
	for i := range nums {
		if cnt[i] != 0 {
			continue
		}
		tmpMap := make(map[int]bool)
		// tmp := make([]int, 0)
		tmpCnt := 0
		// 循环条件搞错了...
		// for 0 == cnt[i] {
		// fmt.Printf("debug: term new---\n")
		for !tmpMap[i] || cnt[i] != 0 {
			tmpMap[i] = true
			// tmp = append(tmp, i)
			tmpCnt++
			i = nums[i]
		}
		// fmt.Printf("debug: i: %v tmp[i]: %v\n", i, tmpMap[i])
		/*
			遍历为集合map，会导致结果混乱，所以不能用map遍历
			debug: i: 0 tmp[i]: true
			debug: index: 6
			debug: index: 2
			debug: index: 0
			debug: index: 5
			debug: ans: 8
		*/
		// for index := range tmp {
		preCnt := cnt[i]
		for index := range tmpMap {
			// fmt.Printf("debug: index: %d\n", index)
			// 之前的环值也需要加入
			// 这样加入: cnt[index] = cnt[i] + tmpCnt,不管是map还是数组，都会出问题
			cnt[index] = preCnt + tmpCnt
			if cnt[index] > ans {
				ans = cnt[index]
			}
		}
		// fmt.Printf("debug: ans: %v\n", ans)
	}
	return ans
}

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

func arrayNesting(nums []int) (ans int) {
    n := len(nums)
    for i := range nums {
        cnt := 0
        for nums[i] < n {
            i, nums[i] = nums[i], n
            cnt++
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return
}
// 链接：https://leetcode.cn/problems/array-nesting/solution/shu-zu-qian-tao-by-leetcode-solution-7ur3/