Python Leetcode

Python version: 3.7.11

Leetcode profile: https://leetcode.com/dnhb/

User Guide

init.py: This script allows users to create a Jupyter notebook of a Leetcode problem by paste the name or URL of that problem in leetcode.com from computer clipboard, and this notebook consists of six parts:

• Problem content
• Summary
• Problem Description
• Method
• Footnote
• script that adds summary to README.md file

Template.ipynb: This file is an instance created by init.py.

Problem & Solution

#	Title	Basic idea (One line)	Tags
1	Two Sum
7	Reverse Integer	1. int -> string, reverse the string and add the sign; O(n) 2. decompose the int one digit by one digit; O(n)	decompose int
9	Palindrome Number	1. reverse(int) string = int string; O(n) 2. int -> string, and compare the begining and the end; O(n/2) 3. split the int in half, and compare; O(n/2)	ambguity overlapped-condition
12	Integer to Roman	rule-based method; O(n) 1. iterate by division 2. iterate by substraction	0 exclusive two list a pair construct rules
13	Roman to Integer	rule-based method; O(n)	previous and current comparison
14	Longest Common Prefix	1. vertical scanning; O(nm) 2. horizontal scanning;O(nm) 3. divide and conquer; O(m*log(n)) 4. binary search; O(nm*log(m))	input taxonomy return taxonomy vertical & horizontal
20	Valid Parentheses	eliminate the pairs by proximity; O(n)	stackall comparison
21	Merge Two Sorted Lists
67	Add Binary	1. binary-decimal-binary; O(n) 2. standard math binary addition; O(n) 3. bitwise operations; O(1)	bitwise addition
69	Sqrt(x)	1. binary search; O(nlog2) 2. Newton method	binary search newton
1512	Number of Good Pairs	1. brute force; O(n^2) 2. combination formula; O(n)	combination
564	Find the Closest Palindrome	1. brute force [DEPRECATE]; O(n) 2. naive 5 forms; O(1) 3. fancy 3 forms; O(1) 4. fancy 4 forms; O(1)	palindrome symmetry observation
125	Valid Palindrome	1. holistic approach; O(n) 2. atomistic approach (two pointer); O(n)	palindrome two pointer string operation
680	Valid Palindrome II	1. brute force [deprecated]; O(n) 2. two pointer (linear) [deprecated]; O(n/2) 3. two pointer (binary); O(logn) 4. two pointer (recursive); O(n)	palindrome two pointer binary search
409	Longest Palindrome	1. count pairs; O(n) 2. count un-paired characters; O(n)	palindrome complementary dict set
1332	Remove Palindromic Subsequences	1. intutive method; O(1)	palindrome intuition
58	Length of Last Word	brute force; O(n)	string
8	String to Integer (atoi)	brute force; O(n)	string regex
65	Valid Number	brute force; O(n)	string regex
468	Validate IP Address	1. divide and conquer; O(n) 2. regex; O(1)	string regex
709	To Lower Case	1. lower(); O(n) 2. dictionary mapping; O(n) 3. XOR method; O(n)	string XOR mapping
38	Count and Sa	1. straightforward loop; O(n) 2. recursive; O(n)	string recursive while
151	Reverse Words in a String	by steps; O(n)	string split
6	Zigzag Conversio	1. built by columns; O(n) 2. built by rows; O(n)	string sequence intuition
1694	Reformat Phone Number	step by step; O(n)	string
33	Search in Rotated Sorted Arra	1. binary search; O(logn) 2. linear method; O(n)	binary search generality
81	Search in Rotated Sorted Array II	1. linear search; O(n) 2. binary search; O(logn)/O(n)	binary search conduct condition
153	Find Minimum in Rotated Sorted Arra	1. linear search; O(n) 2. binary search; O(logn)	binary search interval boundary
154	Find Minimum in Rotated Sorted Array II	binary search; O(logn)/O(n)	binary search categorized discussion
34	Find First and Last Position of Element in Sorted Arra	1. linear search; O(n) 2. 2-time binary search; O(logn)	binary search existence boundary
162	Find Peak Element	1. linear scan; O(n) 2. binary search; O(logn)	binary search monotonicity inflection point mathematical assumption
540	Single Element in a Sorted Arra	1. linear scan; O(n) 2. binary search; O(logn)	binary search drop and pick
74	Search a 2D Matrix	1. linear scan; O(n) 2. binary search; O(logn)	binary search linear data
520	Detect Capital	1. brute force; O(n) 2. two pointer; O(n/2) 3. regex; O(n)	built-in method regex two pointer
941	Valid Mountain Arra	1. two pointer; O(n) 2. one pass; O(n)	two pointer one pass
62	Unique Paths	DP, O(mn)	DP
63	Unique Paths II	DP, O(mn)	DP boundary condition
64	Minimum Path Sum	1. recursive DP; O(mn) 2. iterative DP; O(mn)	DP recursive iterative
70	Climbing Stairs	1. combination method; O(n) 2. DP; O(n)	DP combination
66	Plus One	1. mathematical rule; O(n) 2. built-in convert; O(n)	mathematical built-in