[LeetCode/LintCode] Plus One

sunsmell 发布于2019-08-14 15:17 / 1237人阅读

Problem

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.

Example

Given [1,2,3] which represents 123, return [1,2,4].

Given [9,9,9] which represents 999, return [1,0,0,0].

Solution Update 2018-9

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n-1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i]++;
                return digits;
            }
        }
        int[] res = new int[n+1];
        res[0] = 1;
        return res;
    }
}

进位法：

public class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 1;
        for (int i = digits.length-1; i >= 0; i--) {
            int cur = digits[i] + carry;
            carry = cur / 10;
            digits[i] = cur % 10;
            if (carry == 0) break;
        }
        if (carry == 1) {
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        return digits;
    }
}

逢9化0法：

public class Solution {
    public int[] plusOne(int[] digits) {
        int last = digits.length-1;
        while (last >= 0 && digits[last] == 9) {
            digits[last] = 0;
            last--;
        }
        if (last == -1) {
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        else {
            digits[last] += 1;
            return digits;
        }
    }
}

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

转载请注明本文地址：https://www.ucloud.cn/yun/65564.html

[LeetCode/LintCode] Is Subsequence

Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...

terasum 2019-08-19 11:05 评论0 收藏0
[LeetCode/LintCode] First Bad Version

摘要：分析最后一次循环的时刻当与相差小于时，总是那么如果是，下一次直接跳出循环，返回当与相差大于时，是，变成，如果是，循环结束的条件将是循环结束，返回 Problem The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case,...

lowett 2019-08-15 15:46 评论0 收藏0
[LeetCode/LintCode] Word Ladder

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

张金宝 2019-08-14 15:27 评论0 收藏0
[LeetCode/LintCode] Course Schedule II

Problem There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed a...

Lavender 2019-08-15 17:49 评论0 收藏0
[LeetCode/LintCode] Merge Intervals

摘要：方法上没太多难点，先按所有区间的起点排序，然后用和两个指针，如果有交集进行操作，否则向后移动。由于要求的，就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

gougoujiang 2019-08-14 15:16 评论0 收藏0