easy

两数之和

/*
 * @lc app=leetcode.cn id=1 lang=javascript
 *
 * [1] 两数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const res = [];
    for(let i = 0;i<nums.length;i++){
        let newArr = JSON.parse(JSON.stringify(nums));
        newArr.splice(i,1)
        if(newArr.includes(target-nums[i])){
            res.push(i) ;
            break;
        }
    }

    if(res.length>0){
        for(let j = 0;j<nums.length;j++){
            if(nums[j]===(target-nums[res[0]])&&j!==res[0]){
                res.push(j) ;
                break;
            }
        }
    }

    return res
    


};
// @lc code=end

回文数

/*
 * @lc app=leetcode.cn id=9 lang=javascript
 *
 * [9] 回文数
 */

// @lc code=start
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if(x<0){
        return false
    }
    if(x===0){
        return true
    }
    let s = x.toString();
    let l = Math.ceil(s.length/2);

    for(let i=0;i<l;i++){
        if(s[i]!==s[s.length-1-i]){
            return false
        }
    }

    return true
};
// @lc code=end

罗马数字转整数

/*
 * @lc app=leetcode.cn id=13 lang=javascript
 *
 * [13] 罗马数字转整数
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const relationList = [
        {
            label:'I',
            value:1
        },
        {
            label:'V',
            value:5
        },
        {
            label:'X',
            value:10
        },
        {
            label:'L',
            value:50
        },
        {
            label:'C',
            value:100
        },
        {
            label:'D',
            value:500
        },
        {
            label:'M',
            value:1000
        },
    ]

    const combineList = [
        {
            label:'A',
            value:4
        },
        {
            label:'B',
            value:9
        },
        {
            label:'H',
            value:40
        },
        {
            label:'J',
            value:90
        },
        {
            label:'E',
            value:400
        },
        {
            label:'F',
            value:900
        },
    ]

    const allList = [...relationList,...combineList];

    const mapObj = {}

    allList.forEach(item=>{
        mapObj[item.label] = item.value
    })

    s=s.replace(/IV/g,'A');
    s=s.replace(/IX/g,'B');
    s=s.replace(/XL/g,'H');
    s=s.replace(/XC/g,'J');
    s=s.replace(/CD/g,'E');
    s=s.replace(/CM/g,'F');
    console.log(s)
    let res = 0;

    for(let i = 0;i<s.length;i++){
        res+=mapObj[s[i]]
    }

    return res


};
// @lc code=end

最长公共前缀

/*
 * @lc app=leetcode.cn id=14 lang=javascript
 *
 * [14] 最长公共前缀
 */

// @lc code=start
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let min =strs[0].length ;
    let res=true;
    strs.forEach((item,index)=>{
        if(item[0]!==strs[0][0]){
            res =  false
        }
        let temp = twoSame(item,strs[0])||twoSame(strs[0],item)
        if(temp<min){
            min = temp
        }


    })

    return res?strs[0].slice(0,min):""
};

const twoSame=(s1,s2)=>{
    let temp = ""
    for(let i=0;i<s1.split("").length;i++){
        let item = s1.split("")[i];
        temp+=  item;
        if(s2.indexOf(temp)===-1){
            return i
        }  
    }
}

// @lc code=end

TIP

Accepted 124/124 cases passed (108 ms) Your runtime beats 7.49 % of javascript submissions Your memory usage beats 5.01 % of javascript submissions (47.2 MB)

有效的括号

/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s.length % 2 !== 0) return false
    let arr = s.split("")
    let leftArr = ["(", "{", "["];
    let temp = [];
    for (let i = 0; i < arr.length; i++) {
        if (leftArr.includes(arr[i]))
            temp.push(arr[i]);
        else {
            if (arr[i] === ")") {
                let r = temp.pop();
                if (r !== "(") {
                    return false
                }
            }
            if (arr[i] === "}") {
                let r = temp.pop();
                if (r !== "{") {
                    return false
                }
            }
            if (arr[i] === "]") {
                let r = temp.pop();
                if (r !== "[") {
                    return false
                }
            }
        }
    }


    return temp.length > 0 ? false : true
};
// @lc code=end

TIP

time 86.76% memory 32.67%

合并两个有序链表

/*
 * @lc app=leetcode.cn id=21 lang=javascript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * 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(list1, list2) {
    if(list1 === null && list2 === null) return null;
    let l1 = [],l2 =[];
    while(list1!==null){
        l1.push(list1.val);
        list1 = list1.next
    }
    while(list2!==null){
        l2.push(list2.val);
        list2 = list2.next
    }

    let res =[...l1,...l2].sort((a,b)=>a-b)
    let head = new ListNode(res[0]);
    let resList = head;
    for(let i=1;i<res.length;i++){
        resList.next = new ListNode(res[i]);
        resList = resList.next
    }
    
    return head
};
// @lc code=end

TIP

js sort方法默认按字母顺序排，排序数字需要传递方法

26.删除有序数组中的重复项

/*
 * @lc app=leetcode.cn id=26 lang=javascript
 *
 * [26] 删除有序数组中的重复项
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let res = [...new Set(nums)]
    for(let i = 0;i<res.length;i++){
        nums[i] = res[i]
    }
    return res.length
};
// @lc code=end

27.移除元素

/*
 * @lc app=leetcode.cn id=27 lang=javascript
 *
 * [27] 移除元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {

    for(let i=0;i<nums.length;i++){

        if(nums[i]===val){
            nums.splice(i,1)
            i--;
        }
    }
    return nums.length
};
// @lc code=end

TIP

数组的splice操作会改变原数组;另外使用oldArr.splice(0,0,...newArr)可以合并数组

35.搜索插入位置

/*
 * @lc app=leetcode.cn id=35 lang=javascript
 *
 * [35] 搜索插入位置
 */

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

        return len
    
};
// @lc code=end

