Posts tagged as “easy”

花花酱 LeetCode 1598. Crawler Log Folder

By zxi on September 27, 2020

The Leetcode file system keeps a log each time some user performs a change folder operation.

The operations are described below:

"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
"./" : Remain in the same folder.
"x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the i^th step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Example 1:

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Example 2:

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

Constraints:

1 <= logs.length <= 10³
2 <= logs[i].length <= 10
logs[i] contains lowercase English letters, digits, '.', and '/'.
logs[i] follows the format described in the statement.
Folder names consist of lowercase English letters and digits.

Solution: Simulation

We only need to track the depth of current folder, and name and path can be ignored.

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<string>& logs) {

int ans = 0;

for (const string& log : logs) {

if (log == "../")

ans = max(ans - 1, 0);

else if (log != "./")

++ans;

}

return ans;

}

};

花花酱 LeetCode 1592. Rearrange Spaces Between Words

By zxi on September 20, 2020

You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It’s guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

Example 1:

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Example 2:

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

Example 3:

Input: text = "hello   world"
Output: "hello   world"

Example 4:

Input: text = "  walks  udp package   into  bar a"
Output: "walks  udp  package  into  bar  a "

Example 5:

Input: text = "a"
Output: "a"

Constraints:

1 <= text.length <= 100
text consists of lowercase English letters and ' '.
text contains at least one word.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string reorderSpaces(string text) {

vector<string> words;

string word;

int t = 0;

for (char c : text) {

if (c == ' ') {

++t;

if (!word.empty()) {

words.push_back(word);

word.clear();

}

} else {

word += c;

}

if (!word.empty()) words.push_back(word);

const int n = words.size();

if (n == 1) return words[0] + string(t, ' ');

const int s = t / (n - 1);

const int r = t % (n - 1);

string ans;

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

if (i) ans.append(s, ' ');

ans += words[i];

}

ans.append(r, ' ');

return ans;

}

};

花花酱 LeetCode 1582. Special Positions in a Binary Matrix

By zxi on September 12, 2020

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
              [0,0,1],
              [1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],
              [0,1,0],
              [0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.

Example 3:

Input: mat = [[0,0,0,1],
              [1,0,0,0],
              [0,1,1,0],
              [0,0,0,0]]
Output: 2

Example 4:

Input: mat = [[0,0,0,0,0],
              [1,0,0,0,0],
              [0,1,0,0,0],
              [0,0,1,0,0],
              [0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.

Solution: Sum for each row and column

Brute force:
Time complexity: O(R*C*(R+C))
Space complexity: O(1)

We can pre-compute the sums for each row and each column, ans = sum(mat[r][c] == 1 and rsum[r] == 1 and csum[c] == 1)

Time complexity: O(R*C)
Space complexity: O(R+C)

C++

class Solution {

public:

int numSpecial(vector<vector<int>>& mat) {

const int rows = mat.size();

const int cols = mat[0].size();

vector<int> rs(rows);

vector<int> cs(cols);

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c) {

rs[r] += mat[r][c];

cs[c] += mat[r][c];

}

int ans = 0;

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c)

ans += mat[r][c] && rs[r] == 1 && cs[c] == 1;

return ans;

}

};

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

By zxi on September 5, 2020

Given a string s containing only lower case English letters and the ‘?’ character, convert all the ‘?’ characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non ‘?’ characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for ‘?’.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"

Constraints:

1 <= s.length <= 100
s contains only lower case English letters and ‘?’.

Solution: Greedy

For each ?, find the first one among ‘abc’ that is not same as left or right.

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

C++

class Solution {

public:

string modifyString(string s) {

const int n = s.length();

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

if (s[i] != '?') continue;

for (char c : "abc")

if ((i == 0 || s[i - 1] != c) && (i == n - 1 || s[i + 1] != c)) {

s[i] = c;

break;

}

return s;

}

};

花花酱 LeetCode 1572. Matrix Diagonal Sum

By zxi on September 5, 2020

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Solution: Brute Force

Note: if n is odd, be careful not to double count the center one.

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

C++

class Solution {

public:

int diagonalSum(vector<vector<int>>& mat) {

const int n = mat.size();

int ans = 0;

for (int i = 0; i < n; ++i)

ans += mat[i][i] + mat[i][n - i - 1];

if (n & 1) ans -= mat[n / 2][n / 2];

return ans;

}

};