JS功底好的大佬帮忙解两道题

Question

1..数组内多个版本号中找出版本号最高的一项
var versionNo = ['2.1.4.5','3.1.5','3.1.0.6','2.2','1.9.9'];

2..找出字符串中出现频率最高的字符
var = str = "a,b,c,d,e,f,g,a,b,c,a,a,b,b,a,a,t"

Answer 1

解决第一个问题

解决第一个问题是在找到所有元素中最大的一个，这里需要明确：

• 判断大小的算法
• 在数组中找到最大一个的算法

2021-10-15 更新

由于测试用例每段版本都是 1 位数字，所以原来的代码忽略了一些情况，造成 BUG

• 位运算是按 32 位有符号整数进行运算，需要注意最高位为 1 的情况
• 字符串比较和数值比较结果不会一样，但只有 1 位数字时候，结果相同 😂

下面的代码改了如下几处：

• verstionToNumber()，处理第一段大于 127 会变负数的问题
• numberToVersion()，处理第一段大于 127 转换回来会是负数的问题
• compareVersion()，只是加了注释，没改代码
• maxVersion3()，.split() 后面加了个 .map() 来把字符串转成数字

初步想法

因为版本号都是数字，如果能把版本号的各段组合成一个大整数，那就可以使用 Math.max() 来找最大值，同时解决上述两个问题。要组成最大整数，需要一些限制：

• 版本号最多 4 段
• 每段不大于 255

这样的话，4 段 8-bit 版本号正好可以通过位运算组成 32-bit 整数。（题上没给条件，所以如果实际不符合上述条件，就不能采用这种方法。）

先写个把版本号转成整数的函数（当然可以直接在大过程中写代码，不过基于模块化的思想，写个函数来干这件事比较好）

const versionToNumber = (() => {
    const shifts = [
        // 如果 n 第 8 位是 1，比如 0xd3(211)，
        // n << 24 会变成 -754974720。位运算会按 32 位有符号整数运行，但数学运算不会……
        // 所以改成 (n << 23) * 2。乘以 2 相当于左移 1 位。
        n => (n << 23) * 2,
        n => n << 16,
        n => n << 8,
        n => n
    ];

    return function (ver) {
        return ver
            // 分段
            .split(".")
            // 将每段转成整数（255 以内）
            .map(v => parseInt(v, 10))
            // 通过位运算组成较大整数（32 位）
            .reduce((r, n, i) => r + shifts[i](n), 0);
    };
})();

版本号转成整数之后可以用 Math.max() 找出来最大的

const maxVersion = Math.max(...versionNo.map(versionToNumber));
// 50398464 ⇐ "3.1.5"

现在的问题是，拿到的是一个数，而不是版本字符串，还得转换回来……倒是也不难

function numberToVersion(num) {
    // 最高位是 1 的情况，右移会是负数（最高位仍然是 1），
    // 所以右移 24 位的时候仍然需要跟 0xff 相与
    return [num >> 24 & 0xff, num >> 16 & 0xff, num >> 8 & 0xff, num & 0xff]
        .join(".")
        .replace(/(?:\.0)*$/, "");   // 最后把末尾多余的 0 去掉
}

有了两个工具函数，找最大版本号的函数就是：

function maxVersion1(versions) {
    const max = Math.max(...versions.map(versionToNumber));
    return numberToVersion(max);
}

更进一步

把版本转成数字也就算了，拿到之后还要转回来，很伤。可以不转不？

如果有一个函数，可以从一个对象按条件进行查找就好了。这个函数当然可以用循环或者 reduce 自己写，不过 Lodash 中有现成的叫 _.maxBy()，不妨直接拿来用

import _ from "lodash";   // 如果是网页可以通过 <script> 引入

function maxVersion2(versions) {
    return _(versions)
        .map(ver => [ver, versionToNumber(ver)])  // 把版本转成 ["3.1.5", 50398464] 这样的数组
        .maxBy(it => it[1])[0];  // 找出来最大的之后取 [0] 就是字符串的版本号
}

解除限制

上面的算法都是基于一开始提出来的两个约束。如果不想受此约束，是否可以用 .maxBy() 来实现呢？.maxBy() 需要从对象中找到一个数值来进行比较，但是我们的版本号需要分段多次比较，显然 .maxBy() 不行，得自己写比较算法。

