Leetcode --- 两数问题
2021-04-27 本文已影响0人
_code_x
1.两数之和（1 - 易）
题目描述：给定一个整数数组 nums 和一个整数目标值 target，在该数组中找出 和为目标值 的那 两个 整数，返回它们的数组下标。
示例 :
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
思路：本题可以多解法，但是核心考察点为哈希表，即建立值与索引的映射值，遍历数组获取结果。
代码实现：
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] {map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return null;
}
2.两数之和II（167 - 易）
题目描述：给定数组升序，下标从1开始。
示例 :
输入：numbers = [2,3,4], target = 6
输出：[1,3]
思路：本题可以使用哈希表，但是数组严格升序。利用这一性质，可以定义双指针，遍历数组比较大小。
注意：不能使用二分查找，因为最终结果可能分别分布在两个区间。
代码实现：
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
break;
}
}
return new int[] {left + 1, right + 1};
}
3.两数之和IV（653 - 易）
题目描述：判断二叉搜索树是否有两个元素的和为目标值。
示例 :
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
思路：
法1：直接递归遍历二叉搜索树，利用set存储节点，判断是否出现k - root.val。
法2：利用bst中序升序，双指针求解，如167题。
代码实现：直接遍历
private Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
if (root == null) return false;
if (set.contains(k - root.val)) return true;
set.add(root.val);
return findTarget(root.left, k) || findTarget(root.right, k);
}
4.两整数之和（371 - 中）
题目描述：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 :
输入: a = 1, b = 2
输出: 3
思路：位运算模拟两数相加（可自行举例）：可以递归或者迭代实现。
- 按位计算二进制相加（不算进位），相当于二进制按位异或操作。
- 计算进位值，相当于两个数按位与，再进行左移
- 重复上述操作直到进位值b为0，得到累加和a。
代码实现：
public int getSum(int a, int b) {
while (b != 0) {
int tmp = a ^ b;
b = (a & b) << 1;
a = tmp;
}
return a;
// 递归实现 return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
}
5.两数相加（2 - 中）
题目描述：按照链表逆序形式存储的两个数进行加和，以相同的形式返回结果。数字不含前导0。
示例 :
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
思路：使用迭代模拟两数相加的过程：
- 先计算两节点值加和
sumVal，注意：加上上一轮的进位值 - 记录进位值
carry - 建立结果链表并连接
- 更新索引值，包括结果链表、
l1和l2
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
sum += l1 == null ? 0 : l1.val;
sum += l2 == null ? 0 : l2.val;
carry = sum / 10;
ListNode sumNode = new ListNode(sum % 10);
cur.next = sumNode;
cur = sumNode;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummyHead.next;
}
6.两数相加II（445 - 中）
题目描述：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。要求：不修改链表。
示例 :
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
思路：本题关键使用两个栈实现逆序取出链表的元素进行相加，剩下的解题思路与上题类似。
注意：我们最后返回的结果也是按照正序进行连接的，所以链表要进行倒序连接。
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += (stack1.isEmpty()) ? 0 : stack1.pop();
sum += (stack2.isEmpty()) ? 0 : stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
7.两数相加II（445 - 中）
题目描述：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。要求：不修改链表。
示例 :
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
思路：本题关键使用两个栈实现逆序取出链表的元素进行相加，剩下的解题思路与上题类似。
注意：我们最后返回的结果也是按照正序进行连接的，所以链表要进行倒序连接。
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += (stack1.isEmpty()) ? 0 : stack1.pop();
sum += (stack2.isEmpty()) ? 0 : stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
