题目描述：本题考查的是纯粹字符串操作，遍历i∈[0, numRows)次,从第i个字符起始，每次向后取2 * numRows - 2处的字符累加，需要判断末尾处可取的部分。实现代码：public class Solution { public string Convert(string s, int numRows) { if(string.IsNullOrWhiteSpace(s) || numRows == 1){ return s; } var s1 = ""; int distance = 2 * numRows - 2; for(var i = 0; i < numRows ; i++) { for(int j = i; j < s.Length; j += distance) { s1 += s[j]; if(i !=0 && i != numRows - 1 && j + distance - 2 * i < s.Length){ ...继续阅读 (27)

Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.For example,Given board =[  ["ABCE"],  ["SFCS"],  ["ADEE"]]word = "ABCCED", -> returns true,word = "SEE", -> returns true,word = "ABCB", -> returns false.就是在一个字母矩阵中搜索一个单词。如果通过对某个字符进行上下左右移动所构成的路径，可以找到指定单词则返回true。思路：从矩阵的每个字符分别出发，进行DFS。实现代码：public ...继续阅读 (24)

题目描述：Given a pattern and a string str, find if str follows the same pattern.Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.Examples:pattern = "abba", str = "dog cat cat dog" should return true.pattern = "abba", str = "dog cat cat fish" should return false.pattern = "aaaa", str = "dog cat cat dog" should return false.pattern = "abba", str = "dog dog dog dog" should return false.Notes:You may assume pattern contains only lowercase letters, and st ...继续阅读 (33)

题目描述：Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:Only one letter can be changed at a timeEach intermediate word must exist in the word listFor example,Given:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.Note:Return 0 if there is ...继续阅读 (19)

题目描述：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 '.'.验证一个数独的合法性。思路： 数独输入的规则：每行每列，每个3*3的范围内不能有重复。 直接验证就可以了。使用辅助数组bool[9]分别对：1、对每行判断是否有重复2、对每列判断是否有重复3、对每个3*3判断是否有重复实现代码：public class Solution { public bool IsValidSudoku(char[,] board) { var row = 9; var col = 9; // check each row for(var i = 0;i < row;i ++){ var flag = new bool[9];; for(var j = 0;j < col; j++){ var b = Check(board, i, j, ref flag); if(!b){ ...继续阅读 (180)

题目描述：Given an unsorted integer array, find the first missing positive integer.For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2.Your algorithm should run in O(n) time and uses constant space.在一个数组中找出第一个缺失的正数。要求O(n)的时间复杂度。思路：暂时只能想出O(n*logN)的，对数组排序，然后根据先后元素的差值来判断缺失的数字。需要考虑第一个和最后一个元素的情况。实现代码：public class Solution { public int FirstMissingPositive(int[] nums) { if(nums == null || nums.Length == 0){ return 1; } var list = new List<int>(); for(var i = 0;i < nums.Length;i ++){ if(nums[i] > 0){ list.Add(nums[i]); } } ...继续阅读 (44)

题目描述：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.在一个只包含"()[]{}"的输入中，判断括号的合法性。思路：栈的基本使用。实现代码：public class Solution { public bool IsValid(string s) { var stack = new Stack<char>(); for(var i = 0;i < s.Length; i++){ switch(s[i]){ case '{': case '[': case '(': stack.Push(s[i]); break; case ...继续阅读 (36)

题目描述：Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example,"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.判断回文。需要跳过特殊字符以及同一个字母大小写视为相等的情况。实现代码：public class Solution { public bool IsPalindrome(string s) { var i = 0; var j = s.Length - 1; while(i < j){ while(Skip(s[i]) && i < j){ i++; } while(Skip(s[j]) && i < j){ j--; } var delta = s[i] - s[j]; if(delta != 0 && del ...继续阅读 (32)

题目描述：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.就是要判断字符串s和字符串t中的每个字符出现的次数是否相等。思路：使用哈希表，扫一遍s中的每个字符，存在哈希表中: hash[s[i], n] ，n为出现的次数扫一遍t,如果t[i]不在哈希表中，返回false，否则把hash[t[i]] 的次数减一最后判断hash中的每个字符出现次数是否都为0就可以了实现代码：public class Solution { public bool IsAnagram(string s, string t) { var dict = new Dictionary<char, int>(); for(var i = 0;i < s.Length ...继续阅读 (14)

题目要求：Follow up for "Unique Paths":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.Note: m and n will be at most 100.就是在一个矩阵中，求从左上到右下单元的路径个数，每次只能向下或向右移动。0表示可以通过，1表示障碍。思路：本题依然是1个DP问题。设dp[i,j]表示从左上到矩阵的[i,j]位置的路径个数。1. 当行或列只有1时，如果有障碍，则返回0，否则返回1。当row > 1 且 col > 1:2.1 分别初始化dp的第一行(i)和第一列(j)，即dp[i,0]和dp[0, ...继续阅读 (37)

题目描述：Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.For example,Given n = 3, your program should return all 5 unique BST's shown below.   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \               &nbs ...继续阅读 (25)

题目描述：Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.给定一个高度数组height[]，每个元素表示高度为height[i]的挡板，它们之间的间隔形成积水，求最大积水量。例如高度为1,0,2的挡板，积水量为1。思路：1. 一次遍历，求出每个挡板的左右最大的高度2. 再次遍历height[]，取它左右最大高度的最小值，减去height[i]，就是它的积水量。累加所有挡板的积水量。实现代码：public int Trap(int[] height) { if(height == null || height.Length < 3) { return 0; } var len = height.Length; int[] left = new int[len]; int[] right = new int[ ...继续阅读 (54)

题目描述：Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).For example, this binary tree is symmetric:    1   / \  2   2 / \ / \3  4 4  3But the following is not:    1   / \  2   2   \   \   3    3判断一个树的左右子树是否完全相等。思路：分别对左右子树进行中序遍历，然后对遍历结果进行一一对比。实现代码：public class Solution { public bool IsSymmetric(TreeNode root) { if(root == null || root.left ==null && root.right == null){ return true; } var left = new List<string>(); ...继续阅读 (10)

题目描述：Given a set of distinct integers, 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,3], a solution is:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]求一个集合的所有子集。这个题目是学习backtracking一道不错的入门题，直接使用回溯结构来解就可以了。需要注意的是，每次添加结果时要对当前子集的元素进行升序排序。实现代码：public class Solution { public IList<IList<int>> Subsets(int[] nums) { var result = new List<IList<int>>(); Do(nums, 0, new List<int&g ...继续阅读 (42)

题目描述：Implement atoi to convert a string to an integer.Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.就是完成字符串转整数的操作。本题的复杂点在于情况很多需要考虑：1.可能是负数。2.首字母为+3.跳过开始的'0'4.超大整数（使用double来解析）public class Solution { public int MyAtoi(string str) { if(string.IsNullOrWhiteSpace(str)){ return 0; } str = str.Trim(); ...继续阅读 (13)

题目描述：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].就是讲数组的倒数第k个位置以后（包含k）的元素放在数组前。思路：1.使用辅助队列来完成。2.一次遍历，将k位置前的元素入队列。3.从最后一个元素开始往前遍历，将队列元素依次出队并赋值给nums[i]。 i ∈[n,0)实现代码public class Solution { public void Rotate(int[] nums, int k) { if(nums == null || nums.Length <= 1){ return; } var q = new Queue<int>(); for(var i = nums.Length-1; i>=0; i--){ q.Enqueue(nums[i]); } for(var i = 0 ;i < k; i++){ var n = q.Dequeue(); q.Enque ...继续阅读 (45)

题目描述Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).Follow up:If this function is called many times, how would you optimize it?反转一个无符号数字的二进制串。思路：将n转化字符串，反转字符串，将字符串转换为无符号数。实现代码public class Solution { public uint reverseBits(uint n) { var s = ToBinaryStr(n); var s1 = ""; for(var i = s.Length - 1; i >= 0; i--){ s1 += s[i]; } var x = BinaryToN(s1); return x; ...继续阅读 (27)

题目描述：Follow up for "Remove Duplicates":What if duplicates are allowed at most twice?For example,Given sorted array nums = [1,1,1,2,2,3],Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.移除数组中的重复元素，返回新长度。思路：1.two pointer方法，使用两个指针一前一后（i后，j前），初始化：i=2，j=12.i一直往后走，如果nums[i]不等于nums[j]，或nums[i]不等nums[j-1]：nums[j]=nums[i]，j往后走。3.最后返回j+1实现代码：public int RemoveDuplicates(int[] nums) { if(nums == null){ return 0; } var n = nums.Length; if(n < 3){ return n; ...继续阅读 (27)

题目描述：Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].Solve it without division and in O(n).For example, given [1,2,3,4], return [24,12,8,6].输入数组Nums，返回一个数组output，要求output[i]为，nums[0]...nums[i-1],nums[i+1]....nums[n]的乘积。思路：1.区分是否包含0的情况，存0的索引。2.考虑越界的情况实现代码：public class Solution { public int[] ProductExceptSelf(int[] nums) { if(nums == null || nums.Length == 1){ return nums; } var output = new int[nums.Length]; var zeroIndexes = new List<int>(); for(var i =0 ;i ...继续阅读 (27)

题目描述：Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].对一个数组生成全排列。与Permutation 1几乎一模一样：https://leetcode.com/problems/permutations/唯一不同在于需要去除重复的序列。思路：与Permutation 1 不同，本题采用Heap Permutation的解法来生成全排列。具体参考：https://en.wikipedia.org/wiki/Heap%27s_algorithm实现代码：public class Solution { public IList<IList<int>> PermuteUnique(int[] nums) { var n = nums.Length ; var lst = new List<int>(nums); var dict = new Dictionary<str ...继续阅读 (39)

题目描述：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.Subscribe to see which companies asked this question完成两个字符串相乘。思路：1. 实现1个字符与字符串的相乘函数2. 实现两个字符串相加的函数3. 遍历num1[]，将num1[i]与num2相乘得到r，使用result累加保存r (r需要每次追加'0')。实现代码：public class Solution { public string Multiply(string num1, string num2) { if(string.IsNullOrEmpty(num1) || string.IsNullOrEmpty(num2)){ return ""; } if(num1 == "0" || num2 == "0"){ return "0" ...继续阅读 (20)

题目描述：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at any point in time.在一个m*n的矩阵中，从左上角的位置开始向右下移动，每次只能走右或下。每个单元格包含1个非负数得到和s，每走一步累加这个数字。求从左上到右下路径中的最小s。思路：1.dp问题。初始化dp[0,0] = grid[0,0]。2.初始化第一行和第一列：dp[i,0] = dp[i-1,0] + grid[i,0]；dp[0,i] = dp[0,i-1] + grid[0,i]3.从[i,j]（初始化为[1,1]）的位置向下走，从dp[i-1,j]与dp[i,j-1]中取最小值min，设置dp[i,j] = min + grid[i,j]。4.最后的dp[row-1,col-1]即为最小和。实现代码：public class Solution { public int MinPathSum(int[,] grid) { var ro ...继续阅读 (57)

题目描述：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.就是求一个树的最小层数。思路：从根节点进行BFS ，找到第一个叶子节点即可。实现代码：/** * 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 int MinDepth(TreeNode root) { if(root == null){ return 0; } var layer = 1; var nodes = new List< ...继续阅读 (31)

题目描述：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.在数组nums[]中找到连续子序列构成的最大和。思路：一道典型的DP题。1.使用dp[i]来表示i位置所能达到的最大和2.如果dp[i-1]+nums[i]大于nums[i]，则dp[i] = dp[i-1]+nums[i]；否则，dp[i] = nums[i]。实现代码：public class Solution { public int MaxSubArray(int[] nums) { if(nums.Length == 0){ return 0; } var dp = new int[nums.Length]; dp[0] = nums[0]; for(var i = 1;i < nums.Length; i++){ ...继续阅读 (30)

题目描述：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.在数组nums[]中找到连续子序列构成的最大和。思路：一道典型的DP题。1.使用dp[i]来表示i位置所能达到的最大和2.如果dp[i-1]+nums[i]大于nums[i]，则dp[i] = dp[i-1]+nums[i]；否则，dp[i] = nums[i]。实现代码：public class Solution { public int MaxSubArray(int[] nums) { if(nums.Length == 0){ return 0; } var dp = new int[nums.Length]; dp[0] = nums[0]; for(var i = 1;i < nums.Length; i++){ ...继续阅读 (40)

题目描述：Given an unsorted array, find the maximum difference between the successive elements in its sorted form.Try to solve it in linear time/space.Return 0 if the array contains less than 2 elements.You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.本题直接使用.net内置（或其他编程语言）的排序算法就可以，然后计算间隔找出最大的就行了。以下是一种最简单的实现方式，调用 LINQ的sort（内部实现为stable的快排）然后计算间隔。 public class Solution { public int MaximumGap(int[] nums) { if(nums == null || nums.Length < 2){ return 0; } var lst = nums.OrderBy(n=>n).ToList(); ...继续阅读 (34)

题目描述：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.在一个数组中找到第k大的数字。首先要确定的是，本题可以通过某种排序来完成。由于要找到第k个数字，那么可以通过选择排序或堆排序；显然，堆排序效率更好一些。可以大根堆或小根堆来完成，第k大的数，显然使用大根堆。1.建立堆。2.找出前k大的数字，存入集合List。3.返回List中的最后一个即可。实现代码：public class Solution { public int FindKthLargest(int[] nums, int k) { var index = k - 1; if(index >= nums.Length){ index = nums.Length - 1; } var r = TopK(nums.ToList(), index); return r.Last(); ...继续阅读 (49)

题目描述：Given an array of strings, group anagrams together.For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:[  ["ate", "eat","tea"],  ["nat","tan"],  ["bat"]]Note:For the return value, each inner list's elements must follow the lexicographic order.All inputs will be in lower-case.给定一个单词数组，对它们进行分组：由同样字母组成的单词分为一组。例如ate和eat分为一组。思路：1.使用哈希表存单词的升序排列2.遍历每个单词的过程中，将其升序排列后判断是否在哈希表中存在：如果存在添加到组内；否则创建新组。3.返回结果前需要对哈希的每个组内的单词进行升序排列。实现代码：public class So ...继续阅读 (41)

问题描述： Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.Note:You must not modify the array (assume the array is read only).You must use only constant, O(1) extra space.Your runtime complexity should be less than O(n2).There is only one duplicate number in the array, but it could be repeated more than once.在一个数组中找到重复的那个。由于题目限制了只能使用O(1)的空间，也不能修改参数数组。因此不能排序，也不能创造一个标记数组来一次遍历进行'填空'；并且，由于重复元素可以出现多次，也无法使用等差数列公式求和=>s，再用数组和-s的 ...继续阅读 (46)

题目描述：Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]在小于等于n的数构成的子集中，找到长度为k的子集。例如小于3的子集有{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}，而当k=2时，符合条件的子集为[{1,2},{2,3},{1,3}]。已知k的取值范围是[1,n]。思路：对[1,n]每个元素进行回溯。每次添加当前元素i并进入新过程后还原状态（删除i）。如果当前集合长度等于k添加到结果集并返回。实现代码：public class Solution { public IList<IList<int>> Combine(int n, int k) { var result = new List<IList<int>>(); Do(1, n, k, new List<int ...继续阅读 (39)