Jadual Kandungan
回复内容:
Rumah pembangunan bahagian belakang tutorial php 日本雅虎程序员跳槽程序测试问题

日本雅虎程序员跳槽程序测试问题

Jun 06, 2016 pm 08:34 PM
c java php ruby pengaturcara

一救援机器人有三种跳跃模式,可分别跳跃1m,2m,3m的距离,请用程序实现该机器人行进n米路程时可用的跳跃方式。
程序语言不限,当距离n值足够大时,程序执行时间尽量小。

例:当距离为4米时,输出结果有7种:

<code>1m,1m,1m,1m
1m,1m,2m
1m,2m,1m
1m,3m
2m,1m,1m
2m,2m
3m,1m
</code>
Salin selepas log masuk
Salin selepas log masuk

回复内容:

一救援机器人有三种跳跃模式,可分别跳跃1m,2m,3m的距离,请用程序实现该机器人行进n米路程时可用的跳跃方式。
程序语言不限,当距离n值足够大时,程序执行时间尽量小。

例:当距离为4米时,输出结果有7种:

<code>1m,1m,1m,1m
1m,1m,2m
1m,2m,1m
1m,3m
2m,1m,1m
2m,2m
3m,1m
</code>
Salin selepas log masuk
Salin selepas log masuk

谢谢邀请。

出这道题,明显是为了考察你 DP。我也不多说,直接放码过来了:

<code>cpp</code><code>void step(int n, std::string str) {
    if (n == 0) { std::cout = 1) step(n-1, str+"1m,");
    if (n >= 2) step(n-2, str+"2m,");
    if (n >= 3) step(n-3, str+"3m,");
}
</code>
Salin selepas log masuk

n == 4 的时候,调用:step(4, ""); 原样输出你想要的。


这里只是用最短的代码表述我的思路,怕爆栈的,自行修改。

It is quite similar to my Facebook interview question: a game has 3 levels of scores: 1 point, 2 points, 5 points. please print all the ways you can get 10 points.

日本雅虎程序员跳槽程序测试问题

简单想了一下,这道题目优化思路和斐波那契数列的优化思路相同:记录f(n)。

根据题目可知f(n)=f(n-1)+f(1)=f(n-2)+f(2)=f(n-3)+f(3)=f(1)+f(n-1)=..
手机码字后面两个等式就不写了。
f(n)的可能也就这6种(当然肯定包含重复)

那么一点点推导f(4)因为f123已知,f4可以在O(1)内得到,记录。
f5,此时f1234已知,f5也能在O(1)得到,记录。
那么f(n),根据上述的公式,可以在O(n)内得到。

这是大致思路,接下来解决重复问题就行了。

根据 @AUV_503516 的思路, 写以下代码, 存储结构和空间还可以优化

<code>#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# @file     robot_steps_calculator.py 
# @author   kaka_ace
# @date     Mar 27 2015
# @breif     
#

import copy

class RobotBrain(object):
    CACHE_INIT = {
        1: [['1']],
        2: [['1', '1'], ['2']],
        3: [['1', '1' ,'1'], ['1', '2'], ['2', '1'], ['3']],
    }

    CACHE_KEY_MAP_INIT = dict() # 缓存如 '11', '21' etc. 去重作用
    for k, v in CACHE_INIT.items():
        for l in v:
            s = "".join(l)
            CACHE_KEY_MAP_INIT[s] = True

    def __init__(self):
        self.cache = copy.deepcopy(self.CACHE_INIT)
        self.cache_key_map = copy.deepcopy(self.CACHE_KEY_MAP_INIT)

    def output_solution(self, n: "total length, positive number") -> None:
        if n  None:
        for sl in self.cache[i-delta]:
            s = ''.join(sl)
            delta_str = str(delta)
            if reverse is True:
                # delta + f(i - delta)
                new_key = delta_str + s
            else:
                # f(i - delta) + delta
                new_key = s + delta_str

            if new_key not in self.cache_key_map:
                self.cache_key_map[new_key] = True
                self.cache[i].append([delta_str] + sl)

    @staticmethod
    def _ouput_result(cache_list) -> None:
        for cache_result in cache_list:
            print(",".join([i+"m" for i in cache_result]))


if __name__ == "__main__":
    r = RobotBrain()
    r.output_solution(5)

</code>
Salin selepas log masuk

