Skip to content

Commit bc2a821

Browse files
geemaplegeemaple
committed
Oct 27
1 parent 8c0f9fe commit bc2a821

11 files changed

+729
-8
lines changed

‎README.md‎

Lines changed: 18 additions & 8 deletions
Large diffs are not rendered by default.

‎leetcode/1716.calculate-money-in-leetcode-bank.cpp‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
// Tag: Math
2+
// Time: O(N)
3+
// Space: O(1)
4+
// Ref: -
5+
// Note: -
6+
// Video: https://youtu.be/fUbGNGqOi3w
7+
8+
// Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.
9+
// He starts by putting in $1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday.
10+
// Given n, return the total amount of money he will have in the Leetcode bank at the end of the nth day.
11+
//  
12+
// Example 1:
13+
//
14+
// Input: n = 4
15+
// Output: 10
16+
// Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.
17+
//
18+
// Example 2:
19+
//
20+
// Input: n = 10
21+
// Output: 37
22+
// Explanation: After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.
23+
//
24+
// Example 3:
25+
//
26+
// Input: n = 20
27+
// Output: 96
28+
// Explanation: After the 20th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.
29+
//
30+
//  
31+
// Constraints:
32+
//
33+
// 1 <= n <= 1000
34+
//
35+
//
36+
37+
class Solution {
38+
public:
39+
int totalMoney(int n) {
40+
int base = 21;
41+
int week = n / 7;
42+
int day = n % 7;
43+
int res = 0;
44+
for (int i = 0; i < week; i++) {
45+
res += base + (i + 1) * 7;
46+
}
47+
48+
for (int i = 0; i < day; i++) {
49+
res += i + (week + 1);
50+
}
51+
return res;
52+
}
53+
};

‎leetcode/1716.calculate-money-in-leetcode-bank.py‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
# Tag: Math
2+
# Time: O(N)
3+
# Space: O(1)
4+
# Ref: -
5+
# Note: -
6+
# Video: https://youtu.be/fUbGNGqOi3w
7+
8+
# Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.
9+
# He starts by putting in $1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday.
10+
# Given n, return the total amount of money he will have in the Leetcode bank at the end of the nth day.
11+
#  
12+
# Example 1:
13+
#
14+
# Input: n = 4
15+
# Output: 10
16+
# Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.
17+
#
18+
# Example 2:
19+
#
20+
# Input: n = 10
21+
# Output: 37
22+
# Explanation: After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.
23+
#
24+
# Example 3:
25+
#
26+
# Input: n = 20
27+
# Output: 96
28+
# Explanation: After the 20th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.
29+
#
30+
#  
31+
# Constraints:
32+
#
33+
# 1 <= n <= 1000
34+
#
35+
#
36+
37+
class Solution:
38+
def totalMoney(self, n: int) -> int:
39+
base = 21
40+
week = n // 7
41+
day = n % 7
42+
res = 0
43+
for i in range(week):
44+
res += base + (i + 1) * 7
45+
46+
for i in range(day):
47+
res += i + (week + 1)
48+
49+
return res

