[Programming] Leetcode

Posted on |

Practice and summary.
001 TwoSum
002 AddTwoNumbers
003 Longest Substring Without Repeating Characters

001 TwoSum

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:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Better Approach (Hash Table)

Idea

Hash Table O(n) in time and space Best way to maintain a mapping of each element in the array to its index
Iterate and insert elements into hash table. At the same time, check if current element’s complement already exists in the table.

Code

std::unordered_map: (hashtable) insert and access in O(1) (if a collision occurred, a look up could degenerate to O(n) time)
std::map: elements are sorted by the key, insert and access is in O(log n). Usually the STL internally uses red black trees for ordered maps
Trick A vector ordered from low to high is required to return(?), I didn’t sort my vector by using vector<int> {hash_table[complement], i}; but it just works. (Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<unordered_map>
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash_table;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (hash_table.find(complement) != hash_table.end())
                return vector<int> {hash_table[complement], i};
            hash_table[nums[i]] = i;
        }
    }
};

My Approach (Sort and Match)

Idea

  • Sort O(nlogn) I used struct to store the number&index and write a cmp function for sort.
  • Iterate O(n) Assume target = sort_nums[i] + sort_nums[j] (i < j), iterate the sorted array from two direction: begin->end(i) and end->begin(j) until find the answer.

Code

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
struct Node {
    int num;
    int index;
}node;
bool cmp(struct Node x, struct Node y) {
    return x.num < y.num;
}
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        result.clear();
        vector<Node> nodes;
        for (int i = 0; i < nums.size(); ++i) {
            node.num = nums[i];
            node.index = i;
            nodes.push_back(node);
        }
        sort(nodes.begin(), nodes.end(), cmp);
        for (int i = 0, j = nodes.size() - 1; i < j;) {
            int num = nodes[i].num + nodes[j].num;
            if (num == target) {
                result.push_back(nodes[i].index);
                result.push_back(nodes[j].index);
                sort(result.begin(), result.end());
                return result;
            }
            else if (num < target) {
                ++i;
            }
            else {
                --j;
            }
        }
    }
};

002 AddTwoNumbers

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

Approach (Simulate digits-by-digits sum)

Idea

Simulate digits-by-digits sum starting from the head of list O(max(m, n)) in time and space, m and n represents the length of l1 and l2 respectively

Code

  • Cleaner but slower. (49ms, 56.21%)
  • Only one loop but 4 * max(m, n) times judgement for null pointer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p1 = l1,* p2 = l2, * head = new ListNode(0);
        ListNode* p = head;
        int val = 0;
        while (p1 || p2) {
            val /= 10; // add carry
            if (p1) {
                val += p1->val;
                p1 = p1->next;
            }
            if (p2) {
                val += p2->val;
                p2 = p2->next;
            }
            p->next = new ListNode(val % 10); // subtract overflow
            p = p->next;
        }
        if (val /= 10)
            p->next = new ListNode(1);
        return head->next;
    }
};
  • Faster but longer(redundant). (38ms, 87.27%)
  • Readable: curCarry and lastCarry
  • Three loops but 2 * max(m, n) + m + n times judgement for null pointer. Save time when m >> n or n >> m.
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
int curCarry = 0, lastCarry = 0;
while (p1 && p2) {
    curCarry = (p1->val + p2->val + lastCarry > 9) ? 1 : 0;
    p->next = new ListNode(p1->val + p2->val + lastCarry - curCarry * 10);
    lastCarry = curCarry;
    p = p->next;
    p1 = p1->next;
    p2 = p2->next;
}
while (p1) {
    curCarry = (p1->val + lastCarry > 9) ? 1 : 0;
    p->next = new ListNode(p1->val + lastCarry - curCarry * 10);
    lastCarry = curCarry;
    p = p->next;
    p1 = p1->next;
}
while (p2) {
    curCarry = (p2->val + lastCarry > 9) ? 1 : 0;
    p->next = new ListNode(p2->val + lastCarry - curCarry * 10);
    lastCarry = curCarry;
    p = p->next;
    p2 = p2->next;
}
if (lastCarry)
    p->next = new ListNode(1);

Note

  • Bad ides: Find out the two numbers, add them directly which may results in overflow when the sum is large.
  • Use p->next = ...;: p is a pointer used for iterating, once p = head;, we cannot assign it again like p = new ListNode(val); which will make p a new pointer.

003 Longest Substring Without Repeating Characters

To know is easier than to do! Code again!

Description

Given a string, find the length of the longest substring without repeating characters.

Examples: Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Approach (Sliding Window Optimized)

Idea

longest-substring-without-repeating-characters

Complexity Analysis
Time complexity : O(n). Index j will iterate n times.
Space complexity (Table): O(m). m is the size of the charset.

Code

  • vector<int> charToIndex(256, -1); Because the charset is rather small(total number of Character in Extended ASCII table is 256 (0 to 255)), we can replace the Map(std::unordered_map) with an integer array as direct access table. (Speed: 38ms -> 26ms)
  • int i = -1; reduces the calculate of + which saves time. For example, j - i + 1. (Speed: 26ms -> 18ms/93.52%)
1
2
3
4
5
6
7
8
9
10
11
12
int lengthOfLongestSubstring(string s) {
    int ans = 0;
    int i = -1, j; // ans -> longest substring of every potential substring (i, j)
    vector<int> charToIndex(256, -1); // direct access table
    for (j = 0; j < s.length(); ++j) {
        if (charToIndex[s[j]] > i) // Repeats between (i, j), not the whole string!
            i = charToIndex[s[j]]; // new start
        charToIndex[s[j]] = j; // update everytime
        ans = (j - i) > ans ? j - i : ans;
    }
    return ans;
}