刷题笔记3 ​

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length!==t.length) return false
    let map = new Map()
    for (let i=0;i<s.length;i++) {
        (map.has(s[i])) ? map.set(s[i], map.get(s[i])+1) : map.set(s[i], 1);
        (map.has(t[i])) ? map.set(t[i], map.get(t[i])-1) : map.set(t[i], -1);
    }
    for (let item of map) {
        if (item[1]!==0) return false
    }
    return true
};

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let j = 0
    for (let i=0; i<nums.length; i++) {
        if (nums[i]!==0) {
            nums[j] = nums[i]
            j++
        }
    }
    for (let i=j; i<nums.length; i++) {
        nums[i] = 0
    }
    return nums
};

var intersection = function(nums1, nums2) {
    let resultSet = new Set()
    // 将nums2数组转换为Set, 降低时间复杂度O(m*n)->O(n)
    let nums2Set = new Set(nums2)
    // 遍历nums1
    for (let i=0; i<nums1.length; i++) {
        if (nums2Set.has(nums1[i])) {
            resultSet.add(nums1[i])
        }
    }
    // 返回结果
    return Array.from(resultSet)
};

var addTwoNumbers = function(l1, l2) {
    // 1.将链表中的数字存入栈中
    let stack1 = [],
        stack2 = []
    while (l1!==null) {
        stack1.push(l1.val)
        l1 = l1.next
    }
    while (l2!==null) {
        stack2.push(l2.val)
        l2 = l2.next
    }
    // cur为最后返回的链表, 使用num存储进位的数字
    let cur = null,
        num = 0 
    while (stack1.length!==0 || stack2.length!==0) {
        let sum = 0
        if (stack1.length!==0) sum+=stack1.pop()
        if (stack2.length!==0) sum+=stack2.pop()
        sum += num

        let node = new ListNode(sum%10)
        node.next = cur
        cur = node

        num = Math.floor(sum/10)
    }
    
    if (num!==0) {
        let node = new ListNode(num)
        node.next = cur
        cur = node
    }
    return cur

};

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    // 辅助函数: 判断从位置left到位置right能否构成回文串
    function isPalindrome(left, right) {
        while (left<right) {
            if (s[left]!==s[right]) return false
            left++
            right--
        }
        return true
    }
    // 正文
    let left=0,
        right=s.length-1
    while (left<right) {
        if (s[left]!==s[right]) {
            return isPalindrome(left+1, right) || isPalindrome(left, right-1)
        }
        left++
        right--
    }
    return true
};

var isRectangleOverlap = function (rec1, rec2) {
  if (
    rec1[2] <= rec2[0] ||
    rec1[1] >= rec2[3] ||
    rec1[0] >= rec2[2] ||
    rec1[3] <= rec2[1]
  ) {
    return false;
  } else {
    return true;
  }
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */

var backspaceCompare = function(s, t) {
    let backspaceS = 0,
        backspaceT = 0
    let i = s.length-1,
        j = t.length-1
    while (i>=0 || j>=0) {
        // 对i处理
        while (i>=0) {
            if (s[i]==='#') {
                backspaceS++
                i--
            }else if (backspaceS>0) {
                backspaceS--
                i--
            }else {
                break
            }
        }
        // 对j处理
        while (j>=0) {
            if (t[j]==='#') {
                backspaceT++
                j--
            }else if (backspaceT>0) {
                backspaceT--
                j--
            }else {
                break
            }
        }
        // 判断是否相等
        if (s[i]!==t[j]) return false
        i--
        j--
    }
    return true
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function(nums) {
    // 双指针
    let i=0,
        j=nums.length-1
    while (i<j) {
        if (nums[i]%2===0 && nums[j]%2===1) {
            i++
            j--
        } else if (nums[i]%2===0 && nums[j]%2===0) {
            i++
        } else if (nums[i]%2===1 && nums[j]%2===0) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
            i++
            j--
        } else {
            j--
        }
    }
    return nums
};

var sortArrayByParity = function(nums) {
    // 双指针
    let i=0,
        j=nums.length-1
    while (i<j) {
        if (nums[i]%2===1 && nums[j]%2===0) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
        }

        if (nums[i]%2===0) {
            i++
        }
        if (nums[j]%2===1) {
            j--
        }
    }
    return nums
};

var sortArrayByParityII = function(nums) {
    let j = 1
    for (let i=0; i<nums.length; i+=2) {
        if (nums[i]%2===1) {
            // 遍历j, 到达偶数的位置
            while (nums[j]%2===1 && j<nums.length) {
                j+=2
            }
            // 开始交换
            [nums[i], nums[j]] = [nums[j], nums[i]]
        }
    }
    return nums
};