Posts tagged as “medium”

花花酱 LeetCode 609. Find Duplicate File in System

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/find-duplicate-file-in-system/description/

题目大意：输出系统中文件内容相同的文件名。

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt … fn.txt with content f1_content, f2_content … fn_content, respectively) in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

"directory_path/file_name.txt"

Example 1:

Input:
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
Output:  
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Note:

No order is required for the final output.
You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
The number of files given is in the range of [1,20000].
You may assume no files or directories share the same name in the same directory.
You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest:

Imagine you are given a real file system, how will you search files? DFS or BFS?
If the file content is very large (GB level), how will you modify your solution?
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

Solution: HashTable

Key: content, Value: Array of filenames

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 80ms (beats 94.68%)

class Solution {

public:

vector<vector<string>> findDuplicate(vector<string>& paths) {

unordered_map<string, vector<string>> files; // content -> filenames

for (const string& path : paths) {

string folder;

int i = 0;

while (path[i] != ' ') folder += path[i++];

while (i < path.length()) {

string filename;

string content;

++i; // ' '

while (path[i] != '(') filename += path[i++];

++i; // '('

while (path[i] != ')') content += path[i++];

++i; // ')'

files[content].push_back(folder + "/" + filename);

}

vector<vector<string>> ans;

for (auto& kv : files)

if (kv.second.size() > 1)

ans.push_back(std::move(kv.second));

return ans;

}

};

花花酱 LeetCode 623. Add One Row to Tree

By zxi on March 19, 2018

题目大意：在树的所有第d层位置插入元素v。

Problem

https://leetcode.com/problems/add-one-row-to-tree/description/

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 19 ms (beats 90.85%)

class Solution {

public:

TreeNode* addOneRow(TreeNode* root, int v, int d) {

if (root == nullptr) return nullptr;

// Special case.

if (d == 1) {

TreeNode* new_root = new TreeNode(v);

new_root->left = root;

return new_root;

}

if (d == 2) {

TreeNode* l = root->left;

root->left = new TreeNode(v);

root->left->left = l;

TreeNode* r = root->right;

root->right = new TreeNode(v);

root->right->right = r;

} else {

addOneRow(root->left, v, d - 1);

addOneRow(root->right, v, d - 1);

}

return root;

}

};

花花酱 LeetCode 802. Find Eventual Safe States

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/find-eventual-safe-states/description/

题目大意：给一个有向图，找出所有不可能进入环的节点。

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Illustration of graph

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Idea: Finding Cycles

Solution 1: DFS

A node is safe if and only if: itself and all of its neighbors do not have any cycles.

Time complexity: O(V + E)

Space complexity: O(V + E)

// Author: Huahua

// Running time: 155 ms

class Solution {

public:

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {

vector<State> states(graph.size(), UNKNOWN);

vector<int> ans;

for (int i = 0; i < graph.size(); ++i)

if (dfs(graph, i, states) == SAFE)

ans.push_back(i);

return ans;

}

private:

enum State {UNKNOWN, VISITING, SAFE, UNSAFE};

State dfs(const vector<vector<int>>& g, int cur, vector<State>& states) {

if (states[cur] == VISITING)

return states[cur] = UNSAFE;

if (states[cur] != UNKNOWN)

return states[cur];

states[cur] = VISITING;

for (int next : g[cur])

if (dfs(g, next, states) == UNSAFE)

return states[cur] = UNSAFE;

return states[cur] = SAFE;

}

};

Problem

题目大意：给你两个数组A, B。问最少需要多少次对应位置元素的交换才能使得A和B变成单调递增。

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/description/

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Note:

A, B are arrays with the same length, and that length will be in the range [1, 1000].
A[i], B[i] are integer values in the range [0, 2000].

Solution: Search/DFS (TLE)

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: TLE 84/102 test cases passed.

class Solution {

public:

int minSwap(vector<int>& A, vector<int>& B) {

int ans = INT_MAX;

dfs(A, B, 0, 0, ans);

return ans;

}

private:

void dfs(vector<int>& A, vector<int>& B, int i, int c, int& ans) {

if (c >= ans) return;

if (i == A.size()) {

ans = min(ans, c);

return;

}

if (i == 0 || A[i] > A[i - 1] && B[i] > B[i - 1])

dfs(A, B, i + 1, c, ans);

if (i == 0 || A[i] > B[i - 1] && B[i] > A[i - 1]) {

swap(A[i], B[i]);

dfs(A, B, i + 1, c + 1, ans);

swap(A[i], B[i]);

}

};

Solution: DP

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int minSwap(vector<int>& A, vector<int>& B) {

const int n = A.size();

vector<int> keep(n, INT_MAX);

vector<int> swap(n, INT_MAX);

keep[0] = 0;

swap[0] = 1;

for (int i = 1; i < n; ++i) {

if (A[i] > A[i - 1] && B[i] > B[i - 1]) {

// Good case, no swapping needed.

keep[i] = keep[i - 1];

// Swapped A[i - 1] / B[i - 1], swap A[i], B[i] as well

swap[i] = swap[i - 1] + 1;

}

if (B[i] > A[i - 1] && A[i] > B[i - 1]) {

// A[i - 1] / B[i - 1] weren't swapped.

swap[i] = min(swap[i], keep[i - 1] + 1);

// Swapped A[i - 1] / B[i - 1], no swap needed for A[i] / B[i]

keep[i] = min(keep[i], swap[i - 1]);

}

return min(keep.back(), swap.back());

}

};

Python3

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def minSwap(self, A, B):

n = len(A)

dp = [[float('inf'), float('inf')] for _ in range(n)]

dp[0][0], dp[0][1] = 0, 1

for i in range(1, n):

if A[i] > A[i - 1] and B[i] > B[i - 1]:

dp[i][0] = dp[i - 1][0]

dp[i][1] = dp[i - 1][1] + 1

if B[i] > A[i - 1] and A[i] > B[i - 1]:

dp[i][0] = min(dp[i][0], dp[i - 1][1])

dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1)

return min(dp[-1])

花花酱 LeetCode 413. Arithmetic Slices

By zxi on March 17, 2018

题目大意：返回所有子数组中等差数列的个数。

Problem

https://leetcode.com/problems/arithmetic-slices/description/

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Solution 0: Reduction

Reduce the problem to # of all 1 sub arrays.

B[i – 2] = is_slice(A[i], A[i+1], A[i+2])

Time Complexity: O(n)

Space Complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3) return 0;

vector<int> B(A.size() - 2, 0);

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1])

B[i - 2] = 1;

}

return all1SubArrays(B);

}

private:

// return number of arrays whose values are all ones.

int all1SubArrays(const vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 0; i < A.size(); ++i)

if (A[i]) sum += ++curr;

else curr = 0;

return sum;

}

};

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1]) {

sum += ++curr;

} else {

curr = 0;

}

return sum;

}

};

Posts tagged as “medium”

花花酱 LeetCode 609. Find Duplicate File in System

Problem

Follow-up beyond contest:

Solution: HashTable

花花酱 LeetCode 623. Add One Row to Tree

Problem

Solution: Recursion

花花酱 LeetCode 802. Find Eventual Safe States

Problem

Idea: Finding Cycles

Solution 1: DFS

Related Problems

花花酱 LeetCode 801. Minimum Swaps To Make Sequences Increasing

Problem

Solution: Search/DFS (TLE)

C++

Solution: DP

C++

Python3

花花酱 LeetCode 413. Arithmetic Slices

Problem

Example:

Solution 0: Reduction

Solution 1: Combined

Related Problems: