# Leetcode[1]-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

c++

# Leetcode[4]-Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Code(c++):

# Leetcode[7]-Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Code(C++)

# Leetcode[9]-Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

C++代码：

# Leetcode[12]-Integer to Roman+++

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

C++:

# Leetcode[13]-Roman to Integer+++

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

C++:

Python：

# Leetcode[15]-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(c++):

# Leetcode[18]-4Sum

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

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

C++:

# Leetcode[19]-Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Code(c++):

# Leetcode[20]-Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

• 如果字符为上面给定的三个，则加入到vector中；

• 如果不是，在确保vector容器有字符的情况下，则让其和vector的最后一个比较；

• 如果是匹配的，则将vector容器的大小缩减为size()-1；
• 如果不匹配，则返回false；
• 最后，如果vector元素全部匹配完了，则返回true，否则返回false；

# Leetcode[21]-Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

• 如果l1的值大于l2的值，就将尾部指向l1，并同步向右移动l1的头指针和tail指针
• 如果l1的值小于l2的值，就将尾部指向l2，并同步向右移动l2的头指针和tail指针

Code(c++):

# Leetcode[26]-Remove Duplicates from Sorted Array

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.

Code(c++):

Python代码

# Leetcode[27]-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(c++):

# Leetcode[33]-Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

C++:

# Leetcode[35]-Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

code(c++):

# Leetcode[36]-Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

• 每一行不能出现重复元素
• 每一列不能出现重复元素
• 每一个九方格不能出现重复元素

Code(c++):

# Leetcode[53]-Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

• dp[i] = max(dp[i-1] + nums[i],nums[i])
• dp[0] = nums[0]

C++代码如下：

Python代码如下：

# Leetcode[62]-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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Code(c++):

# Leetcode[63]-Unique Paths II

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 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.

• 第0列，从上到下，如果碰到一个1，则设置该位置和后面的位置都不可到达，即dp[i to n][0]；
• 第0行，从左到右，如果碰到一个1，则设置该位置和右方的位置都不可到达，即dp[0][i to n];
• 其它位置，如果该位置不为1，则到达该位置的方式共有 dp[i][j] = dp[i-1][j] + dp[i][j-1],如果为1，则dp[i][j] = 0；

Code(c++):

# Leetcode[66]-Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Code(c++):

# Leetcode[70]-Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

i表示阶梯数，f(i)表示有多少种走法；

• 当i = 1时，f(1) = 1,
• 当i = 2时，f(2) = 2;
• 当i > 3时，f(i) = f(i-1) + f(i-2)。

# Leetcode[74]-Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

Given target = 3, return true.

while( i < n && j >= 0)

C++代码：

# Leetcode[81]-Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

C++:

# Leetcode[82]-Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return1->2->5. Given 1->1->1->2->3, return 2->3.

Code(c++):

# Leetcode[83]-Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

C++:

# Leetcode[86]-Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Code(c++):

# Leetcode[88]-Merge Sorted Array

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 nums1 and nums2 are m and n respectively.

• 如果nums1的值大于nums2的值，就将nums1的值放到nums1的最后一个；
• 如果nums2的值大于nums1的值，就将nums2的值放到nums1的最后一个；
• ……
• 依次迭代
• ……

Code(c++):

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Code(c++):

# Leetcode[94]-Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return[1,3,2].

• 首先取出栈顶节点，如果不为空的话，就把它的左节点进栈，然后再取栈顶元素，如果不为空，则再让它的左节点进栈，直到栈顶元素是空的节点为止；
• 然后让栈顶的空指针退栈
• 接着判断栈是否为空，如果不为空，则栈顶节点出栈，并将栈顶元素的值加入到数组中，然后把该节点的右节点入栈（右节点是否是空的，此处不做判断，内部的while循环会判断，因为内while循环后的栈顶节点必定是空指针）

# Leetcode[96]-Unique Binary Search Trees

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

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

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

