互联网眺望

发表于 更新于 分类于 本文字数： 739 阅读时长 ≈ 3 分钟

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

力扣给出了一种惊天地泣鬼神的解法，直接把IV,IX等形式替换为字符串a,b,c…等，然后再进行转换，我怎么就想不出来呢。o(╥﹏╥)o

本题涉及的Go语言知识包括：

  1. Go中map的用法：上题中我们列举了Go中map的用法，本题不多叙述。
  2. Go中将字符串作为数组的使用：
1
2
3
s := "abc"
fmt.Println(s[1]) // 98
fmt.Println(string(s[1])) // b
  1. 字符串替换
1
2
3
4
5
6
s := "abcabc"
a := strings.Replace(s, "a", "A", 1)
fmt.Println(s) // abcabc
fmt.Println(a) // Abcabc
b := strings.Replace(s, "a", "A", -1) // -1表示全部替换
fmt.Println(b) // AbcAbc

回到题目上，

一种解法，从右向左或从左向右，每次判断两个字符，来决定数字大小和下标移动距离。

另外一种解法是，直接将4,9等情况的两个字母转换为一个字母，对于每个字母直接在映射中寻找其匹配数字。

易错点包括：（1） map初始化时，最后一行仍然需要保留逗号；（2）map取值时，键为字符串，而字符串s取值s[i]类型为byte，因此，需要使用类型转换string(s[i])

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
import "strings"
func romanToInt(s string) int {
	// 映射表
	romanMap := map[string]int {
		"I": 1,
		"V": 5,
		"X": 10,
		"L": 50,
		"C": 100,
		"D": 500,
		"M": 1000,
		"a": 4,
		"b": 9,
		"c": 40,
		"d": 90,
		"e": 400,
		"f": 900, // 该行的逗号不可省略
	}
	temp := strings.Replace(s, "IV", "a", -1)
	temp = strings.Replace(temp, "IX", "b", -1)
	temp = strings.Replace(temp, "XL", "c", -1)
	temp = strings.Replace(temp, "XC", "d", -1)
	temp = strings.Replace(temp, "CD", "e", -1)
	temp = strings.Replace(temp, "CM", "f", -1)
	result := 0
	// tempArray := []
	for i:= 0; i < len(temp); i++ {
		result += romanMap[string(temp[i])] // temp[i]类型为byte
	}
	return result
}

用Go刷题，Go的知识越多感觉有些凌乱了，可能是时候总结一波了。。。

发表于 更新于 分类于 本文字数： 923 阅读时长 ≈ 3 分钟

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
    给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

涉及到Go的知识包括：

  1. map的使用：（一开始以为这题会用到map，Go中map的遍历顺序不随机的。。。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map1 := map[int]string{
    1000: "M",
    900: "CM",
    500: "D",
    400: "CD", // 注意，该处的逗号不能省略
}
fmt.Println(map1)
map2 := make(map[int]string) // 不指定长度
map2[1000] = "M"
map2[900] = "CM"
fmt.Println(map2)
// 第二个参数指定为1，但是设置两个元素
map3 := make(map[int]string, 1) 
map3[1000] = "M"
map3[900] = "CM"
fmt.Println(map3)
  1. Go中的make，官方文档指出创建map时，第二个参数可能会被忽略而分配一个较小的初始空间。即上述代码的map3是允许的，并不表示限制map的size。这一点类似与Java对ArrayList的初始化。make可用于给切片slice/map/chan（channel 我目前还不知道这个类型是啥）来分配空间。

很多文档将make与new做对比。我们也来学习一下：

  1. Go中的new

官方文档中是这样描述的：new返回一个对应类型零值的指针。

1
2
The new built-in function allocates memory. The first argument is a type, not a value, and the value returned is a pointer to a newly allocated zero value of that type.
新的内置函数分配内存。第一个实参是类型，而不是值，返回的值是一个指针，指向新分配的该类型的零值。

很容易将Go-new与Java-new联想起来，目前没怎么用过，不多说。

  1. Go中字符串拼接：类比Java中的StringBuilder，Go中是否也有类似方法或接口呢？查找资料的时候查到可以使用strings.Join或者bytes.Buffer.WriteString或strings.Builder.WriteString

回到题目上，转换的规则应该是从左到右尽可能选择大的符号来表示。很明显适合使用贪心算法。

