V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
wwsww
V2EX  ›  问与答

一道算法题,有什么好的思路吗?

  •  
  •   wwsww · 2017-06-02 09:21:54 +08:00 · 2207 次点击
    这是一个创建于 1901 天前的主题,其中的信息可能已经有所发展或是发生改变。

    写一个递归函数,输入一个数组,比如数组是['a','b','c'],那么输出

    <a>
     <b>
      <c>
      </c>
     </b>
    </a>
    

    能用 ruby 写更好。

    第 1 条附言  ·  2017-06-02 10:13:26 +08:00
    也是最近才开始有空尝试花个 1-2 小时刷刷题....算法能力较弱。好吧,就是道“题”,配不上“算法”二字行了吧....无论如何还是谢谢各位回复
    15 条回复    2017-06-02 21:54:21 +08:00
    bbx
        1
    bbx  
       2017-06-02 09:24:55 +08:00
    递归
    whatot
        2
    whatot  
       2017-06-02 09:25:30 +08:00
    入栈出栈,不麻烦吧。递归的话,函数式编程的惯用手法,head:tail。
    whatot
        3
    whatot  
       2017-06-02 09:30:01 +08:00
    参考 haskell 里面的快排
    https://learnxinyminutes.com/docs/haskell/

    qsort [] = []
    qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
    where lesser = filter (< p) xs
    greater = filter (>= p) xs
    kindjeff
        4
    kindjeff  
       2017-06-02 09:34:47 +08:00
    用栈就可以
    coderluan
        5
    coderluan  
       2017-06-02 09:36:00 +08:00
    没感觉这是“算法题”,有什么特殊的吗?
    linxy
        6
    linxy  
       2017-06-02 09:39:21 +08:00
    怎么有种自己的作业自己做的感觉
    wwsww
        7
    wwsww  
    OP
       2017-06-02 09:40:57 +08:00
    @coderluan need a recursive function,直接写两三行就搞定了,但明确要求用递归,一下没思路了就。。。
    proudzhu
        8
    proudzhu  
       2017-06-02 09:58:27 +08:00 via iPhone
    递归找最外层的 <char></char> 就行了吧
    AlphaTr
        9
    AlphaTr  
       2017-06-02 10:00:40 +08:00
    JS 的写法:

    ```javascript
    var html = function (list) {
    var indent = lines => lines.split('\n').map(item => ' ' + item).join('\n');
    return list.length > 1 ? `<${list[0]}>\n${indent(html(list.slice(1)))}\n</${list[0]}>` : `<${list[0]}>\n</${list[0]}>`
    }
    ```
    geelaw
        10
    geelaw  
       2017-06-02 10:04:49 +08:00
    要把一个非递归函数写成递归,那是很容易的,举个例子:

    ```C++
    template <typename TIt>
    std::string const theAlgo(TIt &&begin, TIt &&end)
    {
    std::string result;
    std::string helper1{"<"},helper2{">"},helper3{"</"};
    for (; begin != end; ++begin) result = helper1 + *begin + helper2 + result + helper3 + *begin + helper2;
    return std::move(result);
    }
    ```

    上面是非递归,下面是递归:

    ```C++
    template <typename TIt>
    std::string const theAlgo(TIt &&begin, TIt &&end, bool shouldWork = true)
    {
    if (!shouldWork) return "";
    theAlgo(std::forward(begin), std::forward(end), false);
    std::string result;
    std::string helper1{"<"},helper2{">"},helper3{"</"};
    for (; begin != end; ++begin) result = helper1 + *begin + helper2 + result + helper3 + *begin + helper2;
    return std::move(result);
    }
    ```

    只要制造一个没用的调用即可。

    当然,题目不是这个意思,实际上我可以写(伪代码):

    ```自然语言
    TheAlgo(array, pos = 0)
    ____if (pos == array.length) return "";
    ____return "<" + array[pos] + ">" + TheAlgo(array, pos + 1) + "</" + array[pos] + ">";
    ```

    就是把循环变成递归,很无聊。
    seeker
        11
    seeker  
       2017-06-02 10:09:40 +08:00
    这也叫算法题了?是不是过一段时间 hello world 也叫算法题了哦。
    besto
        12
    besto  
       2017-06-02 10:12:20 +08:00
    C 语言带函数头尾也只需要 5 行搞定。
    void fun(char **list, int index, int end) {
    printf("%*s<%s>\n", index, "", list[index]);
    if (index < end - 1) fun(list, index + 1, end);
    printf("%*s</%s>\n", index, "", list[index]);
    }
    wwsww
        13
    wwsww  
    OP
       2017-06-02 10:13:50 +08:00
    @geelaw 明白思路了!谢谢啊!
    loadinger
        14
    loadinger  
       2017-06-02 16:15:20 +08:00
    var arr = ['a', 'b', 'c', 'd'];
    arr.reverse().reduce(function(a, b, c){
    return Array(arr.length - c).join('-') + '<' + b + '>\n' + a + Array(arr.length - c).join('-') + '</' + b + '>\n';
    }, '');

    这样可以撒?
    natat
        15
    natat  
       2017-06-02 21:54:21 +08:00
    chars = ['a', 'b', 'c']

    def chars_print(chars, spaces):
    if len(chars) > 0:
    print(spaces + '<' + chars[0] + '>')
    chars_print(chars[1:], spaces + ' ')
    print(spaces + '</' + chars[0] + '>')

    chars_print(chars, '')

    python 的解法,为啥上面的代码都那么的乱,是排版的锅?
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1176 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:39 · PVG 05:39 · LAX 14:39 · JFK 17:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.