• 初始值dp[0] = 1,dp[1] = 1,
• dp[n] = dp[0] * dp[n-1] + dp[1] * dp[n-2] + …+ dp[i] * dp[n-1-i] +… + dp[n-1] * dp[0]，也就是左边i个节点，右边n-1-i个节点。代码如下：

Code(c++):

# Leetcode[98]-Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

• 如果有左子树，比较根结点与左子树的最大值，如果小于等于则返回false；
• 如果有右子树，比较根结点与右子树的最小值 ，如果大于等于则返回false；
• 接着判断左子树和右子树是否也是合法的二叉搜索树；

Code(c++):

# Leetcode[100]-Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

• 如果p和q都为空，则返回true；否则，
• 如果p和q都非空，并且他们的值都相等，则判断其左右子树是否是相似树；否则
• 返回false；

# Leetcode[101]-Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

Note:
Bonus points if you could solve it both recursively and iteratively.

Code（c++）：

# Leetcode[102]-Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

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

  3
/ \
9  20
/  \
15   7

return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

# Leetcode[103]-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},

  3
/ \
9  20
/  \
15   7

return its zigzag level order traversal as:

[
[3],
[20,9],
[15,7]
]

# Leetcode[104]-Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

C++:

# Leetcode[107]-Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

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

  3
/ \
9  20
/  \
15   7

return its bottom-up level order traversal as:

[
[15,7],
[9,20],
[3]
]

Code(c++):

# Leetcode[110]-Balanced Binary Tree

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.

Code(C++):

# Leetcode[111]-Minimum Depth of Binary Tree

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.

C++:

# Leetcode[113]-Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1

return

[
[5,4,11,2],
[5,8,4,5]
]

• 一个map，保存节点是否出栈过；
• 一个一维数组，保存根结点到当前节点的路径；
• 一个二维数组，保存根结点到当前叶节点的和等于给定sum的路径集合；
• 一个栈，用来辅助深度优先遍历；

• 进栈的时候元素同时添加到一维数组中，并将该节点的map值设置为0,
• 当节点左右节点都为空的时候，判断一维数组里面的数据和是否等于给定sum，如果等于就把它丢到二维数组中，同时执行下一步出栈；
• 出栈的时候也同时缩小一维数组的长度，并将该节点的map值设置为1，表示该节点不能再次进栈了；

Code（c++）：非递归算法：

# Leetcode[114]-Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

   1
/ \
2   5
/ \   \
3   4   6

The flattened tree should look like:

1
\
2
\
3
\
4
\
5
\
6

*思路: * 首先找到根节点左节点的最右子节点，然后把根节点的右子树移到左子树的最右端；接着把根结点的左子树移到右节点上，并将左子树置为空树，同时将根结点往右下移一个节点，依次递归即可。代码如下：

Code(c++):

# Leetcode[118]-Pascal’s Triangle

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

For example, given numRows = 5,
Return

• 第j=0列全为1，第j==i列时，都为1
• 其它列
• a[2][1] = a[1][0]+a[1][1]
• a[3][1] = a[2][0]+a[2][1]
• a[3][2] = a[2][1]+a[2][2]
• ……
• 推算得出
• ……
• a[i][j] = a[i-1][j-1]+a[i-1][j]

# Leetcode[119]-Pascal’s Triangle II

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Python代码

# Leetcode[125]-Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Code(C++):

# Leetcode[128]-Longest Consecutive Sequence

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.

C++:

# Leetcode[129]-Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

# Leetcode[136]-Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Code(c++)

# Leetcode[137]-Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

C++

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

Code(c++):

# Leetcode[143]-Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

C++:

# Leetcode[144]-Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree{1,#,2,3},

1
\
2
/
3

return [1,2,3].

# Leetcode[145]-Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
\
2
/
3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

# Leetcode[147]-Insertion Sort List

Sort a linked list using insertion sort.

# Leetcode[148]-Sort List

Sort a linked list in O(n log n) time using constant space complexity.

• 找到中间点
• 合并两个排好序的链表
• 递归实现归并排序

Code(c++):

# Leetcode[153]-Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

C++:

# Leetcode[154]-Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Ｃ++：

# LeetCode[155]-Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

Code（c++）:

# Leetcode[162]-Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

• 如果只有一个元素，直接返回0；
• 如果元素个数>=2，判断首尾是否大于它的附近元素，大于则返回下标；
• 循环遍历，下标从>=1到 < n-1，判断nums[i]是否同时大于它的附近元素，如果大于则返回该下标；

Code(c++)

# Leetcode[169]-Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Code1(C++):

Code2(C++)

# Leetcode[173]-Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

C++:

# Leetcode[189]-Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

$$ba=(b^{r})^{r}(a^{r})^{r}=(a^{r}b^{r})^{r}$$

Code（c++）：

# Leetcode[191]-Number of Bits

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

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

C++:

Python:

# Leetcode[198]-House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

• 当你打劫第一家的时候，i = 0，可以得到的钱dp[i] = m[0]；
• 当你到达第二家的时候，i = 1，此时能得到的钱数为max(m[0],m[1]),因为不能同时打劫第一家和第二家；
• 当到达第i家的时候，i＞＝２，此时能够得到的钱数应该为max{dp[i-1],dp[i-2]+m[i]},即要么是到达上一家时的最大money数，要么是到达上上家时的最大money+这一家的money数，两者中较大的那个；

Code(c++):

# Leetcode[202]-Happy Number

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

$1^2 + 9^2 = 82$
$8^2 + 2^2 = 68$
$6^2 + 8^2 = 100$
$1^2 + 0^2 + 0^2 = 1$

Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

• 如果链表不为空，保证第一个节点不等于val，如果等于，直接跳到下一个节点；

• 如果此时链表为空，返回该链表；

• 将头结点赋值给一个临时节点，如果该节点的下一个节点不为空，递归遍历；

• 如果下一个节点的值等于给定值，直接跳到下下个节点；
• 如果下一个节点的值不等于给定值，则让跳到下个节点再来循环；
• 最后返回链表的头结点即可。

Code（c++）：

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

# Leetcode[215]-Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

# Leetcode[217]-Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Python代码

# Leetcode[219]-Contains Duplicate II

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

【mapv.find(number) != mapv.end()】并且当前位置和map中找到的位置差小于等于k【i-mapv[number] <= k】，就返回true，不然就将该值加入到map中。依次循环…

Code(c++)

# Leetcode[222]-Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Code(c++):

# Leetcode[226]-Invert Binary Tree

Invert a binary tree.

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

to

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

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

C++递归法求解：

# Leetcode[231]-Power of Two

Given an integer, write a function to determine if it is a power of two.

• 如果n小于0，返回false；
• 如果n等于1或者等于2，返回true；
• 当n大于2时，根据n大于2的条件进行递归，，如果n%2不为0则直接返回false，否则将n/2赋值给n
• 如果循环结束后还没有返回false，则返回true。

C++:

# Leetcode[237]-Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Subscribe to see which companies asked this question

# Leetcode[242]-Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Python代码比较简单，就给出Python代码吧：

Python：

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Could you do it without any loop/recursion in O(1) runtime?

C++

# Leetcode[260]-Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

C++:

# Leetcode[263]-Ugly Number++

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

# Leetcode[283]-Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

• You must do this in-place without making a copy of the array.
• Minimize the total number of operations.

C++代码：

# Leetcode[292]-Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

• 如果n小于4，返回true；
• 如果n%4==0，返回false；
• 否则，返回true。

C++:

Python：

# Leetcode[300]-Longest Increasing Subsequence

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?

• 初始化dp[0]=1；
• 当i>0时，设置一个变量max_dp，初始值为1,记录的是以当前位置结尾时的最长递增子序列长度。通过循环遍历前面的i-1个数，如果位置i的数大于前面位置j的数，就比较max_dp和dp[j]+1,将大的值赋值给max_dp，最后将max_dp赋值给dp[i]；
• 最后，遍历dp[n]，找出最大的值，即为最长递增子序列的长度。

C++代码：