LeetCode

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

For example, given the following triangle

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

Code：Solution

2.The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

Code：Solution

3.Validate if a given string is numeric.

Some examples:

"0"=>true

" 0.1 "=>true

"abc"=>false

"1 a"=>false

"2e10"=>true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Code：Solution

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

Code：Solution

5.remove-element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Code：Solution

6.candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Code：Solution

7.two-sum

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

Code：Solution

8.implement-strstr

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Code：Solution

9.multiply-strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Code：Solution

10.simplify-path

Given an absolute path for a file (Unix-style), simplify it.

For example,

path ="/home/", =>"/home"

path ="/a/./b/../../c/", =>"/c"

Code：Solution

11.rotate-list

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given1->2->3->4->5->NULLand k =2,

return4->5->1->2->3->NULL.

Code：Solution

12.evaluate-reverse-polish-notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Code：Solution

13. divide-two-integers

Divide two integers without using multiplication, division and mod operator.

Code：Solution

14.trapping-rain-water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 

Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

Code：Solution

15.sort-colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: 

You are not suppose to use the library's sort function for this problem.

Code：Solution

16.word-break-ii

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"].

Code：Solutiion

17.decode-ways

A message containing letters fromA-Zis being encoded to numbers using the following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message"12", it could be decoded as"AB"(1 2) or"L"(12).

The number of ways decoding"12"is 2.

Code：Solution

18.3sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:

    (-1, 0, 1)

    (-1, -1, 2)

Code：Solution

19.rotate-list

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given1->2->3->4->5->NULLand k =2,

return4->5->1->2->3->NULL.

Code：Solution

20.text-justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces' 'when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

Code：Solution

21.word-ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the dictionary

For example,

Given:

start ="hit"

end ="cog"

dict =["hot","dot","dog","lot","log"]

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length5.

Code：Solution

22.subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If S =[1,2,3], a solution is:

Code：Solution

23.binary-tree-zigzag-level-order-traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree{3,9,20,#,#,15,7},

return its zigzag level order traversal as:

Code：Solution

24.scramble-string

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 ="great":

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node"gr"and swap its two children, it produces a scrambled string"rgeat".

Code：Solution

25.sudoku-solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character'.'.

You may assume that there will be only one unique solution.

Code：Solution

26.letter-combinations-of-a-phone-number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Code：Solution

27.rotate-image

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?

Code：Solution

28. unique-paths

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?

Code：Solution

29. clone-graph

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use#as a separator for each node, and,as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph{0,1,2# 1,2# 2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by#.

First node is labeled as0. Connect node0to both nodes1and2.

Second node is labeled as1. Connect node1to node2.

Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.

Code：Solution

30. pascals-triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Code：Solution

31. gas-station

There are N gas stations along a circular route, where the amount of gas at station i isgas[i].

You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Code：Solution