[Leetcode] Remove Duplicates from Sorted Array

Posted on January 6, 2016 by admin

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

Posted on January 6, 2016 by admin

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

Posted on January 6, 2016 by admin

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

Posted on January 6, 2016 by admin

Problem

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

For example, given the following binary tree:

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

Posted on January 3, 2016 by admin

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

Posted on January 1, 2016 by admin

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

Posted on January 1, 2016 by admin

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)

Posted on January 1, 2016 by admin

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

Posted on December 31, 2015 by admin

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 3×3 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

Posted on December 31, 2015 by admin

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每一行的值的时候只需要上一行的信息