Posts tagged as “simulation”

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

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

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 173. Binary Search Tree Iterator

By zxi on November 28, 2021

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁶
At most 10⁵ calls will be made to hasNext, and next.

Follow up:

Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Solution: In-order traversal using a stack

Use a stack to simulate in-order traversal.

Each next, we walk to the left most (smallest) node and push all the nodes along the path to the stack.

Then pop the top one t as return val, our next node to explore is the right child of t.

Time complexity: amortized O(1) for next() call.
Space complexity: O(n)

C++

// Author: Huahua

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

class BSTIterator {

public:

BSTIterator(TreeNode* root) : root_(root) {}

int next() {

while (root_) {

s_.push(root_);

root_ = root_->left;

}

TreeNode* t = s_.top(); s_.pop();

root_ = t->right;

return t->val;

}

bool hasNext() {

return (root_ || !s_.empty());

}

private:

TreeNode* root_;

stack<TreeNode*> s_;

};

/**

* Your BSTIterator object will be instantiated and called as such:

* BSTIterator* obj = new BSTIterator(root);

* int param_1 = obj->next();

* bool param_2 = obj->hasNext();

花花酱 LeetCode 119. Pascal’s Triangle II

By zxi on November 27, 2021

Given an integer rowIndex, return the rowIndex^th (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solution: Remember last row

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

C++

# Author: huahua

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int> ans(1, 1);

for (int i = 2; i <= rowIndex + 1; ++i) {

vector<int> tmp(i, 1);

for (int j = 1; j < i - 1; ++j)

tmp[j] = ans[j] + ans[j - 1];

swap(ans, tmp);

}

return ans;

}

};

花花酱 LeetCode 118. Pascal’s Triangle

By zxi on November 27, 2021

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> ans(numRows);

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

ans[i].resize(i + 1);

ans[i][0] = ans[i][i] = 1;

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

ans[i][j] = ans[i-1][j] + ans[i-1][j-1];

}

return ans;

}

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

By zxi on November 27, 2021

There is an m x n grid, where (0, 0) is the top-left cell and (m - 1, n - 1) is the bottom-right cell. You are given an integer array startPos where startPos = [start_row, start_col] indicates that initially, a robot is at the cell (start_row, start_col). You are also given an integer array homePos where homePos = [home_row, home_col] indicates that its home is at the cell (home_row, home_col).

The robot needs to go to its home. It can move one cell in four directions: left, right, up, or down, and it can not move outside the boundary. Every move incurs some cost. You are further given two 0-indexed integer arrays: rowCosts of length m and colCosts of length n.

If the robot moves up or down into a cell whose row is r, then this move costs rowCosts[r].
If the robot moves left or right into a cell whose column is c, then this move costs colCosts[c].

Return the minimum total cost for this robot to return home.

Example 1:

Input: startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
Output: 18
Explanation: One optimal path is that:
Starting from (1, 0)
-> It goes down to (2, 0). This move costs rowCosts[2] = 3.
-> It goes right to (2, 1). This move costs colCosts[1] = 2.
-> It goes right to (2, 2). This move costs colCosts[2] = 6.
-> It goes right to (2, 3). This move costs colCosts[3] = 7.
The total cost is 3 + 2 + 6 + 7 = 18

Example 2:

Input: startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
Output: 0
Explanation: The robot is already at its home. Since no moves occur, the total cost is 0.

Constraints:

m == rowCosts.length
n == colCosts.length
1 <= m, n <= 10⁵
0 <= rowCosts[r], colCosts[c] <= 10⁴
startPos.length == 2
homePos.length == 2
0 <= start_row, home_row < m
0 <= start_col, home_col < n

Solution: Manhattan distance

Move directly to the goal, no back and forth. Cost will be the same no matter which path you choose.

ans = sum(rowCosts[y1+1~y2]) + sum(colCosts[x1+1~x2])

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

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {

int dx = homePos[1] > startPos[1] ? 1 : (homePos[1] < startPos[1] ? -1 : 0);

int dy = homePos[0] > startPos[0] ? 1 : (homePos[0] < startPos[0] ? -1 : 0);

int ans = 0;

while (homePos[1] != startPos[1]) ans += colCosts[startPos[1] += dx];

while (homePos[0] != startPos[0]) ans += rowCosts[startPos[0] += dy];

return ans;

}

};

Posts tagged as “simulation”

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 173. Binary Search Tree Iterator

Solution: In-order traversal using a stack

C++

花花酱 LeetCode 119. Pascal’s Triangle II

Solution: Remember last row

C++

Related Problems

花花酱 LeetCode 118. Pascal’s Triangle

Solution: Simulation

C++

Related Problems

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

Solution: Manhattan distance

C++