Plus One

https://leetcode.com/problems/plus-one/

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

算法描述

这个题目需要注意的地方是假设数组的长度是n，那么一个数的最高有效位是数组的第0个数，数组的最低有效位是数组的第n-1个数。

1. new一个ArrayList为resDigits
2. 按照n-1, n-2, ..., 0这样的顺序读取数组的值，首先将第n-1个数和1相加值为sum
3. 如果有进位（也即sum == 10）,那么resDigits就加个0元素，接着原数组余下元素，即第n-2, n-3, ..., 0位的数值跳到步骤2)继续执行；
   
   如果没有进位，那么resDigits就加上sum，并且数组的余下元素也加到resDigits中
4. 因为得到的resDigits的第0个数是最低有效位，因此按照题目的要求，把resDigits倒过来。

程序代码

public class Solution {

    public int[] plusOne(int[] digits) {

        int length = digits.length;

        if (digits == null || length == 0) {

            return null;

        }

        List<Integer> resDigits = new ArrayList<Integer>();

        int n = digits.length - 1;

        Boolean flag = true;

        do {

            if (flag) {

                int sum = digits[n--] + 1;

                if (sum == 10) {

                    resDigits.add(0);

                    flag = true;

                } else {

                    resDigits.add(sum);

                    flag = false;

                }

            } else {

                resDigits.add(digits[n--]);

            }

        }while(n >= 0);

        if (flag) {

            resDigits.add(1);

        }

        int[] newDigits = new int[resDigits.size()];

        for (int i = resDigits.size() - 1; i >= 0; i--) {

            newDigits[newDigits.length - 1 - i] = resDigits.get(i);

        }

        return newDigits;

    }

}

随机推荐

1. Unity User Group 北京站图文报道：《Unity3D VR游戏与应用开发》

   很高兴,能有机会回报Unity技术社区:我和雨松MOMO担任UUG北京站的负责人, 组织Unity技术交流和分享活动. 本次北京UUG活动场地–微软大厦 成功的UUG离不开默默无闻的付出:提前2小时到 ...

2. Your branch and remoteBranchName have diverged solution

   (zhuan)git pull时解决分支分叉(branch diverged)问题 git pull时出现分支冲突(branch diverged) $ git status # On branch ...

3. EJS-初识

   项目中使用了EJS,因此,也开始接触了EJS. EJS官方定义:it's just plain JavaScript. 总的来说,上手较快(毕竟我是个菜鸟). 第一步:安装: 第二部使用: 在html ...

4. Http请求笔记

   1 HTTP请求报文组成: 请求行:请求方法 url 协议版本 请求头:报文头-属性名:属性值 Accept属性告诉服务端-客户端接受什么类型的响应,可为一个或多个mime类型值 Cookie:服务端 ...

5. R 包

   [下面列出每个步骤最有用的一些R包] .数据导入 以下R包主要用于数据导入和保存数据: feather:一种快速,轻量级的文件格式:在R和python上都可使用 readr:实现表格数据的快速导入 r ...

6. Sql 通过表名查找所有列名

   SELECT * FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME = 'ImmediacyOutKu'

7. 在引用的laravel的@include子模板中传递参数

   调用传参: @include("message",['msg'=>'中国']) 在message子模板中调用msg的值: {{msg}}

8. Prometheus 初体验

   本文环境 Redhat Linux 6.7, Prometheus 2.2.1,node_exporter 1.5.2 介绍 Prometheus 是2012年由 SoundCloud 开源的系统监控 ...

9. 在taro中跳转页面的时候执行两遍componentDidMount周期的原因和解决方法

   在做taro跳转的时候,发现在跳转后的页面会走两遍componentDidMount周期,查看了github上的issues,发现是跳转路由带参为中文引起的,只要把中文参数进行urlencode解决 ...

10. CF 724 G. Xor-matic Number of the Graph

    G. Xor-matic Number of the Graph 链接 题意: 给定一个无向图,一个interesting的三元环(u,v,s)满足,从u到v的路径上的异或和等于s,三元环的权值为s, ...