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

LiuTian
  • 27

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"

回复
阅读 3.6k
12 个回答
✓ 已被采纳

解决第一个问题

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

  • 判断大小的算法
  • 在数组中找到最大一个的算法
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];
}

第一题

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

我也来一发第一题吧:

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

我寻思着第一题不就是一个 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]
}

何必还转过去转过来呢?

功底一塌糊涂,连楼上大佬的代码都看不懂😭

// 1
var versionNo = ["2.1.4.5", "3.1.5", "3.1.0.6", "2.2", "1.9.9"];

while (versionNo.length > 1) {
    versionNo = versionNo
        .filter(x => x.substring(0, 1) == Math.max(...versionNo.map(v => v.substring(0, 1))))
        .filter(x => x.length === Math.max(...versionNo.map(v => v.length)))
        .map((x,_,arr) => (arr.length > 1 && x.length > 1 ? x.substring(2) : x));
}
console.log(versionNo[0]);


// 2
var str = "a,b,c,d,e,f,g,a,b,c,a,a,b,b,a,a,t";

var sortedStr = str.split(",").sort();
var reversedStr = sortedStr.reverse();
console.log(
    sortedStr[
        Math.round(
            Math.max(...Array.from(new Set(sortedStr)).map(c => sortedStr.indexOf(c) + reversedStr.indexOf(c))) / 2
        )
    ]
);
  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];
}
  1. 取最多出现频率的字符
// 考虑到有可能出现频率一样,所以返回的数组
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])))
}
A_way
  • 3
新手上路,请多包涵

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

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);
༨ꫛꪝᝰ_ۣ
  • 2
新手上路,请多包涵

第二题

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));

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

mfevu32o
  • 2
新手上路,请多包涵

第一题

/**
 * 解题思路
 * 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)

第一题:(补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遍历下即可

宣传栏