Posts tagged as “simulation”

花花酱 LeetCode 2. Add Two Numbers

By zxi on December 30, 2019

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Time complexity: O(max(n,m))
Space complexity: O(max(n,m))

C++

// Author: Huahua

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode tail = new ListNode(0);

ListNode dummy = tail;

int sum = 0;

while (l1 != null || l2 != null || sum > 0) {

sum += (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);

tail.next = new ListNode(sum % 10);

tail = tail.next;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

sum /= 10;

}

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

dummy = tail = ListNode(0)

s = 0

while l1 or l2 or s:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

tail.next = ListNode(s % 10)

tail = tail.next

s //= 10

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

return dummy.next

花花酱 LeetCode 405. Convert a Number to Hexadecimal

By zxi on December 7, 2019

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

Solution: Simulation

if input is negative, add 2^32 to it (e.g. set the highest bit to 1)
while num is non zero, mod it by 16 and prepend the remainder to ans string, then divide num by 16.

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

C++

// Author: Huahua

constexpr char kHex[] = "0123456789abcdef";

class Solution {

public:

string toHex(int num) {

if (num == 0) return "0";

long t = num < 0 ? (1LL << 32) + num : num;

string ans;

while (t) {

ans = kHex[t % 16] + ans;

t /= 16;

}

return ans;

}

};

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

By zxi on December 1, 2019

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string tictactoe(vector<vector<int>>& moves) {

vector<vector<string>> b(3, vector<string>(3, "#"));

bool A = true;

for (const auto& move : moves) {

b[move[0]][move[1]] = A ? "A" : "B";

A = !A;

}

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

if (b[i][0] == b[i][1] && b[i][2] == b[i][1] && b[i][0] != "#")

return b[i][0];

if (b[0][i] == b[1][i] && b[2][i] == b[1][i] && b[0][i] != "#")

return b[0][i];

}

if (b[0][0] == b[1][1] && b[1][1] == b[2][2] && b[1][1] != "#")

return b[1][1];

if (b[2][0] == b[1][1] && b[1][1] == b[0][2] && b[1][1] != "#")

return b[1][1];

return moves.size() == 9 ? "Draw" : "Pending";

}

};

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

}

};