银泰百货笔试-前端

算法两个题，

1. 给出最长公共子序列的长度的函数，要求空间都复杂度为O(min(m,n)) ,时间复杂度为O(mn)

function lcs(str1,str2){
    let dp=new Array(str2.length+1).fill(0)
    for(let i=1;i<=str1.length;i++){
        let pre=0
        for(let j=1;j<=str2.length;j++){
            let temp=dp[j]
            dp[j]=str1[i-1]==str2[j-1]?pre+1:Math.max(dp[j-1],dp[j])
            pre=temp
        }
    }
    return dp[str2.length]
}

1. 给出整数数组输出最大值的字符串，如[2，20，23，4，8],输出 '8423220'

function findLargestNumber(nums) {
  const sortedNums = nums.map(String).sort((a, b) => {
    const option1 = a + b;
    const option2 = b + a;
    return option2.localeCompare(option1);
  });

  return sortedNums.join("");
}

const nums1 = [2, 20, 23, 4, 8];
const nums2 = [2, 20, 23, 4, 8, 301, 30, 311, 3];
console.log(findLargestNumber(nums1)); // 输出 '8423220'
console.log(findLargestNumber(nums2)); // 输出 '8433113030123220'