Huahua’s Tech Road

花花酱 LeetCode 1271. Hexspeak

By zxi on November 30, 2019

A decimal number can be converted to its Hexspeak representation by first converting it to an uppercase hexadecimal string, then replacing all occurrences of the digit 0 with the letter O, and the digit 1 with the letter I. Such a representation is valid if and only if it consists only of the letters in the set {"A", "B", "C", "D", "E", "F", "I", "O"}.

Given a string num representing a decimal integer N, return the Hexspeak representation of N if it is valid, otherwise return "ERROR".

Example 1:

Input: num = "257"
Output: "IOI"
Explanation:  257 is 101 in hexadecimal.

Example 2:

Input: num = "3"
Output: "ERROR"

Constraints:

1 <= N <= 10^12
There are no leading zeros in the given string.
All answers must be in uppercase letters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string toHexspeak(string num) {

long n = stol(num);

string ans;

while (n) {

int r = n % 16;

char c;

if (r == 0) c = 'O';

else if (r == 1) c = 'I';

else if (r >= 10 && r <= 15) c = 'A' + r - 10;

else return "ERROR";

ans += c;

n >>= 4;

}

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location

By zxi on November 26, 2019

Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by a grid of size n*m, where each element is a wall, floor, or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle (impossible to walk there).
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

Constraints:

1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid contains only characters '.', '#', 'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.

Solution: BFS + DFS

BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.

C++

// Author: Huahua

struct Node {

int bx;

int by;

int px;

int py;

int key() const { return ((by * 20 + bx) << 16) | (py * 20 + px); }

};

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

Node start;

Node end;

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

for (int x = 0; x < m; ++x)

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

auto hasPath = [&](const Node& cur, int tx, int ty) {

vector<int> seen(m*n);

function<bool(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#')

return false;

if (x == cur.bx && y == cur.by) return false;

int key = y * m + x;

if (seen[key]) return false;

seen[key] = 1;

if (x == tx && y == ty) return true;

return dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

};

return dfs(cur.px, cur.py);

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

const int bx = cur.bx + dx;

const int by = cur.by + dy;

if (bx < 0 || bx >= m || by < 0 || by >= n || grid[by][bx] == '#')

return false;

if (!hasPath(cur, cur.bx - dx, cur.by - dy)) return false;

nxt->bx = bx;

nxt->by = by;

nxt->px = cur.bx;

nxt->py = cur.by;

return true;

};

const vector<int> dirs{0, -1, 0, 1, 0};

unordered_set<int> seen;

queue<Node> q;

q.push(start);

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

Node cur = q.front();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) ||

seen.count(nxt.key()))

continue;

if (nxt.bx == end.bx && nxt.by == end.by) return steps + 1;

seen.insert(nxt.key());

q.push(nxt);

}

++steps;

}

return -1;

}

};

**Solution: A* + BFS**

g : history = # of pushes
h: heuristics = Manhattan distance from the current box position to the target position, always <= actual moves.
f = g + h

C++

100

101

// Author: Huahua, 4 ms, 17.5 MB

struct Node {

int bx;

int by;

int px;

int py;

int h;

int g;

int key() const {

return ((by * m + bx) << 2) | ((bx - px) + 1) | ((by - py) + 1) >> 1;

}

int f() const { return g + h; }

bool operator< (const Node& o) const {

return f() > o.f();

}

static int m;

};

int Node::m;

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

const vector<int> dirs{0, -1, 0, 1, 0};

const int n = grid.size();

const int m = Node::m = grid[0].size();

Node start;

Node end;

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

for (int x = 0; x < m; ++x)

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

auto isValid = [&](int x, int y) {

return !(x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#');

};

auto hasPath = [&](const Node& cur, int tx, int ty) {

if (!isValid(tx, ty)) return false;

vector<int> seen(m*n);

queue<int> q;

q.push(cur.py * m + cur.px);

seen[cur.py * m + cur.px] = 1;

while (q.size()) {

int x = q.front() % m;

int y = q.front() / m;

q.pop();

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

int nx = x + dirs[i];

int ny = y + dirs[i + 1];

if (!isValid(nx, ny)) continue;

if (nx == cur.bx && ny == cur.by) continue;

if (nx == tx && ny == ty) return true;

if (seen[ny * m + nx]++) continue;

q.push(ny * m + nx);

}

return false;

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

nxt->bx = cur.bx + dx;

nxt->by = cur.by + dy;

nxt->px = cur.bx;

nxt->py = cur.by;

nxt->g = cur.g + 1;

nxt->h = abs(nxt->bx - end.bx) + abs(nxt->by - end.by);

if (!isValid(nxt->bx, nxt->by)) return false;

return hasPath(cur, cur.bx - dx, cur.by - dy);

};

vector<int> seen(m*n*4);

priority_queue<Node> q;

start.g = 0;

start.h = abs(start.bx - end.bx) + abs(start.by - end.by);

q.push(start);

while (q.size()) {

Node cur = q.top();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) || seen[nxt.key()]++) continue;

if (nxt.bx == end.bx && nxt.by == end.by) return nxt.g;

q.push(nxt);

}

return -1;

}

};

花花酱 LeetCode 1262. Greatest Sum Divisible by Three

By zxi on November 26, 2019

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

Solution: DP

