Leetcode模块训练2

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
只会存在一个有效答案

//查找表法
//用map记录已经遍历过的数值和下标
//空间换时间
//时间复杂度：O(N)
//空间复杂度：O(N)
func twoSum(nums []int, target int) []int {
	mapTemp := make(map[int]int, len(nums))
	for i, v := range nums {
		if j, ok := mapTemp[target-v]; ok {
			return []int{j, i}
		}
		mapTemp[v] = i
	}
	return nil
}

func main() {
	nums := []int{2, 11, 7, 15}
	target := 9

	result1 := twoSum(nums, target)
	fmt.Println(result1)
}

机器人在一个无限大小的 XY 网格平面上行走，从点(0, 0) 处开始出发，面向北方。
该机器人可以接收以下三种类型的命令 commands ：
	-2 ：向左转90 度
	-1 ：向右转 90 度
	1 <= x <= 9 ：向前移动x个单位长度
在网格上有一些格子被视为障碍物obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi)
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）

注意：
	北表示 +Y 方向。
	东表示 +X 方向。
	南表示 -Y 方向。
	西表示 -X 方向。

示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25

解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25

示例2：
输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65

解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65

提示：
commands[i] 只会存在于 [-2,-1,1,2,3,4,5,6,7,8,9] 中

func max(i, j int) int {
	if i < j {
		return j
	}
	return i
}

func robotSim(commands []int, obstacles [][]int) int {
	// 判断障碍物在该位置是否存在
	obstaclesMap := make(map[[2]int]bool)
	for _, v := range obstacles {
		if len(v) == 2 {
			obstaclesMap[[2]int{v[0], v[1]}] = true
		}
	}
	// []int{北，东，南，西}
	dirX := [4]int{0, 1, 0, -1}
	dirY := [4]int{1, 0, -1, 0}
	x, y, dir, distance := 0, 0, 0, 0 // 当前位置，当前方向，欧式距离
	for _, v := range commands {
		switch v {
		case -2: // 左转
			dir = (dir + 3) % 4
		case -1: // 右转
			dir = (dir + 1) % 4
		default: // 前进
			for i := 0; i < v; i++ { // 向dir方向走v步
				nextX := x + dirX[dir]
				nextY := y + dirY[dir]
				// 判断是否存在障碍物
				if _, ok := obstaclesMap[[2]int{nextX, nextY}]; ok {
					break
				}
				x = nextX
				y = nextY
				// 计算最大欧氏距离
				distance = max(distance, x*x+y*y)
			}
		}

	}
	return distance
}

func main() {
	commands := []int{4, -1, 4, -2, 4}
	var obstacles [][]int
	obstacles = append(obstacles, []int{2, 4})
	sim := robotSim(commands, obstacles)
	fmt.Println(sim)
}

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

提示：strs[i] 仅包含小写字母

/*
排序法
*/
func groupAnagrams(strs []string) [][]string {
	strMap := make(map[string][]string, 0)
	for _, v := range strs {
		strByte := []byte(v)
		sort.Slice(strByte, func(i, j int) bool {
			return strByte[i] < strByte[j]
		})
		strMap[string(strByte)] = append(strMap[string(strByte)], v)
	}
	result := make([][]string, 0, len(strMap))
	for _, v := range strMap {
		result = append(result, v)
	}
	return result
}

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	anagrams := groupAnagrams(strs)
	fmt.Println(anagrams)
}

给定一个字符串s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。
例如，如果words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，
"efabcd"，和"efcdab" 都是串联子串。"acdbef" 不是串联子串，因为他不是任何words排列的连接。
返回所有串联字串在s中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

