1716. The calculation force deducts money from the bank
One question per day on January 15, 2022
Title Description
Hercy wants to save money for her first car. He deposits money in the Likou bank every day.
At first, he deposited 1 yuan on Monday. From Tuesday to Sunday, he deposited 1 yuan more every day than the previous day. In the following Monday, he will deposit 1 yuan more than the previous Monday.
Here you are n, please return to the total amount of money he deposited in Likou bank at the end of day n.
Example 1:
Input: n = 4
Output: 10
Explanation: after the 4th day, the total amount is 1 + 2 + 3 + 4 = 10.
Example 2:
Input: n = 10
Output: 37
Explanation: after the 10th day, the total amount is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. It was noted that Hercy deposited 2 yuan the next Monday.
Example 3:
Input: n = 20
Output: 96
Explanation: after the 20th day, the total amount is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.
Tips:
1 <= n <= 1000
Source: LeetCode
Link: https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
Simple simulation
class Solution {
public int totalMoney(int n) {
int cycle = n / 7;
int mod = n % 7;
int base = (1 + 7) * 7 / 2;
int ans = 0;
for(int i = 0; i < cycle; i++){
ans += base;
base += 7;
}
for(int i = 0; i < mod; i++){
ans += cycle + i + 1;
}
return ans;
}
}
382. Linked list random node
2022.1.16 one question per day
Title Description
Give you a single linked list, randomly select a node in the linked list, and return the corresponding node value. Each node has the same probability of being selected.
Implement the Solution class:
Solution(ListNode head) initializes the object with an array of integers.
int getRandom() randomly selects a node from the linked list and returns the value of the node. All nodes in the linked list have the same probability of being selected.
Example:
input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
output
[null, 1, 3, 2, 2, 3]
explain
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // Return 1
solution.getRandom(); // Return 3
solution.getRandom(); // Return 2
solution.getRandom(); // Return 2
solution.getRandom(); // Return 3
//The getRandom() method should randomly return one of 1, 2 and 3, and the probability of each element being returned is equal.
Tips:
The number of nodes in the linked list is in the range [1, 10 ^ 4]
-10^4 <= Node.val <= 10^4
The getRandom method cannot be called more than 10 ^ 4 times
Advanced:
What if the linked list is very large and the length is unknown?
Can you solve this problem without using additional space?
Source: LeetCode
Link: https://leetcode-cn.com/problems/linked-list-random-node
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
Because it's easy to just return the value
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//Feel it, because you need to initialize the object with an integer array, it's very simple
//Integer arrays are not extra space
//Just store a pointer to the current node in each array
int[] arr;
int len;
Random rd = new Random();
public Solution(ListNode head) {
int idx = 0;
ListNode temp = head;
while(temp != null){
idx++;
temp = temp.next;
}
arr = new int[idx];
temp = head;
idx = 0;
while(temp != null){
arr[idx++] = temp.val;
temp = temp.next;
}
len = idx;
}
public int getRandom() {
int t = rd.nextInt(len);
return arr[t];
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
I thought that the created array was not extra space. It turned out that we should not use any space at all
For reservoir sampling, add nodes from 0 to the list length. Sampling will be carried out every time. If 0 is selected, the node will be returned
This can ensure that the probability of each node is 1/n
Due to the small space and low time complexity, pond sampling can be used for random sampling in large data flow.
Pond sampling is applicable to a very large amount of data, generally flow data. You don't know how many are there. Select multiple elements randomly. These selected elements are placed in a pool, and it is possible to return the number in the pool at any time. For example, in the field of big data, data has been processed all the time. However, if five processed data need to be returned randomly at a certain time node, we can declare a pool with a size of 5 for processing.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//Legendary reservoir sampling
//If you can't, keep smoking
//The current node is returned only when 0 is selected each time
//Each extraction needs to traverse the linked list
ListNode head;
Random rd;
public Solution(ListNode head) {
this.head = head;
rd = new Random();
}
public int getRandom() {
int idx = 1;
int ans = 0;
ListNode temp = head;
while(temp != null){
if(rd.nextInt(idx) == 0)
ans = temp.val;
temp = temp.next;
idx++;
}
return ans;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
1220. Count the number of vowel sequences
2022.1.17 one question per day
Title Description
Give you an integer n, please help us count how many strings with length n can be formed according to the following rules:
Each character in the string should be a lowercase vowel ('a ',' e ',' i ',' o ',' u ')
Each vowel 'a' can only be followed by 'e'
Each vowel 'e' can only be followed by 'a' or 'i'
Each vowel 'i' cannot be followed by another 'i'
Each vowel 'o' can only be followed by 'i' or 'u'
Each vowel 'u' can only be followed by 'a'
Since the answer may be very large, please return the result after module 10 ^ 9 + 7.
Example 1:
Input: n = 1
Output: 5
Explanation: all possible strings are: "a", "e", "i", "o" and "u".
Example 2:
Input: n = 2
Output: 10
Explanation: all possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
Example 3:
Input: n = 5
Output: 68
Tips:
1 <= n <= 2 * 10^4
Source: LeetCode
Link: https://leetcode-cn.com/problems/count-vowels-permutation
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
A simple dynamic programming
You can write fast exponentiation of matrices
class Solution {
int MOD = (int)1e9 + 7;
public int countVowelPermutation(int n) {
//It feels like that state machine transition method
//Is it dynamic programming
//0 1 2 3 4 respectively represent the end of a e i o u
//
int[][] f = new int[n][5];
for(int i = 0; i < 5; i++){
f[0][i] = 1;
}
for(int i = 1; i < n; i++){
f[i][0] = ((f[i - 1][1] + f[i - 1][2]) % MOD + f[i - 1][4]) % MOD;
f[i][1] = (f[i - 1][0] + f[i - 1][2]) % MOD;
f[i][2] = (f[i - 1][1] + f[i - 1][3]) % MOD;
f[i][3] = f[i - 1][2];
f[i][4] = (f[i - 1][2] + f[i - 1][3]) % MOD;
}
int ans = 0;
for(int i = 0; i < 5; i++){
ans = (ans + f[n - 1][i]) % MOD;
}
return ans;
}
}