674. 最长连续递增序列

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

连续递增的子序列 可以由两个下标 lrl < 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)
}
}
}