2014
11-18

# LeetCode-Plus One[数组]

### 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.

// LeetCode, Plus One
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
return digits;
}
private:
// 0 <= digit <= 9
void add(vector<int> &digits, int digit) {
int c = digit;  // carry, 进位

for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
*it += c;
c = *it / 10;
*it %= 10;
}

if (c > 0) digits.insert(digits.begin(), 1);
}
};


// LeetCode, Plus One
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
return digits;
}
private:
// 0 <= digit <= 9
void add(vector<int> &digits, int digit) {
int c = digit;  // carry, 进位

for_each(digits.rbegin(), digits.rend(), [&c](int &d){
d += c;
c = d / 10;
d %= 10;
});

if (c > 0) digits.insert(digits.begin(), 1);
}
};


Java代码:

public class Solution {
public int[] plusOne(int[] digits) {
int k = digits.length-1;
for(; k >= 0; k--)
if(digits[k] != 9) break;

if(k == -1){
int newDigits[] = new int[digits.length + 1];
newDigits[0] = 1;
return newDigits;
}else{
int newDigits[] = new int[digits.length];
for(int i=0; i <= k ; i++)
newDigits[i] = digits[i];
newDigits[k]++;
return newDigits;
}
}
}

1. if(j){
int ans=a ;
for(int x=j-1;x>=0;x–){
if(!a ) break;
ans=min(ans,a );
sum+=ans;
}
}
求解释，，dp的思路是什么呢？

2. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。