题目描述：Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.就是对一个图进行复制。思路：图遍历可以DFS或BFS，两种方式都可以，下面的解法是DFS的递归方式。当然，也可以用队列+哈希表使用BFS完成。1. 在哈希表hash添加图的首节点source，和复制节点cloned（拷贝label）。2. 复制过程：2.1 如果source有neighbors，遍历neighbors，对于每个neighbors[i],判断是否在哈希存在，如果不存在，添加一份neighbor[i]的复制到哈希表中，进入递归；2.2 如果已经存在，或者完成了2.1的复制步骤，将这个neighbor复制到当前map[source]对应的邻居列表中。即map[source].neighbors.Add(map[neighbor[i]])实现代码：/** * Definition for undirected graph. * public class UndirectedGraphNode { * public int label; * public IList<UndirectedGraphNode> neighbors; * ...继续阅读 (37)

题目描述：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   7return its bottom-up level order traversal as:[  [15,7],  [9,20],  [3]]输入一棵二叉树，从底层叶子节点开始，将每层的节点存成一个list，然后逐层将每个list存入结果集中。思路：由于逐层遍历，显然是BFS，不过最底层的叶子集合需要放在最上，每次添加结果集时，将当前层的节点集合插入在首位即可。实现代码：/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public ...继续阅读 (41)

题目描述：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.    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.    A solution set is:    (-1,  0, 0, 1)    (-2, -1, 1, 2)    (-2,  0, 0, 2)在数组中找到四个数和=target。和3Sum思路一模一样，就是外面多加了一层循环。实现代码：public class Solution { ...继续阅读 (35)

题目描述：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.    For 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).本题与 Three Sum Zero类似，不同点在于，之前是寻找a+b+c=0的组合，现在是找最接近target的a+b+c的值。思路：依然是two pointer的思路。1.对数组排序2.使用a表示当前第i轮查找，b=i+1，表示第i轮的第1个元素，b∈[i+1,n)，c=len-1，一开始指向最后一个元素。3.当找到a+b+c=target，直接返回；如果a+b+c < target，b++；否则，c--。4.每次取Math.Abs(a+b+c- targ ...继续阅读 (37)

题目描述：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 in ascending from left to right.Integers in each column are sorted in ascending from top to bottom.For example,Consider the following matrix:[  [1,   4,  7, 11, 15],  [2,   5,  8, 12, 19],  [3,   6,  9, 16, 22],  [10, 13, 14, 17, 24],  [18, 21, 23, 26, 30]]Given target = 5, return true.Given target = 20, return false.本题看起来是Search a 2D Matrix的扩展问题，其实和第一题的思路完全不一样。比较精简的思路是：1.从左下开始找，如果matrix[r ...继续阅读 (48)

题目描述：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}.本题算是链表中很有特点的一道题目。对于链表1->2->3->4->5->6 ，要变成1->6->2->5->3->4，即第i个节点指向倒数第i个节点，而倒数第i个节点，指向第i+1个节点。解法一：使用前后两个指针p和q。具体实现步骤在注释中有详细说明，在此不再赘述。由于时间复杂度为O(N^2)，不够高效导致会超时。无法通过OJ的测试数据。实现代码：/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Soluti ...继续阅读 (34)

题目描述：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.本题依然属于一道位运算的题目，输入一个无符号的整数，判断出1的个数。思路：对于整数n,从n开始对n和n-1做与运算然后赋值给n。即，n=n&n-1。直到n等于n为止。能做多少次运算就说明有多少个1。实现代码：public class Solution { public int HammingWeight(uint n) { int count; for (count=0; n > 0 ; count++){ n &= n-1; } return count; } } ...继续阅读 (58)

题目描述：Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.For example, given the array [2,3,1,2,4,3] and s = 7,the subarray [4,3] has the minimal length under the problem constraint.对于数组A中的子数组a，找到满足Sum(a[0]+a[1]...a[n-1]) >= target时的最短长度的子数组。思路：本题属于移动窗口问题，最直接的办法就是分别以a[i]为起点，不断往后移动指针进行累加存到s，当s>=target时，更新最短长度min。时间复杂度为O(N^2)实现代码：public class Solution { public int MinSubArrayLen(int s, int[] nums) { int? min = null; for(var i = 0;i < nums.Length; i++){ ...继续阅读 (38)

题目描述：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.设计一个栈，要求获取最小值的时间复杂度为常数。思路：对变成语言类库内部的栈进行封装，维护使用一个最小值的成员即可。要注意的就是弹出栈的操作，如果栈中依然有值，需要求出当前最小值更新最小值；如果栈空，最小值设为空。实现代码：public class MinStack { private Stack<int> _stack ; private int? _min; public MinStack(){ _stack = new Stack<int>(); } public void Push(int x) { if(!_min.HasValue || x < _min){ _m ...继续阅读 (33)

题目描述：Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.实现一个LRU的缓存，关于LRU缓存，可以概括为一个指定容量的的缓存，当超出容量时，拿掉最长时间没有使用的那个元素。关于LRU的具体定义可以查看这个链接：http://mcicpc.cs.atu.edu/archives/2012/mcpc2012/lru/lru.html思路：1. 使用哈希来 ...继续阅读 (33)

题目描述：Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Note: Do not modify the linked list.Follow up:Can you solve it without using extra space?判断链表是否有环，如果存在，返回环起始节点；如果不存在，返回Null。思路：1. 使用快慢指针的方法找到环的位置。2. 如果找到了环，慢指针回到起点，快慢指针每次各走一步，下一次相遇的位置就是环的起点。实现代码：/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode DetectCycle(ListNode head) { if(h ...继续阅读 (28)

题目描述：Given an array of integers and an integer k, find out whether 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.在一个数组nums中试着找到两个数nums[i]和nums[j]，其中,i与j的距离要小于等于k。如果找到，返回true，否则返回false。思路：一次遍历num[i...n)，哈希存每个数的位置，如果nums[i]已经出现，就判断上次出现的位置与当前位置的距离是否小于等于k。如果是，返回true；否则，更新Hash[nums[i]]的位置=i。实现代码：public class Solution { public bool ContainsNearbyDuplicate(int[] nums, int k) { var hash = new Dictionary<int, int>(); for(var i = 0;i < nums.Length; i++){ if(!hash.ContainsKey(nums[i])){ ...继续阅读 (44)

题目描述：Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.For example, given the range [5, 7], you should return 4.就是对从m到n之间的数字做与运算。思路：本题的关键在于，求出了n& n-1为v，就可以直接把n设为v，而没必要在求v与n-1之间的数了。实现代码：public class Solution {    public int RangeBitwiseAnd(int m, int n)     {        while(n > m){            n = n & n-1;        }        return n & m ;    }} ...继续阅读 (29)

题目描述：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.Some examples:"3+2*2" = 7" 3/2 " = 1" 3+5 / 2 " = 5就是对1个表达式解析出操作数和操作符，做四则运算，但不包括括号。思路：1. 去除空白字符2. 考虑多位数字的情况3. 如果是'*'或'/'，直接计算；否则入栈4. 由于只剩下加减运算符了，按顺序计算出结果即可。实现代码：public int Calculate(string s) { var exp = s.Where(c => c != ' ').ToList(); var stackOp = new Stack<char>(); var stac ...继续阅读 (43)

本题描述：Given a linked list, determine if it has a cycle in it.Follow up:Can you solve it without using extra space?检测链表中是否有环。思路：经典算法，使用快慢指针，快的一次走两步，慢的一次走一步，如果有环它们一定会相遇。实现代码：/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public bool HasCycle(ListNode head) { if(head == null){ return false; } var p = head; var q = head; while(p != null && q != null &a ...继续阅读 (38)

题目描述：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.判断一个数是否为ugly number。对2,3,5执行以下过程：不断除n，直到无法整除。最后剩余数字为1，则该数为ugly number。实现代码：public class Solution { public bool IsUgly(int num) { if(num <= 0){ return false; } num = Divide(num,2); num = Divide(num,3); num = Divide(num,5); return num == 1; } ...继续阅读 (54)

题目描述：Write a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.Note that 1 is typically treated as an ugly number.本题算是Ugly number 1的扩展问题，求出第n个ugly number。本题属于数学问题，回顾一下ugly number的定义：因数只包含2,3,5的数和1。方法一：基于Ugly number 1中的函数IsUgly，逐个判断从1到n，累计到第n个ugly的number即可。缺点很显然，逐个判断效率非常低。方法二：对于任意1个大于2,3,5的ugly number 来说，除以2,3,5后必然仍是ugly number，可使用哈希来缓存ugly number ，每次除以2,3,5判断是否在哈希中有键值。这种方式使用了大量的空间，并且很多多余的判断浪费在了不是ugly number上。 本解法依然无法被AC。实现代码：public int Nth ...继续阅读 (36)

题目描述：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[     [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).求三角形从上到下构成最小值的和的路径。思路：1.使用一个辅助的二维数组保存当前[i,j]的最小和，再遍历一次最后一层的值从而得到最小值。2.在求和过程中，区分收尾字符和中间字符的情况。假设arr[i,j]来保留第i行第j列的最小和。则：arr[0,0] = triangle[0,0];当j为中间元素：arr[i,j] = Min(arr[i-1,j], arr[i-1,j-1]) + triangle[i,j]当j为首元素：arr[i,0] = arr[i-1,0] + triangle[i,0]当j为末尾元素：arr[i,count-1] ...继续阅读 (63)

题目描述：Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.A region is captured by flipping all 'O's into 'X's in that surrounded region.For example,X X X XX O O XX X O XX O X XAfter running your function, the board should be:X X X XX X X XX X X XX O X X在由'X'和'O'组成的矩阵中，找出所有被'X'包围的'O'，将它们替换为'X'。思路：1.本题可以DFS也可以BFS，但是DFS速度会慢一些，无法通过测试数据。无论哪种方式，就是从四个边的'O'作为切入点n（如果BFS，需要先将四个边的'O'入队列），遍历时找到n的上下左右邻居，分别进行标记（假设标记为A），凡是标记为A的点即为：不能被围的'O'，以这些邻居为中心继续下一次标记。2.然后对board做一个遍历，把剩余的'O'赋值为'X'，而'A'赋值为'O'即可。实现代码：public class Solution { public void Solve(char[,] board) { var r ...继续阅读 (47)

题目描述：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,    1   / \  2   3The 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.思路：DFS问题，即从根节点出发进入统计（存为string s），如果左节点不为空，进入左子树统计；如果右子树不为空进入右子树统计。如果是叶子节点，记录状态放入总结果（List<string> result）。遍历完之后，再遍历一遍result转为整形累加计算结果即可。实现代码：/** * Definition f ...继续阅读 (19)

题目描述：Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.For example,123 -> "One Hundred Twenty Three"12345 -> "Twelve Thousand Three Hundred Forty Five"1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"就是把数字转化为英语单词。思路：1.先把从100-999映射为英文单词的函数写出来：1.1先考虑一位数：一一映射就可以了。函数为Digit()1.2然后考虑两位数的情况：需要区分11-19，函数为Teen()和20-99的情况，函数为Ty()1.3然后对百位数调用Digit()就可以了。如果百位数为0，则调用Teen()或Ty()函数存为Hundred()2.考虑小于等于6位数的情况，即百万以下的数。将这六位数分为前3位和后3位，分别调用Hundred()函数，中间插入"Thousand"即可。 ...继续阅读 (30)

题目描述：Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2], a solution is:[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]思路：又是一道backtracking题目。本题与Combination Sum极为类似。需要注意去重，使用哈希来存升序key。实现代码：public class Solution { public IList<IList<int>> SubsetsWithDup(int[] nums) { Dictionary<string, IList<int>> result = new Dictionary<string, IList<int>> ...继续阅读 (23)

题目描述：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].在一个数组中，只有两个数只出现了1次，其余数都出现了两次。思路：如果空间允许，还是建议直接使用哈希表。实现代码：public class Solution { public int[] SingleNumber(int[] nums) { var hash = new Dictionary<int,int>(); for(var i = 0;i < nums.Length; i++) { if(hash.ContainsKey(nums[i])){ hash[nums[i]] ++; } else{ hash.Add(nums[i], 1); } } ...继续阅读 (36)

题目描述：Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.For example, you may serialize the fo ...继续阅读 (26)

题目描述：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，两层遍历，因此时间复杂度通常是O(N^2)。本题也一样，先找递推式：1.对于每个数字nums[i]，i∈[0,n)，只有1个数字时，它的最大长度为1，因此dp[0...n) = 1，dp[i]表示位置i ...继续阅读 (25)

题目描述：Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?与H-Index的区别就是，这个数组是倒序排序好的。思路：省去了排序的步骤，直接从数组尾部向前遍历就可以了。其余思路与H-index相同。实现代码：public class Solution { public int HIndex(int[] citations) { if(citations.Length == 0){ return 0; } var sum = 0; var j = 0; for(var i = citations.Length - 1;i >= 0; i--){ if(j < citations[i]){ sum ++; } j++; } return sum; } } ...继续阅读 (19)

题目描述：According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):Any live cell with fewer than two live neighbors dies, as if caused by under-population.Any live cell with two or three live neighbors lives on to the next generation.Any live ...继续阅读 (14)

题目描述：You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.For example:Secret number:  "1807"Friend's guess: "78 ...继续阅读 (16)

题目描述：Given a binary tree, return all root-to-leaf paths.For example, given the following binary tree:   1 /   \2     3 \  5All root-to-leaf paths are:["1->2->5", "1->3"]输入1个二叉树，打印出所有从根到叶子的路径。思路：1个基本的DFS题，直接从根对树做DFS，到叶子时收集路径即可。实现代码：/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public IList<string> BinaryTreePaths(TreeNode root) { ...继续阅读 (46)

题目描述：Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.For example,Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.Window position                Max---------------               -----[1  3  -1] -3  5  3  6  7       3 1 [3  -1  -3] 5  3  6  7       3 1 &nbs ...继续阅读 (24)