思路是写一个 compareVersion(a, b)，如果 a 小于 b ，返回 -1，大于返回 1，等于返回 0。考虑到有段长不一样的情况，用 0 补足来进行比较（当然也可以不补足，直接按长度判断，代码略复杂一些）。

下面的 compareVersion() 比较的是两个数组，也就是像 "3.1.5".split(".") 之后的结果。不直接比较版本字符串，是想把拆分这一步放前面，避免每次比较都要先进行一次拆分，减少重复劳动。

// compareVersion 的两个参数数组，
// 里面都应该是数字才能直接用 < 或 > 来比较值大小，
// 如果是字符串，会和预期的数值比较结果不同
function compareVersion(a, b) {
    const len = Math.max(a.length, b.length);
    for (let i = 0; i < len; i++) {
        const va = a[i] ?? 0;  // 用 0 补足
        const vb = b[i] ?? 0;
        if (va < vb) { return -1; }
        if (va > vb) { return 1; }
    }
    return 0;
}

然后就是常规的循环找最大值了

function maxVersion3(versions) {
    if (versions.length < 2) {
        return versions[0];
    }

    // 拆分之后忘了转成数字，补上
    const splitVersions = versions.map(ver => ver.split(".").map(s => parseInt(s, 10)));
    let max = splitVersions[0];
    for (let i = 0; i < splitVersions.length; i++) {
        if (compareVersion(max, splitVersions[i]) < 0) {
            max = splitVersions[i];
        }
    }
    return max.join(".");
}

第二个问题

第二个问题的解决办法也很多，最直接的想法就是写个 map 来计数：

function findMostChar(str) {
    const chars = str.split(",");
    // 遍历计数
    const map = chars.reduce(
        (m, c) => {
            m[c] ??= 0;
            m[c]++;
            return m;
        },
        {}
    );

    // 用 Lodash 找出计数最多的那一个
    return _(map).entries().maxBy(it => it[1])[0];
}

上面的处理办法易懂，但是至少需要遍历两次，可以压缩到一次遍历中

function findMostChar2(str) {
    const map = {};
    const chars = str.split(",");
    let maxChar;
    let maxCount = 0;
    for (let i = 0; i < chars.length; i++) {
        const c = chars[i];
        const count = map[c] = (map[c] ?? 0) + 1;
        if (count > maxCount) {
            maxCount = map[c];
            maxChar = c;
        }
    }
    return maxChar;
}

当然也可以用一个 reduce() 来解决

function findMostChar3(str) {
    return str.split(",")
        .reduce(
            ([mc, mcount, map], c) => {
                const count = map[c] = (map[c] ?? 0) + 1;
                return (count > mcount)
                    ? [c, count, map]
                    : [mc, mcount, map];
            },
            [" ", 0, {}]
        )[0];
}

Answer 2

第一题

versionNo.reduce((pre, item) => {
    let pres = pre.split('.')
    let items = item.split('.')
    let i = 0
    while(pres[i] !== undefined && items[i] !== undefined){
        if(pres[i] == items[i]){
            i++
        }else{
            return Number(pres[i]) > Number(items[i]) ? pre : item
        }
    }
    return items.length > pres.length ? item : pre
}) 

第二题

str.split(',').reduce((o, item) => {
    o[item] = ~~o[item] + 1
    if(o[item] > o._max){
      o._max = o[item]
      o._maxs = item
    }
    return o
}, {_max: 0, _maxs: ''})._maxs

Answer 3

我也来一发第一题吧：

const versionNo = ['2.1.4.5', '3.1.5', '3.1.0.6', '2.20', '1.9.9'];

function getLatestVersion(versions) {
  return versions
    .map((ver) => {
      return {
        original: ver,
        next: ver
          .split('.')
          .map((v) => v.padStart(2, '0'))
          .join('')
          .padEnd(8, 0),
      };
    })
    .sort((a, b) => a.next.localeCompare(b.next))
    .reverse()[0].original;
}

const latest = getLatestVersion(versionNo);

console.log(latest); // 3.1.5

Answer 4

我寻思着第一题不就是一个 sort()[0] 的事儿？

const max = arr => {
    const v = s => s.match(/\d+/g).reduce((p, c) => p * 255 + +c)
    return arr.sort((a, b) => v(b) - v(a))[0]
}