‎leetcode/2043.simple-bank-system.cpp‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
// Tag: Array, Hash Table, Design, Simulation
2+
// Time: O(1)
3+
// Space: O(N)
4+
// Ref: -
5+
// Note: -
6+
// Video: https://youtu.be/-ejSX-2Jznc
7+
8+
// You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)th account having an initial balance of balance[i].
9+
// Execute all the valid transactions. A transaction is valid if:
10+
//
11+
// The given account number(s) are between 1 and n, and
12+
// The amount of money withdrawn or transferred from is less than or equal to the balance of the account.
13+
//
14+
// Implement the Bank class:
15+
//
16+
// Bank(long[] balance) Initializes the object with the 0-indexed integer array balance.
17+
// boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
18+
// boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
19+
// boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.
20+
//
21+
//  
22+
// Example 1:
23+
//
24+
// Input
25+
// ["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
26+
// [[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
27+
// Output
28+
// [null, true, true, true, false, false]
29+
//
30+
// Explanation
31+
// Bank bank = new Bank([10, 100, 20, 50, 30]);
32+
// bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw $10.
33+
// // Account 3 has $20 - $10 = $10.
34+
// bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20.
35+
// // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30.
36+
// bank.deposit(5, 20); // return true, it is valid to deposit $20 to account 5.
37+
// // Account 5 has $10 + $20 = $30.
38+
// bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10,
39+
// // so it is invalid to transfer $15 from it.
40+
// bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist.
41+
//
42+
//  
43+
// Constraints:
44+
//
45+
// n == balance.length
46+
// 1 <= n, account, account1, account2 <= 105
47+
// 0 <= balance[i], money <= 1012
48+
// At most 104 calls will be made to each function transfer, deposit, withdraw.
49+
//
50+
//
51+
52+
class Bank {
53+
public:
54+
vector<long long> bal;
55+
Bank(vector<long long>& balance) {
56+
swap(bal, balance);
57+
}
58+
59+
bool transfer(int account1, int account2, long long money) {
60+
int n = bal.size();
61+
if (account1 <= n && account2 <= n && bal[account1 - 1] >= money) {
62+
bal[account1 - 1] -= money;
63+
bal[account2 - 1] += money;
64+
return true;
65+
}
66+
return false;
67+
}
68+
69+
bool deposit(int account, long long money) {
70+
int n = bal.size();
71+
if (account <= n) {
72+
bal[account - 1] += money;
73+
return true;
74+
}
75+
return false;
76+
}
77+
78+
bool withdraw(int account, long long money) {
79+
int n = bal.size();
80+
if (account <= n && bal[account - 1] >= money) {
81+
bal[account - 1] -= money;
82+
return true;
83+
}
84+
return false;
85+
}
86+
};
87+
88+
/**
89+
* Your Bank object will be instantiated and called as such:
90+
* Bank* obj = new Bank(balance);
91+
* bool param_1 = obj->transfer(account1,account2,money);
92+
* bool param_2 = obj->deposit(account,money);
93+
* bool param_3 = obj->withdraw(account,money);
94+
*/

‎leetcode/2043.simple-bank-system.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
# Tag: Array, Hash Table, Design, Simulation
2+
# Time: O(1)
3+
# Space: O(N)
4+
# Ref: -
5+
# Note: -
6+
# Video: https://youtu.be/-ejSX-2Jznc
7+
8+
# You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)th account having an initial balance of balance[i].
9+
# Execute all the valid transactions. A transaction is valid if:
10+
#
11+
# The given account number(s) are between 1 and n, and
12+
# The amount of money withdrawn or transferred from is less than or equal to the balance of the account.
13+
#
14+
# Implement the Bank class:
15+
#
16+
# Bank(long[] balance) Initializes the object with the 0-indexed integer array balance.
17+
# boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
18+
# boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
19+
# boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.
20+
#
21+
#  
22+
# Example 1:
23+
#
24+
# Input
25+
# ["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
26+
# [[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
27+
# Output
28+
# [null, true, true, true, false, false]
29+
#
30+
# Explanation
31+
# Bank bank = new Bank([10, 100, 20, 50, 30]);
32+
# bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw $10.
33+
# // Account 3 has $20 - $10 = $10.
34+
# bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20.
35+
# // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30.
36+
# bank.deposit(5, 20); // return true, it is valid to deposit $20 to account 5.
37+
# // Account 5 has $10 + $20 = $30.
38+
# bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10,
39+
# // so it is invalid to transfer $15 from it.
40+
# bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist.
41+
#
42+
#  
43+
# Constraints:
44+
#
45+
# n == balance.length
46+
# 1 <= n, account, account1, account2 <= 105
47+
# 0 <= balance[i], money <= 1012
48+
# At most 104 calls will be made to each function transfer, deposit, withdraw.
49+
#
50+
#
51+
52+
class Bank:
53+
54+
def __init__(self, balance: List[int]):
55+
self.bal = balance
56+
57+
def transfer(self, account1: int, account2: int, money: int) -> bool:
58+
n = len(self.bal)
59+
if account1 <= n and account2 <= n and self.bal[account1 - 1] >= money:
60+
self.bal[account1 - 1] -= money
61+
self.bal[account2 - 1] += money
62+
return True
63+
return False
64+
65+
def deposit(self, account: int, money: int) -> bool:
66+
n = len(self.bal)
67+
if account <= n:
68+
self.bal[account - 1] += money
69+
return True
70+
return False
71+
72+
def withdraw(self, account: int, money: int) -> bool:
73+
n = len(self.bal)
74+
if account <= n and self.bal[account - 1] >= money:
75+
self.bal[account - 1] -= money
76+
return True
77+
return False
78+
79+
80+
# Your Bank object will be instantiated and called as such:
81+
# obj = Bank(balance)
82+
# param_1 = obj.transfer(account1,account2,money)
83+
# param_2 = obj.deposit(account,money)
84+
# param_3 = obj.withdraw(account,money)

