beijiyang/algorithmexercise

leetcode & lintcode solutions using JavaScript & Python 算法题解

THIS IS A COLLECTION OF MY LEETCODE/LINTCODE SOLUTION

二分法 Binary Search

key: first position || last position

O(n) => O(logn)

• Classical Binary Search - Easy (classicalBinarySearch.js) (R)
• First Position of Target - Easy (firstPositionOfTarget.js)
• Search for a Range - Medium (searchForARange.js)
• Search Insert Position - Easy (searchInsertPosition.js)
• Search a 2D Matrix - Easy (searchA2DMatrix.js)
• Search a 2D Matrix ii - Medium (searchA2DMatrixII.js)
• First Bad Version - Medium (firstBadVersion.js)
• Find Peak Element - Medium (findPeakElement.js)
• Search in Rotated Sorted Array - Medium (searchInRotatedArray.js)
• Find Minimum in Rotated Sorted Array - Medium （findMinInRotatedSortedArray.js)
• Find First and Last Position of Element in Sorted Array - Medium (findFirstAndLastPositionOfElementInSortedArray.js)
• Median of Two Sorted Arrays - Hard (medianOfTwoSortedArrays.js)

（三步）翻转法

• Recover Rotated Sorted Array - Easy (recoverRotatedSortedArray.js)

Rotate String

key: 两倍之必能还原初始字符串

• Rotate String - Easy (rotateString.js / rotateString.py)
• Rotate String - Easy (rotateStrings.js / rotateStrings.py)

分治法 Divide & Conquer

MergeSort / QuickSort / BinaryTree

• 二叉树 Binary Search

  八成以上都能用分治法解决
  • Balanced Binary Tree - Easy (balancedBinaryTree.js)
  • Maximum Depth of Binary Tree - Easy (maxDepthOfBinaryTree.js / maxDepthOfBinaryTree.py) (root => leaf)
  • Minimum Depth of Binary Tree - Easy (minDepthOfBinaryTree.js) (root => leaf) (use MAX_VALUE)
  • Binary Tree Maximum Path Sum II - Easy (binaryTreeMaxPathSumII.js) (root => any)
  • Binary Tree Maximum Path Sum - Hard (binaryTreeMaxPathSum.js) (any => any)
  • Validate Binary Search Tree - Medium (validateBinarySearchTree.js) (BST)
  • Insert Into a Binary Search Tree - Medium (insertIntoABinarySearchTree.js) (BST)
  • Range Sum of BST - Medium (rangeSumOfBST.js) (BST)
  • Search Range in Binary Search Tree - Medium (searchRangeInBST.js) (BST)
  • Binary Tree Level Order Traversal - Medium (binaryTreeLevelOrderTraversal.js) (BFS template) (R)
  • Binary Tree Preorder Traversal - Medium (binaryTreePreorderTraversal.js / binaryTreePreorderTraversal.py) (R)
  • Binary Tree Inorder Traversal - Medium (binaryTreeInorderTraversal.js) (BFS 宽度优先搜索) (R)
  • Inorder Successor in BST - Medium (inorderSuccessorInBST.js / inorderSuccessorInBST.py) (BST)
  • Path Sum - Easy (pathSum.js)
  • Lowest Common Ancestor of a Binary Tree - Medium (lowestCommonAncestorOfABinaryTree.js)
  • Lowest Common Ancestor of a Binary Search Tree - Easy (lowestCommonAncestorOfABST.js)

动态规划 Dynamic Programming

• Triangle - Medium (triangle.js)
• Minimum Path Sum - Medium (minPathSum.js)
• Unique Paths - Medium (uniquePaths.js)
• Unique Paths II - Medium (uniquePathsII.js)
• Climbing Stairs - Easy (climbingStairs.js)
• Jump Game - Medium (jumpGame.js)
• Jump Game II - Hard (jumpGameII.js)

链表 Linked List

• Remove Duplicates from Sorted List II - Medium (removeDuplicatesFromSortedListII.js)
• Remove Duplicates from Sorted List - Easy (removeDuplicatesFromSortedList.js)
• Reverse Linked List - Easy (reverseLinkedList.js) (TODO: 递归解)
• Reverse Linked List II - Medium (reverseLinkedListII.js)
• Partition List - Medium (partitionList.js)
• Sort List - Medium (sortList.js)
• Reorder List - Medium (reorderList.js)
• Convert binary number in a linked list to integer - Easy (convertBinaryNumberInALinkedListToInteger.js)
• Delete node in a linked list - Easy (deleteNodeInALinkedList.js)
• Middle of the linked list - (Easy) (middleOfTheLinkedList.js)
• Merge two sorted lists - (Easy) (margeTwoSortedLists.js)
• Intersection of two linked lists - Easy (intersectionOfTwoLinkedLists.js)
• Next Greater Node In Linked List - Medium (nextGreaterNodeInLinkedList.js)
• Remove Linked List Elements - Easy (removeLinkedListElements.js)
• Palindrome Linked List - Easy (palindromeLinkedList.js)
• Linked List Cycle - Easy (linkedListCycle.js)
• Linked List Components - Medium (linkedListComponents.js)
• Odd Even Linked List - Medium (oddEvenLinkedList.js)
• Add Two Numbers II - Medium (addTwoNumbersII.js)

数组 Array

Sorted Array

• Kth Largest Element in an Array - Medium (kthLargestElementInAnArray.js)
• Median of Two Sorted Arrays - Hard (medianOfTwoSortedArrays.js)

双指针 Double Pointer

• Partition Array - Medium (partition.js / partition.py)
• Intersection of two linked lists - Easy (intersectionOfTwoLinkedLists.js)

待归类

• Merge Sorted Array - Easy (mergeSortedArray.js)
• Reverse Words in a String - Medium (reverseWordsInAString.js)
• Reverse Words in a String III - Easy (reverseWordsInAStringIII.js)
• Implement strStr() - Easy (strStr.js)

utils

• String.prototpye.reverse (reverseString.js)