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. //This question is the advanced version of question “Search in Rotated Sorted Array I” […]
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 […]
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 […]
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 3 But the following is not: 1 / \ 2 2 \ \ 3 […]
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an […]
Remove Duplicates from Sorted List II 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. 困倦时不要解题，这题做了3遍才AC。 一个bonus，删掉多余的node，以免内存溢出。 我用了superHead的技巧，不用再单独判断链表的起始情况。 查看当前节点和下一个节点，如果相同，将isDuplicated置1.当遇到当前节点和下一节点不同时，看isDuplicated的值，如果是1，则忽略掉它，把isDuplicated置0.如果是0，证明当前节点没有重复，连入结果链表中。 /** * Definition for singly-linked list. * struct ListNode { […]
Remove Duplicates from Sorted Array II Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3]. 很奇怪的题，和此题的第一代没有本质区别。 只要增加一个变量count记录当前已经出现的相同数字的个数。 如果count>2，不移动start，如果小于等于2，copy A[i] to A[start++]。 class Solution { public: int […]
Search a 2D Matrix 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 from left to right. The first integer of each row is greater than the last integer of the previous […]
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. click to show follow up. Follow up:Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A […]
Given an absolute path for a file (Unix-style), simplify it. For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c” click to show corner cases. Corner Cases: Did you consider the case where path = “/../”? In this case, you should return “/”. Another corner case is the […]
