首页 > 代码库 > LeetCode算法练习PlusOne
LeetCode算法练习PlusOne
今天看到酷壳推荐的国外编程LeetCode算法编程网站,上面目前有154道算法题,感觉很有意思,平常工作也比较忙,现在很少有时间来锻炼算法相关的东西,有空的时候静下心来,温习下基础,活跃下自已的思路,也是有必要的。下午先做了个简单的题,后面会陆续补充其它的题目。
1、题目
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.
首先解释下题目,这道题的意思是:
用一个数组来代表一个非负整数,对这个整数进行+1操作,得到的结果也用数组进行表示。这个题目有假设前提:数组里的数字都是在0-9范围内的(刚开始弄迷惑了,以为数组里的数字可以是任意大的值,这样来解这道题的话,会非常困难)。
2、分析
知道前提后,这个题目就比较简单了,从数组最后一位开始,每个位需要判断是否需要进位,如果进位,自已设为0,否则自增即可。直接附源码:
class Solution {public: vector<int> plusOne(vector<int> &digits) {
int size = digits.size(); if (digits[size - 1] < 9) { digits[size - 1] += 1; return digits; } // 是否需要进位 bool carry = true; for (int i = size - 1; i >= 0; i --) { if (!carry) { break; } if (digits[i] == 9) { carry = true; // 进位后,原位置0 digits[i] = 0; if (i == 0) { // 数组首个数字进位后,需要新插入数字首位 digits.insert(digits.begin(), 1); } } else { // 不进位,就退出了 carry = false; digits[i] += 1; } } return digits; }};
LeetCode算法练习PlusOne
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。