问题的难点是如何处理4X与9X这两种情况。我们可以将4X，9X对应的字母看作一个整体，即：IV = 4, IX = 9, XL=40, XC=90, CD= 400, CM = 900。将其余原映射表合并，形成总的数字映射表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
	"fmt"
	"strings"
)

func main() {
	fmt.Println(intToRoman(32))
}

func intToRoman(num int) string {
	nums := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	strs := []string{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}
	var result strings.Builder
	for i := 0; i < len(nums); i++ {
		// 每次查询剩余数字可以放置的最大值
		for ;num >= nums[i]; {
			num -= nums[i]
			result.WriteString(strs[i])
		}
	}
	return result.String()
}

力扣官方给出的硬编码倒是没想过这种算法，学到了(^▽^)。

发表于 更新于 分类于 本文字数： 722 阅读时长 ≈ 3 分钟

  1. 盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

明白题目搞了半天~~

转换为大白话：给n个长度分别为a1, a2, …, an的线段，一端与x轴对齐，依次排开，求与其中两条线段与x轴组成的矩形的最大面积。

笨方法，也是第一直觉，两两求最大值，两个for循环。

进阶：官方名称叫，双指针。即左侧1个指针与右侧1个指针逐步想中间移动，每次移动计算最大面积。也很好理解，和生活直觉也一致。

经过了第10题的洗刷，这题通过测试用例后1次通过，开森^_^

涉及到Go语言知识主要包括：数组操作，数组求长度。

1
2
3
4
5
6
7
8
9
10
a := []int{1,2,3} // 定义初始化, a的类型为[]int
b := [...]int{1,2,3,4,5,7} // 定义初始化，b的类型为[6]int， a与b类型不同
c := []
a[1] = 2 // 下标访问设置元素
length := len(a) // 求长度
fmt.Println(length) // 3
// fmt.Println(maxArea(b)) // 会报错，因为maxArea函数的形参类型为[]int
fmt.Println(b) // [1 2 3 4 5 7]
c := [3]int{0:1, 2:4} // 指定下标初始化
fmt.Println(c) // [1 0 4]

