Skip to content

leetcode.com solutions with unit testing (VSCode+CMake+Boost.Test)

License

Notifications You must be signed in to change notification settings

johnhany/leetcode

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

leetcode

Fast C++ solutions for leetcode.com problems, with VS Code support for CMake building, gdb/lldb debugging, and Boost unit testing.

Stats

Top 100 liked: 78 / 100 78%

Top interviewed: 86 / 145 59%

In total: 159 / 2573 6%

99.00%+ in running time: 105 / 159 66%

Solutions

  1. Two Sum
  • Hash table (unorderd_map): 4ms (top 99.54%)
  1. Add Two Numbers
  • Linked list: 16ms (top 100.00%)
  1. Longest Substring Without Repeating Characters
  • Hash table (vector): 0ms (top 100.00%)
  1. Median of Two Sorted Arrays
  • Non-recursive: 35 ms (top 63.25%)
  • Recursion: 16 ms (top 100.00%)
  1. Longest Palindromic Substring
  • Brutal force: 9ms (top 94.73%)
  • Manacher's algorithm: 0ms (top 100.00%)
  1. ZigZag Conversion
  • Brutal force: 40ms (top 55.26%)
  • Fast for-loop: 8ms (top 100.00%)
  1. Reverse Integer
  • 0ms (top 100.00%)
  1. String to Integer (atoi)
  • 0ms (top 100.00%)
  1. Palindrome Number
  • Lookup table: 52ms (top 100.00%)
  1. Regular Expression Matching
  • Dynamic programming: 4ms (top 100.00%)
  1. Container With Most Water
  • Two pointers: 12ms (top 100.00%)
  1. Integer to Roman
  • Two arrays: 28ms (top 99.20%)
  • Lookup table: 28ms (top 99.20%)
  1. Roman to Integer
  • 10ms (top 67.12%)
  • Map: 44ms (top 97.72%)
  1. Longest Common Prefix
  • 4ms (top 100.00%)
  1. 3Sum
  • Two pointers: 112ms (top 99.88%)
  1. 3Sum Closest
  • Two pointers: 8ms (top 100.00%)
  1. Letter Combinations of a Phone Number
  • Deque: 4ms (top 100.00%)
  • DFS: 0ms (top 100.00%)
  1. 4Sum
  • Set: 40ms (top 82.57%)
  • Fast for-loop: 7ms (top 99.16%)
  1. Remove Nth Node From End of List
  • 0ms (top 100.00%)
  1. Valid Parentheses
  • Stack: 4ms (top 100.00%)
  1. Merge Two Sorted Lists
  • Two swaps: 12ms (top 100.00%)
  1. Generate Parentheses
  1. Merge k Sorted Lists
  • Use 021: 16ms (top 98.02%)
  • Priority queue: 32ms (top 98.10%)
  1. Swap Nodes in Pairs
  • 0ms (top 100.00%)
  1. Reverse Nodes in k-Group
  1. Remove Duplicates from Sorted Array
  1. Remove Element
  • 0ms (top 100.00%)
  1. Implement strStr()
  • 8ms (top 98.99%)
  • KMP: 4ms (top 91.65%)
  1. Divide Two Integers
  • 0ms (top 100.00%)
  1. Substring with Concatenation of All Words
  1. Next Permutation
  • 4ms (top 96.34%)
  1. Longest Valid Parentheses
  • 4ms (top 96.65%)
  1. Search in Rotated Sorted Array
  • 0ms (top 100.00%)
  1. Find First and Last Position of Element in Sorted Array
  • 8ms (top 98.52%)
  1. Search Insert Position
  • 4ms (top 98.31%)
  1. Valid Sudoku
  • 8ms (top 99.96%)
  1. Sudoku Solver
  • 4ms (top 95.52%)
  1. Count and Say
  • 4ms (top 97.84%)
  1. Combination Sum
  • 8ms (top 95.15%)
  1. Combination Sum II
  • 4ms (top 98.92%)
  1. First Missing Positive
  • 4ms (top 96.34%)
  1. Trapping Rain Water
  • 4ms (top 99.71%)
  1. Multiply Strings
  • C++ interface: 8ms (top 72.26%)
  • C interface: 4ms (top 97.53%)
  1. Wildcard Matching
  • 4ms (top 99.84%)
  1. Jump Game II
  • 8ms (top 95.32%)
  1. Permutations
  • Recursive: 20ms (top 22.83%)
  • Better loop: 12ms (top 96.86%)
  • Backtracking: 4ms (top 96.41%)
  1. Permutations II
  • 8ms (top 96.44%)
  1. Rotate Image
  • Direct rotation: 4ms (top 98.21%)
  • Flip & swap: 4ms (top 98.21%)
  1. Group Anagrams
  1. Pow(x, n)
  • 4ms (top 96.07%)
  1. N-Queens
  • 4ms (top 99.62%)
  1. Maximum Subarray
  • Divide and conquer: 8ms (top 96.32%)
  • Kadane: 4ms (top 99.88%)
  • DP: 0ms (top 100.00%)
  1. Spiral Matrix
  • 0ms (top 100.00%)
  1. Jump Game
  1. Merge Intervals
  • 8ms (top 100.00%)
  1. Permutation Sequence
  • 0ms (top 100.00%)
  1. Rotate List
  • 4ms (top 94.70%)
  1. Unique Paths
  • 0ms (top 100.00%)
  1. Unique Paths II
  • 0ms (top 100.00%)
  1. Minimum Path Sum
  • 4ms (top 99.39%)
  1. Plus One
  • 0ms (top 100.00%)
  1. Sqrt(x)
  • 0ms (top 100.00%)
  1. Climbing Stairs
  • 0ms (top 100.00%)
  1. Set Matrix Zeroes
  1. Search a 2D Matrix
  • 4ms (top 99.56%)
  1. Sort Colors
  • 0ms (top 100.00%)
  • three pointer: 0ms (top 100.00%)
  1. Minimum Window Substring
  • sliding window: 32ms (top 38.25%)
  • optimized sliding window: 44ms (top 19.33%)
  • hash: 4ms (top 99.92%)
  1. Subsets
  • 8ms (top 90.16%)
  • backtrack: 4ms (top 98.41%)
  • bitwise: 0ms (top 100.00%)
  1. Word Search
  1. Remove Duplicates from Sorted Array II
  • 3ms (top 92.82%)
  1. Largest Rectangle in Histogram
  • recursion: 32ms (top 14.84%)
  • two vector: 4ms (top 100.00%)
  • one vector: 122ms (top 75.97%)
  1. Partition List
  • 7ms (top 62.59%)
  1. Merge Sorted Array
  • additional space: 4ms (top 96.53%)
  • 3 pointers: 0ms (top 100.00%)
  1. Decode Ways
  • 0ms (top 100.00%)
  1. Reverse Linked List II
  • 0ms (top 100.00%)
  1. Binary Tree Inorder Traversal
  • Recursion - list: 4ms (top 87.58%)
  • Recursion - vector: 4ms (top 43.93%)
  • Stack: 0ms (top 100.00%)
  • Stack: 0ms (top 100.00%)
  1. Unique Binary Search Trees
  • 0ms (top 100.00%)
  1. Validate Binary Search Tree
  • Two pointers: 4ms (top 99.99%)
  • 12ms (top 74.23%)
  1. Symmetric Tree
  • Recursive: 0ms (top 100.00%)
  • Queue: 4ms (top 81.64%)
  1. Binary Tree Level Order Traversal
  • 0ms (top 100.00%)
  1. Binary Tree Zigzag Level Order Traversal
  • 3ms (top 73.66%)
  1. Maximum Depth of Binary Tree
  • 8ms (top 75.97%)
  1. Construct Binary Tree from Preorder and Inorder Traversal
  • 29ms (top 52.40%)
  • hash: 16ms (top 89.76%)
  • Stack: 7ms (top 99.57%)
  1. Construct Binary Tree from Inorder and Postorder Traversal
  1. Convert Sorted Array to Binary Search Tree
  • 4ms (top 99.83%)
  1. Minimum Depth of Binary Tree
  • 4ms (top 99.83%)
  1. Flatten Binary Tree to Linked List
  • 4ms (top 89.52%)
  1. Populating Next Right Pointers in Each Node
  1. Pascal's Triangle
  • swap: 4ms (top 51.26%)
  • resize: 0ms (top 100.00%)
  • 0ms (top 100.00%)
  1. Triangle
  • 0ms (top 100.00%)
  1. Best Time to Buy and Sell Stock
  • priority queue: 12ms (top 17.37%)
  • 4ms (top 97.69%)
  • 76ms (top 99.79%)
  1. Best Time to Buy and Sell Stock II
  • 0ms (top 100.00%)
  1. Best Time to Buy and Sell Stock III
  1. Binary Tree Maximum Path Sum
  1. Valid Palindrome
  • 4ms (top 99.16%)
  1. Word Ladder
  • 28ms (top 99.56%)
  • Graph + BFS: 138ms (top 67.54%)
  • Graph + BiDir BFS: 131ms (top 69.50%)
  • BiDir BFS: 560ms (top 34.48%)
  1. Longest Consecutive Sequence
  • hash: 113ms (top 83.63%)
  • sort: 59ms (top 99.67%)
  • dp: 132ms (top 78.98%)
  1. Surrounded Regions
  • 4ms (top 99.88%)
  1. Palindrome Partitioning
  • backtrack: 159ms (top 63.39%)
  • backtrack + DP: 100ms (top 91.71%)
  1. Gas Station
  • 0ms (top 100.00%)
  1. Single Number
  • 4ms (top 99.88%)
  1. Linked List Cycle
  • 3ms (top 99.91%)
  1. Linked List Cycle II
  • 3ms (top 99.53%)
  1. Binary Tree Preorder Traversal
  • Recursion: 4ms (top 43.36%)
  • Stack: 0ms (top 100.00%)
  1. Binary Tree Postorder Traversal
  • Recursion: 4ms (top 44.24%)
  • Stack: 0ms (top 100.00%)
  1. LRU Cache
  • 711ms (top 29.13%)
  • custom linked list: 316ms (top 99.94%)
  1. Evaluate Reverse Polish Notation
  1. Find Minimum in Rotated Sorted Array
  • 0ms (top 100.00%)
  1. Intersection of Two Linked Lists
  1. Repeated DNA Sequences
  • 3-bit hash: 52ms (top 81.78%)
  • 2-bit hash: 4ms (top 99.71%)
  1. Best Time to Buy and Sell Stock IV
  • 8ms (top 76.49%)
  1. House Robber
  • 0ms (top 100.00%)
  1. Reverse Linked List
  • two pointers: 12ms (top 27.83%)
  • faster two pointers: 7ms (top 74.53%)
  • recursion: 0ms (top 100.00%)
  1. House Robber II
  • 0ms (top 100.00%)
  1. Kth Largest Element in an Array
  • 4ms (top 99.81%)
  1. Maximal Square
  • 8ms (top 99.64%)
  1. Invert Binary Tree
  • 0ms (top 100.00%)
  1. Kth Smallest Element in a BST
  • 7ms (top 99.74%)
  1. Palindrome Linked List
  1. Lowest Common Ancestor of a Binary Search Tree
  1. Lowest Common Ancestor of a Binary Tree
  • 7ms (top 99.85%)
  1. Sliding Window Maximum
  1. Search a 2D Matrix II
  1. First Bad Version
  • 0ms (top 100.00%)
  1. Perfect Squares
  • 0ms (top 100.00%)
  • Tree search: 92ms (top 79.03%)
  1. Move Zeroes
  • two pointers: 33ms (top 50.97%)
  • faster two pointers: 16ms (top 97.08%)
  1. Find the Duplicate Number
  • Binary search: 8ms (top 94.55%)
  • Two pointers: 4ms (top 99.76%)
  1. Longest Increasing Subsequence
  • 0ms (top 100.00%)
  1. Remove Invalid Parentheses
  1. Best Time to Buy and Sell Stock with Cooldown
  • 0ms (top 100.00%)
  1. Coin Change
  1. House Robber III
  1. Intersection of Two Arrays
  • Set: 4ms (top 99.21%)
  • Map: 4ms (top 99.21%)
  1. Intersection of Two Arrays II
  • 4ms (top 99.54%)
  1. Find All Anagrams in a String
  1. Delete Node in a BST
  1. LFU Cache
  1. Fibonacci Number
  • 0ms (top 100.00%)
  1. Convert BST to Greater Tree
  • 20ms (top 100.00%)
  1. Single Element in a Sorted Array
  • recursion: 19ms (top 96.25%)
  • iteration: 12ms (top 99.87%)
  1. Diameter of Binary Tree
  • 7ms (top 89.75%)
  1. Find the Closest Palindrome
  • 0ms (top 100.00%)
  1. Permutation in String
  1. Find Duplicate Subtrees
  1. Maximum Binary Tree
  1. Maximum Swap
  • 0ms (top 100.00%)
  1. Search in a Binary Search Tree
  1. Insert into a Binary Search Tree
  1. Binary Search
  1. Best Time to Buy and Sell Stock with Transaction Fee
  1. Open the Lock
  • BFS: 180ms (top 81.07%)
  1. Flipping an Image
  • 4ms (top 88.29%)
  1. Shortest Path to Get All Keys
  1. Minimum Number of Refueling Stops
  1. Middle of the Linked List
  • 0ms (top 100.00%)
  1. Construct Binary Tree from Preorder and Postorder Traversal
  • 8ms (top 89.88%)
  1. Check Completeness of a Binary Tree
  • 3ms (top 84.99%)
  1. Binary Search Tree to Greater Sum Tree
  • 0ms (top 100.00%)
  1. Frequency of the Most Frequent Element