/*
map，自己写的，时间复杂度偏高
时间复杂度：O(ls*m*n), ls 是输入 s 的长度，m 是 word 的单词, n 是 words 中每个单词的长度
空间复杂度：O(m*n), m 是 word 的单词数，n 是 words 中每个单词的长度
*/
func findSubstring(s string, words []string) []int {
	wordFirstMap := make(map[string]bool, 0)
	for _, v := range words {
		firstStr := string(v[0])
		wordFirstMap[firstStr] = true
	}
	wordLength := len(words[0])
	amount := len(words)
	length := amount * wordLength
	result := make([]int, 0)
	for i, v := range s {
		if i+length > len(s) {
			break
		}
		vStr := string(v)
		if wordFirstMap[vStr] && i+length <= len(s) {
			tempStr := s[i : i+length]
			tempWords := make([]string, 0, amount)
			tempWordMap := make(map[string]int, 0)
			for _, u := range words {
				tempWordMap[u] += 1
			}
			for j := 0; j < length; {
				value := tempStr[j : j+wordLength]
				if tempWordMap[value] > 0 {
					tempWords = append(tempWords, value)
					tempWordMap[value]--
				} else {
					break
				}
				j += wordLength
			}
			if len(tempWords) == amount {
				result = append(result, i)
			}
		}
	}
	return result
}

/*
滑动窗口
时间复杂度：O(ls×n), ls 是输入 s 的长度，n 是 words 中每个单词的长度
空间复杂度：O(m×n), m 是 word 的单词数，n 是 words 中每个单词的长度
*/
func findSubstring2(s string, words []string) (ans []int) {
	ls, m, n := len(s), len(words), len(words[0])
	for i := 0; i < n && i+m*n <= ls; i++ {
		differ := map[string]int{}
		for j := 0; j < m; j++ {
			differ[s[i+j*n:i+(j+1)*n]]++
		}
		for _, word := range words {
			differ[word]--
			if differ[word] == 0 {
				delete(differ, word)
			}
		}
		for start := i; start < ls-m*n+1; start += n {
			if start != i {
				word := s[start+(m-1)*n : start+m*n]
				differ[word]++
				if differ[word] == 0 {
					delete(differ, word)
				}
				word = s[start-n : start]
				differ[word]--
				if differ[word] == 0 {
					delete(differ, word)
				}
			}
			if len(differ) == 0 {
				ans = append(ans, start)
			}
		}
	}
	return
}

func main() {
	s := "wordgoodgoodgoodbestword"
	words := []string{"word", "good", "best", "good"}
	fmt.Println(findSubstring(s, words))
	fmt.Println(findSubstring2(s, words))
}

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

/*
哈希表+双向链表
双向链表带有头结点和尾结点，双向链表用于按时间顺序保存节点
时间复杂度：O(1)
空间复杂度：O(capacity)
*/

type LRUCache struct {
	size       int
	capacity   int
	cache      map[int]*DLinkedNode
	head, tail *DLinkedNode
}

func Constructor(capacity int) LRUCache {
	l := LRUCache{
		capacity: capacity,
		cache:    map[int]*DLinkedNode{},
		head:     initDLinkedNode(0, 0),
		tail:     initDLinkedNode(0, 0),
	}
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}