需要注意的两个点是：

  1. Go语言没有while循环, 使用 for ;循环条件; {} 来实现。
  2. Go语言中没有三目运算符 condition? true-valu1: false-value2，因此需要另外定义max函数

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxArea(height []int) int {
	i, j := 0, len(height)-1
	result := 0
	// go中没有while
	for ;i < j; {
        if height[i] < height[j] {
            // Go 中也没有三目运算符
			result = max((j - i) * height[i], result)
			i++
		} else {
			result = max((j - i) * height[j], result)
			j--
		}
	}
	return result
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

新学到Go中有三个点的用法，补充在下面：

  1. 可变参数函数：

    即允许传递不定长个相同类型的参数。

1
2
3
4
5
6
func myfunc(vals ...int) {
    fmt.Println(reflect.TypeOf(vals))
    for _, v := range vals {
    	fmt.Println(v)
    }
}

  1. 调用可变参数函数

    通过三个点可将数组，切片等转换为可变参数形式调用。

1
2
myfunc(9, 8)
myfunc(a...)

经过测试发现，在可变参数函数中，获取到可变函数的类型为[]Type。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

import (
	"fmt"
	"reflect"
)

func main() {
	a := []int{1, 2, 3, 4}
	b := []int{5, 6, 7}
	fmt.Println(a)
	c := append(a, b...)
	fmt.Println(c)
	myfunc(9, 8)
	myfunc(a...)
}

func myfunc(vals ...int) {
	fmt.Println(reflect.TypeOf(vals))
	for _, v := range vals {
		fmt.Println(v)
	}
}

发表于 更新于 分类于 本文字数： 53 阅读时长 ≈ 1 分钟

起因是通过

  1. 确认返回数据无误

    通过Fiddler等抓包软件，确认返回数据正确：

fiddler-filename确认.png

  1. 曾尝试方案：

    decode

    decodeURL..

  2. 解决方案：使用iconv-lite包

发表于 更新于 分类于 本文字数： 925 阅读时长 ≈ 3 分钟
  1. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

1
2
3
4
5
6
7
8
9
10
11
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

涉及到Go中的知识包括：

  1. 二维数组如何使用：
1
dp := make([][]bool, size)
  1. 如何依次比较两个字符串的各个字符：切片。在考虑中文的情况下我认为应使用[]rune(s)后再进行比较。
1
2
s := "abc"
s[0] == 'a' // true
  1. 字符串拼接：在其中一种解法中，巧妙的拼接字符串以避免数组越界问题。
1
2
s := "aaa"
b := s + "ddd"

查看资料后发现一种性能更高的字符串拼接方式：

1
2
3
4
var b bytes.Buffer
b.WriteString("aaa")
b.WriteString("bbv")
s := b.String()

另外，从力扣官方示例代码中新学到的一种Go语言函数声明方式，函数内函数，像变量一样声明函数：

1
2
3
4
5
6
7
8
func main() {
	// 可以类似变量一样声明函数
	inlineFunction := func() {
        fmt.Println("Hello")
	}
	// 函数调用
	inlineFunction()
}

这题的动态规划略复杂，搞了好久才搞懂。

仅仅一个点和一个星号的正则匹配都这么复杂，各个语言高效实现的完整的正则匹配功能真的厉害！根据《Effective Java》中在使用正则时的介绍，正则表达式最耗时的是按照正则表达式生成有限状态自动机的过程，因此我们可以猜测，至少Java中是采用有限状态自动机来实现的正则匹配的。

动态规划

image.png

定义状态：

image.png

状态转移方程：

image.png

问题的难点除了转移方程复杂外，初始化过程也比较难理解，空串与空串，空串与形式为a*b*c*…的字符串也需要在初始化中指出。另外一种非常巧妙的避免这个过程的方法是通过在两个字符串的头部添加相同的特定字符来实现，我们不做过多阐述。

实现代码如下：

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
func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([][]bool, m + 1)
	for i := 0; i < len(dp); i ++ {
		dp[i] = make([]bool, n + 1)
	}

	// init
	dp[0][0] = true
	// how to init 
	for j := 1; j < n+1; j++ {
		// fmt.Println(p[j-1])
		if p[j-1] == '*' {
			// fmt.Println("j - 1 = ", j-1)
			dp[0][j] = dp[0][j-2]
		}
	}  
	// fmt.Println(dp)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				if j == 1 {
					// 即p以*号开头，按照题意不应出现这种情况，我们为了避免数组越界，增加这种判断
					dp[i][j] = false
				} else {
					if s[i-1] == p[j-2] || p[j-2] == '.' {
						dp[i][j] = dp[i-1][j] || dp[i][j-2]
					} else {
						dp[i][j] = dp[i][j-2]
					}
				}
			} else {
				if s[i-1] == p[j-1] || p[j-1] == '.' {
					dp[i][j] = dp[i-1][j-1]
				} else {
					dp[i][j] = false
				}
			}
			// fmt.Println("d[", i, "][", j, "] = ", dp[i][j])
		}
	}
	return dp[m][n]

}

因为这题耽误了不少时间，这周发的博客有点儿少，清明假期要赶一下了，o(╥﹏╥)o

发表于 更新于 分类于 本文字数： 790 阅读时长 ≈ 3 分钟
  1. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

1
2
3
4
5
6
>输入：x = 121
>输出：true

>输入：x = -121
>输出：false
>解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

进阶：你能不将整数转为字符串来解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最基本的算法：将数字转换为字符串 -> reverse -> 与原字符比较，相同则为true，不同则为false。其中最容易出错的点在于如何将整数转换为字符，即 int to string，单纯的显式转换string(x)并不会将x转换为字符串，而是将x当做ASCII编码转换为了对应字符。解法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import "strconv"

func isPalindrome(x int) bool {
	// 错误方式：该方法会将x认为是utf-8编码，得到莫名其妙的字符。
	// xStr := string(x)
    // 应使用此方法将整型转换为字符串
	xStr := strconv.Itoa(x)
	xBytes := []byte(xStr)
	length := len(xStr)
	reverseBytes := make([]byte, length)
	for index, _ := range xBytes {
		reverseBytes[length - index -1] = xBytes[index]
	}
	for index, v := range xBytes {
		if v != reverseBytes[index] {
			return false
		}
	}
	return true
}

第二种数学方法，将数字反转，与原数字比较。这种方法可能会导致数字越界溢出，因此可变形为依次比较数字的地位和高位，若均相同则返回true，否则返回false。实现逻辑与第三种类似。

第三种，也就是力扣官方给出的算法，取出尾部一半数字，反转，与剩余数字做比较，即

比如，1221，截取尾部21，反转为12，原数字去除尾部后变为12，12=12，则为回文数。

