leetcode 177场周赛题解

ACK

发布于 2020-02-25 15:05:34

4220

发布于 2020-02-25 15:05:34

文章被收录于专栏：flytam之深入前端技术栈

比赛链接

第一题：日期之间隔几天

我偷懒了。直接用js的Date对象求时间戳

/**
 * @param {string} date1
 * @param {string} date2
 * @return {number}
 */
var daysBetweenDates = function(date1, date2) {
    var date1 = new Date(date1).getTime();
    var date2 = new Date(date2).getTime();
    var x = Math.abs(date1 - date2);
    return x / (24 * 60 * 60 * 1000);
};

第二题验证二叉树

思路：这个题虽然说是二叉树，不过和常规的二叉树题没啥关系，通过观察题目给上的不符合条件的输入样例的二叉树可以知道有3种情况不符合 1、一个节点被多于2个的节点同时指。也就是说这个节点的值在输入的leftChild和rightChild数组中出现超过1次

2、互相指的情况。也就是leftChild[leftChild[i]] === i 或者 rightChild[rightChild[i]] === i

3、出现两个根节点。根节点就是一个节点在两个数组中都没出现（也就是没被指），但是它的位置上却非-1，指向了别人

var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
    var leftMap = {};
    var rightMap = {};

    for (let i = 0; i < leftChild.length; i++) {
        if (leftChild[i] > -1 ) {
            leftMap[leftChild[i]] = i;
        }
        
        if (rightChild[i]>-1) {
            rightMap[rightChild[i]] = i;
        }
       
    }
    let flag = false
    for (let i = 0; i < leftChild.length; i++) {
        // 1
        if (rightMap[leftChild[i]]!==undefined) {
            return false
        }
        // 2
        if (leftChild[i] >-1 &&leftChild[leftChild[i]] === i) {
            return false
        }
        if (rightChild[i] >-1 &&rightChild[rightChild[i]] === i) {
            return false
        }
        // 3
        if (leftChild[i]!== -1 || rightChild[i]!== -1) {
            if (leftMap[i] === undefined && rightMap[i]===undefined) {
                if (flag) {
            
                    return false
                }
                flag = true
            }
        }
    }
    return true

};

[第三题最接近的因数]（https://leetcode-cn.com/problems/closest-divisors/）

思路：两个数尽可能接近，并且乘积等于num+1、num+2。直接对num+1、num+2开根号取整，双指针移动，找到第一个符合条件的num+1/num+2，再对比就可以了。

var closestDivisors = function(digits) {

    var a1 = Math.floor(Math.sqrt(digits+1))
    
    var a2 = Math.floor(Math.sqrt(digits+2))


     let left = a1;
     let right = a1;
 
    let left2 = a2;
     let right2 = a2;

     let min = null;
     let result = null
 
     while (true) {
        if (min!==null && (Math.abs(right-left) > min || Math.abs(right2-left2) > min)) {
        
            break
        }


         if (left * right === digits + 1) {
             if (!min || right-left < min) {
                 min = right - left
                 result = [left,right]
                 // 退出循环的条件
                 break
             } 
         }
 
         if (left2 * right2 === digits + 2) {
            if (!min || right2-left2 < min) {
                min = right2 - left2
                result = [left2,right2]
                // 退出循环的条件
                break
            } 
        }

         if (left * right > digits + 1) {
             left--
         } else if (left * right < digits+1 ) {
             right++
         }

         if (left2 * right2 > digits + 2) {
            left2--
        } else if (left2 * right2 < digits+2 ) {
            right2++
        }
     }

     return result
 };

第四题形成三的最大倍数

思路：题目说数可能很大，能被3整除的数，常识可知道每一位加起来也能被3整除。对原数组大到小排序，各位求和，除以3。分3种情况 1、直接能被整除。就是答案了 2、余数是1。从后往前找余数是1的位，去掉改位就是答案。找不到余数是1的话，从后往前找2个余数是2的，去掉也是答案。找不到就是没有结果了 3、余数是2。类似3，不过是先找余数是2，再找两个余数是1。最后注意全0的情况。

var largestMultipleOfThree = function(digits) {
  
 function process() {
    digits.sort((a,b) => b-a)

    const sum = digits.reduce((sum,item) => sum+item,0)
 
    const a = sum % 3
 
    if (a === 0) {
        return digits.join("")
    }
 
    if (a===1) {
     // planA 后往前找一个余1的
         for (let i=digits.length-1;i>=0;i--) {
             if (digits[i]%3 === 1) {
                 // 去掉这个数
                 digits.splice(i,1)
                 return  digits.join("")
             }
         }
         // planB 找两个余2
         // index
         let count = 0
         for (let i=digits.length-1;i>=0;i--) {
             if (digits[i]%3 === 2) {
                 // 去掉这个数
                 digits.splice(i,1)
                 count++
                 if (count===2) {
                     return digits.join("")
                 }
             }
         }
         return ""
 
    }
 
    if (a===2) {
     for (let i=digits.length-1;i>=0;i--) {
         if (digits[i]%3 === 2) {
             // 去掉这个数
             digits.splice(i,1)
             return  digits.join("")
         }
     }
     // planB 找两个余1
     // index
     let count = 0
     for (let i=digits.length-1;i>=0;i--) {
         if (digits[i]%3 === 1) {
             // 去掉这个数
             digits.splice(i,1)
             count++
             if (count===2) {
                 return digits.join("")
             }
         }
     }
     return ""
    }
 }
 let result =process()

 if (/^(0)+$/.test(result)) {
    return "0"
 }
 return result
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度