Fork me on GitHub

leetcode之66. 加一

发表于 | 分类于
字数统计 655 字 | 阅读时长 3 分钟

题目描述：

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

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

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

示例 1:

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

示例 2:

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

解题思路：

思路一：

时间复杂度: $O(n)$, 空间复杂度: $O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
	vector<int> plusOne(vector<int>& digits) {
		int n = digits.size() -1;
		vector<int> m;
		// 首先设计一个flag，默认为0
		int flags = 0;

		// 判断最后一位是否为9
		// 如果为9，进位，flag = 1，同时当前位设为0
		if(digits[n] == 9)
		{
			flags = 1;
			digits[n] = 0;
		}
		else
		{
			digits[n] = digits[n] + 1;
			m = digits;
			return m;
		}

		// 处理完最后一位，接下来处理其他的位
		for(int i = n - 1; i>= 0; )
		{
			if(digits[i] == 9)
			{
				digits[i] = 0;
				i--;
				flags = 1;
			}
			else
			{
				digits[i] = digits[i] + 1;
				flags = 0;
				// 将digits 赋值给m
				m = digits;
				// 直接返回就可以了
				return m;
			}
		} 
		//将digits赋值给m
		m = digits;
		// 循环结束后，如果flags == 1，说明还有进位，需要插入一个1
		if(flags == 1)
		{
			// 在最前面插入一个1
			m.insert(m.begin(),1);
		} 
		return m; 
	}
};

思路二：

时间复杂度: $O(n)$, 空间复杂度: $O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
	vector<int> plusOne(vector<int>& digits) {
		int n = digits.size() -1;
		vector<int> m;
		int flags = 0;
		if(digits[n] == 9)
		{
			for(int i = n; i>= 0; )
			{
				if(digits[i] == 9)
				{
					digits[i] = 0;
					i--;
					flags = 1;
				}
				else
				{
					digits[i] = digits[i] + 1;
					flags = 0;
					break;
				}
			} 
		}
		else
		{
			digits[n] = digits[n] + 1;
			m = digits;
		}
		m = digits;
		// 测试最后是否还有进位
		if( flags == 1)
		{ 
			m.insert(m.begin(),1);

		} 
		return m; 
	}
};

思路三：

运用栈，时间复杂度：$O(n)$,空间复杂度：$O(n^2)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        stack<int> st;
        int d_len = digits.size() - 1;
        for(int i = 0;i <= d_len;i++)
        {
            st.push(digits[i]);
        }
        vector<int> m;
        bool flag = false;
        int temp = st.top();
        st.pop();
        if(temp == 9)
        {
            m.insert(m.begin(),0);
            flag = true;
        }
        else 
        {
            m.insert(m.begin(),temp + 1);
            flag = false;
        }

        while(!st.empty())
        {
            int t = st.top();
            st.pop();
            if(t == 9 && flag)
            {
                m.insert(m.begin(),0);
                flag = true;
            }
            else if(t < 9 && flag) 
            {
                m.insert(m.begin(),t + 1);
                flag = false;
            }
            else 
            {
                m.insert(m.begin(),t);
                flag = false;
            }
        }
        if(flag) m.insert(m.begin(),1);
        return m; 
    }
};