[LintCode] Print Numbers by Recursion

kumfo 发布于2019-08-14 15:17 / 3115人阅读

摘要：只有当位数时，才打印数字。首先分析边界，应该，然后用存最高位。用函数对进行递归运算，同时更新结果数组。更新的过程归纳一下，首先，计算最高位存入，然后，用到倍的和之前里已经存入的所有的数个循环相加，再存入，更新，计算更高位直到等于

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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