又比如，12321，截取尾部321，反转为123，原数字除去尾部为变为12，123 ！= 12，但是，123 / 10 = 12，所以原数字也是回文数。

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
func isPalindrome(x int) bool {
	// 负数
	if x < 0 {
		return false
	}

	// 个位数都是回文数
	if x/10 == 0 {
		return true
	}

	// 即个位数为0，最高位不可能为0，所以一定不是回文数
	if x%10 == 0 {
		return false
	}

	var tailReverse int = 0
	for ; x > tailReverse ; x = x/10 {
		// 下一个最低位数字
		nextNum := x%10
		tailReverse = tailReverse*10 + nextNum
	}

	if x == tailReverse || x == tailReverse/10 {
		return true
	} else {
		return false
	}
}

Go语言力扣刷题系列文章 ｜Go主题月

  1. Go语言力扣刷题-两数之和｜Go主题月
  2. Go语言力扣刷题-两数相加｜Go主题月
  3. Go语言力扣刷题-无重复字符的最长子串｜Go主题月
  4. Go语言力扣刷题-寻找两个正序数组的中位数｜Go主题月
  5. Go语言力扣刷题-最长回文子串｜Go主题月
  6. Go语言力扣刷题-Z字形变换｜Go主题月
  7. Go语言力扣刷题-整数反转｜Go主题月
  8. Go语言力扣刷题-字符串转换整数｜Go主题月

发表于 更新于 分类于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

发现掘金的一个小彩蛋：个人主页，鼠标放置在头像上，头像会转动，越转越快，调皮的程序员。

  1. 字符串转整数

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  • 读入字符串并丢弃无用的前导空格
  • 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  • 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  • 将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  • 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  • 返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

嗯，出个题连算法都给出来，就挺离谱~~另外，既然是解决文档，当然排除使用Go中的Atoi函数，即strconv包。

本题可以学到的Go知识包括：

  1. Go中如何将字符转换为对应的数字，即’2’如何转换为数字2：
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
package main
import (
    "bytes"
    "encoding/binary"
    "fmt"
)
func main()  {
	s := "0123"
	s_w1 := int(s[0]) // 直接显示转换
	fmt.Println(s_w1) // 48, 即'0'在ASCII中的10进制数字
	// 修正后我们采用如下方式可将字符'0'-'9'转换为对应的int数字
	s_w2 := int(s[0] - '0') 
	fmt.Println(s_w2)
    // 查找文档得出的方法：错误方法
	// fmt.Println(ByteToInt(s[0]))
}

/**
* 这个是我理解错误，这个是错误的，错误的!!!
*/
// func ByteToInt(bys byte) int {
// 	temp := make([]byte, 1)
// 	temp[0] = bys
//     bytebuff := bytes.NewBuffer(temp)
//     var data int64
//     binary.Read(bytebuff, binary.BigEndian, &data)
//     return int(data)
// }

为什么删除呢，因为我最初错误的理解为一个byte字节通过二进制操作可转换为int类型，并非如此。在我借鉴的程序中，ByteToInt的形参并非是一个byte，而是[]byte,即多个byte才能够转换为一个int才对，而’2’，ASCII码0011 0010转换为整数2，从本质上说，确实为’2’与’0’的差值。

代码中涉及到关于大小端模式：大端模式，数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中。而小端模式则是数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中。初学的我们不要纠结这些细节，暂时只需要记住“通常，golang中采用的是大端模式”

比如对于数据:0x12345678，从高字节到低字节为：12345678，从低字节到高字节为:78563412。
按照大端模式从低位buf[0]到高位buf[3]则应该为： 12， 34， 56， 78。
按照小端模式从低位buf[0]到高位buf[3]则应该为: 78，56，34，12。

go语言中大小端模式的个人理解

  1. Go中如何表示数字边界：在整数反转中我们详细介绍了Go中的整数类型，以及如何表示32位整数的数字边界。
