leetcode66-加一

原题

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字123。

示例 2:

输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字4321。

解法

思想

根据加法规则进行计算,应注意进位的处理和全是9的特殊情况

代码

  1. 迭代
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length-1;i>=0;i--){
            if(digits[i]!=9) {//不需进位
                digits[i] += 1;
                break;//什么时候不需进位即可退出
            }else {
                if (i == 0) {//首位需进位的特殊情况,需分配一个大一位的数组
                    int[] ret = new int[digits.length+1];
                    ret[0] = 1;
                    return ret;
                }
                digits[i] = 0;//不是首位,需进位
            }
        }
        return digits;
    }
}
  1. 递归
class Solution {
    public int[] plusOne(int[] digits) {
        return addOneAtPos(digits, digits.length-1);
    }

    private int[] addOneAtPos(int[] num, int pos){//在pos位上加一
        if(num[pos]!=9){//不需进位
            num[pos]+=1;
            return num;//什么时候不需进位即可返回
        } else if(pos>0){//不是首位,需进位
            num[pos]=0;
            return addOneAtPos(num, pos-1);
        } else {//首位需进位的特殊情况,需分配一个大一位的数组
            int length = num.length;
            int[] newNum = new int[length+1];
            newNum[0]=1;
            return newNum;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode66-%e5%8a%a0%e4%b8%80/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年11月13日
下一篇 2019年11月15日

相关推荐

  • leetcode86-分隔链表

    原题 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head…

    算法 2020年4月27日
    0160
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数…

    算法 2020年1月3日
    0160
  • leetcode1162-地图分析

    原题 你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域…

    2020年3月29日
    0180
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0250
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 2024年3月24日
    0210
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04690
  • 数组元素左右两边最近较小元素

    原题(来源牛客网) 给定一个不含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例: 输入: ar…

    算法 2020年4月26日
    0700
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    080
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    0110

发表回复

登录后才能评论