58.最后一个单词的长度

/*
 * @lc app=leetcode.cn id=58 lang=javascript
 *
 * [58] 最后一个单词的长度
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    let a = s.split(" ");
    a = [...new Set(a)];
    return a[a.length-1]?a[a.length-1].length:a[a.length-2].length
};
// @lc code=end

TIP

time:93.82% memory 38.49%

66.加一

/*
 * @lc app=leetcode.cn id=66 lang=javascript
 *
 * [66] 加一
 */

// @lc code=start
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    // return(Number(digits.toString().replaceAll(",",""))+1).toString().split('')
    let sub=-1 ;
    //19999
    for(let i=digits.length-1;i>=0;i--){
        if(digits[i]!==9){
            sub =i
            break;
        }
    }
    if(sub!==-1){
        digits[sub]+=1;
        for(let j =sub+1;j<digits.length;j++){
            digits[j] = 0;
        }
    }
else{
    for(let k=0;k<digits.length;k++){
        digits[k] = 0
    }
    digits.unshift(1);

}

return digits
};
// @lc code=end

TIP

time:87.06% memory 38.01%

67.二进制求和

/*
 * @lc app=leetcode.cn id=67 lang=javascript
 *
 * [67] 二进制求和
 */

// @lc code=start
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    // const aA = parseInt(a,2);
    // const bA = parseInt(b,2);
    // return (aA+bA).toString(2)

    let arrA  = a.split("");
    let arrB = b.split("");

    let lenA = arrA.length;
    let lenB = arrB.length;
    let len =(arrA.length>arrB.length)?arrA.length:arrB.length;
    if(len===arrA.length){
        for(let j = 0;j<len-lenB;j++){
            arrB.unshift(0)
        }
    }else{
        for(let j = 0;j<len-lenA;j++){
            arrA.unshift(0)
        }
    }

    let arrR = new Array(len);
    for(let i=len-1;i>=0;i--){
        let tempa = parseInt(arrA[i])||0;
        let tempb = parseInt(arrB[i])||0;
        arrR[i] = tempa+tempb
    }
    let flag =false;
    for(let i=len-1;i>=0;i--){
        if(flag){
            arrR[i]+=1;
            flag =false;
        }
        if(arrR[i]>=2){
            arrR[i] = arrR[i] - 2;
            flag =true
        }
    }

    if(flag){
        arrR.unshift(1)
    }



   return arrR.toString().replace(/,/g,"")

};
// @lc code=end

TIP

好复杂
Accepted 294/294 cases passed (64 ms) Your runtime beats 77.13 % of javascript submissions Your memory usage beats 21.52 % of javascript submissions (43.2 MB)

67 x-的平方根

/*
 * @lc app=leetcode.cn id=69 lang=javascript
 *
 * [69] x 的平方根 
 */

// @lc code=start
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    // return Math.floor(Math.pow(x,0.5))
    if(x<1){
        return 0
    }
    if(x===4){return 2}

    if(x<4){
        return 1
    }


    for(let i =2;i<x;i++){
        if(x/i<i){
            return i-1
        }
    }

};
// @lc code=end

TIP

不如调用Math的方法

70.爬楼梯

/*
 * @lc app=leetcode.cn id=70 lang=javascript
 *
 * [70] 爬楼梯
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    // let res =[ 0,1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
    //      144, 233, 377, 610, 987, 1597, 2584, 4181,
    //       6765, 10946, 17711, 28657, 46368, 75025,
    //        121393, 196418, 317811, 514229, 832040,
    //         1346269, 2178309, 3524578, 5702887,
    //          9227465, 14930352, 24157817, 39088169,
    //           63245986, 102334155, 165580141,
    //            267914296, 433494437, 701408733, 
    //            1134903170, 1836311903][n];
    // return res;

    let arr = [1,2];
    for(let i=2;i<n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1]




    }
// @lc code=end

83.删除排序链表中的重复元素

/*
 * @lc app=leetcode.cn id=83 lang=javascript
 *
 * [83] 删除排序链表中的重复元素
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    
    if(head===null) return null;
    let arr =[];
    while(head!==null){
        arr.push(head.val);
        head = head.next;
    }
    arr = [...new Set(arr)];

    let resHead = new ListNode(arr[0])
    let res = resHead;
    for(let i=1;i<arr.length;i++){
        res.next = new ListNode(arr[i]);
        res = res.next
    }
    return resHead;


};
// @lc code=end

88.合并两个有序数组

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @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) {
    for(let i=m;i<(m+n);i++){
        nums1[i] = nums2[i-m];
    } 
    nums1 = nums1.sort((a,b)=>{return a-b})
};
// @lc code=end

二叉树

递归

//前中后序排序
const preOrder =root=>{
    if(!root) return
    console.log(root.val);
    preOrder(root.left);
    preOrder(root.right);
}
const inOrder =root=>{
    if(!root) return
    preOrder(root.left);
    console.log(root.val);
    preOrder(root.right);
}

const postOrder =root=>{
    if(!root) return
    preOrder(root.left);
    preOrder(root.right);
    console.log(root.val);
}

#