41-50
# 41.数据流中的中位数
剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
这题先暂时跳过，后续再来研究一下
# 42.连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 解法一： 动态规划
可能是我题目做多了吧~，居然做出来了哈哈。
func maxSubArray(nums []int) int {
// 如果长度为0，那么我们直接返回0
if len(nums) == 0 {
return 0
}
// 设当前值为最大
max:=nums[0]
// 然后我们开始遍历整个数组
for i := 1; i < len(nums); i++ {
// 当前的最大值有两种情况，要么当前是最大，要么是前一个加上当前这个最大
nums[i] = Max(nums[i-1]+nums[i],nums[i])
// 然后我们找出最大值就可以了
if max < nums[i] {
max = nums[i]
}
}
return max
}
func Max(a int,b int) int {
if a > b {
return a
} else {
return b
}
}
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
# 43.1~n整数中1出现的次数
剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
看到大佬的题解又觉得自己行了，但是看了一下，算了我是垃圾，先跳过吧。。。。
# 44.数字序列中某一位的数字
剑指 Offer 44. 数字序列中某一位的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
这题目的难点在于如何找出这个规律，我现在这种能力还非常欠缺。。。。
# 解法一： 迭代
唉，还是直接看大佬的题解吧，下面这个是我们得到的数学规律
确定好大致范围后我们还需要进行细分
func findNthDigit(n int) int {
// digit表示数位
// start表示起始数字
// count表示数位的数量
digit:=1
start:= 1
count:= 9
// 当n小于数位数量的时候，我们就退出循环
for n > count {
// 这里是根据我们的数学规律进行计算得到的
n-=count
digit+=1
start*=10
count=digit*start*9
}
// num表示所求数位在第几个数字中
num:=start+(n-1)/digit
// 然后这里确定我们的数位
return int(strconv.Itoa(num)[(n-1)%digit] - '0')
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 45.把数组排成最小的数
剑指 Offer 45. 把数组排成最小的数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
。。。。。这种题真的完全没有思路。。。这题刷的我好难受啊
# 解法一： 自定义排序
这题本质上也是排序，只是由之前的排数字变成了排序字符串，我们把这些东西排好序后就可以得出结果了
func minNumber(nums []int) string {
// 处理边界情况，如果数组为空或长度为0
if nums == nil || len(nums) == 0 {
return "" // 返回空的字符串
}
// 否则定义一个长度为n的字符串数组
strs := make([]string, len(nums))
// 遍历整数数组,把整数转成字符串,并存储到字符串数组
for i := range nums {
strs[i] = strconv.Itoa(nums[i])
}
// 接下来对字符串进行排序,注意这里要自定义对比规则
sort.Slice(strs, func(i, j int)bool{
// 先把两种字符串的拼接结果写出来
s12 := strs[i]+strs[j]
s21 := strs[j]+strs[i]
// 如果字符串s12小于s21，那么我们希望s1排在s2前面。
return s12<s21
})
// 把数组中的字符串依次拼接起来
var buffer bytes.Buffer
for i := range strs{
buffer.WriteString(strs[i])
}
return buffer.String()
}
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
# 46.把数字翻译成字符串
剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
又是一道不会的题。。。这种题还是自己练的太少了唉
# 解法一： 动态规划
动态规划的题目难就难在如何找出状态方程，本题的状态方程如下
func translateNum(num int) int {
// 为了方便计算我们先把数字转换为字符串
s := strconv.Itoa(num)
// 然后使用a，b来暂存,a表示i-2 b表示i-1
a := 1
b := 1
// 然后我们开始计算
for i := 2; i <= len(s); i++ {
// 每次截取两个字符
tmp := s[i-2 : i]
var c int
// 然后比较一下大小
if tmp >= "10" && tmp <= "25" {
c = a + b
} else {
c = a
}
b = a
a = c
}
return a
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 解法二： 数字求余
上面的动态规划虽然省略了dp占用的控件，但是还需要字符串s
利用求余运算 num % 10 和求整运算 num // 10 ，可获取数字 num 的各位数字
func translateNum(num int) int {
a:=1;b:=1;x,y:=num%10,num%10
for num!=0 {
// num/10 来获取各位情况
num/=10
// x相当于10位，然后y相当于个位
x=num%10
// 计算tmp，tmp就是要比较的值
tmp:=10*x+y
var c int
if tmp >= 10 && tmp <= 25 {
c = a+b
} else {
c = a
}
b = a
a = c
y = x
}
return a
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 47.礼物的最大价值
剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
居然做出来了，太激动了，主要是以前做过差不多的哈哈哈
# 解法一： 动态规划
func maxValue(grid [][]int) int {
if len(grid) == 0 {
return 0
}
// 获取grid的长度和宽度
m,n:=len(grid),len(grid[0])
// 初始化dp数组
dp:=make([][]int,m)
// dp数组分配空间
for i:=0;i<m;i++{
dp[i] = make([]int,n)
}
// 因为我们只能向下或者向右，所以我们直接可以算出顶部和左边的值
dp[0][0] = grid[0][0]
// 顶部和左边都是固定的
for i:=1;i<m;i++{
dp[i][0] = grid[i][0] + dp[i-1][0]
}
for i:=1;i<n;i++{
dp[0][i] = grid[0][i]+ dp[0][i-1]
}
// 然后我们计算其他部分的
for i:=1;i<m;i++ {
for j:=1;j<n;j++ {
// 因为根据我们的状态方程，当前最大值要么是上面的+当前的，要么是左边+当前的，我们选一个最大的即可
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j]
}
}
return dp[m-1][n-1]
}
func max(a int,b int) int {
if a > b {
return a
} else {
return b
}
}
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
不过我这解法还是有点不足的地方就是需要额外申请空间的。所以我们这里可以直接在原数组的基础上进行计算，这样就省去了dp数组
func maxValue(grid [][]int) int {
if len(grid) == 0 {
return 0
}
// 获取grid的长度和宽度
m,n:=len(grid),len(grid[0])
// 顶部和左边都是固定的
for i:=1;i<m;i++{
grid[i][0] += grid[i-1][0]
}
for i:=1;i<n;i++{
grid[0][i] += grid[0][i-1]
}
// 然后我们计算其他部分的
for i:=1;i<m;i++ {
for j:=1;j<n;j++ {
// 因为根据我们的状态方程，当前最大值要么是上面的+当前的，要么是左边+当前的，我们选一个最大的即可
grid[i][j] += max(grid[i-1][j],grid[i][j-1])
}
}
return grid[m-1][n-1]
}
func max(a int,b int) int {
if a > b {
return a
} else {
return b
}
}
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
# 48.最长不包含重复字符串的子字符串
剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 解法一： 动态规划+哈希表
因为我们要统计连续的不重复字符串，所以我们必须使用map来暂存数据，然后判断是否重复，然后我们使用tmp来暂存
func lengthOfLongestSubstring(s string) int {
// 使用动态规划
dic:=make(map[byte]int)
// res存储最终结果，然后tmp表示dp[i]
res:=0;tmp:=0
// 遍历整个s
for j := 0; j < len(s); j++ {
// 默认i的值为-1，表示dic里面没有
var i = -1
// 如果当前字符串在map里面存在，我们就返回当前字符串的位置
if _, ok := dic[s[j]]; ok {
i=dic[s[j]]
}
// 更新一下map
dic[s[j]] = j
// 判断是当前的大还是j-i的大
if tmp < j-i {
tmp++
} else {
tmp=j-i
}
// 获取最大值
res = max(res,tmp)
}
return res
}
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
# 解法二： 动态规划+线性遍历
func lengthOfLongestSubstring(s string) int {
// res表示最终结果，tmp表示当前位置下最长的子字符串
res:=0;tmp:=0
// 开始进行遍历
for i := 0; i < len(s); i++ {
j:=i-1
// 找出第一个和当前位置重复的元素
for j >= 0 && s[j] != s[i] {
j--
}
if tmp < i-j {
tmp++
} else {
tmp = i-j
}
// 找出一个最大值
res=max(res,tmp)
}
return res
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 解法三： 双指针+哈希表
我们使用两个指针来表示，如果不重复那么就完全加，如果发现重复的，我们就更新一下位置
func lengthOfLongestSubstring(s string) int{
// 使用dic来暂存数据
dic:=make(map[byte]int)
// res设置为0，j默认为-1
res:=0;j:=-1
// 遍历整个字符串
for i := 0; i < len(s); i++ {
// 当我们的字符串已经存在时
if _,ok:=dic[s[i]];ok {
// 这里我们更新一下j的位置（取最大是为了每次获取最后的，避免重复）
j=max(j,dic[s[i]])
}
// 然后我们更新一下位置信息
dic[s[i]] = i
// 更新一下最大值即可
res=max(res,i-j)
}
return res
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 49.丑树
剑指 Offer 49. 丑数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
唉，对这种数学规律的题目我真的已经无感了。。。我怎么这么菜啊。。。
# 解法一： 动态规划
func nthUglyNumber(n int) int {
// 因为丑树是包含质因子2,3,5的数，所以我们就分别哟经abc来进行表示
a:=0;b:=0;c:=0
// 初始化dp数组
dp:=make([]int,n)
dp[0] = 1
for i:=1;i<n;i++ {
// 我们分别求一下每个质因子和较小的数相乘得到的结果
an:=dp[a]*2;bn:=dp[b]*3;cn:=dp[c]*5
// 当前的丑数值就应该上面三个的最小值
dp[i] = min(an,min(bn,cn))
// 判断一下是哪个最小，然后我们更新一下下标
// 因为我们要确保丑数要每个质因子都要乘一下，所以我们采用3个下标的方式
if dp[i] == an { a++ }
if dp[i] == bn { b++ }
if dp[i] == cn { c++ }
}
return dp[n-1]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 50.第一个只出现一次的字符
剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
害，太难了，本来以为可以直接使用map来解决，但是最后发现go遍历map居然是随机的。。。
# 解法一： 使用数组来存储频次
我傻了，傻乎乎的想怎么找到第一个值，一直在研究数组，但是最后才发现，我直接再遍历一般字符串不就行了。。。
func firstUniqChar(s string) byte {
cnt:=[26]int{}
// 遍历整个数组
for i := 0;i<len(s);i++{
cnt[s[i]-'a']++
}
// 继续遍历
for i := 0; i < len(s); i++ {
// 找出第一个为1的值，找到后我们立马退出
if cnt[s[i]] == 1 {
return s[i]
}
}
return ' '
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15