LeetCode | Learn for Master - Part 5
  • LeetCode – Flip Game II

    You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

    Write a function to determine if the starting player can guarantee a win.

    For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

    Follow up:
    Derive your algorithm’s runtime complexity.

    [Read More...]
  • Leetcode – Palindrome Permutation

    Given a string, determine if a permutation of the string could form a palindrome.

    For example, “code” -> False, “aab” -> True, “carerac” -> True.

    Hint:

    Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

    Analysis

    A native solution is to generate the permutation of the string, then check whether it is a palindrome. 

    A better solution is suggested from the above hint.

    [Read More...]
  • LeetCode – Logger Rate Limiter

    Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

    Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

    It is possible that several messages arrive roughly at the same time.

    Example:

    Logger logger = new Logger();

    // logging string “foo” at timestamp 1
    logger.shouldPrintMessage(1, “foo”); returns true;

    // logging string “bar”

    [Read More...]
  • LeetCode – Moving Average from Data Stream

    Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

    For example,
    MovingAverage m = new MovingAverage(3);
    m.next(1) = 1
    m.next(10) = (1 + 10) / 2
    m.next(3) = (1 + 10 + 3) / 3
    m.next(5) = (10 + 3 + 5) / 3

    Analysis

    We can use a bounded queue to record the last n integers in the window, and define a variable sumN to record the sum of the numbers in the window.

    Each time when a new number is registered,

    [Read More...]
  • Leetcode – Nim Game

    You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

    Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

    For example, if there are 4 stones in the heap, then you will never win the game: no matter 1,

    [Read More...]
  • Leetcode – Permutations ( Java)

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

    For example,
    [1,2,3] have the following permutations:

     Analysis
     
    I will use an example to illustrate how to generate all the permutation of an array. 
     
    Given a list [1, 2, 3, 4],  all the permutations  consists of the four sets:
    the permutations starts with 1:  {1} + {permutations of array [2, 3, 4]}
    the permutations starts with 2, 
    the permutations starts with 3,
    the permutations starts with 4,
     
    Suppose we have a function called search to generate permutations for the subarray nums[start .. end]. 

    [Read More...]
  • Leetcode – Search for a Range (Java)

    Search for a Range

    Given a sorted array of integers, find the starting and ending position of a given target value.

    Your algorithm’s runtime complexity must be in the order of O(log n).

    If the target is not found in the array, return [-1, -1].

    For example,
    Given [5, 7, 7, 8, 8, 10] and target value 8,
    return [3, 4].

    Analysis:

    This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array. 

    For instance, given a sorted array [1,

    [Read More...]
  • Remove Element from an Array (Java)

    LeetCode – Remove Element

    Given an array and a value, remove all instances of that value in place and return the new length.

    Do not allocate extra space for another array, you must do this in place with constant memory.

    The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

    Example:
    Given input array nums = [3,2,2,3], val = 3

    Your function should return length = 2, with the first two elements of nums being 2.

    Analysis

    This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array

    [Read More...]
  • Remove Duplicates from Sorted Array (Java)

    Leetcode: Remove Duplicates from Sorted Array

    Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

    Do not allocate extra space for another array, you must do this in place with constant memory.

    For example,
    Given input array nums = [1,1,2],

    Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

     Analysis
     

    We defined two indexes: pre and cur.

    [Read More...]
  • Leetcode – Remove Nth Node From End of List (Java)

    Remove Nth Node From End of List

    Given a linked list, remove the nth node from the end of list and return its head.

    For example,

       Given linked list: 1->2->3->4->5, and n = 2.
    
       After removing the second node from the end, the linked list becomes 1->2->3->5.
    

    Note:
    Given n will always be valid.
    Try to do this in one pass.

    Analysis:

    The key to solve this problem is to use two pointers: pre and cur. The pre pointer moves N steps in the first place,

    [Read More...]
Page 5 of 9« First...34567...Last »