leetcode算法精髓C++语言版本

soulmachinePublishedsoulmachine算法精粹算法精粹PAGE10PAGE10TableofContents介绍线性表数组RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayIILongestConsecutiveSequence3Sum3Sum4SumRemoveElementMoveZeroesNextPermutationPermutationSequenceValidSudokuTrappingRainWaterRotateImagePlusOneClimbingStairsSetMatrixZeroesGasStationCandyMajorityElementRotateArrayContainsDuplicateContainsDuplicateIIContainsDuplicateIII

01ProductofArrayExceptSelfGameofLifeIncreasingTripletSubsequence单链表ReverseLinkedListOddEvenLinkedListAddTwoNumbersReverseLinkedListIIPartitionListRemoveDuplicatesfromSortedListRemoveDuplicatesfromSortedListIIRotateListRemoveNthNodeFromEndofListSwapNodesinPairsReverseNodesink-GroupCopyListwithRandomPointerLinkedListCycleLinkedListCycleIIReorderListLRUCachePalindromeLinkedList字符串ValidPalindromeImplementstrStr()StringtoInteger(atoi)AddBinaryLongestPalindromicSubstringRegularExpressionMatchingWildcardMatchingLongestCommonPrefix

2ValidNumberIntegertoRomanRomantoIntegerCountandSayAnagramsAnagramSimplifyPathLengthofLastWordIsomorphicStringsWordPattern栈和队列栈MinStackParenthesesLongestParenthesesLargestRectangleinHistogramEvaluateReversePolishNotationImplementStackusingQueues队列ImplementQueueusingStacks二叉树二叉树的遍历BinaryPreorderTraversalBinaryInorderTraversalBinaryPostorderTraversalBinaryLevelOrderTraversalBinaryLevelOrderTraversalIIBinaryRightSideViewInvertBinaryTreeBinarySearchTreeIterator

34BinaryTreeZigzagLevelOrderTraversalRecoverBinarySearchTreeSameTreeSymmetricTreeBalancedBinaryTreeFlattenBinaryTreetoLinkedListPopulatingNextRightPointersinEachNodeII二叉树的构建ConstructBinaryfromPreorderandInorderTraversalConstructBinaryfromInorderandPostorderTraversal二叉查找树UniqueBinarySearchTreesUniqueBinarySearchTreesIIValidateBinarySearchTreeConvertSortedArraytoBinarySearchTreeConvertSortedListtoBinarySearchTreeLCAofBSTKthSmallestElementinaBST二叉树的递归MinimumDepthofBinaryMaximumDepthofBinaryPathSumPathSumIIBinaryTreeMaximumPathSumPopulatingNextRightPointersinEachNodeSumRoottoLeafNumbersLCAofBinaryTree线段树RangeSumQuery-Mutable排序

5插入排序InsertionSortList归并排序MergeTwoSortedArraysMergeTwoSortedListsMergekSortedListsSortList快速排序SortColorsKthLargestElementinanArray桶排序FirstMissingPositive计数排序H-Index基数排序MaximumGap其他LargestNumber小结查找SearchforaRangeSearchInsertPositionSearchinRotatedSortedArraySearchinRotatedSortedArrayIISearcha2DMatrixSearcha2DMatrixIIFindMinimuminRotatedSortedArrayFindMinimuminRotatedSortedArrayIIMedianofTwoSortedArraysH-IndexII

6暴力枚举法SubsetsSubsetsIIPermutationsPermutationsIICombinationsLetterCombinationsofaPhoneNumber广度优先搜索WordLadderWordLadderIISurroundedRegions总结深度优先搜索AdditiveNumberPalindromePartitioningUniquePathsUniquePathsIIN-QueensN-QueensIIRestoreIPAddressesCombinationSumCombinationSumIICombinationSumIIIGenerateParenthesesSudokuSolverWordSearch总结分治法Pow(x,n)Sqrt(x)

789贪心法JumpGameJumpGameIIBestTimetoBuyandSellStockBestTimetoBuyandSellStockIILongestSubstringWithoutRepeatingCharactersContainerWithMostPatchingArray动态规划TriangleMaximumSubarrayMaximumProductSubarrayLongestIncreasingSubsequencePalindromePartitioningIIMaximalRectangleBestTimetoBuyandSellStockIIIBestTimetoBuyandSellStockIVBestTimetoBuyandSellStockwithCooldownInterleavingStringScrambleStringMinimumPathSumEditDistanceDecodeWaysDistinctSubsequencesWordBreakWordBreakIIDungeonGameHouseRobberHouseRobberIIHouseRobberIII