何必还转过去转过来呢？

Answer 5

1. 取最大版本号：

function maxVersion(versions) {
  return versions.sort((a, b) => {
    const v1 = a.split('.');
    const v2 = b.split('.');
    for (let i = 0; i < v1.length; i += 1) {
      //  如果 v2[i] 为 undefined，那么 v1 更大
      if (v2[i] === undefined) {
        return -1;
      }
      if (v1[i] === v2[i]) {
        //  版本一致
        continue
      } else if (v1[i] > v2[i]) {
        return -1;
      } else {
        return 1
      }
    }
    return 0;
  })[0];
}

2. 取最多出现频率的字符

// 考虑到有可能出现频率一样，所以返回的数组
function maxChars(text) {
  // 得到不同字符的次数
  const o = text.split(',').reduce((a, b) => ({ ...a, [b]: (a[b] || 0) + 1}), {});
  // 直接取得出现频率最高的资源的字符
  return Object.keys(o).filter(k => o[k] === Math.max(...Object.keys(o).map(k => o[k])))
}

Answer 6

https://leetcode-cn.com/probl... 第一题建议你去力扣上面找答案，也可以看看人家的讲解

Answer 7

第二题和大家想法差不多，但是第一题我之前都是这么直接判断的

var versionNo = ['2.1.4.5','3.1.5','3.1.0.6','2.2','1.9.9'];
var max = '0.0.0.0';
versionNo.forEach(e => {
  if (e > max) {
    max = e
  }
});
console.log(max);

Answer 8

第二题

function findMax (str) {
  let max = 0, obj;
  str.split(',').reduce((pre, next) => {
    if (next in pre) {
      pre[next]++
      if (pre[next] > max) {
        max = pre[next]
        obj = next
      }
    } else {
      pre[next] = 1
    }
    return pre
  }, {})

  return obj
}

console.log(findMax(str));

Answer 9

versionNo.slice().sort().pop()

Answer 10

第一题

/**
 * 解题思路
 * 1.直接遍历数组，按字典序比较字符串，筛选最大值
 */
var arr = ['2.1.4.5', '3.1.5', '3.1.0.6', '2.2', '1.9.9']
let max = ''
arr.forEach((item) => {
  if (max < item) {
    max = item
  }
})
console.log(max)

第二题

/**
 * 解题思路
 * 1.将字符串转换为数据
 * 2.将数组按字典序排序
 * 3.遍历数组，记录当前字符遍历次数
 * 4.收集遍历次数最多的一个为出现次数最多的字符
 */
var str = 'a,b,c,d,e,f,g,a,b,c,a,a,b,b,a,a,t'
var arr = str.split(',')
arr.sort()

let maxCount = 0
let maxLetter = ''
let curCount = 0
let curLetter = ''

arr.forEach((letter) => {
  if (curLetter != letter) {
    curLetter = letter
    curCount = 0
  }
  curCount++
  if (maxCount < curCount) {
    maxCount = curCount
    maxLetter = curLetter
  }
})

console.log(maxCount, maxLetter)

Answer 11

第一题：（补0逻辑已完善）
单段补全成长度最长的number(1.2.31.4 ->100200031400)，然后拼接起来比数字就是了，同时还要考虑版本号是从大到小的，长度再长，首位不够格就够不上老大。

默认首位的最大的版本，后面依次是二级版本，三级版本...以此类推
默认单段版本号最长到4位，可传参进行修改

function getMaxVersion(arr: string[], maxVersionPieceLen = 4) {

    const version2Number = (version: string[]) => Number(version.map(_ => `${Array(maxVersionPieceLen - `${_}`.length).fill("0").join("")}${_}`).join(""))

    return arr.reduce((pre, cur, index) => {
        const curVersion = cur.split('.');
        const preVersion = pre.split('.');

        //首位大直接return
        if (Number(curVersion[0]) > Number(preVersion[0])) {
            return cur;
        }

        //转数字比较，默认单段最大4位，可根据需要传参
        return version2Number(curVersion) > version2Number(preVersion) ? cur : pre;

    }, arr[0])

}

第二题：
转成map/Object,key为字符串名，value为key的计数，统计完后转entry遍历下即可