diff options
| -rw-r--r-- | leetcode/solutions.org | 104 |
1 files changed, 82 insertions, 22 deletions
diff --git a/leetcode/solutions.org b/leetcode/solutions.org index 340bc73..b8748ce 100644 --- a/leetcode/solutions.org +++ b/leetcode/solutions.org @@ -3,15 +3,11 @@ #+description: Description #+date: 2024-04-29 -* Prelude -#+begin_src c++ :session c++ -test -#+end_src * Arrays ** DONE (#217) Contains duplicate If there are any duplicates, then when the list is sorted they would be consecutive. -#+begin_src c++ :tangle 217.cpp :session c++ +#+begin_src c++ :tangle 217.cpp :session c++ :comments link #include <bits/stdc++.h> using namespace std; @@ -34,7 +30,7 @@ disregarding ordering. Sorting the two strings would force the same order for both strings. -#+begin_src c++ :tangle 242-sort.cpp +#+begin_src c++ :tangle 242-sort.cpp :comments link #include <bits/stdc++.h> using namespace std; bool isAnagram(string s, string t) @@ -45,7 +41,7 @@ bool isAnagram(string s, string t) } #+end_src *** Simple table -#+begin_src c++ :tangle 242-table.cpp +#+begin_src c++ :tangle 242-table.cpp :comments link #include <bits/stdc++.h> using namespace std; bool isAnagram(string s, string t) @@ -64,7 +60,7 @@ bool isAnagram(string s, string t) #+end_src ** DONE (#1) Two sum Given a target find two elements which sum to it. -#+begin_src c++ :tangle 1.cpp +#+begin_src c++ :tangle 1.cpp :comments link #include <bits/stdc++.h> using namespace std; vector<int> twoSum(vector<int> &nums, int target) @@ -81,7 +77,7 @@ vector<int> twoSum(vector<int> &nums, int target) } #+end_src ** DONE (#49) Group anagrams -#+begin_src c++ :tangle 49.cpp +#+begin_src c++ :tangle 49.cpp :comments link #include <bits/stdc++.h> using namespace std; vector<vector<string>> groupAnagrams(vector<string> &strs) @@ -106,7 +102,7 @@ hash tables. *** Sorting the map Once you've generated the map, sort it by frequency (then by number) then take the top k off it. -#+begin_src c++ :tangle 347-sort.cpp +#+begin_src c++ :tangle 347-sort.cpp :comments link #include <bits/stdc++.h> using namespace std; vector<int> topKFrequent(vector<int> &nums, int k) @@ -138,7 +134,7 @@ value. The priority sorts the members. Hence, if we generate the map then place them all in a priority queue, we just need to get the k highest priority items to finish the problem. -#+begin_src c++ :tangle 347-queue.cpp +#+begin_src c++ :tangle 347-queue.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -174,7 +170,7 @@ i: [x from 0 to i - 1] * i is the product [x from 0 to i]. Same the other way. So we can iterate once to produce the products before i and once for the products after i while only doing a set once! -#+begin_src c++ :tangle 238.cpp +#+begin_src c++ :tangle 238.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -201,11 +197,9 @@ Determine if a 9x9 grid is a valid sudoku. You can use a set of hashsets (where membership testing is O(1)) to just check if you've seen a number before. In this case, since we know the exact input data and the properties we want we can use -boolean tables to speed up the process. +boolean arrays which are smaller and easier for the CPU to work with. -I also use a little maths technique to produce a correct ordering of -the boxes via integer division. -#+begin_src c++ :tangle 36.cpp +#+begin_src c++ :tangle 36.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -240,7 +234,7 @@ bool isValidSudoku(vector<vector<char>> &board) #+end_src ** DONE (#128) Longest consecutive sequence -#+begin_src c++ :tangle 128.cpp +#+begin_src c++ :tangle 128.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -260,9 +254,74 @@ int longestConsecutive(vector<int> &nums) return size; } #+end_src +** DONE (#53) Maximum Subarray +Find the maximal sum of a subarray in some array. This is actually a +dynamic programming problem. +*** Brute force +If there's only one element then that is obviously the maximal sum. +A brute force approach would compute it every subarray sum and then +return the best one. + +#+begin_src c++ :tangle 53-bf.cpp :comments link +#include <bits/stdc++.h> +using namespace std; + +int maxSubArray(vector<int> &nums) +{ + int max_sum = nums[0]; + for (int i = 1; i < nums.size(); ++i) + { + // Is nums[i] alone better than what we've made so far? + max_sum = std::max(nums[i], max_sum); + int cur_sum = 0; + for (int j = 0; j <= i; ++j) + cur_sum += nums[i]; + // Is the sum nums[0..i] better than what we've done so far? + max_sum = std::max(std::max(cur_sum, max_sum)); + } + return max_sum; +} +#+end_src + +O(n^2) but can we do better? +*** Dynamic programming +Look at the tree of cur_sum's we need to +compute: ++ at i = 1, cur_sum is sum[0..1] ++ at i = 2, cur_sum is sum[0..2] ++ at i = k, cur_sum is sum[0..k] = sum[0..k-1] + k + +At each iteration we're essentially checking if nums[i] is better or +the sum is better than what we've seen before. + +Obviously the sum is stupidly expensive. Furthermore, we may not even +need to do the entire sum; if the best sum starts at k and ends at k' +there's literally no point in summing numbers before k in cur_sum. So +we may as well introduce that optimisation. +#+begin_src c++ :tangle 53-dp.cpp :comments link +#+end_src +*** Kadane's formulation +#+begin_src c++ :tangle 53-kadane.cpp :comments link +#include <bits/stdc++.h> + +using namespace std; + +int maxSubArray(vector<int> &nums) +{ + if (nums.size() == 1) + return nums[0]; + int max_sum = nums[0], cur_sum = nums[0]; + for (size_t i = 1; i < nums.size(); ++i) + { + cur_sum = std::max(cur_sum + nums[i], nums[i]); + max_sum = std::max(cur_sum, max_sum); + } + return max_sum; +} +#+end_src * Stack ** DONE (#20) Valid Parentheses -#+begin_src c++ :tangle 20.cpp +#+begin_src c++ :tangle 20.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -306,7 +365,7 @@ functions in O(1) (what?!). In exchange for O(n) memory we can implement most of them. Unfortunately all the high performance implementations also use stacks (what's the point!). -#+begin_src c++ :tangle 155.cpp +#+begin_src c++ :tangle 155.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -360,7 +419,7 @@ Encountered an issue with C/C++'s semantics when it comes prefix decrement: it doesn't have an effect until after the statement so the other side of the assignment still considers ~ptr~ to be the same value. Bit interesting, good to note. -#+begin_src c++ :tangle 150.cpp +#+begin_src c++ :tangle 150.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -398,7 +457,7 @@ parentheses. *** Naive solution I generate all 2^n bit strings (where n = 2 * number of pairs) then filer all the invalid bit strings. -#+begin_src c++ :tangle 22-naive.cpp +#+begin_src c++ :tangle 22-naive.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -474,7 +533,7 @@ string (add an open brace or add a closed brace) but only generate the second one based on a condition on the first. As we do these simultaneously we can generate the two possible next steps given an input string. -#+begin_src c++ :tangle 22-backtrack.cpp +#+begin_src c++ :tangle 22-backtrack.cpp :comments link #include <bits/stdc++.h> using namespace std; @@ -531,3 +590,4 @@ vector<int> dailyTemperatures(vector<int> &temperatures) return days; } #+end_src +* Blind 75 |