[Leetcode] Remove Duplicates from Sorted List

Problem

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Analysis

• Use pointer operation
• If next element is repeated, then
• curr.next = curr.next.next
• Else
• curr = curr.next

Code

[Leetcode] Remove Duplicates from Sorted Array

Problem

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

• Keep track of the right positive to write the valid number, it is also the length of the valid numbers
• Keep track of current number
• Write it to the array only when it is different from next number
• Time: O(n)
• Extra space: O(1)

Code

[Leetcode] Minimum Depth of Binary Tree

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Analysis

• Recursive calculate the depth of the tree
• 1 + Math.min(left-tree, right-tree)
• Need to deal with the case when left-tree or right-tree is null
• If left-tree is null, return right-tree
• If right-tree is null, return left-tree
• Time: O(n)
• As it traverses each node once

Code

[Leetcode] Happy Number

Problem

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Analysis

• Since the computation is a recursive process, so that we can recursive check whether a number is a happy number
• We need to maintain a hashset to track whether a number has shown up before
• If yes, then it will not be possible to reach 1 in the future

Code

[Leetcode] Binary Tree Paths

Problem

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Analysis

• Recursive constructing the path in bottom up fashion
• For each node, get its left and right paths recursively, denote them as left and right, then the recursion is
•  (node.val + (each path in left))
• (node.val + (each path in right))
• Time: O(N) where N is the number of nodes in the tree

Code

[Leetcode] 3Sum Cloest

Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Analysis

• Brute force approach
• Enumerate the first, second, third number respectively
• Update the distance compared with the target
• Time: O(n^3)
• Space: O(1)

Code

[Leetcode] Merge Sorted Array

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Analysis

• 题目是把两个sorted的数组合并成一个，这里假设数组1足够大，所以直接合并到数组1
• 记录当前要写入的index，初始值为 m+n-1
• 对两个数组从后往前扫描
• 谁比较大，谁就先写入
• 同时update index
• Time: O(m+n)
• Space: O(1)

Code

Reference
[1] https://leetcode.com/problems/merge-sorted-array/

[Leetcode] Reverse Linked List

Problem 

Reverse a singly linked list.

Analysis

• 这道题就是要把相邻两个node的指针指向反一反，反的过程当中要keep track of next node，不然这时候 node.next 变成前一个节点了
• 所以我们采用两个指针，prev 和 curr 来记录相邻的两个节点
• 反之前，先记录 curr.next, 即 tmp = curr.next 
• 然后可以反了，curr.next = prev
• 然后把prev 和 curr往右移，继续去处理还没反的nodes
• prev = curr
• curr = tmp
• Time: O(n)
• Space: O(1)

Code

[Leetcode] Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis

• 二分搜索 [0,x]
• 若 mid*mid 等于x，或者 (mid*mid<x && (mid+1)*(mid+1)>x), 则返回mid
• 否则若mid*mid < x，则搜索 [mid+1, right]
• 否则若mid*mid > x, 则搜索 [left, mid-1]
• 注意 mid*mid 可能会溢出，要用long类型
• Time: O(log n)
• Space: O(1)

Code

Reference
[1] https://leetcode.com/problems/sqrtx/

[Leetcode] Unique Path II

Problem

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Analysis

• Similar to Unique Path except that we need to decide whether a position has obstacle or not
• If yes, the number of ways to it is 0

Code

[Leetcode] Unique Path

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Analysis

• 对于每一格，有两种到达它的方式，即从左边，或者从上边
• 所以 count[i][j] = count[i-1][j] + count[i][j-1]
• Time: O(n^2)
• Space: O(n^2)
• Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息

Code

[Leetcode] Best Time to Buy and Sell Stock II

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis

• Sum up all possible increase
• Time; O(n)
• Space; O(1)

Code

Reference

[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

[Leetcode] Best Time to Buy and Sell Stock III

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Analysis

• 用一个数组pre记录在第i天或之前完成一个transaction的左右收益
• 用一个数组back记录从第i天或之后开始完成一个transaction的最大收益
• 则完成两个transactions的最大收益为 max(pre[i], back[i])

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

[Leetcode] Best Time to Buy and Sell Stock

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Analysis

• 遍历数组，记录当前最小值，记录当前最大profit
• 当前profit = 当前值 - 当前最小值
• 时间复杂度: O(n)
• 空间复杂度: O(1)

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

[Leetcode] Longest Increasing Subsequence

Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Analysis

• 遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数
• tail 表示当前valid数组的最后一个数， 
• 对于当前读到的数x
• 如果x>tail，则把x append到数组中
• 如果x<valid数组的第一个数，则将其替换为x
• 否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x
• 返回valid数组中有效的数个数

时间复杂度: O(nlogn)

Code

Reference
[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
[2] https://leetcode.com/problems/longest-increasing-subsequence/

[Leetcode] Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis

• 用一个hash表来围护每个数和其对应的index
• 如果有重复的数字，则overwrite， 即保留最后出现的index
• 然后遍历所有的数，如果 （target - 当前数）在哈希表中，且俩数的index不一样，则找到解了
• 复杂度
• Time: O(n)
• Space: O(n)

Code

Reference
[1] https://leetcode.com/problems/two-sum/

[Leetcode] Reverse Words in a String

Problem

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Analysis

• 首先split string by space
• 然后 append word in reverse order
• 注意 如果当前非空，在append下一个word之前，需要append空格

Code

Reference

[1] https://leetcode.com/problems/reverse-words-in-a-string/

[Leetcode] Rotate image

Problem

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Analysis

对于一个n*n的矩阵，可以像剥洋葱一样对每一层进行rotate，一共有n/2层

对于每一层，采用 matrix[i][j] = matrix[n-1-j][i] 进行 in-place的rotation

时间复杂度: O(n^2)
空间复杂度: O(n^2)

Code

[Leetcode] Peek Iterator

Problem:

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Example:

Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Analysis:

Iterator接口只提供了next() 和 hasNext() 函数

• next(), 取下一个元素，同时指针移到下下个元素
• hasNext(), 返回是否还有下一个元素

然后 peek() 函数只取下一个元素，而并不真正移动指针。即，peek如果多次连续被调用，返回的值应该不变 (一直是当前元素)。因此可以用next函数来取下一个元素，并将其cache，所以如果peek多次被调用，只需要返回cache中的值即可。

具体实现如下

• peek()
• 如果cache有效，直接返回cache中的值。
• 否则，调用next函数取下一个元素放在cache中，并将cache设为有效
• next()
• 如果cache有效，则返回cache中的值，并将cache置为失效
• 否则，直接调用next函数
• hasNext()
• 如果cache有效，则直接返回true
• 否则，直接调用hasNext函数

Code:

Reference
[1] https://leetcode.com/problems/peeking-iterator/