第七天华为机考练习（JavaScript node）

注：华为机试和剑指offer的JavaScript Node的书写方式不同，剑指offer只需学核心代码然后return，华为机试需要自写输入输出，输出console就行。leetcode不用管输入输出。

1.leetcode 1071：字符串的最大公因子

https://leetcode.cn/problems/greatest-common-divisor-of-strings/

对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 X 能除尽 str2 。

/**

 * @param {string} str1

 * @param {string} str2

 * @return {string}

 */

var gcdOfStrings = function(str1, str2) {

    //欧几里得算法

   function gcd(max,small){

       if(!(max%small)) return small

       return gcd(small,max%small)

   }

    //如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串（注意拼接顺序不同），那么str1和str2一定存在符合条件的字符串 X。

    if(str1+str2!==str2+str1) return ''

    return str2.substring(0,gcd(str1.length,str2.length))

};

2.leetcode 面试题 17.08： 马戏团人塔（技巧性很强，比较难）

https://leetcode.cn/problems/circus-tower-lcci/

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

/**

 * @param {number[]} height

 * @param {number[]} weight

 * @return {number}

 */

var bestSeqAtIndex = function(height, weight) {

    //二分查找

    function binarySearch(arr,key){

        let left = 0, right = arr.length-1

        while(right>=left){

            let mid=Math.floor((left+right)/2)

            if(key>arr[mid].weight){

                left=mid+1

            }else if(key<arr[mid].weight){

                right=mid-1

            }else if(key==arr[mid].weight){

                return mid

            }

        }

        return left

    }

    //对象数组按照身高升序,相同身高降序排列

    let objArr = []

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

        objArr.push({height:height[i],weight:weight[i]})

    }

    objArr.sort( (x,y) => { return x.height-y.height||y.weight-x.weight })

    let dp = [objArr[0]]

    for(let obj of objArr) {

       dp[dp.length-1].weight<obj.weight?dp.push(obj):dp[binarySearch(dp,obj.weight)]=obj

    }

    return dp.length

};