Posts tagged as “simulation”

花花酱 LeetCode 43. Multiply Strings

By zxi on July 26, 2018

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

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

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

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

for (int i = 0; i < ans.length(); ++i)

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

花花酱 LeetCode 2. Add Two Numbers

By zxi on July 25, 2018

Problem

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

Simulate the addition, draw two numbers (one each) from l1, l2, if list is empty draw 0.

Using a dummy head makes things easier.

Time complexity: O(max(l1,l2))

Space complexity: O(max(l1,l2))

C++

// Author: Huahua

// Running time: 28 ms

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

// Running time: 30 ms

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

int sum = 0;

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

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

if (l1 != null) {

sum += l1.val;

l1 = l1.next;

}

if (l2 != null) {

sum += l2.val;

l2 = l2.next;

}

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

sum /= 10;

tail = tail.next;

}

return dummy.next;

}

Python3

"""

Author: Huahua

Running time: 112 ms

"""

class Solution:

def addTwoNumbers(self, l1, l2):

s = 0

dummy = ListNode(0)

tail = dummy

while l1 or l2 or s > 0:

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

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

tail.next = ListNode(s % 10)

s //= 10

tail = tail.next

return dummy.next

Problem

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 60 ms

class Solution {

public:

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {

int x = 0;

int y = 0;

int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES

int d = 1;

unordered_map<int, unordered_set<int>> o;

for (const auto obstacle : obstacles)

o[obstacle[0]].insert(obstacle[1]);

int ans = 0;

for (int c : commands) {

if (c == -2)

d = (d - 1 + 4) % 4;

else if (c == -1)

d = (d + 1) % 4;

else {

while (c--) {

int tx = x + dirs[d][0];

int ty = y + dirs[d][1];

if (o.count(tx) && o.at(tx).count(ty))

break;

x = tx;

y = ty;

ans = max(ans, x * x + y * y);

}

return ans;

}

};

花花酱 LeetCode 860. Lemonade Change

By zxi on June 30, 2018

Problem

At a lemonade stand, each lemonade costs $5.

Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).

Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays $5.

Note that you don’t have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Solution: Simulation + Greedy

Always use 10 bill first.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

bool lemonadeChange(vector<int>& bills) {

int fives = 0;

int tens = 0;

for (const int bill : bills) {

if (bill == 5) {

++fives;

} else if (bill == 10) {

if (!fives) return false;

++tens;

--fives;

} else if (bill == 20) {

if (tens && fives) {

--tens;

--fives;

} else if (fives >= 3) {

fives -= 3;

} else {

return false;

}

return true;

}

};

Posts tagged as “simulation”

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 2. Add Two Numbers

Problem

Solution: Simulation

C++

Java

Python3

Related Problems

花花酱 LeetCode 874. Walking Robot Simulation

Problem

Solution: Simulation

花花酱 LeetCode 445. Add Two Numbers II

Problem

Solution: Simulation

Related Problems

花花酱 LeetCode 860. Lemonade Change

Problem

Solution: Simulation + Greedy