Aloha les gars. Nous continuons sur les questions d’entrevue populaires. Aujourd’hui, nous allons résoudre quelques problèmes avec l’approche de la fenêtre coulissante.
Meilleur moment pour acheter et vendre des actions
Notre premier problème est tiré de « LeetCode Algorithm Challenges: Best Time to Buy and Sell Stock ».
Description
On vous donne un tableau prices où prices[i] est le prix d’une action donnée sur le ith jour.
Vous voulez maximiser votre profit en choisissant un seule journée acheter une action et choisir une jour différent dans le futur pour vendre ce stock.
Retour le profit maximum que vous pouvez tirer de cette transaction. Si vous ne pouvez réaliser aucun profit, retournez 0.
Exemple 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Exemple 2 :
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Solution
Tout d’abord, comme d’habitude, nous devons comprendre ce que nous allons faire. Il semble que nous devrions trouver un min ACHETER élément et max élément VENTE après l’élément ACHETER. Nous pouvons essayer d’obtenir chaque élément du tableau dans la première boucle, puis comparer tous les autres éléments dans la deuxième boucle, comme max = Math.max(max, prices[j] - prices[i]);.
Essayons de changer la deuxième boucle, et au lieu d’avoir deux boucles, nous pouvons utiliser while.
Nous pouvons utiliser « window » avec des pointeurs de début et de fin. Alors si notre arr[end] est plus grand que arr[start], nous pouvons augmenter le pointeur de fin, n’est-ce pas ? Et dans notre « fenêtre », nous aurons tous les éléments plus grands que arr[start]. J’espère que c’est clair : nous augmentons le pointeur de fin si et seulement si arr[end] est plus grand que arr[start]. Tous les éléments après le pointeur de début sont plus grands.
C’est pourquoi, si tout à coup nous avons arr[end] < arr[start], nous pouvons déplacer le pointeur de début vers la position du pointeur de fin et augmenter à nouveau le pointeur de fin. Wow, cela peut être très difficile à comprendre, mais j’espère que vous l’avez compris. Plongeons en profondeur et vérifions le code correspondant.
Code
public int maxProfit(int[] prices) {
int rez = 0;
int start = 0;
int end = start + 1;
while (end < prices.length){
if (prices[end] > prices[start]){
rez = Math.max(rez, prices[end] - prices[start]);
end++;
} else {
start = end;
end++;
}
}
return rez;
}Et la deuxième variante hallucinante :
public int maxProfit2(int[] prices) {
int max = 0;
for(int i = 0; i < prices.length; i ++){
for(int j = i+1; j < prices.length; j ++){
max = Math.max(max, prices[j] - prices[i]);
}
}
return max;
}Sous-chaîne la plus longue sans caractères répétés
Notre prochain problème est tiré de « Longueur de la plus longue sous-chaîne sans répétition de caractères ».
Description
Étant donné une chaîne strouver la longueur du le plus long sous-chaîne sans répétition de caractères.
Exemple 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Exemple 2 :
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Exemple 3 :
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution
Très bien, nous voulons trouver la sous-chaîne la plus longue sans répétitions. Pour vérifier les répétitions, nous pouvons utiliser Set, Par exemple. Nous devons également vérifier la longueur de la sous-chaîne, qui est un problème central dans cette tâche. Pour ce faire, préparons deux pointeurs : début et fin. Ensuite, nous pouvons déplacer le pointeur de fin à la position suivante uniquement si le caractère sur le le pointeur final est unique. Qu’est-ce que cela signifie? Cela signifie que nous vérifierions l’Ensemble, et si l’Ensemble ne contient pas de caractère, nous l’ajouterons et déplacerons le pointeur de fin.
Mais nous n’avons toujours pas de longueur. Et que faire des répétitions ? Maintenant, nous devons déplacer le pointeur de début alors que notre pointeur de fin ne persiste pas dans le Set: ensuite, vérifiez la longueur entre les pointeurs de début et de fin.
La première variante de code devrait être plus claire pour vous, mais la seconde est plus optimale. Apprécier:
Code
public int lengthOfLongestSubstring(String s) {
Set<Character> dict = new HashSet<>();
int rez = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
while(dict.contains(s.charAt(right))){
dict.remove(s.charAt(left));
left++;
}
dict.add(s.charAt(right));
rez = Math.max(rez, right - left + 1);
}
return rez;
}Seconde variante :
public int lengthOfLongestSubstring2(String s) {
int[] dict = new int[128];
int max = 0;
int curMax = 0;
int start = 0;
int skip = 0;
while(start < s.length()){
int idx = s.charAt(start) - ' ';
if (dict[idx] == 0){
dict[idx] = 1;
start++;
curMax++;
} else {
max = Math.max(max, curMax);
int skipIdx = s.charAt(skip) - ' ';
dict[skipIdx] = 0;
skip++;
curMax--;
}
}
return Math.max(max, curMax);
}Remplacement du caractère répétitif le plus long
Le dernier problème d’aujourd’hui provient de « LeetCode : Remplacement du caractère le plus répétitif ».
Description
Une chaîne vous est donnée s et un entier k. Vous pouvez choisir n’importe quel caractère de la chaîne et le remplacer par n’importe quel autre caractère anglais majuscule. Vous pouvez effectuer cette opération au maximum k fois.
Retour la longueur de la plus longue sous-chaîne contenant la même lettre que vous pouvez obtenir après avoir effectué les opérations ci-dessus.
Exemple 1:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.
Exemple 2 :
Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.
Solution
C’est un problème hallucinant pour moi. Je vous recommande fortement de le déboguer et d’essayer de comprendre chaque itération dans le code ci-dessus.
L’idée principale de cet algorithme est de trouver la valeur de répétition maximale dans le mot à chaque étape (maxFreq). On peut alors calculer le longueur de la sous-chaîne comme end - start + 1. Ce sera la longueur de notre sous-chaîne actuelle. Maintenant nous avons le longueur de la sous-chaîne et maxFreq de caractère. Je veux essayer de soustraire maxFreq du longueur de la sous-chaîne pour obtenir le compte des autres personnages. Je veux le répéter parce que c’est un moment crucial dans ce problème. Je veux calculer la longueur de la sous-chaîne et sous-structurer le nombre du caractère le plus fréquent. Ça me donne le nombre d’autres personnages.
Après cela, nous devons le comparer avec k. Si le nombre de caractères uniques est supérieur à knous devons déplacer le start-pointeret nous le ferions jusqu’à ce que le nombre de caractères uniques soit supérieur à k.
Avez-vous une solution plus optimale ? Pourriez-vous s’il vous plaît le partager avec moi?
Code
public int characterReplacement(String s, int k) {
int start = 0;
Map<Character, Integer> map = new HashMap<>();
int max = 0;
int maxFreq = 0;
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
map.put(cur, map.getOrDefault(cur, 0) + 1);
maxFreq = Math.max(maxFreq, maxCharLength(map));
while ((end - start + 1) - maxFreq > k) {
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
start++;
}
max = Math.max(max, end - start + 1);
}
return max;
}
private int maxCharLength(Map<Character, Integer> map) {
int max = 0;
for (Integer i : map.values()){
max = Math.max(max, i);
}
return max;
}Ne vous inquiétez pas si vous ne le comprenez pas du premier coup. Pour moi, la « fenêtre coulissante » est l’un des problèmes les plus difficiles à tous. Bonne chance!!!