Problem categories

Category Problems
Array / String 1, 3, 6, 11, 14, 15, 16, 18, 20, 22, 26, 27, 28, 30, 31, 38, 41, 42, 44, 45, 48, 49, 54, 55, 56, 73, 75, 76, 80, 88, 125, 239, 283, 349, 350, 438, 567, 670, 832, 1838
Linked list 2, 19, 21, 23, 24, 25, 61, 86, 92, 141, 142, 160, 206, 234, 876
Recursion 4, 33, 34, 35, 69, 74, 153, 215, 240, 278, 287, 301, 540, 704
Dynamic Programming 5, 10, 32, 36, 37, 53, 62, 63, 64, 70, 79, 84, 91, 96, 118, 120, 121, 122, 123, 128, 130, 134, 188, 198, 213, 221, 279, 300, 309, 322, 509, 714, 864, 871
Numerical 7, 8, 9, 12, 13, 29, 43, 50, 66, 136, 150, 564
Backtracking 17, 39, 40, 46, 47, 51, 60, 78, 131
Binary Tree 94, 98, 101, 102, 103, 104, 105, 106, 108, 111, 114, 116, 124, 144, 145, 226, 230, 235, 236, 337, 450, 538, 543, 652, 654, 700, 701, 889, 958, 1038
Graph / DFS 127, 752
System Design 146, 460

