Subsets 2

Problem

Given a collection of integers that might contain duplicates, 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,

---

Idea

把S排序，然后通过判断S[i]!=S[i-1]去掉重复
递归的方法求解.每次插入tmp,就把tmp加到result中.

---

Solution

---

Intersection of Two Linked List

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists: begin to intersect at node c1.
Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

---

Idea

统计两个链表的长度
以短的为基准对齐两个链表的start node
从新的起点开始，两个链表遍历，找第一个相同的元素

---

Solution

---

Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings.

---

Idea

找到最小的串，然后判断这个串的每个字符是否在其他串中的相同位置出现.

---

Solution

---

Path Sum 2

Problem

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,

---

Idea

DFS

---

Solution

---

Spiral Matrix II

Problem

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

---

Idea

---

Solution

---

Multiply Strings

Problem

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.

---

Idea

模拟乘法的过程

---

Solution

---

Count and Say

Problem

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

---

Idea

---

Solution

---

Convert Sorted List to Binary Search Tree

Problem

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

---

Idea

递归的方法解这个题目，注意递归的终止条件，左子树和右子树递归的边界

---

Solution

---