1. 两数之和(1)#
代码语言：javascript
复制给定一个整数数组 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
只会存在一个有效答案
代码语言：javascript
复制//查找表法
//用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)
}
2. 模拟行走机器人(874)#
代码语言：javascript
复制机器人在一个无限大小的 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] 中
代码语言：javascript
复制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)
}
3. 字母异位词分组(49)#
代码语言：javascript
复制给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：strs[i] 仅包含小写字母
代码语言：javascript
复制/*
排序法
*/
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)
}
4. 串联所有单词的子串(30)#
代码语言：javascript
复制给定一个字符串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 由小写英文字母组成
代码语言：javascript
复制/*
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))
}
5. LRU缓存(146)#
代码语言：javascript
复制请你设计并实现一个满足 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
代码语言：javascript
复制/*
哈希表 双向链表
双向链表带有头结点和尾结点，双向链表用于按时间顺序保存节点
时间复杂度：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)
}
6. 子域名访问计数(811)#
代码语言：javascript
复制网站域名 "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 由小写英文字母组成
代码语言：javascript
复制/*
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))
}
7. 数组的度(697)#
代码语言：javascript
复制给定一个非空且只包含非负数的整数数组 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 范围内的整数。
代码语言：javascript
复制/*
我的解法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))
}
