Follow up for "Find Minimum in Rotated Sorted Array":What if duplicates are allowed?Would this affect the run-time complexity? How and why?Suppose a sorted array is rotated at some pivot unknown to yo ...继续阅读 (13)

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).Find the minimum element.You may assume no duplicate exists in the array.思路分析：这题主要考察二分查找，在Rotated Sorted Array中找最小和Search in Rotated Sorted Array类似，只不过此时需要不断把最左边的元素A[l]与A[m]比较1. 如果A[m] < A[l] 那么应该在左边找，更新右边的边界right；2.如果A[m] > A[l] 那么应该在右边找，更新左边的边界left；3.如果A[m]= A[l] ,l++;上述规律可以通过举例子很快发现，这样可以每次减少一般元素，得到O（logN）的算法。注意这题A[m] = A[l] 也有可能发生，虽然没有重复元素，但是m和l可能指向同一个元素，比如当这个数组只有两个元素的时候。如果A[m]= A[l] ,可以执行l++;丢掉一个“冗余元素”也不会丢掉最小值。对于Rotated Sorted Array中有冗余值的情况可以参考本题的扩展Find Minimum in Rota ...继续阅读 (19)

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).Find the minimum element.You may assume no duplicate exists in the array.思路分析 ...继续阅读 (8)

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.For example, given the following matrix:1 0 1 0 0 1 0111 1 1111 1 0 0 1 0Return 4.思路分析：这题考察DP，缓存中间结果减少重复计算，DP方程为if(matrix[i][j] != 0) dp[i,j] = min{dp[i-1,j], dp[i,j-1], dp[i-1,j-1]} + 1; else dp[i,j] = 0其中dp[i,j]表示以[i,j]为右下角的区域内的最大的正方形的边长，最后返回dp数组中最大值的平方即为所求。AC Codepublic class Solution { public int maximalSquare(char[][] matrix) { //dp equation: if(matrix[i][j] != 0) dp[i,j] = min{dp[i-1,j], dp[i,j-1], dp[i-1,j-1]} + 1; else dp[i,j] = 0 int m = matrix.length; ...继续阅读 (22)

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.For example, given the following matrix:1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return ...继续阅读 (11)

Implement the following operations of a queue using stacks.push(x) -- Push element x to the back of queue.pop() -- Removes the element from in front of queue.peek() -- Get the front element.empty() -- Return whether the queue is empty.Notes:You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.You may assume that all op ...继续阅读 (28)

Implement the following operations of a queue using stacks.push(x) -- Push element x to the back of queue.pop() -- Removes the element from in front of queue.peek() -- Get the front element.empty() -- ...继续阅读 (9)

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.Hint:How many majority elements could it possibly have?思路分析：这题是Majority Element的扩展，同样可以采用Moore投票法解决。首先需要分析，如果这样的元素（elements that appear more than ⌊ n/3 ⌋ times）存在，那么一定不会超过两个，证明用反证法很容易理解。接下来就是如何找出这可能的两个元素。可以分两步，找两个candidate和验证candidate出现的次数是否超过⌊ n/3 ⌋ times。 找两个候选candidate的方法就是Moore投票法，和Majority Element中类似。需要验证的原因是，不同于Majority Element中已经限制了主元素一定存在，这题不一定存在这样的元素，即使存在个数也不确定，所以需要验证过程。时间复杂度O（n）,空间复杂度O（1）.AC Code：public class Solution { public Listmajo ...继续阅读 (22)

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.You may assume that the array is non-empty and the majority element always exist in the array.思路分析：求主元素的经典算法是Moore投票算法，基本可以理解为将主元素和不同元素一一对应相消，最后剩下来的元素就是主元素。具体做法是，初始计数器times和candidate都是0,然后遍历数组，当times为0时置换新的candidate，遇到和candidate相同元素times++，遇到和candidate相异元素times--，如此操作，如果主元素存在，最后剩下的一定是主元素。时间复杂度O（n）,空间复杂度O（1）.AC Codepublic class Solution { public int majorityElement(int[] nums) { //0627 //Moore Voting int n = nums.length; int ...继续阅读 (20)

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.Follow up:What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?Hint:Try to utilize the property of a BST.What if you could modify the BST node's structure?The optimal runtime complexity is O(height of BST).思路分析:基本就是实现BST的中序遍历，BST中序遍历得到有序的数组，可以容易知道第k小数，以下给出了递归实现，借助counter记录当前遍历过的node数目，当counter==k时就可以返回。当然也可以借助栈实现迭代的解法。Follow up： ...继续阅读 (42)

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].Follow up:Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)思路分析：基本思路是用两个数组left和right，left保存从最左侧到当前数之前的所有数字的乘积，right保存从最右侧到当前之后的所有数字的乘积，然后，结果数组就是把这两个数组对应位置相乘即可。如果想只是用O（1）的space，就需要复用输入和输出数组的空间，基本思路是，先计算right数组，利用result数组的空间保存，然后计算left数组，只需要一个变量left保存当前从最 ...继续阅读 (28)

Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).Follow up:If this function is called many times, how would you optimize it?Related problem: Reverse Integer思路分析：这题比较简单，基本和Reverse Integer的思路类似，n不断右移位取末位，结果res不断左移位和n的末位取或，如此进行32次即可。考察简单的位运算。AC Codepublic class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { //1145 int res = n & 1; for(int i = 1; i < 32; i++){ ...继续阅读 (35)

Given an array of integers, find out whether there are two distinct indicesiandjin the array such that the difference betweennums[i]andnums[j]is at mosttand the difference betweeniandjis at mostk.思路分析：这题有几个要注意的地方：第一是如何快速搜索是否存在于某个数差值在t以内的数，可以使用TreeSet的subSet函数，可以返回在TreeSet中从在[lower,upper)的数，注意是前闭后开，这个函数返回的是SortedSet接口类型，TreeSet基于BST实现，特别适合于某个range里面的数的快速查找，下面的算法复杂度是O（nlogk）。第二，和Contains Duplicate的前面两题一样，有“the difference betweeniandjis at mostk.”这样的限定的题目我们可以考虑维护一个长度为k的滑动窗口。第三，如果用Integer类型，这题有个test case会使得nums[i] + t + 1溢出变成负数，因此需要使用Long类型来保存数，要注意类型转换。AC Codeimport java.util.SortedSet; // the re ...继续阅读 (33)

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].思路分析：这题基本就是考察双指针的应用，从lower-1开始，遍历nums数组找出missing range，可以利用pre和cur一前一后两个指针移动实现。注意lower和upper的处理，lower可以比nums中最小的数大，upper可以比nums中最大的数小，所以考虑要周全。参考Code（Book中的题目）public ListfindMissingRanges(int[] nums, int lower, int upper) { Listres = new ArrayList(); int pre = lower - 1; for(int i = 0; i < nums.length; i++){ if(i == nums.length){ ...继续阅读 (47)

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as theHamming weight).For example, the 32-bit integer ’11' has binary representation00000000000000000000000000001011, so the function should return 3.Credits:Special thanks to@tsfor adding this problem and creating all test cases.思路分析：这题考察位运算，比较容易想到的思路是不断进行左移位操作然后并且和1做&运算，就可以每次判定最后一位是否是1，从而得到1的个数，见注释的code,这种算法需要做32次移位操作。这题有更快的解法，那就是利用n&(n-1)可以去掉最右侧的1，例如n 000110100n-1 000110011&后 000110000最右侧的1消失。于是我们可以不断做这样的操作直到n变成0。就可以知道有多少个1。n&(n-1)还有一个应用，就是快速判断某个数是否是2的k次方，即判断某个数的二进制表示是否只包括一个1，n&( ...继续阅读 (38)

Invert a binary tree.4 / \ 2 7 / \ / \ 1 3 6 9to4 / \ 7 2 / \ / \ 9 6 3 1Trivia:This problem was inspired bythis original tweetbyMax Howell:Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.思路分析：这是最近比较火的一个题目，因为一条推特的转播“Google HR：我们90%的工程师都用你写的软件，但是你竟然不会在白板上面反转一颗二叉树，所以滚吧”，各方看法不一，但看这个题目，的确是一个很简单的题目。考察最基本的递归和树操作。下面给出了递归实现和借助栈的迭代实现（非递归实现）。后一个版本的可扩展性更好，可以处理更大的树。实在是容易题，就是DFS遍历一遍树节点，把每个树节点的左右孩子互换就可以了。或许是那个ios开发牛人不屑于准备就去Google面试，结果被爆，与其说是能力问题，不如说是态度问题。AC Code/** * Definition for a binar ...继续阅读 (31)

Implement a trie withinsert,search, andstartsWithmethods.Note:You may assume that all inputs are consist of lowercase lettersa-z.思路分析：这题主要考察Trie 即前缀树的实现，Trie可以用于字典的压缩存储，可以节省空间，但是不节省时间（和HashSet相比）。这题实质是实现一颗多叉树（分支因子26）的插入和查找操作。定义每个TrieNode保存char c，保存一个HashMap用于储存所有的孩子节点，key是对应的字符，value是孩子节点，定义flag hasWord来标记这个node上是否存在word。对于插入操作，直接从上向下分层扫描树，如果没有对应字符节点存在就新建节点，如果有就去相应路径向下探察。对于查询操作，前缀树的定义可以保证当我们从前向后扫描字符串时候，每一个字符都可以从上到下对应前缀树的每一层，所以扫描过程中如果有任何一个字符不存在于当前层中，就可以立刻停止查找返回null，也就是不存在这样的word或者前缀，否则继续从对应的分支向下探察。时间复杂度是O（L），L是树的高度，也就是最长word的长度，空间复杂度26^L，每一层分支因子26，有L层。AC Codeclass TrieNode { // Initialize y ...继续阅读 (31)

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.思路分析:这题很简单，一个HashSet搞定。AC Codepublic class Solution { public boolean containsDuplicate(int[] nums) { SetappearedNum = new HashSet(); for(int i = 0; i < nums.length; i++){ if(!appearedNum.contains(nums[i])){ appearedNum.add(nums[i]); } else return true; } return false; } } ...继续阅读 (32)

Given an array of integers and an integerk, find out whether there there are two distinct indicesiandjin the array such thatnums[i] = nums[j]and the difference betweeniandjis at mostk.思路分析：这题比较简单，可以直接定义一个长度最大为k的滑动窗口，用一个set维护窗口内的数字判断是否出现重复，使用两个指针start和end标记滑动窗口的两端，初始都是0，然后end不断进行扩展，扫描元素判断是否出现重复元素，直到发现end-start>k, 就开始移动start，并且在set中移除对应的元素。如果以为扫描到数组末尾还没有发现重复元素，那就可以返回false。时间复杂度和空间复杂度都是O（N）。AC Codepublic class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { //0842 SetappearedNum = new HashSet(); int start = 0, end = 0; for(int i = 0; i < ...继续阅读 (19)

Write an algorithm to determine if a number is "happy".A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.Example:19 is a happy number12+ 92= 8282+ 22= 6862+ 82= 10012+ 02+ 02= 1思路分析：这题比较简单，就是不断的做各个位置数字的平方加和操作，看是否会产生1。但是有一个地方要注意，就是怎么判断出现了循环，这里定义了一个Set，保存所有出现过的数字，对于计算得到的新的和，如果没有在Set中出现，就添加到Set中继续进行平 ...继续阅读 (20)

Description:Count the number of prime numbers less than a non-negative number,n.思路分析：这题是一道数学题，求小于n的所有质数。容易想到的思路是定义个isPrime的判定函数，对小于n的数一个一个判定，但是时间复杂度O（N^2）。有没有更快的算法呢？有，这是一个经典的找质数的算法，Sieve of Eratosthenes，名字虽然比较奇怪，但是其实是一个很简单易懂的算法，wiki上有一张图，生动显示了找质数的过程：简而言之，就是初始假定所有数都是质数，然后从2+2开始，划掉2+2×2，2+2×3...也就是把2的所有倍数划掉（不含2，因为2是质数），同理然后把3的所有倍数划掉，以此类推，如果i是质数，那么把i的所有倍数划掉，最后数一下剩下来的质数个数即可。时间复杂度 O(n log log n)，空间复杂度是O（n）。当然下面的code还有可以优化的地方，比如定义isNotPrime数组，避免开始遍历一遍所有数组，默认为false，最后的count过程也可以写进前面的遍历过程，减少遍历次数，但是时间复杂度还是不改变。AC Codepublic class Solution { public int countPrimes(int n) { if(n <= 2) return 0; ...继续阅读 (36)

Given a binary tree, imagine yourself standing on therightside of it, return the values of the nodes you can see ordered from top to bottom.For example:Given the following binary tree,1 <--- / \ 2 3 <--- \ \ 5 4 <---You should return[1, 3, 4].思路分析：这题本质上是考察树的遍历，读完题目要能准备理解题意就是要返回每一个level最右边的结点，所以想到用BFS，借助队列实现，但是每一层从右向左扫描，同时记住index，每一个level index为0的node就是需要保存到结果之中的node。时间复杂度O（N），空间复杂度也是O（N），因为需要额外队列保存结点。AC Code/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode( ...继续阅读 (19)

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.思路分析：这题要求拷贝链表，包括内容，next指针和random指针。容易想到的思路是定义一个hashmap保存旧链表节点到新链表节点的映射关系，第一次遍历链表，只拷贝next指针和node，并且init hashmap， 第二遍遍历链表再拷贝所有节点的random指针,借助hashmap可以在O（1）时间内由给定旧链表节点找到新链表对应节点。时间复杂度和空间复杂度都是O（n）。另有一个解法不需要额外空间，需要三遍遍历，要仔细画图分析，详细可见http://codeganker.blogspot.com/2014/03/copy-list-with-random-pointer-leetcode.htmlhttp://blog.csdn.net/fightforyourdream/article/details/16879561AC Code/** * Definition for singly-linked list with a random pointer ...继续阅读 (22)

The set[1,2,3,…,n]contains a total ofn! unique permutations.By listing and labeling all of the permutations in order,We get the following sequence (ie, forn= 3):"123""132""213""231""312""321"Givennandk, return thekthpermutation sequence.Note:Givennwill be between 1 and 9 inclusive.思路分析：这题主要是需要找规律，n个数的permutation总共有n!个，如果当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，把k%(n-1)!得到的是剩余部分的permutation index，k/(n-1)!可以返回num的index(即1，2，3...n中的哪一个)，如此操作，初始令round=n-1, 不断执行k%(n-1)!并执行round--，直到round=0，就可以拼出所求的permutation sequence。注意初始要执行k--，这样k就是从0开始，numIdx也可以从0开始，这样才可以求出争取的nu ...继续阅读 (36)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonightwithout alerting the police.思路分析：典型的动态规划，和求最大和子数组有点类似，global[i] 表示num[0...i]之间的最优解，那么DP方程可以写作global[i] = Max(global[i-2] + ...继续阅读 (32)

matlab矩阵的表示和简单操作转自 http://www.cnblogs.com/Ran_Ran/archive/2010/12/11/1903070.html 的matlab 矩阵运算的经典总结一、矩阵的表示在MATLAB中创建矩阵有以下规则：a、矩阵元素必须在”[ ]”内；b、矩阵的同行元素之间用空格（或”,”）隔开；c、矩阵的行与行之间用”;”（或回车符）隔开；d、矩阵的元素可以是数值、变量、表达式或函数；e、矩阵的尺寸不必预先定义。二，矩阵的创建：1、直接输入法最简单的建立矩阵的方法是从键盘直接输入矩阵的元素，输入的方法按照上面的规则。建立向量的时候可以利用冒号表达式，冒号表达式可以产生一个行向量，一般格式是： e1:e2:e3，其中e1为初始值，e2为步长，e3为终止值。还可以用linspace函数产生行向量，其调用格式为：linspace(a,b,n) ，其中a和b是生成向量的第一个和最后一个元素，n是元素总数。2、利用MATLAB函数创建矩阵基本矩阵函数如下：(1) ones()函数：产生全为1的矩阵，ones(n)：产生n*n维的全1矩阵，ones(m,n)：产生m*n维的全1矩阵；(2) zeros()函数：产生全为0的矩阵；(3) rand()函数：产生在（0，1）区间均匀分布的随机阵；(4) eye()函数：产生单位阵；(5) randn()函数：产生均值为 ...继续阅读 (40)

Given an unsorted integer array, find the first missing positive integer.For example,Given[1,2,0]return3,and[3,4,-1,1]return2.Your algorithm should run inO(n) time and uses constant space.思路分析：这题要求O(n)时间和常数空间。肯定不能使用基于比较的排序，于是考虑counting sort，Bucketsort，radix sort等O（n）的Distribution sorts排序算法。借助桶排序的思想，我们重用输入的数组，进行数据交换使得A[0]=1,A[1]=2,...A[i]=i+1，这样我们就可以从前向后扫描，如果那个数违反了A[i]=i+1，那就是说明第一个缺失的正数是i+1。所以可以扫描数组，把数A[i]换到index为A[i]-1处，但是对于负数，0或者不在数组range内的数跳过。有一个比较tricky的地方是，当进行交换后，要注意换过来的新数是否满足A[i]=i+1，如果不满足还要继续进行交换。所以我们有i--的操作，交换后仍然检查一次当前位置。最后在wiki上摘录排序算法分类如下：Sorting algorithmsExchange sortsBubble sort Coc ...继续阅读 (34)

Given a string containing just the characters'('and')', find the length of the longest valid (well-formed) parentheses substring.For"(()", the longest valid parentheses substring is"()", which has length = 2.Another example is")()())", where the longest valid parentheses substring is"()()", which has length = 4.思路分析：这题做括号匹配，很容易想到用栈，但是这题栈里面保存括号的index比较好，方便长度计算。基本做法是，遇到左括号入栈，遇到右括号出栈，当进行出栈操作的时候，考虑两种情况1 当前栈为空，那么没法匹配这个右括号，以该位置的下一个位置i+1为考察括号子串的起点。2 当前栈不为空，弹出栈顶元素。弹出后如果栈为空，那么合法子串长度是i-start+1;弹出后栈不为空，也就是还有多余的左括号在里面，那么合法子串长度为从当前栈顶元素下一个元素开始，到i结束，也就是i-(stack.peek()+1)+1 = i - stack.peek()。对字符串进行一遍扫描，时间复杂度 ...继续阅读 (45)

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.OJ's undirected graph serialization:Nodes are labeled uniquely.We use#as a separator for each node, and,as a separator for node label and each neighbor of the node.As an example, consider the serialized graph{0,1,2#1,2#2,2}.The graph has a total of three nodes, and therefore contains three parts as separated by#.First node is labeled as0. Connect node0to both nodes1and2.Second node is labeled as1. Connect node1to node2.Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.V ...继续阅读 (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 X X O O X X X O X X O X XAfter running your function, the board should be:X X X X X X X X X X X X X O X X思路分析：这题比较简单，主要考察搜索，基本的思路是搜索和边缘的O连通的那些O，用特殊字符#标记出来，然后遍历矩阵把O赋为X，把#赋值为O。而搜索与边缘的O连通的O的方法，可以用DFS或者BFS，尝试从边缘每一个O开始搜索。但是这题用DFS递归写法会超时，因为测试用例有一个很大的矩阵，会导致递归栈溢出。下面AC Code用的是BFS，借助于队列实现的迭代式的BFS。另外队列保存的是矩阵中的数的一维index，要注意换算方法。这个算法在图形学中称为Flood fill算法。时间复杂度为O(mn)，空间复杂度为O（m+n）。AC Codepublic class Solution { //use bfs search(in an iterat ...继续阅读 (38)