LeetCode刷题笔记 - JavaScript（十五）

文章目录

• • 1.剑指 Offer II 033. 变位词组
  • 2.剑指 Offer II 034. 外星语言是否排序
  • 3.剑指 Offer II 035. 最小时间差

剑指 Offer II 033. 变位词组

剑指 Offer II 034. 外星语言是否排序

剑指 Offer II 035. 最小时间差

1.剑指 Offer II 033. 变位词组

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

题目大意：把字符串数组中所有的变位词组放在同一个集合中返回。变位词组就是指字符串由相同字符组成的字符串。

解题思路：基础做法就是将字符串中的字符排序，然后以排序后的字符串为键，值为以当前字符组成的字符串集合。在此之上的优化写法是用计数法替代排序，用O(n)的时间和空间复杂度，优化掉排序的时间复杂度。

代码：

var groupAnagrams = function(strs) {
    let map = new Map();
    for(const str of strs) {
        const arr = new Array(26).fill(0);
        for(const ch of str) {
            arr[ch.charCodeAt() - 'a'.charCodeAt()] ++;
        }
        let temp = "";
        for(let i = 0;i < 26; i++) {
            if(arr[i]) {
                temp += String.fromCharCode(i+97) + arr[i];
            }
        }
        
        if(map.has(temp)) {
            map.get(temp).push(str);
        } else {
            map.set(temp,[str]);
        }
    }
    return [...map.values()];
};
           

2.剑指 Offer II 034. 外星语言是否排序

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

题目大意：将字母的排列顺序打乱，问字符串数组是否按照字母顺序排列。

解题思路：首先，离线处理字符序列。然后枚举字符串，看字符串组是否有按照字符顺序排列。

代码：

var isAlienSorted = function(words, order) {
    const arr = new Array(26).fill(0);
    for(let i = 0; i < order.length; i++) {
        arr[order[i].charCodeAt() - 97] = i;
    }
    let flag;
    for(let i = 1; i < words.length; i++) {
        flag = false;
        for(let j = 0; j < words[i - 1].length && j < words[i].length; j++) {
            const pre = words[i-1][j];
            const cur = words[i][j];
            if(arr[pre.charCodeAt() - 97] < arr[cur.charCodeAt() - 97]) {
               flag = true;
               break;
            } else if(arr[pre.charCodeAt() - 97] > arr[cur.charCodeAt() - 97]) {
                return false;
            }
        }
        if(!flag) {
            if(words[i-1].length > words[i].length) {
                return false;
            }
        }
    }
    return true;
};
           

3.剑指 Offer II 035. 最小时间差

给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

题目大意：求n个时间中的最小时间差。

解题思路：将n个时间排序，则最小时间差必然出现在相邻两个/首位时间中，然后根据鸽巢原理，只有1440中时间情况，当时间的情况超过1440时，则最小时间差为0.

代码：

var findMinDifference = function(timePoints) {
    const n = timePoints.length;
    if(n > 1440) return 0;
    timePoints.sort();
    let pre = getminu(timePoints[0]);
    let ans = pre - getminu(timePoints[n-1]) + 1440;
    for(let i = 1;i < n; i++) {
        const cur = getminu(timePoints[i]);
        ans = Math.min(ans, cur - pre);
        pre = cur;
    }
    return ans;
};

function getminu(time) {
    const zero = '0'.charCodeAt();
    return ((time[0].charCodeAt() - zero) * 10 + time[1].charCodeAt() - zero) *60 + ((time[3].charCodeAt() - zero) * 10 + time[4].charCodeAt() - zero);
}