2. Add Two Numbers

Question: 

You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution: 

 

Add each element of two list with the help of a variable "carry". When both of the lists meet their end, return result.

1. One of the list is NULL:

l1:    NULL

l2:    1->2

sum: 1->2

2.  The lengths of l1 and  l2 are different:

l1:     2->2

l2:     9->9->9

sum: 1->2->0->1

Coding(C++): 

/**
 * 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* res = new ListNode(0);
        ListNode* head = res;
        int carry = 0;
        while(l1 && l2){
            res->next = new ListNode((l1->val+l2->val+carry)%10);
            res = res->next;
            carry = (l1->val+l2->val+carry)/10;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1){
            res->next = new ListNode((l1->val+carry)%10);
            res = res->next;
            carry = (l1->val+carry)/10;
            l1 = l1->next;
        }
        while(l2){
            res->next = new ListNode((l2->val+carry)%10);
            res = res->next;
            carry = (l2->val+carry)/10;
            l2 = l2->next;
        }
        if(carry > 0){
            res->next = new ListNode(carry);
        }
        return head->next;
    }
};

1. Two Sum

Question: 

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.

Example:

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

Solution(Array):

Use two for-loops: nums[i]+nums[j]==target, time complexity is O(n^2)

Coding(C++):

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int n = nums.size();
        vector res;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if(nums[i]+nums[j]==target){
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;
    }
};

Solution(Hash_table): 

hash_table.find(target - nums[i]) != hash_table.end(), time complexity: O(n)
map::find: Searches the container for an element with a key equivalent to k and returns an iterator to it if found, otherwise it returns an iterator to map::end.


Coding(C++):
 

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector res;
        map hash_table;
        hash_table.clear();
        int n = nums.size();
        for(int i = 0; i < n; i++){
            hash_table[nums[i]] = i;
        }
        for(int i = 0; i < n; i++){
            if(hash_table.find(target-nums[i]) != hash_table.end()){
                if(hash_table[target-nums[i]] > i){
                    res.push_back(i);
                    res.push_back(hash_table[target-nums[i]]);
                    return res;
                }
                if(hash_table[target-nums[i]] < i){
                    res.push_back(hash_table[target-nums[i]]);
                    res.push_back(i);
                    return res;
                }
            }
        }
        return res;
    }
};

Matlab/ Solve System of Linear Equations with symbolic constances

Consider the following system:
a1x + b1y = c1
a2x + b2y = c2
Declare the system of equations:

syms x y a1 a2 b1 b2 c1 c2
eqn1 = a1*x + b1*y == c1
eqn2 = a2*x + b2*y == c2
[A,B]= equationsToMatrix([eqn1, eqn2], [x, y])

A =
[ a1, b1]
[ a2, b2]
B =
 c1
 c2

237. Delete Node in a Linked List

Question:

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution(Linked List): 

According to the question: delete a node (except the tail).
O(1).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

Solution:

Shifting the remaining portion of the giving linked list to left by one node. Take the tail into consideration.
O(n).

Code(C++):
 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* p1 = node;
        ListNode* p2 = node->next;
        while(p2->next != NULL){
            p1->val = p2->val;
            p1 = p2;
            p2 = p2->next;
        }
        p1->val = p2->val;
        p1->next = NULL;
    }
};

243. Shortest Word Distance

Question:

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution(Array):

abs(idx1-idx2)

Code(C++):

class Solution {
public:
    int shortestDistance(vector& words, string word1, string word2) {
        int n = words.size();
        int idx1 = -1;
        int idx2 = -1;
        int dist = INT_MAX;
        for(int i=0;i<n;i++){
            if(words[i] == word1) idx1=i;
            else if(words[i] == word2) idx2=i;
            if(idx1 != -1 && idx2 != -1)
                dist = min(dist,abs(idx1-idx2));
        }
        return dist;
    }

};

104. Maximum Depth of Binary Tree

Question:

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution:(Tree)

Use DFS

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left)+1,maxDepth(root->right)+1);
    }
};

258. Add Digits

Question: 

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:

Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

Solution(Brute-Force):

 At each loop, add all the digits together and check if it has only one digit, if so, return the number.

Code(C++) :

class Solution {
public:
    int addDigits(int num) {
        int n = num;
        while(n > 9){
            int sum = 0;
            while(n){
                sum += (n%10);
                n /= 10;
            }
            n = sum;
        }
        return n;
    }
};

293. Flip Game

Question:

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

Solution:(String)

From i=0 to i=n-2, if there exists two consecutive "++", then it will be one result.
O(n).

Code(C++):

class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        int n = s.size();
        int i = 0;
        vector<string> res;
        while(i<n-1){
            if(s[i]=='+' && s[i+1]=='+'){
                string tmp = s;
                tmp[i] = '-';
                tmp[i+1] = '-';
                res.push_back(tmp);
            }
            i++;
        }
        return res;
    }
};

266. Palindrome Permutation

Question:

Given a string, determine if a permutation of the string could form a palindrome.
For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?
2. Count the frequency of each character.
3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Solution:(HashTable)

S="aab", whose length is odd number.
a-->2
b-->1
S="aabd",whose length is even number.
a-->2
b-->1
d-->1
O(n).

Code(C++):

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map hashTable;
        int odd = 0;
        for(auto ch:s){
            hashTable[ch]++;
            if(hashTable[ch]%2==1) odd++;
            else odd--;
        }
               return odd<2;
    }
};

292. Nim Game

Question: 

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Solution: 

Suppose there are 4k+i(1<=i<=3) stones. At first, you take i stones. Then, at each round, make sure that the total number of stones, that you and your friend take, is 4.
O(1).

Code(C++):

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Matlab

>> simulink

Frequency (rad/sec): 2pai around the circle