easy – Page 50 – Huahua’s Tech Road

花花酱 LeetCode 1104. Path In Zigzag Labelled Binary Tree

By zxi on July 1, 2019

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

1 <= label <= 10^6

Solution: Math

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

vector<int> pathInZigZagTree(int label) {

deque<int> ans;

while (label) {

ans.push_front(label);

int h = 31 - __builtin_clz(label);

label = ((1 << h) + (1 << (h + 1)) - 1 - label) / 2;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 1051. Height Checker

By zxi on May 27, 2019

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

1 <= heights.length <= 100
1 <= heights[i] <= 100

Solution: Sorting

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

C++

class Solution {

public:

int heightChecker(vector<int>& heights) {

vector<int> h(heights);

sort(begin(h), end(h));

int ans = 0;

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

ans += (heights[i] != h[i]);

return ans;

}

};

花花酱 LeetCode 1041. Robot Bounded In Circle

By zxi on May 14, 2019

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

"G": go straight 1 unit;
"L": turn 90 degrees to the left;
"R": turn 90 degress to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: "GGLLGG"
Output: true
Explanation: 
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.

Example 3:

Input: "GL"
Output: true
Explanation: 
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:

1 <= instructions.length <= 100
instructions[i] is in {'G', 'L', 'R'}

Solution: Simulation

When instructions end, if the robot is back to (0,0) or is not facing north (which guarantees it will come back to 0, 0 for another 1 or 3 rounds)

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

C++

// Author: Huahua

class Solution {

public:

bool isRobotBounded(string instructions) {

int x = 0;

int y = 0;

int d = 0;

vector<int> dx{0, 1, 0, -1};

vector<int> dy{-1, 0, 1, 0};

for (char c : instructions) {

if (c == 'G') {

x += dx[d];

y += dy[d];

} else {

d = (d + (c == 'L' ? 3 : 1)) % 4;

}

return x == 0 && y == 0 || d;

}

};

花花酱 LeetCode 1042. Flower Planting With No Adjacent

By zxi on May 14, 2019

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

Solution: Graph coloring, choose any available color

Time complexity: O(|V|+|E|)
Space complexity: O(|V|+|E|)

C++

class Solution {

public:

vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {

vector<int> ans(N, 0);

vector<vector<int>> G(N);

for (const auto& p : paths) {

G[p[0] - 1].push_back(p[1] - 1);

G[p[1] - 1].push_back(p[0] - 1);

}

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

int mask = 0;

for (const auto& j : G[i])

mask |= (1 << ans[j]);

for (int c = 1; c <= 4 && ans[i] == 0; ++c)

if (!(mask & (1 << c))) ans[i] = c;

}

return ans;

}

};

花花酱 LeetCode 38. Count and Say

By zxi on April 17, 2019

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

// Author: Huahua, 4 ms, 8.6 MB

class Solution {

public:

string countAndSay(int n) {

string ans = "1";

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

ans = say(ans);

return ans;

}

private:

string say(const string& n){

string ans;

int s = 0, l = n.length();

for (int e = 1; e <= l; ++e)

if (e == l || n[s] != n[e]) {

int count = e - s;

ans += '0' + count;

ans += n[s];

s = e;

}

return ans;

}

};

Posts tagged as “easy”

花花酱 LeetCode 1104. Path In Zigzag Labelled Binary Tree

Solution: Math

C++

花花酱 LeetCode 1051. Height Checker

Solution: Sorting

C++

花花酱 LeetCode 1041. Robot Bounded In Circle

C++

花花酱 LeetCode 1042. Flower Planting With No Adjacent

Solution: Graph coloring, choose any available color

C++

花花酱 LeetCode 38. Count and Say

Problem

C++