dp[i] := max sum that has a remainder i when mod 3.

dp[(i + num) % 3] = max( dp[(i + num) % 3] , dp[i] + num)

ans: dp[0]

C++

// Author: Huahua

class Solution {

public:

int maxSumDivThree(vector<int>& nums) {

vector<int> dp(3);

for (int num : nums) {

vector<int> tmp(dp);

for (int s : tmp)

dp[(s + num) % 3] = max(dp[(s + num) % 3], s + num);

}

return dp[0];

}

};

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

By zxi on November 26, 2019

Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output

[null,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output

[null,true,true,false]

Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output

[null,true,false,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.find(5); // return True

Constraints:

TreeNode.val == -1
The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6

Solutoin 1: Recursion and HashSet

Time complexity: Recover O(n), find O(1)
Space complexity: O(n)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root) {

recover(root, 0);

}

bool find(int target) {

return s_.count(target);

}

private:

unordered_set<int> s_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

s_.insert(val);

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

Solution 2: Recursion and Binary format

The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1

e.g. target = 13, t = 13 + 1 = 14

t = 14, t % 1 = 0, t / 2 = 7, left

t = 7, t % 1 = 1, t / 2 = 3, right

t = 3, t % 1 = 1, t / 2 = 1, right

13 => right, right, left

Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root): root_(root) {

recover(root, 0);

}

bool find(int target) {

++target;

stack<bool> right;

while (target != 1) {

right.push(target & 1);

target >>= 1;

}

TreeNode* node = root_;

while (!right.empty() && node) {

node = right.top() ? node->right : node->left;

right.pop();

}

return node;

}

private:

TreeNode* root_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

花花酱 LeetCode 1260. Shift 2D Grid

By zxi on November 26, 2019

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] becomes at grid[i][j + 1].
Element at grid[i][m - 1] becomes at grid[i + 1][0].
Element at grid[n - 1][m - 1] becomes at grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Solution 1: Simulation

Simulate the shift process for k times.

Time complexity: O(k*n*m)
Space complexity: O(1) in-place

C++

// Author: Huahua, 80ms, 13.5 MB

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

while (k--) {

int last = grid[n - 1][m - 1];

for (int i = n - 1; i >= 0; --i)

for (int j = m - 1; j >= 0; --j) {

if (i == 0 && j == 0)

grid[i][j] = last;

else if (j == 0)

grid[i][j] = grid[i - 1][m - 1];

else

grid[i][j] = grid[i][j - 1];

}

return grid;

}

};

Solution 2: Rotate

Shift k times is equivalent to flatten the matrix and rotate by -k or (m*n – k % (m * n)).

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

C++

// Author: Huahua, 68 ms, 14.4 MB

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

k = m * n - k % (m*n);

vector<int> g;

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

g.insert(end(g), begin(grid[i]), end(grid[i]));

rotate(begin(g), begin(g) + k, end(g));

auto it = begin(g);

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

for (int j = 0; j < m; ++j)

grid[i][j] = *it++;

return grid;

}

};

O(1) space in-place rotation

C++

// Author: Huahua， 68 ms, 13.6 MB

class MatrixIterator {

public:

MatrixIterator(vector<vector<int>>& data, int index = 0) :

data_(data),

index_(index) {}

MatrixIterator& operator++() {

++index_;

return *this;

}

MatrixIterator& operator--() {

--index_;

return *this;

}

MatrixIterator operator +(int dis) const {

return MatrixIterator(data_, index_ + dis);

}

MatrixIterator operator -(int dis) const {

return MatrixIterator(data_, index_ - dis);

}

bool operator==(const MatrixIterator& o) const {

return data_ == o.data_ && index_ == o.index_;

}

bool operator!=(const MatrixIterator& o) const {

return data_ != o.data_ || index_ != o.index_;

}

ptrdiff_t operator-(const MatrixIterator& o) const {

return index_ - o.index_;

}

MatrixIterator& operator=(const MatrixIterator& o) {

data_ = o.data_;

index_ = o.index_;

return *this;

}

int& operator*() {

if (index_ <= 0) {

return data_[0][0];

} else if (index_ >= m() * n()) {

return data_.back().back();

} else {

return data_[index_ / m()][index_ % m()];

}

private:

int n() const { return data_.size(); }

int m() const { return n() == 0 ? 0 : data_[0].size(); }

vector<vector<int>>& data_;

int index_;

};

namespace std {

template<>

struct iterator_traits<MatrixIterator> {

typedef ptrdiff_t difference_type;

typedef int value_type;

typedef int* pointer;

typedef int& reference;

typedef random_access_iterator_tag iterator_category;

};

}

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

k = m * n - k % (m*n);

MatrixIterator it(grid);

rotate(it, it + k, it + m * n);

return grid;

}

};

Huahua's Tech Road

花花酱 LeetCode 1271. Hexspeak

Solution: Simulation

C++

花花酱 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location

Solution: BFS + DFS

C++

Solution: A* + BFS

C++

花花酱 LeetCode 1262. Greatest Sum Divisible by Three

C++

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

Solutoin 1: Recursion and HashSet

C++

Solution 2: Recursion and Binary format

C++

花花酱 LeetCode 1260. Shift 2D Grid

Solution 1: Simulation

C++

Solution 2: Rotate

C++

C++

**Solution: A* + BFS**