1
xiaoming1992 2019-11-12 01:41:50 +08:00 via Android
func
const result = [] const availTuples = [...] availTuples.foreach const (a, b) = tuple result.push(map(a), func(b)) return result |
2
xiaoming1992 2019-11-12 01:42:21 +08:00 via Android 1
艹了,我的空格缩进都给我吃掉了。。。
|
3
lihongming 2019-11-12 02:05:27 +08:00 via iPhone
第一反应是迭代。
每次截取 1-2 位数字( 2 位数字需要<=26 ),然后把剩下的数字迭代给自己。 时间、空间复杂度都是 O(N),准确来说是 2N,可能效率不是最高,但很容易想 |
4
geelaw 2019-11-12 02:34:17 +08:00 via iPhone
|
5
Mirage09 2019-11-12 02:35:29 +08:00 via iPhone
|
6
lihongming 2019-11-12 02:38:23 +08:00
@Mirage09 哈哈哈,第一次见这么多负分的题,竟然还有公司拿来笔试?
|
7
lihongming 2019-11-12 02:53:26 +08:00
@geelaw 是的,我想简单了,迭代的时间复杂度应该是 O(N^2)
|
8
Mirage09 2019-11-12 03:53:26 +08:00 1
|
9
mskf 2019-11-12 03:53:30 +08:00
刚试了下,反向 dp 应该是最简单的。。。不是很理解为啥这题这么多踩啊,是不是以前的测试数据有问题
|
10
xiadong1994 2019-11-12 05:39:12 +08:00 via iPhone
最基本的 dp
|
11
caixiangyu17 2019-11-12 07:30:34 +08:00
动态规划,根据第一位数值,分解成两个子问题
char(a[0])+f(a[1...n]) char(a[0]*10+a[1]) + f(a[2...n]) 细节就不说了,会动态规划不难 |
12
siriussilen 2019-11-12 09:04:47 +08:00 3
这道题,可以从记忆化递归的角度来理解,比如对于一个字符串 F("2213")=5, 可以分解为 F("213")和 F("13")两个子问题,在 F("213")这个子问题中又可以分为 F("13")和 F("3")两个子子问题,F("13")这个子子问题和 F("13")子问题是重复的,因而可以考虑使用记忆化搜索或动态规划来解决这个问题。
特别地,如果一个数中的一个前缀和两个前缀都是合法的,那么这个值等于斐波那契数列+1(此时解空间实际上就等价于斐波那契数列的状态转移方式),例如,f("12121212")=Fibonacci number(8+1) = 34 ```cpp class Solution { public: int numDecodings(string s) { if(s.length() == 0) return 0; unordered_map<string, int> ways; ways[""] = 1; function<int(const string &s)> dfs = [&](const string& s){ if(ways.count(s)) return ways[s]; if(s[0] == '0') return 0; // 第一位是 0,这是非法的返回 0 if(s.length() == 1) return 1; // e.g. 1-9,返回一种方式 int w = dfs(s.substr(1)); // 把第一位去掉,子问题 1 int prefix = stoi(s.substr(0,2)); // 取前两位,子问题 2 if(prefix <= 26) w += dfs(s.substr(2)); // 检查是否合法 ways[s] = w; return w; }; return dfs(s); } }; ``` 执行用时 :8 ms, 在所有 cpp 提交中击败了 37.55%的用户 内存消耗 :16.5 MB, 在所有 cpp 提交中击败了 5.18%的用户 记忆化搜索比较好理解,此外我的思考难免存在不足,欢迎批评指教 |
13
knva 2019-11-12 09:57:32 +08:00
首先分割这些字符
0 位为 0 直接返回 0 ; 若 s[i-1]==1 则 +1 若 s[i-1]==2 并且 s[i]<=6 +1 字符串中有 0 则特殊处理 |
14
petelin 2019-11-12 11:37:56 +08:00 via iPhone
这难道不是回溯吗
|
15
zpfhbyx 2019-11-12 11:56:01 +08:00
- -,这么多高大上,只有我是 kv 交换,然后输出 123 的排列组合中单个小于 26 的组合么..
|
16
petelin 2019-11-12 12:54:03 +08:00
```
func numDecodings(s string) (ans int) { backtrace(s, &ans) return } func backtrace(s string, ans *int){ if len(s) == 0{ *ans++ return } if '1' <= s[0] && s[0] <= '9'{ backtrace(s[1:], ans) } if len(s) > 1{ if (s[0] == '1') || (s[0] == '2' && '0' <= s[1] && s[1] <= '6') { backtrace(s[2:], ans) } } }``` 这个叫不叫回溯? 有没有学院派大佬 |
17
petelin 2019-11-12 12:56:06 +08:00
我理解这个应该是搜索. 或者就是递归
然后如果用动态规划写, 这题就是一个 fib 的变种. fib(3) = fib(2) + fib(1) fib(1)不一定能加起来, 因为前两个数不一定在[1,26] |