leetcode算法精髓C++語(yǔ)言版本

soulmachinePublishedsoulmachine算法精粹算法精粹PAGE10PAGE10TableofContents介紹線性表數(shù)組RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayIILongestConsecutiveSequence3Sum3Sum4SumRemoveElementMoveZeroesNextPermutationPermutationSequenceValidSudokuTrappingRainWaterRotateImagePlusOneClimbingStairsSetMatrixZeroesGasStationCandyMajorityElementRotateArrayContainsDuplicateContainsDuplicateIIContainsDuplicateIII

01ProductofArrayExceptSelfGameofLifeIncreasingTripletSubsequence單鏈表ReverseLinkedListOddEvenLinkedListAddTwoNumbersReverseLinkedListIIPartitionListRemoveDuplicatesfromSortedListRemoveDuplicatesfromSortedListIIRotateListRemoveNthNodeFromEndofListSwapNodesinPairsReverseNodesink-GroupCopyListwithRandomPointerLinkedListCycleLinkedListCycleIIReorderListLRUCachePalindromeLinkedList字符串ValidPalindromeImplementstrStr()StringtoInteger(atoi)AddBinaryLongestPalindromicSubstringRegularExpressionMatchingWildcardMatchingLongestCommonPrefix

2ValidNumberIntegertoRomanRomantoIntegerCountandSayAnagramsAnagramSimplifyPathLengthofLastWordIsomorphicStringsWordPattern棧和隊(duì)列棧MinStackParenthesesLongestParenthesesLargestRectangleinHistogramEvaluateReversePolishNotationImplementStackusingQueues隊(duì)列ImplementQueueusingStacks二叉樹(shù)二叉樹(shù)的遍歷BinaryPreorderTraversalBinaryInorderTraversalBinaryPostorderTraversalBinaryLevelOrderTraversalBinaryLevelOrderTraversalIIBinaryRightSideViewInvertBinaryTreeBinarySearchTreeIterator

34BinaryTreeZigzagLevelOrderTraversalRecoverBinarySearchTreeSameTreeSymmetricTreeBalancedBinaryTreeFlattenBinaryTreetoLinkedListPopulatingNextRightPointersinEachNodeII二叉樹(shù)的構(gòu)建ConstructBinaryfromPreorderandInorderTraversalConstructBinaryfromInorderandPostorderTraversal二叉查找樹(shù)UniqueBinarySearchTreesUniqueBinarySearchTreesIIValidateBinarySearchTreeConvertSortedArraytoBinarySearchTreeConvertSortedListtoBinarySearchTreeLCAofBSTKthSmallestElementinaBST二叉樹(shù)的遞歸MinimumDepthofBinaryMaximumDepthofBinaryPathSumPathSumIIBinaryTreeMaximumPathSumPopulatingNextRightPointersinEachNodeSumRoottoLeafNumbersLCAofBinaryTree線段樹(shù)RangeSumQuery-Mutable排序

5插入排序InsertionSortList歸并排序MergeTwoSortedArraysMergeTwoSortedListsMergekSortedListsSortList快速排序SortColorsKthLargestElementinanArray桶排序FirstMissingPositive計(jì)數(shù)排序H-Index基數(shù)排序MaximumGap其他LargestNumber小結(jié)查找SearchforaRangeSearchInsertPositionSearchinRotatedSortedArraySearchinRotatedSortedArrayIISearcha2DMatrixSearcha2DMatrixIIFindMinimuminRotatedSortedArrayFindMinimuminRotatedSortedArrayIIMedianofTwoSortedArraysH-IndexII

6暴力枚舉法SubsetsSubsetsIIPermutationsPermutationsIICombinationsLetterCombinationsofaPhoneNumber廣度優(yōu)先搜索WordLadderWordLadderIISurroundedRegions總結(jié)深度優(yōu)先搜索AdditiveNumberPalindromePartitioningUniquePathsUniquePathsIIN-QueensN-QueensIIRestoreIPAddressesCombinationSumCombinationSumIICombinationSumIIIGenerateParenthesesSudokuSolverWordSearch總結(jié)分治法Pow(x,n)Sqrt(x)

