Joyce' Blog
0%

minimum-path-sum & valid-number

发表于

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

题解

感觉，和62, 63题的思路没有区别。可不可以把二维数组缩减为一位数组呢？没想出来……下面这样其实也还不错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minPathSum(vector<vector<int>>& grid) {
	int m = grid.size();//行
	int n = grid[0].size();//列
	int **a = new int*[m];
	for (int i = 0; i < m; i++)
		a[i] = new int[n];
	a[m - 1][n - 1] = grid[m - 1][n - 1];
	for (int i = m - 2; i >= 0; i--)
		a[i][n - 1] = a[i + 1][n - 1] + grid[i][n - 1];
	for (int i = n - 2; i >= 0; i--)
		a[m - 1][i] = a[m - 1][i + 1] + grid[m - 1][i];
	for (int i = m - 2; i >= 0; i--)
	{
		for (int j = n - 2; j >= 0; j--)
		{
			a[i][j] = grid[i][j] + min(a[i + 1][j], a[i][j + 1]);
		}
	}
	return a[0][0];
}

题目描述

验证给定的字符串是否可以解释为十进制数字。

说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：

  • 数字 0-9

  • 指数 - “e”

  • 正/负号 - “+”/“-“
  • 小数点 - “.”

当然，在输入中，这些字符的上下文也很重要

题解

有种自动机的味道。

剩下的就是各种面向特殊样例编程的过程了。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
int start = 0;
bool get_exp(string s, int & i, int len)
{
	i++;
	if (i == len)return false;
	if (s[i] == '-' || s[i] == '+')
	{
		i++;
		if (s[i] >= '0'&&s[i] <= '9')
		{
			while (i < len&&s[i] >= '0'&&s[i] <= '9')
			{
				i++;
			}
			if (i == len)return true;
		}
	}
	else if (i < len&&s[i] >= '0'&&s[i] <= '9')
	{
		while (i < len&&s[i] >= '0'&&s[i] <= '9')
		{
			i++;
		}
		if (i == len)return true;
	}
	return false;
}
bool get_frac(string s, int & i, int len)
{
	i++;
	if (i == len && i - 1 == start)return false;
	while (i<len&&s[i] >= '0'&&s[i] <= '9')
	{
		i++;
	}
	if (i == len)return true;
	else if (s[i] == 'e')
	{
		if (i - 1 == start)
			return false;
		else
			return get_exp(s, i, len);
	}
	return false;
}
bool isNumber(string s) {
	int len = s.length();
	if (!len)return false;
	int i = 0;
	while (s[i] == ' ') { i++; }
	start = i;
	while (s[len - 1] == ' ')len--;
	if (i < len)
	{
		if (s[i] == '-' || s[i] == '+')
		{
			i++;
			if (i == len)return false;
			if (s[i] >= '0'&&s[i] <= '9')
			{
				while (i < len&&s[i] >= '0'&&s[i] <= '9')
				{
					i++;
				}
				if (i == len)return true;
				else if (s[i] == '.')
				{
					return get_frac(s, i, len);
				}
				else if (s[i] == 'e')
				{
					return get_exp(s, i, len);
				}
			}
			else if (s[i] == '.')
			{
				return get_frac(s, i, len);
			}
		}
		else if (s[i] >= '0'&&s[i] <= '9')
		{
			while (i < len&&s[i] >= '0'&&s[i] <= '9')
			{
				i++;
			}
			if (i == len)return true;
			else if (s[i] == '.')
			{
				return get_frac(s, i, len);
			}
			else if (s[i] == 'e')
			{
				return get_exp(s, i, len);
			}
		}
		else if (s[i] == '.')
		{
			return get_frac(s, i, len);
		}
	}
	return false;
}