Netherspite

排序

147. Insert Sort List

Description

Sort a linked list using insertion sort.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
    if(head === null) return null;
    let result = new ListNode(-Infinity), p = result, prev = null;
    while(head !== null) {
        while(result !== null && head.val > result.val) {
            prev = result;
            result = result.next;
        }
        let temp = head.next;
        prev.next = head;
        head.next = result;
        head = temp;
        result = p;
        prev = null;
    }
    return p.next;
};

21. Merge Two Sorted Lists && 23. Merge k Sorted Lists && 148. Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.

Solution

var mergeTwoLists = function(l1, l2) {
    let node = new ListNode(), p = node;
    while(l1 !== null && l2 !== null) {
        if(l1.val <= l2.val) {
            node.next = l1;
            l1 = l1.next;
        }else {
            node.next = l2;
            l2 = l2.next;
        }
        node = node.next;
    }
    if(l1 === null) {
        node.next = l2;
    }else {
        node.next = l1;
    }
    return p.next;
};
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if(head === null || head.next === null) return head;
    let fast = head, slow = head;
    while(fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    fast = slow;
    slow = slow.next;
    fast.next = null;
    let l1 = sortList(head),
        l2 = sortList(slow);
    return mergeTwoLists(l1, l2);
};
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if(lists.length === 0) return null;
    if(lists.length === 1) return lists[0];
    return lists.reduce(mergeTwoLists);
};

41. First Missing Positive

Description

Given an unsorted integer array, find the smallest missing positive integer.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    sort(nums);
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] !== i + 1) return i + 1;
    }
    return nums.length + 1;
};
function sort(nums) {
    let n = nums.length;
    for(let i = 0; i < n; i++) {
        let temp = nums[i];
        while(temp !== i + 1) {
            if (temp <= 0 || temp > n || temp === nums[temp - 1])
                break;
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
            temp = nums[i];
        }
    }
}

75. Sort Colors

Description

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Solution

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let i = 0, j = nums.length - 1;
    for(let k = 0; k < j + 1;) {
        if(nums[k] === 0) {
            [nums[i], nums[k]] = [nums[k], nums[i]];
            i++;
            k++;
        }else if(nums[k] === 2) {
            [nums[j], nums[k]] = [nums[k], nums[j]];
            j--;
        }else k++;
    }
};

贪心

763. Partition Labels

Description

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Solution

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let last = {};
    for(let i = 0; i < S.length; i++) {
        last[S[i]] = i;
    }
    let j = 0, prev = 0, result = [];
    for(let i = 0; i < S.length; i++) {
        j = Math.max(j, last[S[i]]);
        if(i === j) {
            result.push(i - prev + 1);
            prev = i + 1;
        }
    }
    return result;
};

984. String Without AAA or BBB

Description

Given two integers A and B, return any string S such that:

  • S has length A + B and contains exactly A 'a' letters, and exactly B 'b' letters;
  • The substring 'aaa' does not occur in S;
  • The substring 'bbb' does not occur in S.

Solution

/**
 * @param {number} A
 * @param {number} B
 * @return {string}
 */
var strWithout3a3b = function(A, B) {
    let S = [];
    while(A > 0 || B > 0) {
        let writeA = false;
        let l = S.length;
        if(l >= 2 && S[l - 1] === S[l - 2]) {
            if(S[l - 1] === 'b') writeA = true;
        }else {
            if(A >= B) writeA = true;
        }
        if(writeA) {
            A--;
            S.push('a');
        }else {
            B--;
            S.push('b');
        }
    }
    return S.join('');
}

暴力搜索

46. Permutations

Description

Given a collection of distinct integers, return all possible permutations.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = [], temp = [];
    dfs(nums, temp, result);
    return result;
};
function dfs(nums, temp, result) {
    if(temp.length === nums.length) {
        result.push(temp.slice());
        return;
    }
    for(let i of nums) {
        if(temp.indexOf(i) === -1) {
            temp.push(i);
            dfs(nums, temp, result);
            temp.pop();
        }
    }
}

78. Subsets

Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let sub = function(num) {
        if(num.length === 0) return [];
        let prefix = [[num[0]]],
            post = sub(num.slice(1))
        for(let p of post) {
            prefix.push([num[0]].concat(p));
        }
        return prefix.concat(post);
    }
    return [[]].concat(sub(nums));
};

90. Subsets II

Description

Given a collection of integers that might contain duplicates, nums\, return all possible subsets (the power set).

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    nums.sort((a , b) => a - b);
    let sub = (num) => {
        if(num.length === 0) return [];
        let set = [[num[0]]],
            po = sub(num.slice(1));
        for(let p of po) {
            set.push([num[0]].concat(p));
        }
        return set.concat(po);
    }
    let re = sub(nums),
        set = new Set(re.map(x => x.join(',')));
    return [[]].concat([...set].map(x => x.split(',')));
};

17. Letter Combinations of a Phone Number

Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Solution

/**
 * @param {string} digits
 * @return {string[]}
 */
const nums2Alpha = [
        '', '', 
        'abc',
        'def',
        'ghi',
        'jkl',
        'mno',
        'pqrs',
        'tuv',
        'wxyz',
    ];
var letterCombinations = function(digits) {
    let result = [];
    if(digits.length === 0) return result;
    dfs(digits, 0, '', result);
    return result;
};
function dfs(digits, start, str, result) {
    if(digits.length === start) {
        result.push(str);
        return;
    }
    let cs = nums2Alpha[digits[start].charCodeAt() - '0'.charCodeAt()];
    for(let i = 0; i < cs.length; i++) {
        dfs(digits, start + 1, str + cs[i], result);
    }
}

广度优先搜索

127. Word Ladder

Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Solution

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    const L = beginWord.length;
    let dict = {};
    wordList.forEach(word => {
        for(let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
          	
            let transformations = dict[newWord] ? dict[newWord]: [];
            transformations.push(word);
            dict[newWord] = transformations;
        }
    })
    let queue = [];
    queue.push([beginWord, 1]);
    let visited = {};
    visited[beginWord] = true;
    while(queue.length > 0) {
        let node = queue.shift(),
            word = node[0],
            level = node[1];
        for(let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
            if(dict[newWord]) {
                for(let j = 0; j < dict[newWord].length; j++) {
                    let adj = dict[newWord][j];
                    if(adj === endWord) {
                        return level + 1;
                    }
                    if(!visited[adj]) {
                        visited[adj] = true;
                        queue.push([adj, level + 1]);
                    }
                }
            }
        }
    }
    return 0;
};

 上一页

HTML

 评论