题解

  • 1 Two Sum
    • Given a number array, find all number pairs that sum to k.
    • O(n) time.
  • 18 4Sum
    • O(n^3) worst time because there might be Theta(n^3) answers.
  • 36 Valid Sudoku
    • Validate a 9x9 sudoku.
    • O(81) time.
  • 128 Longest Consecutive Sequence
    • Given a number array, find the maximum length of a consecutive sequence.
    • O(n) time. Union-find also works.
  • 249 Group Shifted Strings
    • Given a list of strings, sort them according to shifting equivalance classes.
    • O(nk) time, where k is the maximum length of string element.
  • 299 Bulls and Cows
    • 4-digit number guessing game, generate hints (correct numbers & correct places).
  • 325 Maximum Size Subarray Sum Equals k
    • O(n) time. Classical prefix-sum.
  • 438 Find All Anagrams in a String
    • Sliding window, maintain rest character set.
  • 454 4Sum II
    • Given four number arrays, count number of quadruples that sum up to zero.
    • O(n^2) time by count two sums first.
  • 532 K-diff Pairs in an Array
    • Find number of (a,b) pairs in an array that |a-b| is k.
  • 567 Permutation in String
    • Similar to 438.
  • 609 Find Duplicate File in System
  • 939 Minimum Area Rectangle
    • Given (x, y) points, find minimum area of square constructed by four of them.
    • O(n^2) time by checking point pairs as diagonal points. Find rest in hashset.
  • 966 Vowel Spellchecker
    • Implement a dictionary supporting capitalization and vowel corrections.
    • Store normalized representations in a hashset.
  • 1001 Grid Illumination
    • Given lights on a board, shutting off a light will shut down eight lights around it. A light will enlight x axis, y axis and a cross. Finish light shut offs and enlighted or not queries.
    • Sort lights into four classes: x, y, x+y, x-y.
  • 1002 Find Common Characters
    • Find common characters in given words.