Leetcode 6-10
6. Z 字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串 为”LEETCODEISHIRING” 行数为 3 时，排列如下（忽略下划线）：
L _ C _ I _ R
E T O E S I I G
E _ D _ H _ N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。请你实现这个将字符串进行指定行数变换的函数。
解: 这是一个有规律的图形阵，没什么可说的，直接套规律公式，避免一切花里胡哨
-
code
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
30func convert(s string, numRows int) string {
if numRows == 1{
return s
}
rs := []rune(s)
l := len(rs)
ret := []rune{}
for i := 0; i < numRows; i++ {
j := 0
for {
ind := (2*numRows-2)*j + i
if ind < l {
ret = append(ret, rs[ind])
} else {
break
}
if i != 0 && i != numRows-1 {
ind2 := (2*numRows-2)*(j+1) - i
if ind2 < l {
ret = append(ret, rs[ind2])
} else {
break
}
}
j++
}
}
return string(ret)
}
7. 整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21func reverse(x int) int {
if x < 0 {
return -(reverse(-x))
}
var y int32 = int32(x)
bl := []int32{}
for y > 0 {
bl = append(bl, y%10)
y = y / 10
}
var ret int32
for i := 0; i < len(bl); i++ {
if ret > (math.MaxInt32-bl[i])/10 {
return 0
}
ret = 10*ret + bl[i]
}
return int(ret)
}
8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
-
code
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
48func myAtoi(str string) int {
var max = math.MaxInt32
bas := 1 // 乘子
nbs := make([]int,0)
start:=false
for i:=range str{
b:=str[i]
if !start{
if b==' '{
continue
}
if b == '-'{
bas = -1
start = true
continue
} else if b=='+'{
start = true
continue
} else if '0'<=b && b<='9'{
start = true
}else{
return 0
}
}
if '0'<=b && b<='9'{
nbs=append(nbs,int(b-'0'))
}else{
break
}
}
if bas == -1{
max += 1
}
ret:=0
for i:=0;i<len(nbs);i++{
if ret>max/10 || (ret==max/10 && nbs[i]>max%10){
ret = max
break
}
ret = ret*10 + nbs[i]
}
return bas * ret
}
9. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
解: TIP:反转一半就可以了
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20func isPalindrome(x int) bool {
if x<0{
return false
}
if x==0{
return true
}
var bl []int
for x>0{
bl = append(bl, x%10)
x = x/10
}
l:=len(bl)/2
for i:=0;i<l;i++{
if bl[i]!=bl[len(bl)-i-1]{
return false
}
}
return true
}
10. 正则表达式匹配
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
解: 递归，很明显的
-
code
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
33func isMatch(s string, p string) bool {
lp := len(p)
ls := len(s)
if ls == 0 && lp == 0{
return true
}
if ls !=0 && lp == 0 {
return false
}
if ls == 0 && lp!=0 {
if p[lp-1] == '*'{
if lp == 1{
return true
}
return isMatch(s, p[:lp-2])
}
return false
}
if p[lp-1] == '.' || p[lp-1] == s[ls-1]{
return isMatch(s[:ls-1], p[:lp-1])
}
if p[lp-1] == '*'{
if isMatch(s, p[:lp-2]){
return true
}
if (s[ls-1] == p[lp-2] || p[lp-2] == '.') {
return isMatch(s[:ls-1], p);
}
return false;
}
return false
}