RangeSumQuery-ImmutableRangeSumQuery2D-Immutable图CloneGraph位操作ReverseBitsRepeatedDNASequencesNumberof1BitsGrayCodeSingleNumberSingleNumberIISingleNumberIIIPowerofMissingNumberMaximumProductofWordLengthsBitwiseANDofNumbersRangePowerofThreeRectangleArea数论HappyNumberUglyNumberUglyNumberIISuperUglyNumberFractiontoRecurringDecimalFactorialTrailingZeroesNimGame模拟ReverseIntegerPalindromeNumberInsertInterval

MergeIntervalsMinimumWindowSubstringMultiplyStringsSubstringwithConcatenationofAllWordsPascal'sTrianglePascal'sTriangleIISpiralMatrixSpiralMatrixIIZigZagConversionDivideIntegersJustificationMaxPointsonaLine

16.416.516.616.716.816.916.1016.1216.1316.1416.15算法精粹算法精粹介绍PAGE19介绍PAGE19算法精粹——举一反三，抛弃题海战术刚接触ACM算法竞赛的新手。背后有强大的AlgoHub支持。(即将上线上在线判断代码。这样的一大好处是，读者可以边看书，边实现自己的代码，然后提交到网站上验证自己的想法是否正确。AlgoHub的使命是成为最好的算法学习和交流平台。AlgoHubPOJ,ZOJ,leetcodeHackerRank等网站的经典题目（一些质量不高的题目则忽略），AlgoHub有非常简单的加题系统，用户不需要写一行代码即可自己添加题目，所以AlgoHub的题库还在飞速增长中。每道题都有完整的代码。提下尽可能简短，方面读者在面试中能快速写出来。每道题都有多种解法。反三，让读者触类旁通。本书支持多种主流编程语言。目前支持Java,C++,C#,Python,Ruby,JavaScript,Swift,Scala,Clojure,将来还会支持更多编程语言。在线阅读/book/soulmachine/algorithm-essentials/内容目录介绍线性表数组RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayIILongestConsecutiveSequence3Sum3Sum4SumRemoveElementMoveZeroesNextPermutationPermutationSequenceValidSudokuTrappingRainWaterRotateImagePlusOneClimbingStairsSetMatrixZeroesGasStationCandyMajorityElementRotateArrayContainsDuplicateContainsDuplicateIIContainsDuplicateIIIProductofArrayExceptSelfGameofLifeIncreasingTripletSubsequence单链表ReverseLinkedListOddEvenLinkedList

AddTwoNumbersReverseLinkedListIIPartitionListRemoveDuplicatesfromSortedListRemoveDuplicatesfromSortedListIIRotateListRemoveNthNodeFromEndofListSwapNodesinPairsReverseNodesink-GroupCopyListwithRandomPointerLinkedListCycleLinkedListCycleIIReorderListLRUCachePalindromeLinkedListValidPalindromeImplementstrStr()StringtoInteger(atoi)AddBinaryLongestPalindromicSubstringRegularExpressionMatchingWildcardMatchingLongestCommonPrefixValidNumberIntegertoRomanRomantoIntegerCountandSayAnagramsAnagramSimplifyPathLengthofLastWordIsomorphicStringsWordPattern栈和队列栈MinStackParenthesesLongestParenthesesLargestRectangleinHistogramEvaluateReversePolishNotationImplementStackusingQueues队列ImplementQueueusingStacks二叉树二叉树的遍历BinaryPreorderTraversalBinaryInorderTraversalBinaryPostorderTraversalBinaryLevelOrderTraversalBinaryLevelOrderTraversalIIBinaryRightSideViewInvertBinaryTreeBinarySearchTreeIteratorBinaryTreeZigzagLevelOrderTraversalRecoverBinarySearchTreeSameTreeSymmetricTreeBalancedBinaryTreeFlattenBinaryTreetoLinkedListPopulatingNextRightPointersinEachNodeII二叉树的构建ConstructBinaryTreefromPreorderandInorderTraversalConstructBinaryTreefromInorderandPostorderTraversal二叉查找树UniqueBinarySearchTreesUniqueBinarySearchTreesIIValidateBinarySearchTreeConvertSortedArraytoBinarySearchTreeConvertSortedListtoBinarySearchTreeLCAofBSTKthSmallestElementinaBST二叉树的递归MinimumDepthofBinaryMaximumDepthofBinaryPathSumPathSumIIBinaryTreeMaximumPathSumPopulatingNextRightPointersinEachNodeSumRoottoLeafNumbersLCAofBinaryTree线段树RangeSumQuery-Mutable排序插入排序InsertionSortList归并排序MergeTwoSortedArraysMergeTwoSortedListsMergekSortedListsSortList快速排序SortColorsKthLargestElementinanArray桶排序FirstMissingPositive计数排序H-Index基数排序MaximumGap其他LargestNumber小结查找SearchforaRangeSearchInsertPositionSearchinRotatedSortedArraySearchinRotatedSortedArrayIISearcha2DMatrixSearcha2DMatrixIIFindMinimuminRotatedSortedArrayFindMinimuminRotatedSortedArrayIIMedianofTwoSortedArraysH-IndexII暴力枚举法SubsetsSubsetsIIPermutationsPermutationsIICombinationsLetterCombinationsofaPhoneNumber广度优先搜索WordLadderWordLadderIISurroundedRegions总结深度优先搜索AdditiveNumberPalindromePartitioningUniquePathsUniquePathsIIN-QueensN-QueensIIRestoreIPAddressesCombinationSumCombinationSumIICombinationSumIIIGenerateParenthesesSudokuSolverWordSearch总结分治法Pow(x,n)Sqrt(x)贪心法JumpGameJumpGameIIBestTimetoBuyandSellStockBestTimetoBuyandSellStockIILongestSubstringWithoutRepeatingCharactersContainerWithMostPatchingArray动态规划TriangleMaximumSubarrayMaximumProductSubarrayLongestIncreasingSubsequencePalindromePartitioningIIMaximalRectangleBestTimetoBuyandSellStockIIIBestTimetoBuyandSellStockIVBestTimetoBuyandSellStockwithCooldownInterleavingStringScrambleStringMinimumPathSumEditDistanceDecodeWaysDistinctSubsequencesWordBreakWordBreakIIDungeonGameHouseRobberHouseRobberIIHouseRobberIIIRangeSumQuery-ImmutableRangeSumQuery2D-Immutable图CloneGraph位操作ReverseBitsRepeatedDNASequencesNumberof1BitsGrayCodeSingleNumberSingleNumberIISingleNumberIIIPowerofMissingNumberMaximumProductofWordLengthsBitwiseANDofNumbersRangePowerofThreeRectangleArea数论HappyNumberUglyNumberUglyNumberIISuperUglyNumberFractiontoRecurringDecimalFactorialTrailingZeroesNimGame模拟ReverseIntegerPalindromeNumberInsertIntervalMergeIntervalsMinimumWindowSubstringMultiplyStringsSubstringwithConcatenationofAllWordsPascal'sTrianglePascal'sTriangleIISpiralMatrixSpiralMatrixIIZigZagConversionDivideIntegersJustificationMaxPointsonaLineCommunityQQ237669375Github:/soulmachine/algorithm-essentials微博：@灵魂机器LicenseBookLicense:CCBY-SA3.0License算法精粹算法精粹线性表PAGE20线性表PAGE20这类题目考察线性表的操作，例如，数组，单链表，双向链表等。算法精粹算法精粹数组PAGE21数组PAGE21本节主要讲关于数组的各种算法题。算法精粹算法精粹RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayPAGE23RemoveDuplicatesfromSortedArray描述Givenasortedarray,removetheduplicatesinplacesuchthateachelementappearonlyonceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.Forexample,GiveninputarrayA=[1,1,2],Yourfunctionshouldreturnlength=2,andAisnow[1,2].分析无代码//RemoveDuplicatesfromSortedArray//RemoveDuplicatesfromSortedArray//时间复杂度O(n)，空间复杂度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;}};相关题目RemoveDuplicatesfromSortedArrayII算法精粹算法精粹RemoveDuplicatesfromSortedArrayIIRemoveDuplicatesfromSortedArrayIIPAGE25RemoveDuplicatesfromSortedArrayII描述Followupfor"RemoveDuplicates":Whatifduplicatesareallowedatmosttwice?Forexample,givensortedarrayA=[1,1,1,2,2,3],yourfunctionshouldreturnlength=5,andAisnow[1,1,2,2,3]分析变量即可解决。如果是没有排序的数组，则需要引入一个hashmap来记录出现次数。代码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下面是一个更简洁的版本。上面的代码略长，不过扩展性好一些，例如将occur2改为occur3，就变成了允许重复最多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;相关题目RemoveDuplicatesfromSortedArray算法精粹算法精粹LongestConsecutiveSequencePAGE27LongestConsecutiveSequencePAGE27LongestConsecutiveSequence描述Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.Forexample,Given[100,4,200,1,3,2],Thelongestconsecutiveelementssequenceis[1,2,3,4].Returnitslength:4.algorithmshouldruninO(n)分析如果允许O(nlogn)的复杂度，那么可以先排序，可是本题要求O(n)。由于序列里的元素是无序的，又要求O(n)，首先要想到用哈希表。张，直到不连续为止，记录下最长的长度。代码};};}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);算法精