LeetCode 2.Add Two Numbers,67.Add Binary,371.Sum of Two Integers,66.Plus One

发表于 | 分类于 ，
字数统计： 5k | 阅读时长≈ 0:05

LeetCode 2.Add Two Numbers

Description:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Difficulty:Medium

分析：

这道题的难度是Medium，涉及到链表操作，由于我对链表不是很熟悉，在这里还是浪费了很多时间复习一下链表操作。

解题思路还算比较清晰的，注意题目输入数据是从个位开始到高位输入，因此也比较好处理，每次各自取两个链表的一个结点，进行加法运算，注意需要考虑进位，把运算结果存在一个临时链表中即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode preHead(0), *p = &preHead;
		int extra = 0;// 进位
		while (l1 || l2 || extra) {
			int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
			extra = sum / 10;
			p->next = new ListNode(sum % 10);
			p = p->next;
			l1 = l1 ? l1->next : l1;
			l2 = l2 ? l2->next : l2;
		}
		return preHead.next;
	}
};

Similar Questions

LeetCode 67.Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

Difficulty:Easy

分析：

主要考虑两个串的长度。
1.a的长度比b长：这里我用了一个判断，把b的长度小于0作为判断条件之一，当b的所有字符处理完后，而a还有字符没处理，此时b的长度已经降到小于0了。
2.b的长度比a长：同理，当a的所有字符处理完后，而b还有字符没处理。
另外一个注意点就是进位处理了，当a、b都处理完后，将退出循环，此时需要判断最后一次循环是否产生了进位，若为真，则需要在结果result串前面加上‘1’。

代码如下：

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
class Solution {
public:
	string addBinary(string a, string b) {
		string result;
		int len_a = a.length() - 1;
		int len_b = b.length() - 1;
		int extra = 0;
		char c;
		while (len_a >= 0 || len_b >= 0) {
			c = (a[len_a] - '0') + (b[len_b] - '0') + extra + '0';
			if (len_a > len_b && len_b < 0) { // a的长度比b长，例如11，1
				c = (a[len_a] - '0') + extra + '0';
			}
			else if (len_a < len_b && len_a < 0) { // 表示的长度比a长，例如1，11
				c = (b[len_b] - '0') + extra + '0';
			}
			extra = 0;// 进位
			if ((c - '0') >= 2) {// 进位判断
				extra = 1;
				c = c - 2;
			}
			result = c + result;// string连接
			len_a--;
			len_b--;
		}
		if (extra == 1) result = '1' + result;// 注意最前面可能还有进位，例如11，1
		return result;
	}
};

另一种解法：其实大同小异

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// another solution
class Solution {
public:
	string addBinary(string a, string b) {
		string result;
		int len_a = a.length() - 1;
		int len_b = b.length() - 1;
		int c = 0;
		while (len_a >= 0 || len_b >= 0 || c == 1) {
			c += len_a >= 0 ? a[len_a--] - '0' : 0;
			c += len_b >= 0 ? b[len_b--] - '0' : 0;
			result = char(c % 2 + '0') + result;
			c /= 2;
		}
		return result;
	}
};

LeetCode 371,Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Difficulty:Easy

分析：

题意表明不能直接用+号，但我试了一下，直接return a + b; 也是可以Accepted的，哈哈哈。

回到本题，其实是考察一些基本的布尔代数知识。
两个二进制整数 a 和 b，如果相加的过程中如果没有进位，那么 a+b=a^b（ ^ 表示异或）。
那么 a+b 的进位为多少呢，只有 1+1 时才会出现进位。所以 a+b 的进位可以表示为 (a & b) << 1（ & 表示两个数字的按位与运算，<<表示左移运算）。之所以要左移1位，是因为要向高位进一位。

所以有如下关系：
设加数为a、b ，和为S ，向高位的进位为C
S=a^b
C=(a & b) << 1
该过程不断递归直至进位C为0即可得到运算结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 递归
class Solution {
public:
	int getSum(int a, int b) {
		if (a == 0) return b;
		return getSum((a & b) << 1, a ^ b);
	}
};
// another solution：非递归
class Solution {
public:
	int getSum(int a, int b) {
		while (a) {
			int x = a ^ b;
			a = (a & b) << 1;
			b = x;
		}
		return b;
	}
};

LeetCode 66.Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

输入：9 9 9 9
输出：1 0 0 0 0

输入：9 9 9 8
输出：9 9 9 9

输入：9 9 8 9
输出：9 9 9 9

Difficulty:Easy

分析：

主要是题意要弄懂，一个正整数，以vector输入，然后将这个数加1，其实就是看vector最后一个数是否为9，如果不是9，则最后一个数加1，返回结果就行；如果为9，设为0，继续判断前一个数是否为9……

代码如下：

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
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	vector<int> plusOne(vector<int>& digits) {
		for (int i = digits.size() - 1; i >= 0; i--) {
			if (digits[i] != 9) {
				digits[i]++;
				return digits;
			}
			digits[i] = 0;
		}
		digits.insert(digits.begin(), 1);
		return digits;
	}
};
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	Solution s;
	vector<int> result(n + 1);
	result = s.plusOne(a);
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}
	return 0;
}
------本文结束感谢阅读------