# Algorithms leetcode
###### tags: `algorithms` `leetcode` `code` `leet` `thuật toán`

Big O
https://www.bigocheatsheet.com
Quan trọng 2 thứ :
+ Thời gian chạy
+ Bộ nhớ

### 1. Two sum
Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

:::spoiler **Đáp án 1 : O(n^2) -> terrible**

var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let k = i + 1; k < nums.length; k++) {
            if (nums[i] + nums[k] === target)
                return [i, k]
        }
    }
    return []
};

:::

:::spoiler **Đáp án 2 : O(n) và memory : O(n)**
Map(key, value:index)

var twoSum = function (nums, target) {
 const map = new Map();
    for(let i=0;i<nums.length;i++){
        // map.set(key,value)
        // map.has(key) 
        // map.get(key)
      
        let remain = target - nums[i];
        if(map.has(remain)){
            return [map.get(remain),i]
        }else{
            map.set(nums[i],i);
        }
  
    }
      return []
}; 

:::

### 20. Valid parentheses
https://leetcode.com/problems/valid-parentheses/
Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Đáp án :

var isValid = function(s) {
    if(!s.length) return true;
    const stack = [];
    const openChar = ['(','{','['];
    const closeChar = [')','}',']']
    for(let character of s){
        const isOpenChar = ['(','{','['].includes(character);
        if(isOpenChar){
            stack.push(character);
        }else{
            const top = stack.pop();
            if(openChar.indexOf(top)!==closeChar.indexOf(character)){
                return false;
            }
        }
    }
    return stack.length === 0;
};

### 21. Merge two sorted list
link list
https://leetcode.com/problems/merge-two-sorted-lists/
Solve :
https://www.youtube.com/watch?v=XIdigk956u0&list=PLF_1Qi3jFDOsicefz1oRwhjPsKHdOD0A0&index=3

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    const dummy = new ListNode(-Infinity);
    let prev = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            prev = l1;
            l1 = l1.next;
        } else {
            prev.next = l2; 
            prev = l2;
            l2 = l2.next; // tăng 1 lên
        }
    }
    if (!l1) prev.next = l2;
    if (!l2) prev.next = l1;
    return dummy.next;
};

### 121. Best Time to Buy and Sell Stock