Environment

sudo snap install --classic code
sudo apt-get install pylint
  • clang (used by default. You can use other tools as long as your .vscode/c_cpp_properties.json file is modified correctly)
wget -O - http://apt.llvm.org/llvm-snapshot.gpg.key|sudo apt-key add -
sudo apt-get update
sudo apt-get install clang-8 lldb-8
  • CMake
  • Boost (for unit testing)
wget -O boost_1_70_0.tar.gz https://dl.bintray.com/boostorg/release/1.70.0/source/boost_1_70_0.tar.gz
tar xzvf boost_1_70_0.tar.gz
cd boost_1_70_0/

sudo apt-get update
sudo apt-get install build-essential g++ python-dev autotools-dev libicu-dev build-essential libbz2-dev libboost-all-dev

./bootstrap.sh --prefix=/usr/
./b2
sudo ./b2 install

Usage

Each folder contains 3 files: solution.hpp, solution.cpp and solution_test.cpp. The first folder 001-Two-Sum contains an additional main.cpp file, in case you don't feel like using unit testing and you can test your own cases in main.cpp.

Add following lines to your settings.json to configure the building and linting:

{
    "clang.executable": "clang++",
    "clang.cflags": ["c11"],
    "clang.cxxflags": ["-std=c++17"],
    "lldb.executable": "lldb"
}

