Leetcodeブラシ問題記録-js

Leetcodeの書き込み記録
209.08.01から毎日少なくとも1本のleetcode文字列を書きます.125配列:26 67 88 118 119チェーン表:21ツリー:100 101 108 112
08001 13.Roman to Integer Easy構想:Mapオブジェクトを作成してローマ字表を保存する.文字列を巡回して、最初の文字が大きいか、または2番目の文字が大きいなら、足し算をします.減算をするより小さいです.

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    if(!s||s.length === 0) return 0
    let map = new Map([['I',1],['V',5],['X',10],['L',50],['C',100],['D',500],['M',1000]]);
    let n = s.length - 1;
    let result = map.get(s[n])
    while(n > 0) {
        const cur = map.get(s[n])
        const pre = map.get(s[n - 1]) 
        if(pre < cur) {
            result -= pre
        } else {
            result += pre
        }
        n--
    }
    return result
}; 

0802 14.Longest Common Prfix Easy考え方:最初に並べ替えて、最初と最後の要素splitで分割して巡回比較します.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    
    if(strs==null) return '';
    if(strs.length == 0) return '';
    if(strs.length == 1) return strs[0];
    
    let list = strs.concat().sort();
    
    let list_first = list[0].split('');
    let list_last = list[list.length - 1].split('');
    let result = '';
    
    list_first.forEach((word,index) => {
        
        if (index!==result.length) return;
        
        if (list_first[index] == list_last[index]) {
            result += word;
        }
    })
    return result;
};

21.1 Merge Two Sorted Lists Easy考え方:簡単なチェーン問題です.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let preHead = new ListNode();
    let current = preHead;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = new ListNode(l1.val)
            l1 = l1.next
        } else {
            current.next = new ListNode(l2.val)
            l2 = l2.next
        }
        current = current.next;
    }
    current.next = l1 || l2;
    return preHead.next;
};

08003 26.Remove Dupliccates from Sorted Aray Easy考え方:行列が重い問題に行きます.

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    nums.forEach((item,index) => {
        while(item == nums[index + 1]) {
            nums.splice(index + 1, 1);
        }
    })
    return nums.length;
};

08004.Remove Element

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    while(nums.indexOf(val,0) >= 0) {
        nums.splice(nums.indexOf(val,0), 1);
    }
    return nums.length;
};

08006 288.Implement str()

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle)
};

35.Search Insert Position

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if(nums.indexOf(target) !== -1) { 
        return nums.indexOf(target)
    } else {
        for(let i = 0;i<=nums.length;i++){
            if(nums[i]>=target) {
                return i
            } else if(i==nums.length) {
                return i
            }
        }
    }
    
};

0837.Maximum Subarray

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if(nums.length == 1) return nums[0]
    let res = nums[0]
    let currentSum = 0
    nums.forEach(item=>{
        currentSum = Math.max(item + currentSum,item)
        res = Math.max(currentSum, res)
    })
    return res
};

0828.Length of Last Wordは、文字列が空の場合、または最後の単語がない場合はゼロに戻ります.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    if(!s) return 0
    s = s.trim()
    let arr = s.split(" ")
    return arr[arr.length - 1].length
};

66.Plus Oneは、数字がそれぞれ9の場合に注意してください.

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i = digits.length - 1; i >= 0; i--) {
        let current = digits[i] + 1
        
        if(current == 10){
            digits[i] = 0
        } else {
            ++digits[i]
            break
        }
        
        if(i==0&&current==10) digits.unshift(1)
    }
    return digits
};

67. Add Binary考え方は先にゼロを補って、それからビットから計算を始めて、進数の問題に注意します.

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let res = ''
    let aLen = a.length
    let bLen = b.length
    let carry = 0
    //   
    if(aLen > bLen){
        for(let i = 0 ; i < aLen - bLen; i++) {
            b = '0' + b
        }
    } else {
        for(let i = 0; i < bLen - aLen; i++) {
            a = '0' + a
        }
    }
    for(let i = Math.max(aLen,bLen) - 1; i>=0; i--) {
        let sum = Number(a[i]) + Number(b[i]) + carry
        res = String(sum % 2) + res
        carry = Math.floor(sum/2)
    }
    if(carry) {
        res = '1'+res
    }
    return res
};

