[LintCode] Print Numbers by Recursion

kumfo 發布于2019-08-14 15:17 / 2935人閱讀

摘要：只有當位數時，才打印數字。首先分析邊界，應該，然后用存最高位。用函數對進行遞歸運算，同時更新結果數組。更新的過程歸納一下，首先，計算最高位存入，然后，用到倍的和之前里已經存入的所有的數個循環相加，再存入，更新，計算更高位直到等于

Problem

Print numbers from 1 to the largest number with N digits by recursion.

Example

Given N = 1, return [1,2,3,4,5,6,7,8,9].

Given N = 2, return [1,2,3,4,5,6,7,8,9,10,11,12,...,99].

Note

只有當位數n >= 0時，才打印數字。首先分析邊界n = 0，應該return 1，然后用base存最高位。用helper()函數對base進行遞歸運算，同時更新結果數組res。
更新res的過程：

res = {1, 2, 3, 4, 5, 6, 7, 8, 9};
base = helper(n-1, res); //10
//i = 1 ~ 9;
for i:
curbase = i * base; //10, 20, 30, 40, ... , 80, 90
res.add(curbase); // 10; 20; ... ; 80; 90
//j = index of res;
for j:
res.add(curbase + res.get(j)); //11, 12, 13, ... , 18, 19;
                               //21, 22, 23, ... , 28, 29;
                               //...

歸納一下，首先，計算最高位存入base，然后，用1到9倍的base（curbase）和之前res里已經存入的所有的數（res.size()個）循環相加，再存入res，更新res.size，計算更高位直到base等于10^n...

Solution

Recursion

public class Solution {
    public List numbersByRecursion(int n) {
        List res = new ArrayList();
        if (n >= 0) {
            helper(n, res);
        }
        return res;
    }
    public int helper(int n, List res) {
        if (n == 0) return 1;
        int base = helper(n-1, res);
        int size = res.size();
        for (int i = 1; i <= 9; i++) {
            int curbase = i * base;
            res.add(curbase);
            for (int j = 0; j < size; j++) {
                res.add(curbase + res.get(j));
            }
        }
        return base * 10;
    }
}

Non-recursion

public class Solution {
    public List numbersByRecursion(int n) {
        List res = new ArrayList();
        int max = 1;
        while (n != 0) {
            max *= 10;
            n--;
        }
        for (int i = 1; i < max; i++) {
            res.add(i);
        }
        return res;
    }
}

GPU云服務器云服務器 Numbers recursion LintCode LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65580.html

[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是組合中不能存在重復的元素，因此，在遞歸時將初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 評論0 收藏0
[LintCode] Ugly Number

Problem Write a program to check whether a given number is an ugly number`. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly ...

raise_yang 2019-08-14 15:20 評論0 收藏0
[LintCode] Max Tree

Problem Given an integer array with no duplicates. A max tree building on this array is defined as follow: The root is the maximum number in the arrayThe left subtree and right subtree are the max tre...

afishhhhh 2019-08-14 16:42 評論0 收藏0
[LintCode/LeetCode] Binary Tree Serialization

摘要：這里要注意的是的用法。所以記住，用可以從自動分離出數組。跳過第一個元素并放入數組最快捷語句建立的用意記錄處理過的結點并按處理所有結點和自己的連接下面先通過判斷，再修改的符號的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

keithyau 2019-08-14 15:12 評論0 收藏0
Understanding Recursion

Recursion, simply put, is calling a function on itself. It can used to break down complex problems into smaller manageable similar units that can be handled by the same function. Recursion vs Iteratio...

HtmlCssJs 2019-08-22 15:42 評論0 收藏0