‎leetcode/2048.next-greater-numerically-balanced-number.cpp‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
// Tag: Hash Table, Math, Backtracking, Counting, Enumeration
2+
// Time: O(N)
3+
// Space: O(N)
4+
// Ref: -
5+
// Note: -
6+
// Video: https://youtu.be/yMjRNt9h1nQ
7+
8+
// An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.
9+
// Given an integer n, return the smallest numerically balanced number strictly greater than n.
10+
//  
11+
// Example 1:
12+
//
13+
// Input: n = 1
14+
// Output: 22
15+
// Explanation:
16+
// 22 is numerically balanced since:
17+
// - The digit 2 occurs 2 times.
18+
// It is also the smallest numerically balanced number strictly greater than 1.
19+
//
20+
// Example 2:
21+
//
22+
// Input: n = 1000
23+
// Output: 1333
24+
// Explanation:
25+
// 1333 is numerically balanced since:
26+
// - The digit 1 occurs 1 time.
27+
// - The digit 3 occurs 3 times.
28+
// It is also the smallest numerically balanced number strictly greater than 1000.
29+
// Note that 1022 cannot be the answer because 0 appeared more than 0 times.
30+
//
31+
// Example 3:
32+
//
33+
// Input: n = 3000
34+
// Output: 3133
35+
// Explanation:
36+
// 3133 is numerically balanced since:
37+
// - The digit 1 occurs 1 time.
38+
// - The digit 3 occurs 3 times.
39+
// It is also the smallest numerically balanced number strictly greater than 3000.
40+
//
41+
//  
42+
// Constraints:
43+
//
44+
// 0 <= n <= 106
45+
//
46+
//
47+
48+
class Solution {
49+
public:
50+
int nextBeautifulNumber(int n) {
51+
vector<int> counter = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
52+
int size = to_string(n).size();
53+
return dfs(n, 0, size, counter) ?: dfs(n, 0, size + 1, counter);
54+
}
55+
56+
int dfs(int n, int val, int size, vector<int> &counter) {
57+
if (size == 0) {
58+
for (int i = 1; i <= 9; i++) {
59+
if (counter[i] == i) {
60+
continue;
61+
}
62+
if (counter[i] != 0) {
63+
return 0;
64+
}
65+
}
66+
return val > n ? val : 0;
67+
}
68+
69+
int res = 0;
70+
for (int i = 1; i <= 9 && res == 0; i++) {
71+
if (counter[i] > 0 && counter[i] <= size) {
72+
counter[i] -= 1;
73+
res = dfs(n, val * 10 + i, size - 1, counter);
74+
counter[i] += 1;
75+
}
76+
}
77+
78+
return res;
79+
}
80+
};

0 commit comments

Comments
 (0)