[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

[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 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

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

[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/