LeetCode-05/10/2020

Posted on In

This is a record of my craking process for Leetcode.

1. Two Sum#

1.1 Problem Description#

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

1.2 Soulution#

It is very easy to come up with a brute force soulution which Time complex is O(n ^ 2).However, we can use a map structure to record the num and index in the nums we have iteratered. And also, when we check each number, we can find (target - number) in the current map. Then, it will be the solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for(int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        if(map.containsKey(temp) && map.get(temp) != i) {
            return new int[] {i, map.get(temp)};
        }
    }
    return null;
}

2 Add Two Numbers#

2.1 Problem 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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

2.2 Soulution#

This problem is quite similar to merge sort. Hence, in my case, I use the concept the merge sort to generate a new line. In addition, when we calculate the last number, we shuould determine whether it has a carry. In my case, I use a variable called flag to record the carry.

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        int num = l1.val + l2.val;
        int flag = 0;
        if(num >= 10) flag = 1;
        num %= 10;
        ListNode ans = new ListNode(num);
        ListNode p = ans;
        l1 = l1.next;
        l2 = l2.next;
        while(l1 != null || l2 != null) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            num = num1 + num2 + flag;
            flag = 0;
            if(num >= 10) flag = 1;
            num %= 10;
            p.next = new ListNode(num);
            p = p.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if(flag == 1) p.next = new ListNode(1);
        return ans;
    }
}

2 Add Two Numbers#

2.1 Problem 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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

2.2 Soulution#

This problem is quite similar to merge sort. Hence, in my case, I use the concept the merge sort to generate a new line. In addition, when we calculate the last number, we shuould determine whether it has a carry. In my case, I use a variable called flag to record the carry.

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        int num = l1.val + l2.val;
        int flag = 0;
        if(num >= 10) flag = 1;
        num %= 10;
        ListNode ans = new ListNode(num);
        ListNode p = ans;
        l1 = l1.next;
        l2 = l2.next;
        while(l1 != null || l2 != null) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            num = num1 + num2 + flag;
            flag = 0;
            if(num >= 10) flag = 1;
            num %= 10;
            p.next = new ListNode(num);
            p = p.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if(flag == 1) p.next = new ListNode(1);
        return ans;
    }
}