立贴！从今天开始刷题。

顺便吐槽一下，本论坛居然没有C#的代码支持。

1. public class Solution {
   
2.     public IList<IList<int>> Subsets(int[] nums) {
   
3.         IList<IList<int>> result = new List<IList<int>>();
   
4.         IList<int> subset = new List<int>();
   
5.         Helper(result,subset,nums,0);
   
6.         return result;
   
7.     }
   
8.    
   
9.     public void Helper(IList<IList<int>> res,IList<int> subset,int[] nums,int index)
   
10.     {
    
11.         res.Add(new List<int>(subset));
    
12. 
    
13.         for (int i = index; i < nums.Length; i++)
    
14.         {
    
15.             subset.Add(nums);
    
16.             Helper(res, subset, nums, i + 1);
    
17.             subset.RemoveAt(subset.Count - 1);
    
18.         }
    
19.     }
    
20. }

复制代码

238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

这题比较傻瓜，感觉不会考。简单讲就是把所有左边的乘积取出来，然后乘上右边的乘积。

算左边的时候一个loop，算右边的时候一个loop。这样就可以用2个O(n)。2个O(n)还是O(n)。

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input:
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output:
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

    A straight forward solution using O(mn) space is probably a bad idea.
    A simple improvement uses O(m + n) space, but still not the best solution.
    Could you devise a constant space solution?

此题难度一般，但是follow up感觉非常难。我是没啥好办法，不知道有大神能给指点一下嘛？

380. Insert Delete GetRandom O(1)


Design a data structure that supports all following operations in average O(1) time.

    insert(val): Inserts an item val to the set if not already present.
    remove(val): Removes an item val from the set if present.
    getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

此题有点难度，就是用hast表来插入和删除，用数组来随机返回数字。

删除的时候，要在数组里面相应删除对应的数据，所以必须先和数组最后一个元素交换然后再删删除。

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

好长时间不使用链表了，这个链表要好好熟悉一下。