LeetCode #1~6

LeetCode practice using C++ by Visual Studio Code @ubuntu 16.04

george16886/LeetCode

#1 Two Sum Easy

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.

Solution 1: 暴力解 -> T(n) = O(n²)，S(n) = O(1)

Solution 2: 以空間換取時間，建HashMap -> T(n) = O(n)，S(n) = O(n)

1. 用HashMap建立數字與座標的映射
2. 若target減去當前數字存在於HashMap中即為解

hint: unordered_map<int, int> hmap;

#2 Add Two Numbers Medium

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 contains 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.

1. 兩個鍵結依序相加生成新節點放到新鍵結之後
2. 兩個鍵結長度可能不同 -> 需判斷鍵結若為空，則取 0，否則取節點值
3. 用一個cursor指向新鍵結的最後一個節點來紀錄目前處理位置
4. 避免兩個鍵結同時為空 -> 需先建立一個dummy節點
5. 最後需要特別處理最高位的進位，carry若為 1 -> 建立一個值為 1 的節點

hint: ListNode *ans = new ListNode(-1);

迴圈寫法: T(n) = O(max(m,n))，S(n) = O(max(m,n))

遞迴寫法: T(n) = O(max(m,n))，S(n) = O(max(m,n))

Follow up:

#2.5

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912.

1. 翻轉鍵結相加再翻轉
2. 補0到相同長度用遞迴方式處理

#3 Longest Substring Without Repeating Characters Medium

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

Solution 1: T(n) = O(n²)，S(n) = O(1)

1. 不使用HashMap比較暴力的解法
2. 使用兩個index，i 用來遍歷字串，j 用來檢查是否有重複的字母
3. 若遇到重複字母，則更新 j 的起始點
4. 若無重複則累加，找出最長的子字串長度

Solution 2: T(n) = O(n)，S(n) = O(min(m,n))

1. 建立一個HashMap紀錄字母最後出現的位置
2. 使用一個sliding window，使window在無重複字母的情形下盡可能擴展
3. 用一個index紀錄window左邊界的前一個位置，因此default為 -1
4. 若遇到相同字母且該字母在window中，更新index

#4 Median of Two Sorted Arrays Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Solution 1: T(n) = O(m+n)，S(n) = O(m+n)

重新排序合併成一個新的sorted array，排序到中位數的位置

1. 建立一個新的vector，用兩個index分別從兩個array取值，從小到大放進新建的vector，取到中位數的位置
2. 若有一個array先被取完，將它最後一個值設為比另一個array的最大值多 1 (或設為整數最大值)，以避免再來取這個array
3. 需判斷總數為奇數或偶數時中位數的取法不同
4. 需另外處理兩個或其中一個array為空的情形

Solution 2: T(n) = O(m+n)，S(n) = O(m+n)

1. 改善solution 1，不用去考慮數列個數為偶數或奇數
2. 取第 (m+n+1)/2 和第 (m+n+2)/2 個數字求其平均值
3. 注意第 n 個數字的index是 n–1

Solution 3: T(n) = O(log(m+n))，S(n) = O(1)

對中位數的index使用二分法遞迴找出中位數的值

1. 假設所求為第 k 個數字，用兩個變數 i, j 來紀錄兩個數列的起始位置
2. 若起始位置大於數列長度，表示該數列已全數淘汰 -> 直接找另一個數列
3. k=1時，表示要取第一個數字 -> 取兩數列起始位置上的較小的那個
4. 分別在兩個數列中查找第 k/2 個數字
5. 若不存在 -> 淘汰另一個數列的前 k/2 個數字
6. 比較兩數列第 k/2 個數字的大小，淘汰較小的數列的前 k/2 個數字
7. 更新 k -> 遞迴去淘汰兩數列中 k/2 個較小的數字

Solution 4: T(n) = O(log(min(m, n)))，S(n) = O(1)

迭代形式的二分搜索法

Very concise O(log(min(M,N))) iterative solution with detailed explanation — LeetCode Discuss

#5 Longest Palindromic Substring Medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Solution 1: T(n) = O(n²)，S(n) = O(1)

1. 從第二個字母開始，當作中心往兩邊擴展檢查兩邊字母是否一樣
2. 一樣的話就更新輸出回文字串的起始index以及長度
3. 長度為偶數的回文字串 -> 先檢查兩相鄰字母是否一樣
4. 一樣的話讓檢查回文的左邊界index先減 1

Solution 2: T(n) = O(n²)，S(n) = O(1)

改善solution 1，將步驟3的檢查兩相鄰字母合併到checkPalindrome中

Solution 3: T(n) = O(n²)，S(n) = O(n²)

Dynamic Programming的作法

1. 宣告一個二維數列isPalindrome來紀錄在區間 [i, j] 內是否為回文字串
2. 需特別處理空字串，否則數列isPalindrome會宣告失敗
3. 規則如下:
   a. 當 i = j，表示只有一個字母，必為回文
   b. 當 i = j+1，為兩相鄰字母，若兩字母相等則為回文
   c. 當 i > j+1，不相鄰兩字母若相等，且區間 [i-1, j+1] 為回文則為回文

Solution 4: T(n) = O(n)，S(n) = O(n)

Manacher’s Algorithm

Manacher’s Algorithm Explained — Longest Palindromic Substring

#6 ZigZag Conversion Medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Solution 1: T(n) = O(n)，S(n) = O(n)

1. 以一條直線加一條斜線為一個loop，每個loop會跳過jump個字母
2. jump的規律可以觀察出來是numRows*2–2 -> loop = length/jump
3. 先考慮落在直線上的字母，在原字串的index應為j*jump+i
4. 再補上其他在斜線上的字母，在原字串的index應為index+jump-2*i
5. 處理取值範圍超過字串長度的狀況
6. 處理numRows為 1 造成jump為 0 的狀況

Solution 2: T(n) = O(n)，S(n) = O(n)

改善solution 1，j 為直線上字母的位置 -> 斜線上字母index = j+jump-2*i

Solution 3: T(n) = O(n)，S(n) = O(n)

1. 建一個大小為numRows的字串vector，vector的index表示第幾個row
2. 兩個for loop，往下走和往上走，按順序將字母丟入對應row子字串中
3. 最後將vector中的子字串按vector的index順序接起來即為所求