1
2
3
4
5
const MAX_UINT32 = ^uint32(0)
const MIN_UINT32 = 0
// 最大无符号去掉符号位
const MAX_INT32 = int(MAX_UINT32 >> 1)
const MIN_INT32 = - MAX_INT32 - 1
  1. Go中如何使用正则表达式：关于正则表达式详细可参考Google关于正则表达式的RE2语法文档，以及维基百科正则表达式。Go常用的正则方法可参考掘金文章：Go正则表达式使用，示例代码如下
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
package main
import (
    "fmt"
    "regexp"
)
func main() {
    buf := "weialfidnd8930232jdjfkdjka09232"
    //解析正则表达式，如果成功返回解释器
    reg1 := regexp.MustCompile(`\d.\d`)
    if reg1 == nil {
        fmt.Println("regexp err")
        return
    }

    //提取，第二个参数表示只查找前n个匹配项，如果n<0， 则查找所有匹配内容
    result1 := reg1.FindAllStringSubmatch(buf, -1)
	// result1 := reg1.FindAllString(buf, -1)
	fmt.Println("result1 = ", result1)
	for _, v := range result1 {
		fmt.Println("find = ", v[0])
	}

	// 第二个参数返回的error，无错误时返回nil
	match, _ := regexp.MatchString("p([a-z]+)ch", "peach")
    fmt.Println(match)
}

个人认为，能够熟练使用正则表达式，网络API，处理集合与列表，是“精通一门语言”的前提，Java也应该包括熟练使用stream库。

查看力扣官网给出的有限状态自动机来解决，也容易理解，不多阐述。我们给出Go语言的正则表达式的解法，参考了力扣中的一个python解法：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import (
	"regexp"
	"strings"
)

const MAX_UINT32 = ^uint32(0)	
	const MIN_UINT32 = 0
	// 最大无符号去掉符号位
	const MAX_INT32 = int(MAX_UINT32 >> 1)
	const MIN_INT32 = - MAX_INT32 - 1


func stringToInt(s string) int  {

	i, num := 0, 0
	if s[0] == '-' || s[0] == '+' {
		i = 1
	}

	for ; i < len(s); i++ {
		popNum := int(s[i] - '0')
		if (num > MAX_INT32/10) || (num == MAX_INT32/10 && popNum > 7) || (num < MIN_INT32/10) || (num == MIN_INT32/10 && popNum < -8) {
			if s[0] == '-' {
				return MIN_INT32
			} else {
				return MAX_INT32
			}
		}
		num = num*10 + popNum
	}

	if s[0] == '-' {
		return -num
	} else {
		return num
	}
}


func myAtoi(s string) int {

	// 去除空格
	str := strings.TrimSpace(s)
	//  # 解释器：^表示子串开始，\d表示数字。表示子串以‘+’，‘-’或数字开头并跟后续至少一个数字
	reg1 := regexp.MustCompile(`^[\+\-]?\d+`)
	// 查找第一个匹配上的子串

	numArray := reg1.FindAllStringSubmatch(str, 1)
	if len(numArray) == 0 {
		return 0
	}
	num := stringToInt(numArray[0][0])
	// num = int(*num) #由于返回的是个列表，解包并且转换成整数
	return max(min(num,MAX_INT32), MIN_INT32)    //#返回值
	// return num
}

func min(num1, num2 int) int  {
	if num1 < num2 {
		return num1
	}
	return num2
}

func max(num1, num2 int) int  {
	if num1 < num2 {
		return num2
	}
	return num1
}

代码比想象中复杂o(╥﹏╥)o

Go语言力扣刷题系列文章 ｜Go主题月

  1. Go语言力扣刷题-两数之和｜Go主题月
  2. Go语言力扣刷题-两数相加｜Go主题月
  3. Go语言力扣刷题-无重复字符的最长子串｜Go主题月
  4. Go语言力扣刷题-寻找两个正序数组的中位数｜Go主题月
  5. Go语言力扣刷题-最长回文子串｜Go主题月
  6. Go语言力扣刷题-Z字形变换｜Go主题月
  7. Go语言力扣刷题-整数反转｜Go主题月

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 :
$$
[-2^{31}, 2^{31}-1]
$$
，就返回0.假设环境不允许存储 64 位整数（有符号或无符号）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

