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