789貪心法JumpGameJumpGameIIBestTimetoBuyandSellStockBestTimetoBuyandSellStockIILongestSubstringWithoutRepeatingCharactersContainerWithMostPatchingArray動(dòng)態(tài)規(guī)劃TriangleMaximumSubarrayMaximumProductSubarrayLongestIncreasingSubsequencePalindromePartitioningIIMaximalRectangleBestTimetoBuyandSellStockIIIBestTimetoBuyandSellStockIVBestTimetoBuyandSellStockwithCooldownInterleavingStringScrambleStringMinimumPathSumEditDistanceDecodeWaysDistinctSubsequencesWordBreakWordBreakIIDungeonGameHouseRobberHouseRobberIIHouseRobberIII

RangeSumQuery-ImmutableRangeSumQuery2D-Immutable圖CloneGraph位操作ReverseBitsRepeatedDNASequencesNumberof1BitsGrayCodeSingleNumberSingleNumberIISingleNumberIIIPowerofMissingNumberMaximumProductofWordLengthsBitwiseANDofNumbersRangePowerofThreeRectangleArea數(shù)論HappyNumberUglyNumberUglyNumberIISuperUglyNumberFractiontoRecurringDecimalFactorialTrailingZeroesNimGame模擬ReverseIntegerPalindromeNumberInsertInterval

MergeIntervalsMinimumWindowSubstringMultiplyStringsSubstringwithConcatenationofAllWordsPascal'sTrianglePascal'sTriangleIISpiralMatrixSpiralMatrixIIZigZagConversionDivideIntegersJustificationMaxPointsonaLine