func (this *LRUCache) Get(key int) int {
	if v, ok := this.cache[key]; ok {
		this.moveToHead(v)
		return v.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if _, ok := this.cache[key]; !ok {
		node := initDLinkedNode(key, value)
		this.cache[key] = node
		this.addToHead(node)
		this.size++
		if this.size > this.capacity {
			tail := this.removeTail()
			delete(this.cache, tail.key)
			this.size--
		}
	} else {
		node := this.cache[key]
		node.value = value
		this.moveToHead(node)
	}
}

type DLinkedNode struct {
	key, value int
	prev, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode {
	return &DLinkedNode{
		key:   key,
		value: value,
	}
}

func (this *LRUCache) addToHead(node *DLinkedNode) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

func (this *LRUCache) removeNode(node *DLinkedNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLinkedNode) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLinkedNode {
	node := this.tail.prev
	this.removeNode(node)
	return node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
func main() {
	capacity := 2
	obj := Constructor(capacity)
	obj.Put(1, 1)
	obj.Put(2, 2)
	obj.Get(1)
}

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，
最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，
同时也会隐式访问其父域名 "leetcode.com" 以及 "com" 。
计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。
例如：
"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。
给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

示例 1：
输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：
例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：
输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：
按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

提示：
1 <= cpdomain.length <= 100
1 <= cpdomain[i].length <= 100
cpdomain[i] 会遵循 "repi d1i.d2i.d3i" 或 "repi d1i.d2i" 格式
repi 是范围 [1, 104] 内的一个整数
d1i、d2i 和 d3i 由小写英文字母组成

/*
map
时间复杂度：O(n)，n为所有子域名的长度
空间复杂度：O(n)，n为所有子域名的长度
*/
func subdomainVisits(cpdomains []string) []string {
	domainMap := make(map[string]int, 0)
	for _, v := range cpdomains {
		splits := strings.Split(v, " ")
		rep, _ := strconv.Atoi(splits[0])
		domain := splits[1]
		splitDom := strings.Split(domain, ".")
		tempDom := ""
		for i := len(splitDom) - 1; i >= 0; i-- {
			if i == len(splitDom)-1 {
				tempDom = splitDom[i]
			} else {
				tempDom = splitDom[i] + "." + tempDom
			}
			domainMap[tempDom] += rep
		}
	}
	res := make([]string, 0, len(domainMap))
	for k, v := range domainMap {
		rep := strconv.Itoa(v)
		res = append(res, rep+" "+k)
	}
	return res
}

func main() {
	cpdomains := []string{"900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"}
	fmt.Println(subdomainVisits(cpdomains))
}

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：
输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

示例 2：
输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

提示：
nums.length 在 1 到 50,000 范围内。
nums[i] 是一个在 0 到 49,999 范围内的整数。

/*
我的解法map：
时间复杂度较高
空间复杂度：O(n)
*/
func findShortestSubArray(nums []int) int {
	numMap, maxNum, maxCount := make(map[int]int, 0), 0, 0
	for _, v := range nums {
		numMap[v]++
		if numMap[v] > maxCount {
			maxNum = v
			maxCount = numMap[v]
		}
	}

	maxSlice := make([]int, 0)
	maxSlice = append(maxSlice, maxNum)
	for k, v := range numMap {
		if v == maxCount && k != maxNum {
			maxSlice = append(maxSlice, k)
		}
	}
	minLen := 50000
	for _, v := range maxSlice {
		i, j := 0, len(nums)-1
		for i < len(nums) {
			if nums[i] == v {
				break
			}
			i++
		}
		for j >= 0 && j >= i {
			if nums[j] == v {
				break
			}
			j--
		}
		if j-i+1 < minLen {
			minLen = j - i + 1
		}
	}
	return minLen
}

/*
官方思路map
时间复杂度：O(n)
空间复杂度：O(n)
*/
type assist struct {
	count int
	l, r  int
}

func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}

func findShortestSubArray2(nums []int) int {
	numMap := make(map[int]*assist, 0)
	for i, v := range nums {
		if value, ok := numMap[v]; ok {
			value.count++
			value.r = i
			numMap[v] = value
		} else {
			numMap[v] = &assist{
				count: 1,
				l:     i,
				r:     i,
			}
		}
	}

	maxCount, res := 0, 0
	for _, v := range numMap {
		if v.count > maxCount {
			maxCount = v.count
			res = v.r - v.l + 1
		} else if v.count == maxCount {
			res = min(res, v.r-v.l+1)
		}
	}
	return res
}

func main() {
	nums := []int{1, 2, 2, 3, 1, 4, 2}
	//nums := []int{1, 2, 2, 3, 1}
	fmt.Println(findShortestSubArray(nums))
	fmt.Println(findShortestSubArray2(nums))
}