题解 | #代理服务器#

代理服务器

https://www.nowcoder.com/practice/1284469ee94a4762848816a42281a9e0

package main

import (
	"fmt"
)

func main() {

	proxyMap := make(map[string]struct{})
	serverList := make([]string, 0)

	shot := ""

    empty := struct{}{}

	// 模块A 读代理服务器
	n := 0
	_, _ = fmt.Scan(&n)
	for i := 0; i < n; i++ {
		var proxy string
		_, _ = fmt.Scan(&proxy)
		proxyMap[proxy] = empty
		if n == 1 {
			// 仅为 1 考虑命中
			shot = proxy
		}
	}

	// 模块B 读目标服务器
	m := 0
	_, _ = fmt.Scan(&m)
	for i := 0; i < m; i++ {
		var next string
		_, _ = fmt.Scan(&next)
		serverList = append(serverList, next)
		if shot != "" && shot == next {
			// 仅为 1 且命中，则返回不对
			fmt.Print(-1)
            return
		}
	}

	// 模块 C 贪心遍历
	visitedMap := make(map[string]struct{})
	visited := 0
	count := 0
	for _, server := range serverList {
		_, ok := proxyMap[server]
		if ok {
			_, isVisited := visitedMap[server]
			if !isVisited {
				visitedMap[server] = empty
				visited++
			}

			if visited == n {
				count++
				visited = 1
				visitedMap = map[string]struct{}{server: empty}
			}
		}
	}

	fmt.Print(count)

}

A：遍历读取代理服务器，这里我做了个小技巧，分析题目要求，有返回-1的可能，且说明了输入的代理服务器各不相同，那只可能是 “只有一个代理服务器，且它在访问列表出现了”，这种情况我用了个 shot 变量保存

B ：遍历读取目标服务器，使用数组保存一下返回的顺序。如果 shot 不是的，说明只有一个代理服务器，如果与此同时命中了shot，说明应该返回 -1 终止程序了

3：核心算法区

C ：我这里用了个新变量 visitedMap 来保存每个代理的使用情况，visited作为访问了多少个代理的数量，实际上如果想节省空间，也可以用proxyMap，但是时间复杂度会上升。

具体内容是遍历目标服务器列表，访问到存在于“代理服务器”中元素的时候，将，判断是不是所有代理都访问过了，不是就忽略

当所有代理都访问过时：视为之前一直在使用最后代理服务器，遇到了该切换了，需要进行以下操作，清空访问情况和代理服务器访问次数，将最后一个代理服务器视为已访问，切换次数 + 1

举例 1

代理 A, B, C 访问 T, H, L, A, E, B

开始遍历的时候，还不知道第一个应该用什么服务器， count = 0， visit = 0

THL不存在于代理服务器，无视

到达 A 时， A还没有访问过，先标记。此时访问记录：visit = 1， visitedMap 有 A

E 忽略，到达 B 时， B 还没有访问过，先标记。此时访问记录：visit = 2， visitedMap 有 A、B