若用Go解决此问题，则我们需要知道：

  1. Go求余数的运算符”%“与除法运算符”/“的区别。

  2. Go中表示的整数的类型有哪些？范围如何？

    Go中有int8， int16，int32，int64，显然，本题我们使用int32。经测试int32在计算2^31时会溢出。

    那么我们常用的不指定bit数的int是多少位的呢？官方文档中，这是这样解释的：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    uint8       the set of all unsigned  8-bit integers (0 to 255)
    uint16      the set of all unsigned 16-bit integers (0 to 65535)
    uint32      the set of all unsigned 32-bit integers (0 to 4294967295)
    uint64      the set of all unsigned 64-bit integers (0 to 18446744073709551615)

    int8        the set of all signed  8-bit integers (-128 to 127)
    int16       the set of all signed 16-bit integers (-32768 to 32767)
    int32       the set of all signed 32-bit integers (-2147483648 to 2147483647)
    int64       the set of all signed 64-bit integers (-9223372036854775808 to 9223372036854775807)

    uint     either 32 or 64 bits
    int      same size as uint

    Explicit conversions are required when different numeric types are mixed in an expression or assignment. For instance, int32 and int are not the same type even though they may have the same size on a particular architecture.
    直译为：一个表达式或赋值中混合了不同数字类型时，需要显式类型转换。如int与int32尽管在某些特定的体系结构中具有相同的(占位)大小，它们也不是同一种类型，仍然需要显式类型转换。

  3. Go中的数学包是哪个？如何表示两个极端的数字-2^31 与 2^31-1 呢？

    Go中的数学包是math:

    import math

    math中表示x的y次方为：math.Pow(x, y)， 但是函数的定时为：func Pow(x, y float64) float64。即函数表示的是float64类型的运算。

    Go中并没有类似C语言的可以直接使用的INT_MAX，或者类似Java的Integer.MAX_INT的值，需要自己定义，这就又引出了Go中另一个知识：常量

  4. 常量const：

    const identifier [type] = value

    有过前端开发经验的应该对这个词不会陌生。常量，按照定义，也自然是不可修改的。

    基础测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main
import "fmt"
const MAX_UINT32 = ^uint32(0)
const MIN_UINT32 = 0
// 最大无符号去掉符号位
const MAX_INT32 = int32(MAX_UINT32 >> 1)
const MIN_INT32 = - MAX_INT32 - 1

func main() {
  var s int = 1024*1024*1024*2*2
  fmt.Println(s) // 输出为4294967296，未溢出
  var s32 int32 = 1024 // 2^10
  fmt.Println(s32*s32*s32*2) // 2^32, 输出为-2147483648，溢出
  fmt.Println(MAX_INT32) // 2147483647, 未溢出
  fmt.Println(MIN_INT32) // -2147483648，未溢出
}

回到题目，我们求解算法为：依次弹出最高位数字，相加求和。

1
2
3
4
... result ....
popNum = popNum % 10 // 弹出高位数字
x = x / 10 // 剩余数字
result = result * 10 + popNum

问题的关键在于如何判断溢出：即如何判断result*10 + popNum是否溢出：因为我们知道最大数字为2147483647，所以分为两种情况，当popNum大于7和popNum<=7。同理，最小数为-2147483648，分popNum<-8和popNum>=-8来考虑。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reverse(x int) int {
    const MAX_UINT32 = ^uint32(0)
	const MIN_UINT32 = 0
	// 最大无符号去掉符号位
	const MAX_INT32 = int(MAX_UINT32 >> 1)
	const MIN_INT32 = - MAX_INT32 - 1
	
	var result int = 0
	for ; x != 0; {
		popNum := x % 10
		x = x / 10
        // 一开始想类似java一样，希望格式化一些，每个||符号之前换行的，结果报错了。
		if (result > MAX_INT32/10) || (result == MAX_INT32/10 && popNum > 7) || (result < MIN_INT32/10) || (result == MIN_INT32/10 && popNum < -8) {
			return 0
		}
		result = result * 10 + popNum
	}
	return result
}

Go语言力扣刷题系列文章 ｜Go主题月

  1. Go语言力扣刷题-两数之和｜Go主题月
  2. Go语言力扣刷题-两数相加｜Go主题月
  3. Go语言力扣刷题-无重复字符的最长子串｜Go主题月
  4. Go语言力扣刷题-寻找两个正序数组的中位数｜Go主题月
  5. Go语言力扣刷题-最长回文子串｜Go主题月
  6. Go语言力扣刷题-Z字形变换｜Go主题月

发表于 更新于 分类于 本文字数： 828 阅读时长 ≈ 3 分钟

Z字形变换：

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题目搞了半天才搞懂Z变换是怎么回事，就是将一个字符串的字符，按照指定行依次按照下图方式进行排列，最终再按照行进行依次读取形成新的字符串：

↓↗↓↗↓…

本题设计到Go语言中知识包括：

  1. 字符串与字符的相互转换：
1
// s 为string时，s[i]类型为byte，可通过string(s[i])将其转换为字符
  1. List的使用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main
