Press "Enter" to skip to content

Posts tagged as “weekly contest”

花花酱 LeetCode Weekly Contest 137

1046. Last Stone Weight

Solution: Simulation (priority_queue)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

Time complexity: O(n)
Space complexity: O(n)

C++

1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

Time complexity: O(n^2*l)
Space complexity: O(n)

C++

1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

C++

花花酱 LeetCode Weekly Contest 135 (1037, 1038, 1039, 1040)

LeetCode 1037. Valid Boomerang

Solution: Math
Time complexity: O(1)
Space complexity: O(1)

C++

LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

Time complexity: O(n)
Space complexity: O(n)

C++

1039. Minimum Score Triangulation of Polygon

Solution: DP

Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j
answer: dp[0][n – 1]

Time complexity: O(n^3)
Space complexity: O(n^2)

C++/bottom-up

C++/top-down

Python

1040. Moving Stones Until Consecutive II

Solution: Sliding Window

Time complexity: O(nlogn)
Space complexity: O(1)

C++

花花酱 LeetCode Weekly Contest 134 (1033,1034,1035,1036)

1033. Moving Stones Until Consecutive

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

1034. Coloring A Border

Solution: DFS

Time complexity: O(mn)
Space complexity: O(mn)

C++

1035. Uncrossed Lines

Solution: LCS

Time complexity: O(nm)
Space complexity: O(mn)

C++

1036. Escape a Large Maze

Solution: limited search

Time complexity: O(b^2)
Space complexity: O(b^2)

C++

// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };

花花酱 LeetCode Weekly Contest 132 (1025,1026,1027,1028)

1025. Divisor Game

Solution: Recursion with Memoization

Time complexity: O(n^2)
Space complexity: O(n)

C++

1026. Maximum Difference Between Node and Ancestor

Solution: Resolution, pass min / max of ancestor nodes

Time complexity: O(n)
Space complexity: O(n)

C++

1027. Longest Arithmetic Sequence

Solution 1: Brute Force + Pruning

Time complexity: O(n^3) ~ O(n^2) in practice
Space complexity: O(n)

C++

1028. Recover a Tree From Preorder Traversal

Solution: Recursion

Check the current depth and expected depth, if don’t match, return nullptr.

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode Weekly Contest 131 (1021, 1022, 1023, 1024)

LeetCode 1021. Remove Outermost Parentheses

Solution: Track # of opened parentheses

Let n denote the # of opened parentheses after current char, keep ‘(‘ if n > 1 and keep ‘)’ if n > 0

Time complexity: O(n)
Space complexity: O(1)

C++

LeetCode 1022. Sum of Root To Leaf Binary Numbers

Solution: Recursion + Math

Keep tracking the number from root to current node.

Time complexity: O(n)
Space complexity: O(n)

C++

LeetCode 1023. Camelcase Matching

Solution: String…

Time complexity: O(n)
Space complexity: O(n)

C++

LeetCode 1024. Video Stitching

Solution 1: DP

Time complexity: O(nT^2)
Space complexity: O(T^2)

C++

C++/V2