Maximum Subarray

Description LeetCode 53 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer

Longest Palindromic Substring

Description Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” Analysis The brute force method whose time is \(O(n^3)\) is obvious. But we want to explore the

Count Primes

Description Count the number of prime numbers less than a non-negative number, n. Example: Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Analysis It is easy to come up with the brute force method. When judging a prime number, we need to judge if there

Bézout’s Identity

Bézout’s identity is number-theoretic conclusion that should be remembered. if \(gcd(a_{1},a_{2},\ldots ,a_{n})=d\) then there are integers \(x_{1},x_{2},\ldots ,x_{n}\) such that $$d=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}$$ has the following properties: \(d\) is the smallest positive integer of this form every number of this form is a multiple of \(d\) We can apply it with the following problem. Description LeetCode 365

Divide Two Integers

Description LeetCode 29 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7, divisor = -3 Output: -2 Note: Both dividend and divisor will

Multiply Strings

Description LeetCode 43 Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = “2”, num2 = “3” Output: “6” Example 2: Input: num1 = “123”, num2 = “456” Output: “56088” Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero,

The Knuth-Morris-Pratt Algorithm

KMP algorithm aims to solve the string matching problem. And I believe that it is the most efficient solution of this problem. First let’s review this problem. String Matching Given a text string \(T[1…n]\) and a pattern \(P[1…m]\), if \(0<=s<=n-m\) and \(T[s+1…s+m]]=P[1…m]\), then \(P\) occurs with shift \(s\). The string matching problem is to find

Reverse Integer

1 Problem LeetCode 7 Reverse Integer Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 −

Power of an Element

Directly calculate \(pow(a,b)\) is \(O(b)\). It is trivial. We can use repeated squaring to solve it efficiently as \(O(lgb)\), that is to say, divide \(b\) into several power of \(2\). And calculate \(pow(a,2^i)\) and sum them. For example, \(a^{11}=a^{2^0}\times a^{2^1}\times a^{2^3}\). Sometimes we want to get the modular exponentiation. The solution is based on the

Chinese Remainder Theorem

1 Description Given two arrays of \(n\) integers, \(num\) and \(rem\), find the minimum \(x\) that satisfies \(x\ mod\ num_i=rem_i (i=1,…,n)\). 2 Solution Calculate the product of \(num\) as \(prod\). Let \(nums_i\) divide prod as \(pp_i\). And \(inv_i\) is the modular multiplicative inverse of \(pp_i\) with respect to \(num_i\) that can be solved by extended