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.

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).

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

Example

Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example

Given the following triangle

1
2
3
4
5
6

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,

We get the following sequence (ie, for n = 3):

1
2
3
4
5
6

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note

Given n will be between 1 and 9 inclusive.

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

Example

the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

Given a collection of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example

Given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,

A solution set is:

1
2
3
4
5
6

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, * , / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Examples:

1
2
3

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note

Do not use the eval built-in library function.