This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/longest-palindromic-substring | |
class Solution { | |
public: | |
string longestPalindrome(const string &s) { // Manacher's algorithm, O(n) time | |
if (s.size() <= 1) return s; | |
// insert a bogus char between chars, including outer boundaries | |
string t = "|"; | |
for (auto ch : s) t += ch, t += "|"; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <math.h> | |
#include <boost/dynamic_bitset.hpp> | |
void print_subsets(const std::string &str) { | |
std::cout << "[empty string]\n"; | |
const int n = str.size(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <stack> | |
struct TreeNode { | |
int val; | |
TreeNode* left; | |
TreeNode* right; | |
TreeNode() : val(0), left(nullptr), right(nullptr) {} | |
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/find-median-from-data-stream | |
class MedianFinder { | |
priority_queue<int> maxHeap; | |
priority_queue<int, vector<int>, greater<int>> minHeap; | |
public: | |
void addNum(int num) { | |
if (maxHeap.empty() || maxHeap.top() >= num) | |
maxHeap.push(num); | |
else |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/implement-strstr | |
class Solution { | |
public: | |
// Brute force, O((m - n) * n) worst and average case, O(n) best case | |
int strStrNaive(const string& text, const string& pattern) { | |
int m = text.size(), n = pattern.size(); | |
// be consistent with C/C++ strstr() and Java indexOf() | |
if (!n) return 0; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
int getPivotIndex(int& l, int& r) { | |
return l + (r - l) / 2; | |
//return l + rand() % (r - l + 1); | |
} | |
int partition(vector<int>& A, int& l, int& r) { | |
int i = l, pivotIndex = getPivotIndex(l, r), pivot = A[pivotIndex]; | |
swap(A[pivotIndex], A[r]); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/split-array-largest-sum | |
// Same as https://www.codingninjas.com/codestudio/library/book-allocation-problem | |
class Solution { | |
public: | |
/* | |
* Let dp[i][j + 1] be the an optimal solution to the subproblem with i subarrays within | |
* A[0..j]. Let sum[i][j] be the sum of the numbers in A[i..j]. Then: | |
* |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/median-of-two-sorted-arrays | |
// https://www.youtube.com/watch?v=LPFhl65R7ww | |
// https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation | |
class Solution { | |
public: | |
double findMedianSortedArrays(vector<int>& a1, vector<int>& a2) { | |
if (a1.size() > a2.size()) swap(a1, a2); // ensure a1 is shorter |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string | |
/* | |
* # Brute force approach | |
* | |
* Generate all substrings, and count the unique chars in each. | |
* | |
* Time complexity: O(n^2) to generate all substrings, O(n) to count unique chars for | |
* each. Total: O(n^3). | |
* |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/merge-k-sorted-lists | |
/* | |
* O(N log k) time and O(1) space, where N is the total number of nodes. | |
* | |
* # Explanation of the time complexity | |
* | |
* Let n be an upper bound on the number of nodes of each list. | |
* | |
* We iteratively merge pairs of lists as follows: |
NewerOlder