Category: Leetcode

bookmark_borderLeetcode笔记（15）Populating Next Right Pointers in Each Node

Posted on by javayu

Given a binary tree

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL Initially, all next pointers are set to NULL

Note:
* You may only use constant extra space.
* You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree,

        1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

        1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Continue reading “Leetcode笔记（15）Populating Next Right Pointers in Each Node”

bookmark_borderLeetcode笔记（13）Best Time to Buy and Sell Stock III

Posted on by javayu

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.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Continue reading “Leetcode笔记（13）Best Time to Buy and Sell Stock III”

bookmark_borderLeetcode笔记（12）Populating Next Right Pointers in Each Node II

Posted on by javayu

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Continue reading “Leetcode笔记（12）Populating Next Right Pointers in Each Node II”

bookmark_borderLeetcode笔记（11）Word Break II

Posted on by javayu

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Continue reading “Leetcode笔记（11）Word Break II”

bookmark_borderLeetCode笔记（9）Largest Rectangle in Histogram

Posted on by javayu

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Continue reading “LeetCode笔记（9）Largest Rectangle in Histogram”

bookmark_borderLeetCode笔记（8）Longest Consecutive Sequence

Posted on by javayu

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Continue reading “LeetCode笔记（8）Longest Consecutive Sequence”

bookmark_borderLeetCode笔记（6）Recover Binary Search Tree

Posted on by javayu

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Continue reading “LeetCode笔记（6）Recover Binary Search Tree”