Posts published in “Simulation”

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

}

};

花花酱 LeetCode 1252. Cells with Odd Values in a Matrix

By zxi on November 9, 2019

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m

Solution 1: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

vector<vector<int>> a(n, vector<int>(m));

for (const auto& idx : indices) {

for (int x = 0; x < m; ++x) ++a[idx[0]][x];

for (int y = 0; y < n; ++y) ++a[y][idx[1]];

}

int ans = 0;

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

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

ans += a[i][j] & 1;

return ans;

}

};

Solution 2: Counting

For each row and column, compute how many times it will be increased (odd or even).
For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.
Time complexity: O(n*m + k)
Space complexity: O(n+m)

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

vector<int> cols(m);

vector<int> rows(n);

for (const auto& idx : indices) {

rows[idx[0]] ^= 1;

cols[idx[1]] ^= 1;

}

int ans = 0;

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

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

ans += rows[i] ^ cols[j];

return ans;

}

};

花花酱 LeetCode 1222. Queens That Can Attack the King

By zxi on October 14, 2019

On an 8×8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation:  
The queen at [0,1] can attack the king cause they're in the same row. 
The queen at [1,0] can attack the king cause they're in the same column. 
The queen at [3,3] can attack the king cause they're in the same diagnal. 
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. 
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. 
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]

Example 3:

Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

Constraints:

1 <= queens.length <= 63
queens[0].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
At most one piece is allowed in a cell.

Solution2: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

vector<vector<int>> b(8, vector<int>(8));

for (const auto& q : queens)

b[q[0]][q[1]] = 1;

vector<vector<int>> ans;

for (const auto& q : queens) {

for (int dx = -1; dx <= 1; ++dx)

for (int dy = -1; dy <= 1; ++dy) {

if (dx == 0 && dy == 0) continue;

int x = q[1] + dx;

int y = q[0] + dy;

while (x >= 0 && y >= 0 && x < 8 && y < 8 && !b[y][x]) {

if (x == king[1] && y == king[0])

ans.push_back(q);

x += dx;

y += dy;

}

return ans;

}

};

Solution 2: HashTable + Binary Search

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

Support arbitrarily large boards, e.g. 1e9 x 1e9 with 1e6 # of queens.

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

unordered_map<int, map<int, vector<int>>> rows, cols, diag1, diag2;

for (const auto& q : queens) {

const int x = q[1];

const int y = q[0];

rows[y][x] = q;

cols[x][y] = q;

diag1[x + y][x] = q;

diag2[x - y][x] = q;

}

const int x = king[1];

const int y = king[0];

vector<vector<int>> ans;

find(rows, y, x, ans);

find(cols, x, y, ans);

find(diag1, x + y, x, ans);

find(diag2, x - y, x, ans);

return ans;

}

private:

void find(const unordered_map<int, map<int, vector<int>>>& m, int idx, int key, vector<vector<int>>& ans) {

if (!m.count(idx)) return;

const auto& d = m.at(idx);

auto it = d.upper_bound(key);

if (it != end(d))

ans.push_back(it->second);

if (it != begin(d))

ans.push_back(prev(it)->second);

}

};

花花酱 LeetCode 1073. Adding Two Negabinary Numbers

By zxi on June 6, 2019

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Note:

1 <= arr1.length <= 1000
1 <= arr2.length <= 1000
arr1 and arr2 have no leading zeros
arr1[i] is 0 or 1
arr2[i] is 0 or 1

Solution: Simulation

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

C++

// Author: Huahua, 8 ms, 9.2 MB

class Solution {

public:

vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {

int i = arr1.size();

int j = arr2.size();

int carry = 0;

vector<int> ans;

while (i || j || carry) {

int sum = (i ? arr1[--i] : 0) + (j ? arr2[--j] : 0) + carry;

ans.push_back(sum & 1);

carry = -(sum >> 1);

}

while (ans.back() == 0 && ans.size() > 1) ans.pop_back();

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

return ans;

}

};