Press "Enter" to skip to content

Posts tagged as “leetcode”

花花酱 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 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

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

Solution 2:

Solution 3:

 

花花酱 LeetCode 422. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

 

花花酱 Leetcode 500. Keyboard Row