用C写了一段:

<code>unsigned int count(unsigned int n)
{
    switch(n) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 2;
        case 3: return 4;
        default: return (count(n - 1) + count(n - 2) + count(n - 3));
    }
    return 0;
}
</code>
Salin selepas log masuk

运行结果:

<code>n = 0; t = 0
n = 1; t = 1
n = 2; t = 2
n = 3; t = 4
n = 4; t = 7
n = 5; t = 13
n = 6; t = 24
n = 7; t = 44
n = 8; t = 81
n = 9; t = 149
...
</code>
Salin selepas log masuk

好吧,原来是要详细列出每种方法的方案,我没认真看…… =_,=b

直接采用递归的话会有很多重复的计算,比如在n=7的时候,会有1+1+1+steps(4),1+2+steps(4),3+steps(4),所以step(4)会被重复计算多次。因此在需要做记忆之前的结果

<code>int steps[LENGTH] = {0, 1, 2, 4};
int n, i;
for ( i = 4; i </code>
Salin selepas log masuk

写个For循环算了,

这也就OI初中组的水平......典型的动态规划一点儿弯儿都没绕

这也就是考递归的问题.

如果是要求一共有多少种方法,就可以简单用一位数组做动态规划。如果要求输出所有解,就老老实实的求吧。代码用递归写的。

<code>JAVA</code><code>    /**
     * return number of all distinct paths for a given distance..
     * O(n) time and O(n) space using dp.
     */
    public int allPath(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1; // useless
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i > allPaths(int n) {
        List<list>> res = new ArrayList<list>>();
        helper(n, 0, new ArrayList<integer>(), res);
        return res;
    }
    private void helper(int n, int cur, List<integer> list, List<list>> res) {
        if (cur > n) {
            return;
        }
        if (cur == n) {
            res.add(list);
            return;
        }
        for (int i = 1; i  newList = new ArrayList<integer>(list);
            newList.add(i);
            helper(n, cur + i, newList, res);
        }
    }
</integer></list></integer></integer></list></list></code>
Salin selepas log masuk

分别n/3,n/2,看余数是多少。如果被3整除就是3333...; n/3有余数y2,y2/2没有余数,就是33333...2; n/3有余数y2,y2/2也有余数,最终的余数就用1来跳,3333...1。上面是n很大的情况。如果n小于等于3,一步就够。

f(n)=1,n=1
f(n)=2,n=2
f(n)=4,n=3
f(n)=f(n-1)+f(n-2)+f(n-3),n>3

<code>int fuck(int length)
{
    if(length </code>
Salin selepas log masuk

指数的时间复杂度,因为产生了重复计算,按照斐波那契数列的方法,改成迭代或者在递归函数里多传点参数,时间复杂度能变成线性的。

艹,看错题目了,将错就错

<code>void p(const list<int> &state)
{
    for(auto it=state.begin();it!=state.end();it++)
        if(it != --state.end())
            cout append(list<int> m,int k)
{
    m.push_back(k);
    return m;
}

int cfuck(int length,list<int> state)
{
    if(length </int></int></int></code>
Salin selepas log masuk

哎,C++知识全忘光了(反正我也进不了雅虎)。不过这道题目无论怎么样时间复杂度都是指数级的,所以就无所谓在最短的时间内了

大神你们都超屌的

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

Bagaimana anda menghuraikan dan memproses HTML/XML dalam PHP? Bagaimana anda menghuraikan dan memproses HTML/XML dalam PHP? Feb 07, 2025 am 11:57 AM

Tutorial ini menunjukkan cara memproses dokumen XML dengan cekap menggunakan PHP. XML (bahasa markup extensible) adalah bahasa markup berasaskan teks yang serba boleh yang direka untuk pembacaan manusia dan parsing mesin. Ia biasanya digunakan untuk penyimpanan data

Cuti atau kembali dari Java 8 Stream Foreach? Cuti atau kembali dari Java 8 Stream Foreach? Feb 07, 2025 pm 12:09 PM

Java 8 memperkenalkan API Stream, menyediakan cara yang kuat dan ekspresif untuk memproses koleksi data. Walau bagaimanapun, soalan biasa apabila menggunakan aliran adalah: bagaimana untuk memecahkan atau kembali dari operasi foreach? Gelung tradisional membolehkan gangguan awal atau pulangan, tetapi kaedah Foreach Stream tidak menyokong secara langsung kaedah ini. Artikel ini akan menerangkan sebab -sebab dan meneroka kaedah alternatif untuk melaksanakan penamatan pramatang dalam sistem pemprosesan aliran. Bacaan Lanjut: Penambahbaikan API Java Stream Memahami aliran aliran Kaedah Foreach adalah operasi terminal yang melakukan satu operasi pada setiap elemen dalam aliran. Niat reka bentuknya adalah

Program PHP untuk mengira vokal dalam rentetan Program PHP untuk mengira vokal dalam rentetan Feb 07, 2025 pm 12:12 PM

Rentetan adalah urutan aksara, termasuk huruf, nombor, dan simbol. Tutorial ini akan mempelajari cara mengira bilangan vokal dalam rentetan yang diberikan dalam PHP menggunakan kaedah yang berbeza. Vokal dalam bahasa Inggeris adalah a, e, i, o, u, dan mereka boleh menjadi huruf besar atau huruf kecil. Apa itu vokal? Vokal adalah watak abjad yang mewakili sebutan tertentu. Terdapat lima vokal dalam bahasa Inggeris, termasuk huruf besar dan huruf kecil: a, e, i, o, u Contoh 1 Input: String = "TutorialSpoint" Output: 6 menjelaskan Vokal dalam rentetan "TutorialSpoint" adalah u, o, i, a, o, i. Terdapat 6 yuan sebanyak 6

Java Made Simple: Panduan Pemula untuk Kuasa Pengaturcaraan Java Made Simple: Panduan Pemula untuk Kuasa Pengaturcaraan Oct 11, 2024 pm 06:30 PM

Java Made Simple: Panduan Permulaan untuk Kuasa Pengaturcaraan Pengenalan Java ialah bahasa pengaturcaraan berkuasa yang digunakan dalam segala-galanya daripada aplikasi mudah alih hingga sistem peringkat perusahaan. Untuk pemula, sintaks Java adalah ringkas dan mudah difahami, menjadikannya pilihan ideal untuk pembelajaran pengaturcaraan. Sintaks Asas Java menggunakan paradigma pengaturcaraan berorientasikan objek berasaskan kelas. Kelas ialah templat yang menyusun data dan tingkah laku yang berkaitan bersama-sama. Berikut ialah contoh kelas Java yang mudah: publicclassPerson{privateStringname;privateintage;

Cipta Masa Depan: Pengaturcaraan Java untuk Pemula Mutlak Cipta Masa Depan: Pengaturcaraan Java untuk Pemula Mutlak Oct 13, 2024 pm 01:32 PM

Java ialah bahasa pengaturcaraan popular yang boleh dipelajari oleh pembangun pemula dan berpengalaman. Tutorial ini bermula dengan konsep asas dan diteruskan melalui topik lanjutan. Selepas memasang Kit Pembangunan Java, anda boleh berlatih pengaturcaraan dengan mencipta program "Hello, World!" Selepas anda memahami kod, gunakan gesaan arahan untuk menyusun dan menjalankan program, dan "Hello, World!" Pembelajaran Java memulakan perjalanan pengaturcaraan anda, dan apabila penguasaan anda semakin mendalam, anda boleh mencipta aplikasi yang lebih kompleks.

Program Java untuk mencari kelantangan kapsul Program Java untuk mencari kelantangan kapsul Feb 07, 2025 am 11:37 AM

Kapsul adalah angka geometri tiga dimensi, terdiri daripada silinder dan hemisfera di kedua-dua hujungnya. Jumlah kapsul boleh dikira dengan menambahkan isipadu silinder dan jumlah hemisfera di kedua -dua hujungnya. Tutorial ini akan membincangkan cara mengira jumlah kapsul yang diberikan dalam Java menggunakan kaedah yang berbeza. Formula volum kapsul Formula untuk jumlah kapsul adalah seperti berikut: Kelantangan kapsul = isipadu isipadu silinder Dua jumlah hemisfera dalam, R: Radius hemisfera. H: Ketinggian silinder (tidak termasuk hemisfera). Contoh 1 masukkan Jejari = 5 unit Ketinggian = 10 unit Output Jilid = 1570.8 Unit padu menjelaskan Kirakan kelantangan menggunakan formula: Kelantangan = π × r2 × h (4

See all articles