674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

解题思路

因为求的是递增序列，所以当前元素小于等于上一个元素时，表示上一个递增子序列结束，我们更新下一个子序列开始位置，并求出此时最大子序列，依此循环即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findLengthOfLCIS(nums []int) int {
   var ans, start int
   for k, v := range nums {
      if k > 0 && v <= nums[k-1] {
         start = k
      }
      ans = max(ans, k-start +1)
   }
   return ans
}

func max(a, b int) int {
   if a < b {
      return b
   }
   return a
}

682. 棒球比赛

你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

  1. 整数 x - 表示本回合新获得分数 x
  2. "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
  3. "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
  4. "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

示例 1：

输入：ops = [“5”,“2”,“C”,“D”,"+"]
输出：30
解释：
“5” - 记录加 5 ，记录现在是 [5]
“2” - 记录加 2 ，记录现在是 [5, 2]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5].
“D” - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
“+” - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30

示例 2：

输入：ops = [“5”,"-2",“4”,“C”,“D”,“9”,"+","+"]
输出：27
解释：
“5” - 记录加 5 ，记录现在是 [5]
“-2” - 记录加 -2 ，记录现在是 [5, -2]
“4” - 记录加 4 ，记录现在是 [5, -2, 4]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
“D” - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
“9” - 记录加 9 ，记录现在是 [5, -2, -4, 9]
“+” - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
“+” - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27

示例 3：

输入：ops = [“1”]
输出：1

解题思路

题目比较简单，因为数据都是合法的，所以不需要额外验证数据，直接用数组模拟栈处理即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func calPoints(ops []string) int {
	var stack []int
	for _, op := range ops {
		switch op {
		case "+":
			stack = append(stack, stack[len(stack)-1]+stack[len(stack)-2])
		case "D":
			stack = append(stack, stack[len(stack)-1]*2)
		case "C":
			stack = stack[:len(stack)-1]
		default:
			score, _ := strconv.Atoi(op)
			stack = append(stack, score)
		}
	}
	var count int
	for _, i := range stack {
		count += i
	}
	return count
}

694. 数组的度

给定一个非空且只包含非负数的整数数组 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 。

解题思路

通过哈希记录当前数值出现的次数与首次出现和最后一次出现，取出最多出现次数的值，用最后一次出现减去第一次出现的即可得出度

示例代码

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
type entry struct {
   cnt, l, r int
}

func findShortestSubArray(nums []int) int {
   var ans, maxCnt int
   mp := map[int]entry{}
   for i, v := range nums {
      if e, ok := mp[v]; ok {
         e.cnt++
         e.r = i
         mp[v] = e
      } else {
         mp[v] = entry{1, i, i}
      }
   }
   for _, e := range mp {
      if e.cnt > maxCnt {
         maxCnt, ans = e.cnt, e.r-e.l+1
      }
      if e.cnt == maxCnt {
         ans = min(ans, e.r-e.l+1)
      }
   }
   return ans
}

func min(a, b int) int {
   if a < b {
      return a
   }
   return b
}

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

> 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

解题思路

略

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int, target int) int {
   l, r := 0, len(nums)-1
   for l <= r {
      mid := (r-l)/2 + l
      num := nums[mid]
      if num == target {
         return mid
      } else if target < num {
         r = mid - 1
      } else {
         l = mid + 1
      }
   }
   return -1
}

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
 

示例：

输入：
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

解题思路

利用数组存储，直接对数组进行插入，查找，删除

示例代码

略

解题思路

**HashSet是在时间和空间上做权衡的例子：**如果不考虑空间问题，直接使用顺序存储的方式，用一个超大的数组报错，每个Key都有单独的位置。插入和查找都会比较费时间。

为了平衡时间和空间的平衡，HashSet是基于数组实现的，通过hsah方法求键Key在数组中的位置，当hash后的位置存在冲突的时候，在解决冲突。设计合适的 hash 函数，一般都是对分桶数取模%，为了避免冲突，尽量采用质数取模

c9bbf70f3f0c446ed294e087d8565348.jpg

示例代码

使用了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
34
35
36
37
38
39
type MyHashSet struct {
   data []list.List
}

const base = 997

func Constructor() MyHashSet {
   return MyHashSet{make([]list.List, base)}
}

func (this *MyHashSet) hash(key int) int {
   return key % base
}

func (this *MyHashSet) Add(key int) {
   if !this.Contains(key) {
      h := this.hash(key)
      this.data[h].PushBack(key)
   }
}

func (this *MyHashSet) Remove(key int) {
   h := this.hash(key)
   for e := this.data[h].Front(); e != nil; e = e.Next() {
      if e.Value.(int) == key {
         this.data[h].Remove(e)
      }
   }
}

func (this *MyHashSet) Contains(key int) bool {
   h := this.hash(key)
   for e := this.data[h].Front(); e != nil; e = e.Next() {
      if e.Value.(int) == key {
         return true
      }
   }
   return false
}

706. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

  • MyHashMap() 用空映射初始化对象
  • void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
  • int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
  • void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

 

示例：

输入：
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

解题思路

与上题几乎一致，唯一的区别在于我们存储的不是key本身，而是 (key,value) 对。除此之外，代码基本是类似的。

示例代码

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
type entry struct {
   key, value int
}

const base = 997

type MyHashMap struct {
   data []list.List
}

func Constructors() MyHashMap {
   return MyHashMap{make([]list.List, base)}
}

func hash(key int) int {
   return key % base
}

func (this *MyHashMap) Put(key int, value int) {
   h := hash(key)
   for e := this.data[h].Front(); e != nil; e = e.Next() {
      if v := e.Value.(entry); v.key == key {
         e.Value = entry{key, value}
         return
      }
   }
   this.data[h].PushBack(entry{key, value})
}

func (this *MyHashMap) Get(key int) int {
   h := hash(key)
   for e := this.data[h].Front(); e != nil; e = e.Next() {
      if v := e.Value.(entry); v.key == key {
         return v.value
      }
   }
   return -1
}

func (this *MyHashMap) Remove(key int) {
   h := hash(key)
   for e := this.data[h].Front(); e != nil; e = e.Next() {
      if v := e.Value.(entry); v.key == key {
         this.data[h].Remove(e)
      }
   }
}