Posts tagged as “simulation”

花花酱 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 59. Spiral Matrix II

By zxi on September 29, 2019

Given a positive integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

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

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int> > generateMatrix(int n) {

vector<vector<int>> ans(n, vector<int>(n));

int dir = 2, x = 0, y = 0;

int max_x = n - 1, max_y = n - 1;

int min_x = 0, min_y = 1;

int i = 0;

while (++i <= n*n) {

ans[y][x] = i;

switch (dir) {

// up

case 1: if (--y == min_y) { dir = 2; ++min_y; } break;

// right

case 2: if (++x == max_x) { dir = 3; --max_x; } break;

// down

case 3: if (++y == max_y) { dir = 4; --max_y; } break;

// left

case 4: if (--x == min_x) { dir = 1; ++min_x; } break;

}

return ans;

}

};

花花酱 LeetCode 232. Implement Queue using Stacks

By zxi on July 22, 2019

Implement the following operations of a queue using stacks.

push(x) — Push element x to the back of queue.
pop() — Removes the element from in front of queue.
peek() — Get the front element.
empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution: Use two stacks

amortized cost: O(1)

C++

class MyQueue {

public:

/** Initialize your data structure here. */

MyQueue() {}

/** Push element x to the back of queue. */

void push(int x) {

s1_.push(x);

}

/** Removes the element from in front of queue and returns that element. */

int pop() {

if (s2_.empty()) move();

int top = s2_.top();

s2_.pop();

return top;

}

/** Get the front element. */

int peek() {

if (s2_.empty()) move();

return s2_.top();

}

/** Returns whether the queue is empty. */

bool empty() {

return s1_.empty() && s2_.empty();

}

private:

stack<int> s1_;

stack<int> s2_;

void move() {

while (!s1_.empty()) {

s2_.push(s1_.top());

s1_.pop();

}

};