Steps to build a solution:

  1. Change the line set(PROBLEM_NAME {Problem_Folder}) in CMakeLists.txt to choose the problem you want to solve, in which {Problem_Folder} is the folder name of the problem. For example, set(PROBLEM_NAME "001-Two-Sum").

  2. Press Ctrl + Shift + P to bring up the Command Palette of VSCode. Type in CMake, and look for a CMake: Configure command, select it. It will configure the cache files and makefile which are located in build folder by default.

  3. Type in or look for a CMake: Build command in the Command Palette and execute it. It will compile the source codes of the solution that you previously chose.

  4. Debug Press Ctrl + Shift + D or click the bug icon on the left. The .vscode/launch.json for debugging is already set up for you, and both GDB and LLDB is supported.

    gdb: Choose (gdb) Launch and you're good to go.

    lldb: Choose (lldb) Launch. You may need to disable and re-enable ms-vscode.cpptools and mitaki28.vscode-clang extensions in case the variables won't properly display in "Watch" Panel. Data visualization is supported (https://github.com/vadimcn/vscode-lldb/wiki/Data-visualization).

  5. Unit testing Type in or look for a CMake: Run tests command in the Command Palette and execute it. It will run all test cases in solution_test.cpp. Feel free to add your own test cases.

Clear build folder:

  1. Press Ctrl + Shift + P to bring up the Command Palette. Type in Task: Run Task and press enter. Choose clean will delete everything in the build folder. Bear in mind that you need to configure the project after cleaning the folder or switching to another solution, by either executing Task: Run Task -> configure or CMake: Configure.

About

leetcode.com solutions with unit testing (VSCode+CMake+Boost.Test)

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published