题目描述：Given an array of integers, every element appears three times except for one. Find that single one.在数组中找到出现不是3次的那个数。思路：虽然题目推荐使用位运算，但基于代码可读性考虑，在实际应用场景中如果内存允许，本人还是建议直接使用哈希来做。实现代码：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.Add(nums[i],1); } else{ hash[nums[i]]++; } } foreach(var k in hash.Keys){ if(hash[k] != 3){ ...继续阅读 (39)

问题描述：Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.输入一个m*n的矩阵，判断如果matrix[i,j]为0（i∈[0,m) , j∈[0,n)），则把它的整行和整列都标记为0。思路：第一次遍历：使用队列存值为0的位置第二次遍历，遍历队列进行标记。空间复杂度为O(n^2)这里有一个空间复杂度为常数的解法，但是可读性不够强因此不推荐，如果空间允许的情况下，依然推荐使用O(n^2)空间复杂度的解法。http://www.programcreek.com/2012/12/leetcode-set-matrix-zeroes-java/实现代码：public class Solution { public void SetZeroes(int[,] matrix) { var row = matrix.GetLength(0); var col = matrix.GetLength(1); if(row <= 1 && col <= 1){ return; } var q = new Queue<Pos>(); ...继续阅读 (16)

题目描述：Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.Note: The input string may contain letters other than the parentheses ( and ).Examples:"()())()" -> ["()()()", "(())()"]"(a)())()" -> ["(a)()()", "(a())()"]")(" -> [""]就是输入一个字符串，其中包含了'('和')'以及字母。对这个字符串进行最小次数的删除，假设只删除了1次得到：str1（删除了第i位），str2(删除了第j位)...，strN。将这些删除后的字符串符合括号匹配的（就是除了字母外，'('和')'构成的是一个有效的括号字符串）加入结果集中。思路：1. 本题可以用DFS也可以BFS，但由于本题求的是最小次数而非第一个匹配的结果，因此BFS比较合适。2. 如果s不符合要求，对s的第i位进行移除， ...继续阅读 (58)

题目描述：Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.Note: You may not slant the container.已知一个height数组，代表从0到n的纵坐标，对于height[i]和height[j]来说，它们构成的最大水容量为i和j的距离 * Min(height[i], height[j])。问，求出height数组中哪两点间的水容量最大？思路：算是一个two pointer的经典问题，左右两边开始找,left=0,right = n-1：1. 如果左边高度低，则left++；如果右边高度低，则r--；如果相等，则left++并且right--; 2. 每次计算左右两点的水容量，并更新max值即可实现 ...继续阅读 (20)

题目描述：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给定已排序的数组，试图找到值为target的索引，如果没有找到，则返回它能够插入的位置，使得插入后数组仍为升序。思路：本题依然是二分法，只是要添加对插入的处理。实现代码：public class Solution { public int SearchInsert(int[] nums, int target) { var l = 0; var r = nums.Length - 1; while(l < r - 1){ var m = (l + r) / 2; var i = GetEqualsIndex(t ...继续阅读 (5)

题目描述：Given a list, rotate the list to the right by k places, where k is non-negative.For example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL.就是将倒数K个节点放在链表前。思路：1. 遍历链表判断长度len是否小于k，如果是，则k = k % len2. 如果len = k或len < 2或k < 1，直接返回3. 遍历链表，移动len - k - 1个位置，存当前位置为q4. 将q之后的节点存入stack5. 遍历stack，依次将节点设为头结点6. 最后，将q.next指向Null实现代码：/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode RotateRi ...继续阅读 (56)

题目描述：Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.就是把罗马数字转化为整数。1. 首先要了解罗马数字对应的整数：字符IVXLCDM数字15105010050010002.转换规则在罗马字符串s中，对于s[i]和s[i+1]，如果s[i+1]数字小，则整数为s[i]+s[i+1]，否则：如果s[i+1]比s[i]大，则s[i]与s[i+1]表示s[i+1]-s[i]。思路：遍历罗马字符串s，一一映射为字符，total初始化为s[0]，i∈[0,n)，比较s[i]和s[i+1]，如果后面大则直接累加s[i+1]；否则把减去s[i]的二倍并加上当前数s[i+1]。实现代码：public class Solution { public int RomanToInt(string s) { if(string.IsNullOrEmpty(s)) { return 0; } var len = s.Length; var result = Convert(s[0]); if(len < 2){ re ...继续阅读 (40)

题目描述：All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.For example,Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",Return:["AAAAACCCCC", "CCCCCAAAAA"].就是在一个字符串s中长度为10的字串中找到出现次数大于1次的子串。思路：使用哈希统计s[i...i+10]出现的次数，i∈[0,n-9)。实现代码：public class Solution { public IList<string> FindRepeatedDnaSequences( ...继续阅读 (21)

问题描述：Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.Example 1:11110110101100000000Answer: 1Example 2:11000110000010000011Answer: 3给定一个二维数组grid，1表示陆地，0表示海洋，求出岛屿的数量，岛屿的定义为：上下左右为海洋或超出边界(在grid之外)。例如对于11000110000010000011这个二维数组而言，由1111构成了一个岛屿；中间的1构成了一个岛屿；最后的11构成了另一个岛屿，一共3个岛屿。思路：本题考虑的还是DFS：1.初始化一个标记数组flag[,]2.遍历grid[,]，如果当前为'1'，则DFS从当前位置向上，下，左，右进行标记（注意判断越界），如果下一个位置也为'1'，flag[row,col]=true。这样一来， ...继续阅读 (54)

题目描述：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, return 1->2->5.Given 1->1->1->2->3, return 2->3.删除链表中有重复的元素，本题需要的是完全删除重复的元素，而不是保留一份，比如对于链表做重复元素删除：1-1-2-3，删除后为2-3，而不是1-2-3。思路：1. 遍历一次存重复的元素，存哈希。重复元素的判断：p.val == p.next.val2. 再遍历一次跳过重复元素即可。实现代码：/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { ...继续阅读 (28)

题目描述：Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).For example,S = "ADOBECODEBANC"T = "ABC"Minimum window is "BANC".Note:If there is no such window in S that covers all characters in T, return the empty string "".If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.本题就是要在串S中找到一个字串S[i...k]，其中i,k∈[0,n) ，n为S的长度，使得S[i...k]包含字符串T中的所有字符。思路：1. 使用hashT来保存每个字符出现的次数2. 初始化hashS（将t的每个字符添加到hashS并将值初始化为0，即出现次数都为0），遍历一次s（i∈[0,n)） ...继续阅读 (38)

题目描述：Write a program to find the node at which the intersection of two singly linked lists begins.For example, the following two linked lists:A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3begin to intersect at node c1.Notes:If the two linked lists have no intersection at all, return null.The linked lis ...继续阅读 (42)

题目描述：There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?For example:2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.2, [[1,0],[0,1]]There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should als ...继续阅读 (26)

题目描述：Given a binary tree, return the postorder traversal of its nodes' values.For example:Given binary tree {1,#,2,3},   1    \     2    /   3return [3,2,1].就是二叉树的后序遍历。思路：后序遍历的顺序- 左右根 ，直接使用递归实现就可以了。实现代码：/** * 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<int> PostorderTraversal(TreeNode root) { var result = new List<int>(); ...继续阅读 (37)

题目描述：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.在一个被部分旋转的排序好的序列中，查找一个数字。思路：由于该序列只有一部分被旋转，因此还是可以做二分查找的。*相当于要在两个递增序列中判断向左还是向右，并且，左边递增序列的最小值大于右边递增序列的最大值。设m,l,l分别为中间，左边，右边索引。target为要找的数1. 当nums[m] 比两边都大时：如果target小于nums[r]，说明target位于右边的递增序列上，因此向右找，l=m否则：如果target大于nums[m]，说明target只能在左边序列上，并且在m右侧，因此向右找，l=m如果target小于nums[m]，说明target在左边序列的m左侧。因此向左找，r=m2. 当nums[m] 比两边都小时（m只可能位于右边 ...继续阅读 (25)

题目描述：Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?Would this affect the run-time complexity? How and why?Write a function to determine if a given target is in the array.思路：这个题目与Search in Rotated Sorted Array基本是一样的，在旋转过的排序好的数组中进行二分查找，区别只是在于这个题目的输入可能包含重复元素。本题解法基本与Search in Rotated Sorted Array I相同，区别只是需要跳过重复元素。这里是Search in Rotated Sorted Array的解法：<link>而对于本题，需要在得到中间索引m后跳过左右重复元素，并重新计算m：while(l < m && nums[l] == nums[m]){   l++;   }   while(r > m && nums[r] == nums[m]){   r--;    ...继续阅读 (16)

题目描述：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.比较两个二叉树是否完全相同。思路：直接对两个树从根节点同时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 bool IsSameTree(TreeNode p, TreeNode q) { CompareTree(p, q); return _same; } private bool _same = t ...继续阅读 (16)

题目描述：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.就是把数组nums中的值为val的元素放在数组最后，返回新长度。思路：1.由于元素已有的顺序可以被改变，因此可以使用两个索引i和j进行两头找。j从后往前找值不为val的元素，i从前向后找值为val的元素，直到i与j相遇为止，交互nums[i]和nums[j]2.然后继续移动i,直到nums[i]为val为止，此时i的位置即为新长度，返回i即可。实现代码：public class Solution { public int RemoveElement(int[] nums, int val) { if(nums.Length == 0){ return 0; } var i = 0; var j = nums.Length - 1; while(i < j){ while(i < ...继续阅读 (11)

题目描述：The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order,We get the following sequence (ie, for n = 3):"123""132""213""231""312""321"Given n and k, return the kth permutation sequence.Note: Given n will be between 1 and 9 inclusive.对于n，先构造从1到n的数字序列s（例如3，s="123"），对于s的所有全排列情况，求出第k种排列的字符串。例如对于"123"，第3种排列的情况为"213"。思路：1.本题属于排列问题，一开始想到的是回溯。可发现题目只要求求出第k种情况，因此没必要track所有的排列状态导致浪费空间，并且这种算法会超时。2.使用nums[0...n]存放数字1到n（例如"123"，nums为{1,2,3}），循 ...继续阅读 (36)

题目描述：Given an index k, return the kth row of the Pascal's triangle.For example, given k = 3,Return [1,3,3,1].返回一个帕斯卡三角形的第n行。思路：本题的实现比较直接，只要了解帕斯卡三角形的构成就可以实现了。1.初始化nums为{1,1}，对应的行为1。2.对于i∈[1,rowIndex):首位和末尾添加1；相邻项（nums[i],nums[i+1]）相加构成nums[i]的新值。实现代码：public class Solution { public IList<int> GetRow(int rowIndex) { if(rowIndex == 0){ return new List<int>(){1}; } if(rowIndex == 1){ return new List<int>(){1,1}; } var list = new List<int>(){1,1}; for(var i = 1;i < rowIndex; i++){ var r = new List<int> ...继续阅读 (16)

题目描述：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 ...继续阅读 (38)

题目描述：Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.本题就是需要计算一个数组中出现次数超过n/3次的元素。暂时没想出如何使用O(1)的空间复杂度来做，思路还是使用哈希来完成。实现代码：public class Solution { public IList<int> MajorityElement(int[] nums) { if(nums == null || nums.Length == 0){ return new List<int>(); } var hash = new Dictionary<int,int>(); var len = nums.Length; for (var i = 0;i < len; i++) { if(!hash.ContainsKey(nums[i])) ...继续阅读 (9)

题目描述：Given a list of non negative integers, arrange them such that they form the largest number.For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.Note: The result may be very large, so you need to return a string instead of an integer.给定一个由非负数构成的数组nums，对所有元素进行排序拼成字符串s，求当s最大时的情况。本题的问题类型归为排序问题。对于nums中的n1和n2来说：1. 当n1[0](第1位) > n2[0]时，返回n12. 如果相同，则比较str(n1n2)和str(n2n1)，取较大的那个。实现代码：public class Solution { public string LargestNumber(int[] nums) { var nodes = new List<Node>(); for(var i = 0;i < nums.Length; i++){ nodes.Add(new Node(nums[i])); } var lis ...继续阅读 (18)

题目描述：Invert a binary tree.     4   /   \  2     7 / \   / \1   3 6   9to     4   /   \  7     2 / \   / \9   6 3   1就是把一棵二叉树进行反转。思路：本题的实现比较直接：后续遍历，交换节点。实现代码：/** * 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 TreeNode InvertTree(TreeNode root) { Travel(ref root) ...继续阅读 (17)

题目描述：Note: This is an extension of House Robber.After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.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.与之前的第一个版本类似，只是 ...继续阅读 (24)

题目描述：You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. ...继续阅读 (19)

题目描述：Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.Examples: "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"]"105", 5 -> ["1*0+5","10-5"]"00", 0 -> ["0+0", "0-0", "0*0"]"3456237490", 9191 -> []给定一串数，在数字中间插入操作符构成表达式，计算表达式，使得结果等于target。思路：由于要考虑多位数的情况，对于数组nums,需要对每一位nums[i]（其中i ...继续阅读 (97)

题目描述：Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.Ensure that numbers within the set are sorted in ascending order.Example 1:Input: k = 3, n = 7Output:[[1,2,4]]Example 2:Input: k = 3, n = 9Output:[[1,2,6], [1,3,5], [2,3,4]]就是从1到9构成的数组{1,2,3,4,5,6,7,8,9}中，找到一种组合，包含K个元素，和为n。思路：是一个典型的回溯问题，也算是问题：从数组nums中找到所有和为n的组合情况的子问题。 运用回溯模型直接解即可。 在遍历过程中，只需要收集只有k个元素的组合。实现代码：public class Solution { public IList<IList<int>> CombinationSum3(int k, int n) { ...继续阅读 (15)

题目描述：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.就是实现一个搜索二叉树的迭代器。思路：初始化时对树中序遍历元素入队列；hasNext：判断队列是否空；Next:拿出队列当前元素。缺陷：这个做法的缺陷在于如果只拿1个元素，仍然需要对整树遍历一次；可是大多数情况下，使用迭代器的目的显然是从头遍历到尾，因此这个方案是make sense的。实现代码：/** * Definition for binary tree * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * p ...继续阅读 (11)

题目描述：Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.You may not alter the values in the nodes, only nodes itself may be changed.Only constant memory is allowed.For example,Given this linked list: 1->2->3->4->5For k = 2, you should return: 2->1->4->3->5For k = 3, you should return: 3->2->1->4->5就是在遍历链表的过程中，如果从当前节点开始算，节点数大于k个，反转这k个节点；然后从当前位置向后移动k个位置，继续反转的过程，直到从当前节点到最后的节点数小于K个停止反转。思路：1. 创建反转函数，反转从当前开始的k个节点。 这个函数空间 ...继续阅读 (14)