Note: Heap in algorithm and data structure is a different concept with the heap in memory management. Heap in memory management is more like a pool. There is a discussion at StackOverflow, we don’t talk about the detail of this different. You know we are talking about the heap concept in algorithm and data structure is enough for us. We still follow the style of Introduction to Algorithms.
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Given target =
Given target =
Source url: https://leetcode.com/problems/majority-element/
Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exists in the array.
Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Explanation: [4,-1,2,1] has the largest sum = 6.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
I am trying to solve every problem of Leetcode and write blogs to record it. Now I plan to read Introduction to Algorithms and solve problems match the book contents.
What is Divide and conquer?
Divide and conquer is a method to solve a complex problem. When we think of a problem too complex or too big, we can try to divide the problem to some easy problems or small problems. Then we try to solve these small/easy problems and combine the results to solve the complex/big problem.
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Input: 1->2->4, 1->3->4
Given an array
A of positive integers, call a (contiguous, not necessarily distinct) subarray of
A good if the number of different integers in that subarray is exactly
3 different integers:
Return the number of good subarrays of
Input: A = [1,2,1,2,3], K = 2
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Input: A = [1,2,1,3,4], K = 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
s1 = “ab”
s2 = “eidbaooo”
Explanation: s2 contains one permutation of s1 (“ba”).
s2 = “eidboaoo”
- The input strings only contain lower case letters.
- The length of both given strings is in the range [1, 10,000].
Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Output: [0, 6]
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Output: [0, 1, 2]
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.