Instantly share code, notes, and snippets.

# Viktor Karpovvitkarpov

• Sort options
Created Nov 6, 2019
Trapping Rain Water (Dynamic Programming)
View trapping-rain-water.cpp
 class Solution { public: int trap(const vector& h) { int n = h.size(); vector left_max(n + 1); vector right_max(n + 1); for (int i = 1; i <= n; i++) { left_max[i] = max(left_max[i - 1], h[i - 1]); }
Created Oct 29, 2019
42. Trapping Rain Water
View trapping-water.cpp
 class Solution { public: int trap(const vector& h) { int n = h.size(); vector left_max(n + 1); vector right_max(n + 1); for (int i = 1; i <= n; i++) { left_max[i] = max(left_max[i - 1], h[i - 1]); }
Created Oct 25, 2019
Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram)
View largest-rectangle-in-histogram.js
 // Time: O(n * log (n)) // Memory: O(log (n)) /** * @param {number[]} heights * @return {number} */ var largestRectangleArea = function(heights) { if (!heights.length) { return 0;
Last active Oct 20, 2019
678. Valid Parenthesis String (dynamic programming)
View valid-parenthesis-string.js
 /** * @param {string} s * @return {boolean} */ var checkValidString = function(s) { const n = s.length; const dp = new Array(n).fill(0).map(() => new Array(n).fill(false)); for (let i = 0; i < n; i++) { if (s[i] == "*") {
Created Oct 17, 2019
View lru.cpp
 class LRUCache { typedef pair Node; typedef list::iterator ref; list q; unordered_map m; int capacity; void insert(int key, int value) { if (m.find(key) != m.end()) {
Created Oct 15, 2019
Sort Colors
View sort-colors.cpp
 class Solution { public: void sortColors(vector& nums) { int p0 = 0; int p1 = 0; int p2 = nums.size() - 1; while (p1 <= p2) { if (nums[p1] == 1) { p1++;
Created Oct 3, 2019
200. Number of Islands (https://leetcode.com/problems/number-of-islands/)
View number-of-islands.cpp
 class Solution { private: void eraseIsland(vector>& grid, int x, int y) { if (grid[y][x] == '0') { return; } grid[y][x] = '0'; if (y > 0) eraseIsland(grid, x, y - 1); if (y < grid.size() - 1) eraseIsland(grid, x, y + 1);
Created Oct 3, 2019
Divide Two Integers (32 bits environment only, O(log n) time complexity)
View divide-two-integers.js
 /** * @param {number} dividend * @param {number} divisor * @return {number} */ var divide = function(dividend, divisor) { if (dividend == INT_MIN && divisor == -1) { return INT_MAX; }
Created Sep 5, 2019
Binary Search Approach (https://leetcode.com/problems/two-sum)
View two-sum.cpp
 class Solution { public: vector twoSum(vector& nums, int target) { vector> numsNpos; for (auto i = 0; i < nums.size(); i++) { numsNpos.push_back({ nums[i], i }); } sort(numsNpos.begin(), numsNpos.end());
Last active Dec 27, 2018
Computer Science Club, 27.12.2018 (Strings)
View Computer-Science-Club-27-12-2018.md

# Computer Science Club, 27.12.2018

Here's a set of problems for the class. Exploiring strings.

## Is Unique

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Hints:

You can’t perform that action at this time.