LeetCode 001 ～ 100 刷题

1 ～ 6：

TODO

题目大意：给定一个32位有符号数字，将数字为进行反转。例如321反转后123，-123反转后-321。若反转后数字超出32位数字所能表示范围则返回0。

解题思路：暂无，C++、Java用户注意int溢出情况。

func reverse(x int) int {
	res := 0
	for x != 0 {
		res, x = res * 10 + x % 10, x / 10
	}
	
	if res > 2147483647 || res < -2147483648 {
		return 0
	}
	
	return int(res)
}

题目大意：给定一个字符串，将开头的数字取出，可以忽略最左侧的空格。

解题思路：直接遍历字符串s，使用state标记前一个字符的类型。

func myAtoi(s string) int {
	res := 0
	base := 10
    
	state := 1

	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			if state != 1 { // 遇到空格但是前一个不是空格，直接结束
				return res
			}
		} else if s[i] == '-' { // 遇到负号，前一个需要是空格，且设置state = 2
			if state == 1 {
				state = 2
				base = -10
			} else {
				return res
			}
		} else if s[i] == '+' { // 同遇到负号
			if state == 1 {
				state = 2
			} else {
				return res
			}
		} else if s[i] >= '0' && s[i] <= '9' { // 遇到数字，置state = 3
			state = 3
			res = res * 10 + (int(s[i]) - '0') * base / 10
			if res > 2147483647 {
				return 2147483647
			}
			if res < -2147483648 {
				return -2147483648
			}
		} else { // 其他情况，直接返回
			return res
		}
	}

	return res
}

题目大意：给定一个整数，判断该数字是否为回文数字（即正读和反渎一样）。

解题思路：可以参考题目七的思路，负数直接返回false，正数进行反转，判断反转后的数字是否和原数字相等。

func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}

	y, z := 0, x
	for z != 0 {
		y, z = y * 10 + z % 10, z / 10
	}
	return x == y
}

10、字符串匹配

题目大意：给定两个字符串s、p，s只包含小写字母，p包含小写字母、'.'、'*'三种字符，其中'.'可以匹配任意一个小写字母，'*'可以匹配前面的一个字符0次或者多次，计算s和p是否可以完全匹配。

解题思路：经典的动态规划算法，借用辅助的动态规划数组dp[len(s) + 1][len(p) + 1]，dp[i][j]表示s[0: i]和p[0: j]是否可以完全匹配。在dp数组中多申请一行和一列方便计算s和p为空的情况，因此在计算到dp[i][j]时计算的是s[i - 1]和p[j - 1]。s[i - 1]和p[j - 1]可以匹配，即s[i - 1] = p[j - 1]或者p[j - 1] = ‘.’，dp[i][j]的值由dp[i - 1][j - 1]获得；在p[j - 1] = '*'的情况下，需要讨论s[i - 1]和p[j - 2]的关系，当s[i - 1] = p[j - 2] 或者 p[j - 2] = '.'时可以使用*进行一次匹配，dp[i][j] = dp[i - 1][j]，否则dp[i][j] = dp[i][j - 2];其他情况时dp[i][j] = false。递归方程如下所示（为添加为true的情况）：

func isMatch(s string, p string) bool {
    // 这里构造动态规划数组
    dp := make([][]bool, 0)
	for i := 0; i < len(s) + 1; i++ {
		dp = append(dp, make([]bool, len(p) + 1))
	}
    
    // 初始化，s、p长度为0的情况为true
	dp[0][0] = true
    // 这里初始化s为空，p跳跃出现‘*’的情况。类似s = ‘’， p = ‘a*b*c*’的情况。
    for i := 2; i < len(p) + 1; i++ {
        if p[i - 1] == '*' {
            dp[0][i] = dp[0][i - 2]
        }
    }
	
    // 动态规划
	for i := 1; i < len(s) + 1; i++ {
		for j := 1; j < len(p) + 1; j++ {
            // s[i - 1]和p[j - 1]可以匹配
			if p[j - 1] == '.' || p[j - 1] == s[i - 1] {
				dp[i][j] = dp[i - 1][j - 1]
			} else if p[j - 1] == '*' { // p[j - 1]出现‘*’的情况
                // 这里默认s[i - 1]和p[j - 2]不可以匹配
				dp[i][j] = dp[i][j - 2]
                // s[i - 1]和p[j - 2]可以匹配
				if p[j - 2] == '.' || p[j - 2] == s[i - 1] {
					dp[i][j] = dp[i][j] || dp[i - 1][j]
				}
			}
		}
	}
	
	return dp[len(s)][len(p)]
}