程序员面试金典---16

变为词组

思路：

哈希模拟

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
	// {'aet':["ate","eat","tea"]}
    let hash = new Map()
    // 循环
    for(let item of strs){
        // 字符串排序
        const temp = item.split('').sort().join('')
        // 如果有了
        if(hash.has(temp)){
            // 把这个往value里面push
            hash.get(temp).push(item)
        }else{
        	// 没有就设置这个
            hash.set(temp, [item])
        }
    }
    // 返回value，需要解构
    return [...hash.values()]
};

搜索旋转数组

思路：

• 分两段递增
• 两段上二分搜索
• 先左后右，为了最小索引

var search = function(arr, target) {

    // 二分搜索写成模板方便调用，查找左边界的二分搜索
    var biSearch = function(left, right){
        while(left <= right){
            let mid = left + ((right - left)>>1);
            if(arr[mid] >= target){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return arr[left]===target? left : -1;
    }

    // 找到中间的断点区分两段
    let point = 0
    for(let i = 0; i < arr.length-1;i++){
        if(arr[i] <= arr[i+1]){
            point++;
        } else break;
    }
    // 左边进行二分搜索
    let leftRes = biSearch(0, point);
    if(leftRes!== -1) return leftRes; // 左边找到了就返回
    else { // 左边没找到就找右边
        let rightRes = biSearch(point+1, arr.length -1)
        return rightRes;
    }

}