import (
    "container/list" // 需引入import "container/list"
    "fmt"
)
func main()  {
	myList := list.New()
    myList.PushBack(1) // 其他添加元素方法包括：PushBackList， PushFront， PushFrontList， InsertAfter， InsertBefore
    myList.PushBack("abc") // 同一个list可以放置不同类型的元素
    myList.PushBack(3)
    for e := myList.Front(); e != nil; e = e.Next() { // 遍历有Next(), Prev()
		fmt.Println(e.Value)
		println(e.Value) // 会打印出地址串，而非内容
	}	
}

// list移动元素的方法包括：MoveAfter，MoveBefore，MoveToBack，MoveToFront
// 访问元素：Front(), Back(), 注意访问元素值应为Front().Value, Back().Value
// 获取列表长度Len()
// 删除元素：Remove(e)
// 清空：Init

前面的题目把我给绕进去了，一直再总结归纳Z字形变换的数学规律，其实使用模拟方法更容易求解，也更好理解：即一步一步的模拟字符串的Z字形变换，然后依次输出各行字符。

原本因为不熟悉Go的字符串与字符转换，想学习一下Go的List类型，发现有点复杂，最终使用了[]string来实现，开森！

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
func convert(s string, numRows int) string {
	if numRows > len(s) || numRows == 1 {
		return s
	}
	// 初始化
	// result := make([]list.List, numRows)
	result := make([]string, numRows)
	down := true // 字符添加方向
	sIndex := 0
	// 模拟Z编号
	for i:= 0; sIndex < len(s); sIndex++ {
        /**
        * 每一次：
        * 1. 先将该字符放置进去
        * 2. 根据移动方向判断下一个字符放置的位置
        * 3. 根据位置判断下一步是否需要修改移动方向
        */
		// println("向第", i, "行添加", string(s[sIndex]), "字符")
		result[i] += string(s[sIndex])
		if down { // 向下添加时，每添加一个，行数+1
			// result[i+1] += string(s[sIndex])
			i++
		} else { // 非向下时，每添加一个，行数-1
			// result[i-1] += string(s[sIndex])
			i--
		}
		if i % (numRows - 1) == 0 { // 到达每行的下端顶点或上端顶点
			down =  !down // 变化添加方向
		}
	}

	// 输出
	ss := ""
	for i := 0; i < len(result); i++ {
		ss += result[i]
	}
	return string(ss)
}

Go语言力扣刷题系列文章 ｜Go主题月

  1. Go语言力扣刷题-两数之和｜Go主题月
  2. Go语言力扣刷题-两数相加｜Go主题月
  3. Go语言力扣刷题-无重复字符的最长子串｜Go主题月
  4. Go语言力扣刷题-寻找两个正序数组的中位数｜Go主题月
  5. Go语言力扣刷题-最长回文子串｜Go主题月

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

输入：s = “cbbd”
输出：”bb”

输入：s = “a”
输出：”a”

输入：s = “ac”
输出：”a”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本题解法涉及到Go语言数组，字符串的知识包括：

  1. Go中如何定义多维数组：
1
2
3
4
5
6
var s = [][]int{{1,2,3}, {4,5,6}}
var s1 = [2][3]int{{1,2,3}, {4,5,6}}
var s2 = [3][3]int{{1,2,3}, {4,5,6}}
println(len(s)) // 2
println(len(s1)) // 2
println(len(s2)) // 3
  1. Go中如何定义动态二维数组：
1
2
3
4
5
6
7
8
9
10
n, m := 2, 3
arr := make([][]int, n)
for i := 0; i < len(arr); i++ {
	arr[i] = make([]int, m)
}
for i := 0; i < len(arr); i++ {
	for j := 0; j < len(arr[i]); j++ {
		println(arr[i][j])
	}
}
  1. 新学到可以使用append给数组添加元素
1
2
3
4
5
6
7
8
刚学到Go中可以使用append给数组添加元素
var a []int
a = append(a, 1)
var arr [][]int
row1 := []int{1,2,3}
row2 := []int{4,5,6}
arr = append(arr, row1)
arr = append(arr, row2)
  1. Go中字符串与数组如何转换：
1
2
3
4
5
6
7
8
9
10
// 确认没有中文字符时，可以用byte
en := "124"
enArray := []byte(en)
// 有中文或特殊字符时，应用rune
ch := "你好abc"
chArray := []rune(ch)
chByteArray := []byte(ch)
println(len(enArray)) // 3
println(len(chArray)) // 5
println(len(chByteArray)) // 9, 一个中文字符占用3个字节