16.416.516.616.716.816.916.1016.1216.1316.1416.15算法精粹算法精粹介紹PAGE19介紹PAGE19算法精粹——舉一反三，拋棄題海戰(zhàn)術(shù)剛接觸ACM算法競(jìng)賽的新手。背后有強(qiáng)大的AlgoHub支持。(即將上線上在線判斷代碼。這樣的一大好處是，讀者可以邊看書(shū)，邊實(shí)現(xiàn)自己的代碼，然后提交到網(wǎng)站上驗(yàn)證自己的想法是否正確。AlgoHub的使命是成為最好的算法學(xué)習(xí)和交流平臺(tái)。AlgoHubPOJ,ZOJ,leetcodeHackerRank等網(wǎng)站的經(jīng)典題目（一些質(zhì)量不高的題目則忽略），AlgoHub有非常簡(jiǎn)單的加題系統(tǒng)，用戶不需要寫(xiě)一行代碼即可自己添加題目，所以AlgoHub的題庫(kù)還在飛速增長(zhǎng)中。每道題都有完整的代碼。提下盡可能簡(jiǎn)短，方面讀者在面試中能快速寫(xiě)出來(lái)。每道題都有多種解法。反三，讓讀者觸類旁通。本書(shū)支持多種主流編程語(yǔ)言。目前支持Java,C++,C#,Python,Ruby,JavaScript,Swift,Scala,Clojure,將來(lái)還會(huì)支持更多編程語(yǔ)言。在線閱讀/book/soulmachine/algorithm-essentials/內(nèi)容目錄介紹線性表數(shù)組RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayIILongestConsecutiveSequence3Sum3Sum4SumRemoveElementMoveZeroesNextPermutationPermutationSequenceValidSudokuTrappingRainWaterRotateImagePlusOneClimbingStairsSetMatrixZeroesGasStationCandyMajorityElementRotateArrayContainsDuplicateContainsDuplicateIIContainsDuplicateIIIProductofArrayExceptSelfGameofLifeIncreasingTripletSubsequence單鏈表ReverseLinkedListOddEvenLinkedList

AddTwoNumbersReverseLinkedListIIPartitionListRemoveDuplicatesfromSortedListRemoveDuplicatesfromSortedListIIRotateListRemoveNthNodeFromEndofListSwapNodesinPairsReverseNodesink-GroupCopyListwithRandomPointerLinkedListCycleLinkedListCycleIIReorderListLRUCachePalindromeLinkedListValidPalindromeImplementstrStr()StringtoInteger(atoi)AddBinaryLongestPalindromicSubstringRegularExpressionMatchingWildcardMatchingLongestCommonPrefixValidNumberIntegertoRomanRomantoIntegerCountandSayAnagramsAnagramSimplifyPathLengthofLastWordIsomorphicStringsWordPattern棧和隊(duì)列棧MinStackParenthesesLongestParenthesesLargestRectangleinHistogramEvaluateReversePolishNotationImplementStackusingQueues隊(duì)列ImplementQueueusingStacks二叉樹(shù)二叉樹(shù)的遍歷BinaryPreorderTraversalBinaryInorderTraversalBinaryPostorderTraversalBinaryLevelOrderTraversalBinaryLevelOrderTraversalIIBinaryRightSideViewInvertBinaryTreeBinarySearchTreeIteratorBinaryTreeZigzagLevelOrderTraversalRecoverBinarySearchTreeSameTreeSymmetricTreeBalancedBinaryTreeFlattenBinaryTreetoLinkedListPopulatingNextRightPointersinEachNodeII二叉樹(shù)的構(gòu)建ConstructBinaryTreefromPreorderandInorderTraversalConstructBinaryTreefromInorderandPostorderTraversal二叉查找樹(shù)UniqueBinarySearchTreesUniqueBinarySearchTreesIIValidateBinarySearchTreeConvertSortedArraytoBinarySearchTreeConvertSortedListtoBinarySearchTreeLCAofBSTKthSmallestElementinaBST二叉樹(shù)的遞歸MinimumDepthofBinaryMaximumDepthofBinaryPathSumPathSumIIBinaryTreeMaximumPathSumPopulatingNextRightPointersinEachNodeSumRoottoLeafNumbersLCAofBinaryTree線段樹(shù)RangeSumQuery-Mutable排序插入排序InsertionSortList歸并排序MergeTwoSortedArraysMergeTwoSortedListsMergekSortedListsSortList快速排序SortColorsKthLargestElementinanArray桶排序FirstMissingPositive計(jì)數(shù)排序H-Index基數(shù)排序MaximumGap其他LargestNumber小結(jié)查找SearchforaRangeSearchInsertPositionSearchinRotatedSortedArraySearchinRotatedSortedArrayIISearcha2DMatrixSearcha2DMatrixIIFindMinimuminRotatedSortedArrayFindMinimuminRotatedSortedArrayIIMedianofTwoSortedArraysH-IndexII暴力枚舉法SubsetsSubsetsIIPermutationsPermutationsIICombinationsLetterCombinationsofaPhoneNumber廣度優(yōu)先搜索WordLadderWordLadderIISurroundedRegions總結(jié)深度優(yōu)先搜索AdditiveNumberPalindromePartitioningUniquePathsUniquePathsIIN-QueensN-QueensIIRestoreIPAddressesCombinationSumCombinationSumIICombinationSumIIIGenerateParenthesesSudokuSolverWordSearch總結(jié)分治法Pow(x,n)Sqrt(x)貪心法JumpGameJumpGameIIBestTimetoBuyandSellStockBestTimetoBuyandSellStockIILongestSubstringWithoutRepeatingCharactersContainerWithMostPatchingArray動(dòng)態(tài)規(guī)劃TriangleMaximumSubarrayMaximumProductSubarrayLongestIncreasingSubsequencePalindromePartitioningIIMaximalRectangleBestTimetoBuyandSellStockIIIBestTimetoBuyandSellStockIVBestTimetoBuyandSellStockwithCooldownInterleavingStringScrambleStringMinimumPathSumEditDistanceDecodeWaysDistinctSubsequencesWordBreakWordBreakIIDungeonGameHouseRobberHouseRobberIIHouseRobberIIIRangeSumQuery-ImmutableRangeSumQuery2D-Immutable圖CloneGraph位操作ReverseBitsRepeatedDNASequencesNumberof1BitsGrayCodeSingleNumberSingleNumberIISingleNumberIIIPowerofMissingNumberMaximumProductofWordLengthsBitwiseANDofNumbersRangePowerofThreeRectangleArea數(shù)論HappyNumberUglyNumberUglyNumberIISuperUglyNumberFractiontoRecurringDecimalFactorialTrailingZeroesNimGame模擬ReverseIntegerPalindromeNumberInsertIntervalMergeIntervalsMinimumWindowSubstringMultiplyStringsSubstringwithConcatenationofAllWordsPascal'sTrianglePascal'sTriangleIISpiralMatrixSpiralMatrixIIZigZagConversionDivideIntegersJustificationMaxPointsonaLineCommunityQQ237669375Github:/soulmachine/algorithm-essentials微博：@靈魂機(jī)器LicenseBookLicense:CCBY-SA3.0License算法精粹算法精粹線性表PAGE20線性表PAGE20這類題目考察線性表的操作，例如，數(shù)組，單鏈表，雙向鏈表等。算法精粹算法精粹數(shù)組PAGE21數(shù)組PAGE21本節(jié)主要講關(guān)于數(shù)組的各種算法題。算法精粹算法精粹RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayPAGE23RemoveDuplicatesfromSortedArray描述Givenasortedarray,removetheduplicatesinplacesuchthateachelementappearonlyonceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.Forexample,GiveninputarrayA=[1,1,2],Yourfunctionshouldreturnlength=2,andAisnow[1,2].分析無(wú)代碼//RemoveDuplicatesfromSortedArray//RemoveDuplicatesfromSortedArray//時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)classSolution{public:intremoveDuplicates(vector<int>&nums){if(nums.empty())return0;intindex=1;for(inti=1;i<nums.size();i++){if(nums[i]!=nums[index-1])nums[index++]=nums[i];}returnindex;}};相關(guān)題目RemoveDuplicatesfromSortedArrayII算法精粹算法精粹RemoveDuplicatesfromSortedArrayIIRemoveDuplicatesfromSortedArrayIIPAGE25RemoveDuplicatesfromSortedArrayII描述Followupfor"RemoveDuplicates":Whatifduplicatesareallowedatmosttwice?Forexample,givensortedarrayA=[1,1,1,2,2,3],yourfunctionshouldreturnlength=5,andAisnow[1,1,2,2,3]分析變量即可解決。如果是沒(méi)有排序的數(shù)組，則需要引入一個(gè)hashmap來(lái)記錄出現(xiàn)次數(shù)。代碼1//RemoveDuplicatesfromSortedArrayII//RemoveDuplicatesfromSortedArrayII//Timecomplexity:O(n),SpaceComplexity:O(1)classSolution{public:intremoveDuplicates(vector<int>&nums){if(nums.size()<=2)returnnums.size();intindex=2;for(inti=2;i<nums.size();i++){if(nums[i]!=nums[index-2])nums[index++]=nums[i];}returnindex;}};代碼2下面是一個(gè)更簡(jiǎn)潔的版本。上面的代碼略長(zhǎng)，不過(guò)擴(kuò)展性好一些，例如將occur2改為occur3，就變成了允許重復(fù)最多3次。};};}nums[index++]=nums[i];}returnindex;//RemoveDuplicatesfromSortedArrayII//TimeComplexity:O(n),SpaceComplexity:O(1)classSolution{public:intremoveDuplicates(vector<int>&nums){constintn=nums.size();intindex=0;for(inti=0;i<n;++i){if(i>0&&i<n-1&&nums[i]==nums[i-1]&&nucontinue;相關(guān)題目RemoveDuplicatesfromSortedArray算法精粹算法精粹LongestConsecutiveSequencePAGE27LongestConsecutiveSequencePAGE27LongestConsecutiveSequence描述Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.Forexample,Given[100,4,200,1,3,2],Thelongestconsecutiveelementssequenceis[1,2,3,4].Returnitslength:4.algorithmshouldruninO(n)分析如果允許O(nlogn)的復(fù)雜度，那么可以先排序，可是本題要求O(n)。由于序列里的元素是無(wú)序的，又要求O(n)，首先要想到用哈希表。張，直到不連續(xù)為止，記錄下最長(zhǎng)的長(zhǎng)度。代碼};};}intlongest=0;for(autoi:nums){intlength=1;for(intj=i-1;my_set.find(j)!=my_set.end();--my_set.erase(j);++length;}for(intj=i+1;my_set.find(j)!=my_set.end();++my_set.erase(j);++length;}longest=max(longest,length);}returnlongest;//LongestConsecutiveSequence//TimeComplexity:O(n)，SpaceComplexity:O(n)classSolution{public:intlongestConsecutive(constvector<int>&nums){unordered_set<int>my_set;for(autoi:nums)my_set.insert(i);算法精