V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
qiShaMingZi
V2EX  ›  Python

一道笔试题: 输入一串数字,求对应英文字母出现的可能性 z = {'a':1, 'b':2, .... , 'z':26}, 输入: 123,输出: abc, lc, aw(l: 12, w: 23)

  •  
  •   qiShaMingZi · 2019-11-12 01:22:10 +08:00 · 4461 次点击
    这是一个创建于 1839 天前的主题,其中的信息可能已经有所发展或是发生改变。
    17 条回复    2019-11-12 12:56:06 +08:00
    xiaoming1992
        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
    xiaoming1992
        2
    xiaoming1992  
       2019-11-12 01:42:21 +08:00 via Android   ❤️ 1
    艹了,我的空格缩进都给我吃掉了。。。
    lihongming
        3
    lihongming  
       2019-11-12 02:05:27 +08:00 via iPhone
    第一反应是迭代。
    每次截取 1-2 位数字( 2 位数字需要<=26 ),然后把剩下的数字迭代给自己。

    时间、空间复杂度都是 O(N),准确来说是 2N,可能效率不是最高,但很容易想
    geelaw
        4
    geelaw  
       2019-11-12 02:34:17 +08:00 via iPhone
    @lihongming #3 这个问题的输出长度可以达到 Omega(1.6^n),因此不可能时间是 O(n)。

    此外这个输出长度也表示空间至少需要 Omega(n),因此朴素的算法已经是最佳。
    Mirage09
        5
    Mirage09  
       2019-11-12 02:35:29 +08:00 via iPhone
    lihongming
        6
    lihongming  
       2019-11-12 02:38:23 +08:00
    @Mirage09 哈哈哈,第一次见这么多负分的题,竟然还有公司拿来笔试?
    lihongming
        7
    lihongming  
       2019-11-12 02:53:26 +08:00
    @geelaw 是的,我想简单了,迭代的时间复杂度应该是 O(N^2)
    Mirage09
        8
    Mirage09  
       2019-11-12 03:53:26 +08:00   ❤️ 1
    mskf
        9
    mskf  
       2019-11-12 03:53:30 +08:00
    刚试了下,反向 dp 应该是最简单的。。。不是很理解为啥这题这么多踩啊,是不是以前的测试数据有问题
    xiadong1994
        10
    xiadong1994  
       2019-11-12 05:39:12 +08:00 via iPhone
    最基本的 dp
    caixiangyu17
        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])
    细节就不说了,会动态规划不难
    siriussilen
        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%的用户


    记忆化搜索比较好理解,此外我的思考难免存在不足,欢迎批评指教
    knva
        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 则特殊处理
    petelin
        14
    petelin  
       2019-11-12 11:37:56 +08:00 via iPhone
    这难道不是回溯吗
    zpfhbyx
        15
    zpfhbyx  
       2019-11-12 11:56:01 +08:00
    - -,这么多高大上,只有我是 kv 交换,然后输出 123 的排列组合中单个小于 26 的组合么..
    petelin
        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)
    }
    }
    }```

    这个叫不叫回溯? 有没有学院派大佬
    petelin
        17
    petelin  
       2019-11-12 12:56:06 +08:00
    我理解这个应该是搜索. 或者就是递归
    然后如果用动态规划写, 这题就是一个 fib 的变种. fib(3) = fib(2) + fib(1) fib(1)不一定能加起来, 因为前两个数不一定在[1,26]
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1661 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:36 · PVG 00:36 · LAX 08:36 · JFK 11:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.