本文使用Go语言实现动态规划算法。

在检索资料的过程中，看到一句很有意思的动态规划理解方式：

Dynamic Programming is just a fancy way to say ‘remember stuff to save time later’

定义动态规划最优解的状态特征：is_palindrome[i] [j] 等于true或false， 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串。

动态规划状态转移方程/递推公式：从长度较短的字符串向长度较长的字符串进行转移

动态规划边界条件/初始化：当i=j时，is_palindrome[i] [j]= true， is_palindrome[i] [i + 1] = s[i] == s[i + 1]。

动态规划代码实现如下：

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
func longestPalindrome(s string) string {
	runeS := []rune(s)
	length := len(runeS)
	/**
	* dp := make([length][length]bool)
	* 编译报错：non-constant array bound length
	* Go中如何定义二维数组？
	*/
	dp := make([][]bool, len(runeS))
	for i := 0; i < len(runeS); i++ {
		dp[i] = make([]bool, len(runeS))
	}
	targetLeft := 0
	targetLength := 1


	for right := 0; right < length; right++ {
		// 代码错误注意事项：首次条件为left < right，导致无法执行left==right为true的情况
		for left := 0; left <= right; left++ {
			// println("left = ", left, ", runeS[left] = " + string(runeS[left]))
			// println("right = ", right, ", runeS[right] = " + string(runeS[right]))
			if left == right {
				// println("left === right")
				dp[left][right] = true
			} else if right -left == 1 {
				// println("right - left = 1")
				dp[left][right] = (runeS[left] == runeS[right])
			} else {
				// println("test...")
				dp[left][right] = dp[left+1][right-1] && runeS[left] == runeS[right]
			}

			if dp[left][right] && (right - left + 1) > targetLength {
				targetLength = right - left + 1
				targetLeft = left
				
				// println("s[left][right] = " + string(runeS[targetLeft:targetLeft+targetLength-1]))
			}
			
		}
	}

	return string(runeS[targetLeft:targetLeft+targetLength])
}

尴尬的是，第一次没有屏蔽掉println，竟然超时了，看来以后生产环境下还是尽量去掉print！！！

补充Manacher算法代码解析：搞了半天算法，还是代码更容易懂：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* Manacher
*/
func longestPalindrome(s string) string {
	start, end := 0, -1
	t := "#"
	for i := 0; i < len(s); i++ {
		t += string(s[i]) + "#"
	}
	t += "#"
	s = t
	println(s)
	// 存储各个位置的最大臂长
	arm_len := []int{}
	// right表示搜索到的最右边界
	right, j := -1, -1
	for i := 0; i < len(s); i++ {
		// 对于每一个i点
		var cur_arm_len int
		if right >= i { // i点在right点的左侧
			// i_sym为i相对于j的对称点
			i_sym := j*2-i
			// i点的最短臂长
			min_arm_len := min(arm_len[i_sym], right-i)
			// 从最短臂长向外搜索
			cur_arm_len = expand(s, i-min_arm_len, 	i+min_arm_len)
		} else { // i点在right点右侧，一无所知
			cur_arm_len = expand(s, i, i)
		}
		// 记录i点最大臂长
		arm_len = append(arm_len, cur_arm_len)
		if i + cur_arm_len > right {
            // 更新中心j的位置
            j = i
			// 更新right的位置
			right = i +  cur_arm_len
		}
		if cur_arm_len*2+1 > end - start {
			// 最大臂长更新
			start = i - cur_arm_len
			end = i + cur_arm_len
		}
	}
	ans := ""
	for i := start; i <= end; i++ {
		if s[i] != '#' {
			ans += string(s[i])
		}
	}
	return ans
}

func expand(s string, left, right int) int {
	for ;left>=0&&right<len(s)&&s[left]==s[right]; left, right = left-1, right + 1{}
	// 要求的是臂长，所以要除2
	return (right - left -2) / 2
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

Go语言力扣刷题系列文章 ｜Go主题月

  1. Go语言力扣刷题-两数之和｜Go主题月

  2. Go语言力扣刷题-两数相加｜Go主题月

  3. Go语言力扣刷题-无重复字符的最长子串｜Go主题月

  4. Go语言力扣刷题-寻找两个正序数组的中位数｜Go主题月