88. Merge Sorted Arayは先に二つの配列を一つにまとめて並べ替えて、nums 1に再割り当てします.

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    const num = nums1.splice(0, m).concat(nums2.splice(0,n))
    num.sort((a,b)=> a - b)
    num.forEach((_n,i)=> nums1[i]=_n)
    return nums1
};

ツリー関連の問題100.Same Treeは二つの二叉の木が等しいかどうかを判断して、再帰します.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(!p && !q) return true
    if(!p || !q || p.val !== q.val) return false
    return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right)
};

101.Symmetric Treeは、ツリーが対称かどうかを判断し、100題と同じように再帰的に使用するが、再帰的な対象が必要であることに注意する.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true
    function mirror(left,right) {
        if(!left && !right) return true
        if (!left || !right || left.val !== right.val) return false
        return mirror(left.left,right.right)&&mirror(left.right,right.left)
    }
    return mirror(root.left, root.right)
};

107.Binary Tree Level Order Traversal II

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if(!root) return []
    let result = []
    let queue = [root]
    
    while(queue.length > 0) {
        let size = queue.length
        let current = []
        
        for (let i = 0; i < size; i++) {
            let head = queue.shift()
            current.push(head.val)
            if(head.left !== null) { queue.push(head.left) }
            if(head.right !== null) { queue.push(head.right) }
        }
        result.unshift(current)
    }
    
    return result
};

1080.onvert Sorted Aray to Binary Search Tree

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(!nums.length) return null
    
    let half = Math.floor(nums.length / 2)
    let root = new TreeNode(nums[half])
    
    if(nums.slice(0,half).length>0){
        root.left = sortedArrayToBST(nums.slice(0,half))
    }
    if(nums.slice(half+1).length>0){
        root.right = sortedArrayToBST(nums.slice(half+1))
    }
    return root
};

08029 110.Balanced Binary Treeは二叉の木をバランスよく保っています.左右の子樹の高さの差は1を超えてはいけません.バランス係数:1 0-1(左の正、右の負)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if(root == null) return true
    
    let left = treeSize(root.left)
    let right = treeSize(root.right)
    let difference = Math.abs(right - left)
    let result = true
    
    if(difference>1) return false
    
    return result && isBalanced(root.left) && isBalanced(root.right)
};
var treeSize = function(root) {
    if(root == null) return 0
    return 1 + Math.max(treeSize(root.left),treeSize(root.right))
}

112.Path Sumは木と一つの和をあげます.パスがあるかどうかとこれと同じです.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(root == null) return false
    if(root.left == null && root.right == null) return sum == root.val
    return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val)
};

118.Pascals Triangle楊輝三角

前の2行は不変です.[1][1,1]

k行はk個の要素

があります.

行目と最後の要素は1

です.

は、k(k＞2)行目のn(n＞1&n＜k)個の要素A［k］［n］に対して、A［k］［n］＝A［k−1］＋A［k−1］［n］

である.

/**
 * @param {number} numRows
 * @return {number[][]}
 */
function getRows (pre) {
    let currentRow = [1]
    for(let i = 0;i

119.Pascals Triangle II構想を同じくして、現在の配列を交換する.

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
function currentRow(pre) {
    let row = [1]
    for(let i = 0;i

125.Vaild Palindrome有効回答

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    s = s.replace(/[^0-9a-zA-Z]+/gmi,'')
    s = s.toLowerCase()
    let l = 0
    let r = s.length - 1
    
    while(l < r){
        if(s.charAt(l)!==s.charAt(r)) return false
        ++l
        --r
    }
    return true
};

136.Single Number

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        let current = nums.pop()
        if(nums.includes(current)){
            nums.unshift(current)
            continue;
        }
        return current
    }
};