Editer Questions posées lors d'entretiens
Plutôt une liste de tests techniques avec les solutions trouvées (en général) par moi donc peut être pas optimale mais au bout je les comprends (vaguement).
Afficher tous les nombres pairs entre 0 et 100
for(int i=0;i<100;i++) {
if (i%2==0) { // si le reste de la division de i par 2 est 0
System.out.println(i); // alors c'est pair
}
}
}
Afficher la somme de tous les nombres de 0 à 100 inclu
int somme = 0;
for(int i=0;i<=100;i++) {
somme+=i;
}
System.out.println(somme);
On peut aussi juste faire :
System.out.println(100*(100+1)/2);
Créer un jeu de carte, le mélanger, sortir 2 cartes au hasard
package littleTests;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
class Solution {
public static void main(String[] args) {
List<String> base = Arrays.asList("1","2","3","4","5","6","7","8","9","10","V","Q","K");
List<String> suitList = Arrays.asList(" of hearts", " of diamonds", " of clovers", " of tiles");
List<String> deck = new ArrayList();
for (String suit:suitList) {
for (String value:base) {
deck.add(value+suit);
}
}
System.out.println(deck.size());
System.out.println(deck);
Collections.shuffle(deck);
System.out.println(deck);
int r = new Random().nextInt(0, deck.size());
System.out.println(deck.get(r));
deck.remove(r);
r = new Random().nextInt(0, deck.size());
System.out.println(deck.get(r));
deck.remove(r);
}
}
Super Nombre
Pour un nombre en texte ("123"), le dupliquer par x ("123123123"), additionner tous les chiffres du nombre entre eux, répéter jusqu'à être sous 0 :
private static long getSuperDigit(String digit, int k) {
//pour chaque caractere du string on convertit sa representation ("4") en int puis multiplie tout ensemble
long superDigitTentative = digit.chars().mapToLong(Character::getNumericValue).sum();
//additionner le resultat ((1+2+3)*3) revient au meme que dupliquer (1+2+3+1+2+3+1+2+3)
superDigitTentative*=k; //mais moins consommateur en resources
if(superDigitTentative>9) {
superDigitTentative = getSuperDigit(""+superDigitTentative, 1);
}
return superDigitTentative;
}
FizzBuzz
Pas de piège. Pour chaque nombre entre 1 et le nombre donné, si mutiple de 3 ET 5 (càd reste de la division par 3 ou 5 égal à 0) afficher FizzBuzz, mutiple de 3 afficher fizz, multiple de 5 afficher buzz, sinon afficher le nombre :
public static void fizzBuzz(int n) {
// Write your code here
for(int i=1;i<=n;i++) {
if (i%3==0 && i%5==0) {
System.out.println("FizzBuzz");
}else if (i%3==0) {
System.out.println("Fizz");
}else if (i%5==0) {
System.out.println("Buzz");
}else {
System.out.println(i);
}
}
}
Plus Minus
Avec un tableau de nombres positifs/negatifs/ou à zéro, calculer le ration d'éléments négatifs, positifs, 0. Forcer le formant en sortie à être x.xxxxxx.
Rien de sorcier, pour compter on peut utiliser arr.stream().filter(n -> n>0).count() qui donne un Long qu'on va caster en String.
public static void plusMinus(List<Integer> arr) {
int positiveNumbers = (int) arr.stream().filter(n -> n>0).count();
int negativeNumbers = (int) arr.stream().filter(n -> n<0).count();
int zeroNumbers = (int) arr.stream().filter(n -> n==0).count();
System.out.println(String.format("%.6f", (float)positiveNumbers/arr.size()));
System.out.println(String.format("%.6f", (float)negativeNumbers/arr.size()));
System.out.println(String.format("%.6f", (float)zeroNumbers/arr.size()));
}
Mini-Max Sum
Dans un tableau "arr" de 5 entier, renvoyer la somme des 4 plus grands et la somme des 4 plus petits.
Simple, on trie le tableau de grand a petit et on additionne en sautant le premier, puis de petit à grand et on additionne en sautant le premier.
ArrayList<Integer> bigToSmall = new ArrayList<>(arr);
bigToSmall.sort((a,b) -> b-a);
System.out.print(bigToSmall.stream().skip(1L).collect(Collectors.summingLong(a -> a))); //saute le + grandm additionne les 4 petits
System.out.print(" ");
ArrayList<Integer> smallToBig = new ArrayList<>(arr);
smallToBig.sort((a,b) -> a-b);
System.out.print(smallToBig.stream().skip(1L).collect(Collectors.summingLong(a -> a))); //additionne les 4 grands
Conversion format horaire
Convertir 01:00:00PM en 13:00:00, il faut juste avoir les patterns de DateTimeFormatter :
public static String timeConversion(String s) {
LocalTime ldt = LocalTime.parse(s, DateTimeFormatter.ofPattern("hh:mm:ssa"));
return ldt.format(DateTimeFormatter.ofPattern("HH:mm:ss"));
}
Inverser 2 variables
Pour inverser 2 variables le plus simple est d'utiliser une variable intermédiaire, temporaire :
int a=1, b=9;
System.out.println("a vaut " + a + ", b vaut " + b);
int tmp; //la var temporaire
tmp=a;
a=b;
b=tmp;
System.out.println("a vaut " + a + ", b vaut " + b);
Mais on peut aussi s'en sortir avec des soustractions :
int a=1, b=9;
System.out.println("a vaut " + a + ", b vaut " + b);
a=b-a; //9-1=8
b=b-a; //9-8=1
a=a+b; //8+1=9
System.out.println("a vaut " + a + ", b vaut " + b);
//a vaut 1, b vaut 9
//a vaut 9, b vaut 1
Ca marche tout le temps :
int a=11, b=9;
System.out.println("a vaut " + a + ", b vaut " + b);
a=b-a; //9-11=-2
b=b-a; //9--2=11
a=a+b; //-2+11=9
System.out.println("a vaut " + a + ", b vaut " + b);
//a vaut 11, b vaut 9
//a vaut 9, b vaut 11
Lonely Integer
Trouver l'entier seul dans un tableau où les autres sont en double, exemple [2,6,3,3,2,1,6] 1 est seul.
Une soluce simple consiste à transformer en arrayList et utiliser lastIndexOf :
int[] monTableau = {2,6,3,3,2,9,6};
List<Integer> maListe =
Arrays.stream(monTableau).mapToObj(a->a).collect(Collectors.toList()); //.boxed() au lieu de mapToObj(a->a) marche aussi
for(int i=0;i<monTableau.length;i++) {
if(maListe.indexOf(maListe.get(i)) == maListe.lastIndexOf(maListe.get(i))) {
System.out.println("Celui qui est seul" + maListe.get(i));
break;
}
}
On peut aussi trier la liste, la parcourir et vérifier que le nombre d'après ne soit pas égal au nombre en cours mais bon....
public static int lonelyinteger(List<Integer> a) {
if(a.size()==1) {
return a.get(0);
}
Integer toReturn = null;
a.sort((j,k) -> j-k);
for(int i=0;i<a.size()-1;i++) {
System.out.println("test de "+ a.get(i));
if(i>0 && a.get(i) != a.get(i-1) && a.get(i) != a.get(i+1)) {
toReturn = a.get(i);
System.out.println("vu !!!" + toReturn);
break;
}
}
if(toReturn==null) {
toReturn=a.get(a.size()-1);
}
return toReturn;
}
}
Inverser un tableau
Assez simple, on parcourt le tableau dans un sens avec l'index i ET par soustraction avec la taille du tableau cela nous permet de le parcourir aussi dans l'autre sens. On inverse les 2 valeurs avec une variable temp.
package littleTests;
import java.util.Arrays;
class Solution {
public static void main(String[] args) {
int[] monTableau = {1,2,3,4,5,6,7};
System.out.println("Mon tableau est " + Arrays.toString(monTableau));
for(int i=0;i<monTableau.length/2;i++) { //depuis l'index 0, jusqu'à la moitiée du tableau (car sinon on réinverserait après la moitié !!)
int temp=monTableau[i];//on sauve pos0, puis pos1, puis pos2....
//(monTableau.length-1)-i sera egal à (8-1-0)=7, puis 6, puis 5....
monTableau[i] = monTableau[(monTableau.length-1)-i]; //pos0 prend la valeur de pos7, puis pos1=pos6...
monTableau[(monTableau.length-1)-i] = temp; //pos7 prend la valeur de pos0, puis pos6 la valeur de pos1...
System.out.println("Mon tableau devient " + Arrays.toString(monTableau));
}
}
}
/*
Mon tableau est [1, 2, 3, 4, 5, 6, 7]
Mon tableau devient [7, 2, 3, 4, 5, 6, 1]
Mon tableau devient [7, 6, 3, 4, 5, 2, 1]
Mon tableau devient [7, 6, 5, 4, 3, 2, 1]
*/
Flipping the matrix
Soluces : https://medium.com/@subhanusroy/flipping-the-matrix-hackerrank-optimised-solution-in-c-java-python-with-explanation-a3dad70149ee, https://www.youtube.com/watch?v=4rin1enhuQQ
Une question ""facile"" d'HackerRank (ils ont tort). John donne un tableau de 2n*2n. Le nombre n est variable, par exemple pour n=2 on aura un tableau de 2*2 * 2*2 donc 4*4.
a b c d
e f g h
i j k l
m n o p
On peut inverser les lignes ou les colonnes. Il faut trouver la valeur maximum qu'on puisse avoir dans la sous matrix n*n en haut `a gauche (autrement dit abef).
HackerRank nous donne 20min pour résoudre ça, autant dire que c'est impossible si on ne connait pas la soluce.
La soluce c'est qu'il faut prendre la plus grande valeur parmi admp, bcno, eihl, fgjk, car ce sont les seules permutations possibles vu qu'on inverse juste (on ne fait pas glisser !!). Donc la soluce sera par exemple aclj.
New Year Chaos
Imaginer une file de personnes avec un ticket. Chaque personne peut demander à la personne devant d'échanger sa place avec lui.
Dans cette liste [2,1,5,3,4], le 2 a sauté une place, le 5 a sauté deux places.
Compter le nombre de saut mais egalement afficher "Too chaotic" si le nombre de saut est supérieur à 2.
Ci-dessous soluce de https://www.youtube.com/watch?v=LgszjFykAbE
Elle consiste à prédire la prochaine place qu'on devrait trouver, en donnant 3 possibilités. 1,2,3 pour commencer.
Si on a eu 1 en position 0, aucun problème.
Mais si on a eu 2, alors on s'attend à trouver 1 à la prochaine position, ou bien 3 s'il y a eu un pot de vin, ou bien 4. Mais au delà serait révélateur d'un double pot de vin (pas sûr de comprendre pourquoi....).
Si on a eu 3, alors on s'attend à trouver 1 à la prochaine position, ou bien 2 s'il y a eu un pot de vin, ou bien 4. Mais au delà serait révélateur d'un double pot de vin (pas sûr de comprendre pourquoi....).
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
*/
public static void minimumBribes(List<Integer> q) {
int totalBribes=0;
int posPrevue=1; // le chiffre qu'on s'attend a trouver `a ce stade de parcours du tableau
// ce n'est pas forcement i ! Si i=0 mais qu'on vient juste
// de voir 2, on s'attendra a trouver 3 derriere
int prevSiDecalageDeUn=2; // le chiffre qu'on s'attend a trouver s'il y a eu un decalage de un
int prevSiDecalageDe2=3; //....un decalage de 2.
for(int i=0;i<q.size();i++) {
System.out.println("On teste la pos " + i + ", qui devrait etre " + posPrevue);
if (posPrevue==q.get(i)) {
System.out.println("Sa position semble coherente, on avance" + i);
System.out.println("posPrevue passe de " + posPrevue + "a " + prevSiDecalageDeUn);
posPrevue = prevSiDecalageDeUn;
System.out.println("prevSiDecalageDeUn passe de " + prevSiDecalageDeUn + "a " + prevSiDecalageDe2);
prevSiDecalageDeUn = prevSiDecalageDe2;
System.out.println("prevSiDecalageDe2 ++");
prevSiDecalageDe2++;
} else if (prevSiDecalageDeUn==q.get(i)) {
System.out.println("Ce n'est pas le cas, pot de vin detecte");
totalBribes++;
System.out.println("prevSiDecalageDeUn passe de " + prevSiDecalageDeUn + "a " + prevSiDecalageDe2);
prevSiDecalageDeUn = prevSiDecalageDe2;
System.out.println("prevSiDecalageDe2 ++");
prevSiDecalageDe2++;
} else if (prevSiDecalageDe2==q.get(i)) {
System.out.println("Ce n'est pas le cas, double pot de vin detecte");
totalBribes+=2;
System.out.println("prevSiDecalageDe2 ++");
prevSiDecalageDe2++;
} else{
System.out.println( "Too chaotic");
return;
}
}
System.out.println(totalBribes);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, t).forEach(tItr -> {
try {
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> q = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
Result.minimumBribes(q);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
}
}
Entrée:
1
5
2 1 5 3 4
Supprimer élement
2 entrées : un chiffre qu'on veut supprimer et un tableau. Mettre les valeurs désirées au debut du tableau. Par ex [3,2,2,3], 3 n'est pas désiré, le tableau devient [2,2,3,3]. Il faut aussi renvoyer le nombre d'éléments désirés.
Ma solution lente et verbeuse :
class Solution {
public int removeElement(int[] nums, int val) {
int maxLengthToCheck = nums.length-1;
for(int i=0;i<maxLengthToCheck;i++) {
System.out.println("Checking pos " + i + ", there is " + nums[i] + " here.");
if (nums[i] == val) { //le nombre courant est non-voulu
System.out.println("Moving " + nums[i] + "...");
int tmp;
// on inverse le nombre courant (non-voulu) avec le dernier du tableau
tmp=nums[i];
nums[i]=nums[maxLengthToCheck]; // attention ce dernier est peut etre non-voulu aussi, faudra verif
nums[maxLengthToCheck]=tmp;
// on sait que le dernier est non desire donc on s'arretera desormais a celui d'avant
maxLengthToCheck--;
//on reverif le nombre a la pos qu'on vient de verif, car le nombre de fin de tableau peut etre non-voulu lui aussi
i--;
}
}
System.out.println(Arrays.toString(nums));
//bon la c'est juste une petite boucle pour compter les nombres voulus
int numberOfWanted=0;
for(int i=0;i<nums.length;i++) {
if (nums[i] != val) {
numberOfWanted++;
}
}
System.out.println("numberOfWanted="+numberOfWanted);
return numberOfWanted;
}
}
Une solution courte, lui transforme le tableau [3,2,2,3] en [2,2,2,3]. Il fait un peu l'inverse en detectant le nombre voulu et remplaçant petit à petit le tableau :
class Solution {
public int removeElement(int[] nums, int val) {
int indexPourRemplacerTableau=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
System.out.println("il y a un nombre voulu a l'index " + i);
System.out.println("le tableau etait " + Arrays.toString(nums)); //3, 2, 2, 3
nums[indexPourRemplacerTableau]=nums[i];
System.out.println("le tableau devient " + Arrays.toString(nums)); //2, 2, 2, 3
indexPourRemplacerTableau++;
}
}
return indexPourRemplacerTableau;
}
}
Supprimer elements en doublon d'un tableau ordonné
Si on a [0,0,1,1,1,2,2,3,3,4] on veut [0,1,2,3,4 et peu importe le reste du tableau].
Même technique que précedemment : on a un index qui permet de remplacer le tableau petit à petit par les nombres voulus. Cette fois-ci le nombre non-voulu n'est pas fixe, c'est simplement le nombre précédent (vu aue le tableau est trié).
class Solution {
public int removeDuplicates(int[] nums) {
int compteurIndexNombresVoulus=1;
int dernierNombre=nums[0];
for(int i=1;i<nums.length;i++) {
System.out.println(Arrays.toString(nums));
System.out.println("on travaille sur " + nums[i]);
System.out.println("le dernier nombre était " + dernierNombre + ", actuellement on a " + nums[i] );
if (nums[i] != dernierNombre) {
System.out.println("on prend !");
nums[compteurIndexNombresVoulus] = nums[i];
compteurIndexNombresVoulus++;
} else {
System.out.println("on n'en veut pas.");
}
dernierNombre = nums[i];
}
//System.out.println(Arrays.toString(nums));
return compteurIndexNombresVoulus;
}
}
On peut faire plus court et sans variable "dernier nombre". Vu que le tableau est trié, conserver le premier nombre, vérifier pour chaque nombre que le nombre d'après est plus grand, et sauvegarder ce nombre ci, bien sûr on arrête la boucle à l'avant dernier nombre :
class Solution {
public int removeDuplicates(int[] nums) { //1,1,2
int compteurIndexNombresVoulus=1; //on laisse le premier nombre
for(int i=0;i<nums.length-1;i++) { //jusqu'a l'avant dernier
System.out.println(Arrays.toString(nums));
System.out.println("on travaille sur " + nums[i]);
System.out.println(nums[i] + " est il plus petit que " + nums[i+1]);
if(nums[i] < nums[i + 1]){
System.out.println("on prend !"); //1 est plus petit que 2
nums[compteurIndexNombresVoulus] = nums[i+1]; //on ajoute 2
compteurIndexNombresVoulus++;
}
}
System.out.println(Arrays.toString(nums));
return compteurIndexNombresVoulus;
}
}
169. Majority Element
Trouver l'élément qui apparaît plus que la majorité du temps.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Ca marche mais c'est lent car parcourt le tableau à chaque parcours de tableau (complexité O(n^2)):
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> freqHshMap = new HashMap<>(); //une map nombre, frequence
for (int i=0;i<nums.length;i++) { //pour chaque element
int count = 0;
for (int j=0;j<nums.length;j++) { // on compte l'integralite des elements identiques (O(n^2) dommage)
if (nums[j] == nums[i]) {
System.out.println(nums[i] + " vu");
count++; // incremente un compteur quand on en trouve
}
// System.out.println(nums[i] + " apparait " + count + " fois ");
freqHshMap.put(nums[i], count); //renseigne la hashmap
}
}
// System.out.print(freqHshMap);
return Collections.max(freqHshMap.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
On peut s'en sortir juste avec un tour :
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> freqHshMap = new HashMap<>(); //une map nombre, frequence
for (int i=0;i<nums.length;i++) { //pour chaque element
int value = freqHshMap.getOrDefault(nums[i], 0); //on va utiliser la valeur dans la hashmap si elle existe, zero sinon
freqHshMap.put(nums[i], value + 1); //a cette valeur on rajoute 1
}
System.out.println(freqHshMap);
return Collections.max(freqHshMap.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
Solution en 2 lignes, trier le tableau et renvoyer la moitié/2 du tableau :
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[(nums.length/2)];
}
}
121. Best Time to Buy and Sell Stock
Un tableau contenant les prix de chaque jour, trouver le meilleur profit qu'on puisse faire en achetant jour x et vendant jour y.
Une solution lente est de, pour chaque jour, comparer avec les jours suivants :
class Solution {
public int maxProfit(int[] prices) {
int bestDiff=0;
for(int i=0;i<prices.length;i++) { // pour chaque jour
for(int j=i+1;j<prices.length;j++) { // on compare avec les jours suivants
int diffOfThisIteration=prices[j]-prices[i];
//System.out.println("Diff achat a " + prices[i] + " et vente a " + prices[j] + "=" + diffOfThisIteration);
if(diffOfThisIteration>0 && diffOfThisIteration>bestDiff) {
bestDiff = diffOfThisIteration;
}
}
}
return bestDiff;
}
}
Une autre solution est de garder en valeur les positions du meilleur prix, du pire prix et de la diff :
class Solution {
public int maxProfit(int[] prices) {
int lowestPricePos=0; //La pos ou se trouve le meilleur prix
int highestPricePos=1; //La pos ou se trouve le pire prix
int bestProfit = 0; //Le meilleur profit
for(int i=0;i<prices.length-1;i++) {
System.out.println("Day " + i);
if (prices[i] < prices[lowestPricePos]) { //si le prix du jour est inferieur a celui qu'on a sauve
lowestPricePos = i; //ca devient le nouveau plus bas
System.out.println("New lowest price: " + prices[lowestPricePos]);
highestPricePos = lowestPricePos; // le plus haut prix on peut l'oublier vu qu'on s'interesse juste au futur
// on a deja le profit possible en memoire de toute facon donc on peut oublier
// le jour du plus haut prix
}
//System.out.println("Comparing " + prices[i+1] +" and "+ prices[highestPricePos]);
if (prices[i+1] >= prices[highestPricePos]) {
highestPricePos = i+1;
//System.out.println("New highest price: " + prices[highestPricePos]);
}
if (lowestPricePos<highestPricePos && (prices[highestPricePos] - prices[lowestPricePos])>bestProfit ) {
profit = prices[highestPricePos] - prices[lowestPricePos];
//System.out.println("Best profit, buy day" + lowestPricePos + ", sell day " + highestPricePos + ", earn "+ bestProfit );
}
}
return profit;
}
}
Mais en fait on n'a même pas besoin du meilleur prix. On peut juste fixer en mémoire le jour meilleur prix, le meilleur profit, puis essayer de calculer le profit jour par jour, tout en continuant de sauver le prix le plus bas quand on le rencontre :
class Solution {
public int maxProfit(int[] prices) {
int lowestPricePos=0; // le jour du prix le plus bas
int bestProfit = 0; // le meilleur profit
for(int i=0;i<prices.length;i++) {
System.out.println("Day " + i);
if (prices[i] < prices[lowestPricePos]) { // si le prix du jour est inferieur au prix le plus bas
lowestPricePos = i; // on sauve son numero
System.out.println("New lowest price: " + prices[lowestPricePos]);
}
int profitIfSellingLowestToday = prices[i] - prices[lowestPricePos];
if (profitIfSellingLowestToday>bestProfit) { // si vendre aujourd'hui, a partir du prix le plus bas, rapporte plus que le meilleur profit
bestProfit = profitIfSellingLowestToday;
System.out.println("Best profit, buy day" + lowestPricePos + ", sell day" + i + ", earn "+ bestProfit );
}
}
return bestProfit;
}
}
Détecter palindrome
Détecter si la string, une fois les caractères non-alpha numériques enlevés, est un palindrome.
Solution assez lente consistant à remplacer les caractères avec une regex puis inverser la chaîne avec un string builder :
class Solution {
public boolean isPalindrome(String s) {
String alphabetOnly = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
System.out.println("alphabetOnly=" + alphabetOnly);
return (new StringBuilder(alphabetOnly).reverse().toString()).equals(alphabetOnly);
}
}
Caractère par caractère, avec la vérif majuscule/char spécial via la classe Character :
class Solution {
public boolean isPalindrome(String s) {
char[] alphabetOnly = s.toCharArray();
int indexFin=alphabetOnly.length-1;
int indexDebut = 0;
while (indexDebut < indexFin) {
if(!Character.isLetterOrDigit(alphabetOnly[indexDebut])) {
indexDebut++;
}else if(!Character.isLetterOrDigit(alphabetOnly[indexFin])) {
indexFin--;
} else {
if (Character.toLowerCase(alphabetOnly[indexDebut]) != Character.toLowerCase(alphabetOnly[indexFin])) {
return false;
}
indexFin--;
indexDebut++;
}
}
return true;
}
}
392. Is Subsequence
Vérifier qu'une chaine apparait dans l'ordre dans une autre, peu importe s'il y a des charactères au milieu.
Example 1: Input: s = "abc", t = "ahbgdc"
Output: true
Example 2: Input: s = "axc", t = "ahbgdc"
Output: false
Pas compliqué on compare avec indexOf depuis la dernière position trouvée, en sauvegardant le résultat :
class Solution {
public boolean isSubsequence(String s, String t) {
char[] strToTest = s.toCharArray();
int lastPosFind=-1;
for(int i=0;i<strToTest.length;i++) {
System.out.println("Testing " + strToTest[i]);
int posFind = t.indexOf(strToTest[i], lastPosFind+1);
System.out.println("posFind " + posFind);
if (posFind==-1 || posFind<lastPosFind) {
return false;
}
lastPosFind = posFind;
}
return true;
}
}
Cette solution là est plus originale, elle parcourt la longue chaine tout en parcourant la petite uniquement lorsqu'une correspondance est trouvée :
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length() == 0) return true;
int j=0;
int i=0;
while(j<t.length()){
if(t.charAt(j)==s.charAt(i)){ //si les char sont egaux
i++; //on avance i
}
if(i==s.length()) return true; //si on est arrive a la fin de s c'est ok
j++; //sinon on avance j
}
return false;
}
}
383. Ransom Note
Renvoyer true si on peut écrire une chaîne de caractères (lettre anonyme) avec les lettres d'une autre (un magazine).
Rien de spécial j'ai fait comme si j'avais vraiment un magazine et y ai découpé des morceaux :
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
StringBuffer sb = new StringBuffer(magazine); // classe qui permet de découper des Strings
for(char theChar:ransomNote.toCharArray()) {
int charPositionInTheMagazine = sb.toString().indexOf(theChar); // récupère la pos dans le magazine découpé
if (charPositionInTheMagazine == -1) {
return false;
}
sb.deleteCharAt(charPositionInTheMagazine); // découpe
}
return true;
}
}
Plus intéressant, avoir un tableau et calculer la fréquence des lettres :
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] letterFrequenciesRansomNote = new int[26];
int[] letterFrequenciesMagazine = new int[26];
Arrays.fill(letterFrequenciesRansomNote, 0);
Arrays.fill(letterFrequenciesMagazine, 0);
//create an array with the frequency of letters in ransomNote
for(char theChar:ransomNote.toCharArray()) {
int posInAlphabet = ((int) theChar)-97;
letterFrequenciesRansomNote[posInAlphabet]++;
}
//create an array with the frequency of letters in magazine
for(char theChar:magazine.toCharArray()) {
int posInAlphabet = ((int) theChar)-97;
letterFrequenciesMagazine[posInAlphabet]++;
}
//check if the frequencies of each letter in the ransom note is more than it is in the mnagazine
for(int i=0;i<letterFrequenciesRansomNote.length;i++) {
if (letterFrequenciesRansomNote[i]>letterFrequenciesMagazine[i]) {
return false;
}
}
return true;
}
}
21. Merge Two Sorted Lists
On a deux linked lists: list1 = [1,2,4], list2 = [1,3,4]
On doit les fusionner: [1,1,2,3,4,4]
/**
* 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 {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head1 = list1;
ListNode head2 = list2;
ListNode startingNewNode = null; // creation du node qu'on va renvoyer
//utile egalement pour garer une ref vers le reste de la liste en memoire
ListNode newNode = null; // le node qu'on va alimenter pendant l'iteration
while (head1 != null || head2 != null) { //tant qu'un des deux nodes n'est pas nul
ListNode nodeToAdd; // pour avoir access au node a ajouter facilement
if(head1 == null) { // si le node1 est nul, on ajoute le 2e sans se poser de question
System.out.println("a we save head2 "+head2.val);
nodeToAdd = head2;
head2 = head2.next;
}
else if(head2 == null) { //pareil si le node2 est nul
System.out.println("b we save head1 "+head1.val);
nodeToAdd = head1;
head1 = head1.next;
} else if(head1.val <= head2.val) { //si la valeur du 1 est plus petite ou egal que la val du 2
System.out.println("c head1 "+head1);
System.out.println("c head1 next"+head1.next);
System.out.println("c we save head1 "+head1.val);
nodeToAdd = head1; //la valeur a mettre est celle du 1
head1 = head1.next; //et on passe au node suivant de la liste 1
} else { // on prend le 2 si la valeur du 2 est plus petite
System.out.println("d we save head2 "+head2.val);
nodeToAdd = head2;
head2 = head2.next;
}
//la partie la plus dure
if (startingNewNode == null) { // si on a pas encore defini le node de depart
newNode = new ListNode(nodeToAdd.val); // deja on assigne notre var node qui sera iteree
//attention il faut creer un nouvel objet et pas reutiliser un node existant dans une des 2 listes car le next sera different
startingNewNode = newNode; // et on defini ce premier node comme notre node de depart
} else { //si on a deja un node de depart
newNode.next = new ListNode(nodeToAdd.val); //on dit que le prochain node aura la valeur qu'on a choisi
newNode = newNode.next; //et on oublie la variable de depart -elle est tjrs referencee dans un des next : startingNewNode.next.next....
}
}
return startingNewNode;
}
}
Trouver le premier index d'une chaine dans une autre
Chaine abcdef {"botte de foin", haystack), trouver la position de bcd ("aiguille", needle) ou renvoyer -1 si ça n'existe pas.
Rien de compliqué, pour chaque lettre de la botte de foin on teste les X lettres suivantes (correspondant aux lettres de l'aiguille) :
public int strStr(String haystack, String needle) {
//return haystack.indexOf(needle); // bien sûr on pourrait juste faire ça mais bon
char[] haystackCA = haystack.toCharArray();
char[] needleCA = needle.toCharArray();
for(int i=0;i<haystackCA.length;i++) {
for(int j=0;j<needleCA.length;j++) {
if(i+needleCA.length>haystackCA.length) {
return -1;
}
System.out.print("Testing " + haystackCA[i+j] + "against " + needleCA[j]);
if (haystackCA[i+j] != needleCA[j]) {
System.out.println("nope...");
break;
}
System.out.println("Yes for now...");
if(j==needleCA.length-1) {
System.out.println("Found everything !");
return i;
}
}
}
return -1;
}
20. Valid Parentheses
Renvoyer true si les parenthèses/accolades/crochets sont corrects, càd "
{()}()" mais pas "([)]" ni "[}".
Ne marche pas pour ([)] :
class Solution {
public boolean isValid(String s) {
int parenthesisOpened = 0;
int bracketOpened = 0;
int braceOpened = 0;
for(char c:s.toCharArray()) {
if (c=='(') {
parenthesisOpened++;
}
if (c=='{') {
bracketOpened++;
}
if (c=='[') {
braceOpened++;
}
if (c==')') {
parenthesisOpened--;
}
if (c=='}') {
bracketOpened--;
}
if (c==']') {
braceOpened--;
}
}
return braceOpened==0 && bracketOpened==0 && parenthesisOpened==0;
}
}
Utilise une stack, une pile de caractères et vérifie que le dernier fermant correspond a un ouvrant en haut de la stack. Si oui, on sort l'ouvrant de la stack (pop) :
import java.util.EmptyStackException;
class Solution {
public boolean isValid(String s) {
Stack<Character> charStack = new Stack<>();
for(char c:s.toCharArray()) {
try {
if (c==')') { // parenthese fermante
if (charStack.peek() == '(') { //on verifie si le dernier char sauvegardé était une parenthese ouvrante
charStack.pop(); //oui, on le sort de la pile
} else{
return false; //non, c'est une erreur
}
} else if (c=='}') {
if (charStack.peek() == '{') {
charStack.pop();
} else{
return false;
}
} else if (c==']') {
if (charStack.peek() == '[') {
charStack.pop();
} else{
return false;
}
} else {
charStack.push(c); // si ce n'est pas une fermante, on sauve
}
} catch (EmptyStackException e) {
return false; //on a essayé de pop ou peek alors aue la stack était vide
}
}
return charStack.isEmpty();
}
}
13. Roman to Integer
Convertir chiffres romains en arabes, attention aux trois cas où on doit faire une soustraction :
-I devant V (5) ou X (10) fait 4 ou 9.
-X devant (50) ou C (100) fait 40 ou 90.
-C devant D (500) ou M (1000) fait 400 ou 900.
Soluce très bourrine, on couvre tous les cas à coup de if/switchs et on additionne, ça va relativement vite :
class Solution {
public int romanToInt(String s) {
char[] charArray = s.toCharArray();
int finalValue=0;
for(int i=0;i<charArray.length;i++) {
int currentValue = 0;
// testing the special cases
if(i+1<charArray.length) {
if(charArray[i] == 'I') {
if(charArray[i+1] == 'V') {
currentValue = 4;
}
if(charArray[i+1] == 'X') {
currentValue = 9;
}
}
if(charArray[i] == 'X') {
if(charArray[i+1] == 'L') {
currentValue = 40;
}
if(charArray[i+1] == 'C') {
currentValue = 90;
}
}
if(charArray[i] == 'C') {
if(charArray[i+1] == 'D') {
currentValue = 400;
}
if(charArray[i+1] == 'M') {
currentValue = 900;
}
}
}
// special values where triggered
if(currentValue>0) {
//System.out.println("" + charArray[i] + charArray[i+1] + " devient " + currentValue);
i++;
} else { // special values where NOT triggered
switch (charArray[i]) {
case 'I': currentValue=1; break;
case 'V': currentValue=5; break;
case 'X': currentValue=10; break;
case 'L': currentValue=50; break;
case 'C': currentValue=100; break;
case 'D': currentValue=500; break;
case 'M': currentValue=1000; break;
}
//System.out.println(charArray[i] + " devient " + currentValue);
}
finalValue += currentValue;
}
return finalValue;
}
}
205. Isomorphic Strings
Deux chaines de caractères sont dites isomorphiques si on peut remplacer les caractères de l'une (origine) par l'autre (destination) avec une table de correspondance. Exemple : ABCA
⇒ JTYJ (A devient J, B devient T....).
Assez simple, on parcourt lettre par lettre et sauve la lettre origine A dans une hashmap, avec destination J pour valeur. Si la lettre origine existe déjà dans la hashmap, on vérifie que c'est bien la lettre destination en cours qu'on avait sauvé (sinon pas bon). Il faut aussi penser à vérifier si la lettre de destination n'est pas déjà mappée par une autre lettre origine que celle en cours :
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> charMap = new HashMap();
char[] origin = s.toCharArray();
char[] dest = t.toCharArray();
for(int i=0;i<origin.length;i++) { // we loop on each letter from origin and destination
if (charMap.get(origin[i]) == null) { //the letter doesn't exists yet in the map
if (!charMap.containsValue(dest[i])) { // the destination letter is not already mapped by another origin letter
charMap.put(origin[i],dest[i]);
} else {
return false; // the destination letter is already mapped by another origin letter ! forbidden.
}
} else {
if(charMap.get(origin[i]) != dest[i]) {
return false; // the letter already exist as a key but the value is not the current letter
}
}
}
return true;
}
}
228. Summary Ranges
On a un tableau ordonné par exemple 1,2,3,5,6 il faut donner l'intervale des chiffres qui se suivent. 1->3 et 5->6. Autre exemple: 1,2,3,6,8,9 donnera 1->3, 6, 8->9.
Première tentative avec des règles dans tous les sens, ne marche pas sur [0,1,9] :
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<>();
if(nums.length==0) return result;
int biggestNumber = nums[nums.length-1];
int smallestNumber = nums[0];
int startingFrom = nums[0];
int lastStartingFromAdded = startingFrom-1;
int j = 0;
for(int i=smallestNumber;i<biggestNumber;i++) {
System.out.println(i);
if (nums[j] != i) {
System.out.println(nums[j] + "should be " + i);
System.out.println("range is " + startingFrom + " to " + nums[j-1]);
if (lastStartingFromAdded != nums[j-1]) {
if (startingFrom == nums[j-1]) {
System.out.println("Adding without ->");
result.add(startingFrom+"");
} else {
System.out.println("Adding with ->");
result.add(startingFrom + "->" + nums[j-1]);
}
lastStartingFromAdded = startingFrom;
System.out.println("lastStartingFromAdded is " + lastStartingFromAdded);
startingFrom = nums[j];
}
}
if (nums[j] == i) {
// all good, the number are following each others...
j++;
}
}
if(nums[j] == biggestNumber) { // if we are at the end of the array
System.out.println("End of the array... we add the last one.");
System.out.println("range is " + startingFrom + " to " + nums[j]);
if (startingFrom == nums[j]) {
System.out.println("Adding without ->");
result.add(startingFrom+"");
} else {
System.out.println("Adding with ->");
result.add(startingFrom + "->" + nums[j]);
}
}
return result;
}
}
Un peu simplifié, fonctionne :
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<>();
if(nums.length==0) return result; //cas limite : tableau vide
int startOfRange = nums[0]; //debut de l'intervalle
for(int i=0;i<nums.length;i++) { //on parcourt chaque element du tableau
System.out.println("nums[i]=" + nums[i]);
if(i>0 && nums[i]!=nums[i-1]+1) { //si on est sur la 2e case du tableau, on verifie qu'elle vaut bien la premiere+1
System.out.println("nums[i] est different de l'attendu qui devrait etre " + (nums[i-1]+1));
//on va noter du debut de l'intervalle jusqu'a la derniere valeur correcte...
if(startOfRange == nums[i-1]) { // si le debut de l'intervalle EST la derniere valeur correcte alors on l'affiche
System.out.println(startOfRange); //sans fleche ->
result.add(startOfRange + "");
} else { //sinon on affiche debut de l'intervalle -> derniere valeur correcte
System.out.println(startOfRange + "->" + nums[i-1]);
result.add(startOfRange + "->" + nums[i-1]);
}
startOfRange = nums[i];
System.out.println("startOfRange becomes " + startOfRange);
}
if(i == nums.length-1) { //cas special, on est arrive a la fin du tableau
System.out.println("This is the last number: " + nums[i]);
if(i==0 || nums[i]!=nums[i-1]+1) { //cas limite, i==0, tableau avec une seule valeur
System.out.println("nums[i] is different from expected");
System.out.println(startOfRange+"");
result.add(startOfRange+"");
} else {
System.out.println(startOfRange + "->" + nums[i]);
result.add(startOfRange + "->" + nums[i]);
}
}
}
return result;
}
}
58. Length of Last Word
Trouver la longueur du dernier mot dans une liste de mots séparés par des espaces :
class Solution {
public int lengthOfLastWord(String s) {
//split() supprime les espace à la fin sauf si on lui donne un 2e param negatif
String[] strings = s.split(' ');
return strings[strings.length-1].length;
}
}
14. Longest Common Prefix
Retourner le prefixe commun d'une liste de mot (chat, cheval ont pour prefixe commun ch).
class Solution {
//le plan est d'avancer lettre par lettre sur chaque mot et de tester
public String longestCommonPrefix(String[] strs) {
//deja on va choper le mot le plus court car c'est certain que le prefixe commun ne sera pas plus long
int sizeOfShortestWord = strs[0].length();
for(int i=1;i<strs.length;i++) {
if (strs[i].length() < sizeOfShortestWord) {
sizeOfShortestWord = strs[i].length();
}
}
String commonPrefix = "";
//cette boucle pour tester position de lettre par lettre
for(int i=0;i<sizeOfShortestWord;i++) {
String lastPrefix = strs[0].charAt(i)+"";
System.out.println("Pour le mot "+ strs[0] + " on trouve la lettre " + strs[0].charAt(i) + " a la position " + i);
for(int j=1;j<strs.length;j++) {
//cette boucle pour tester la lettre, mot par mot
System.out.println("Pour le mot "+ strs[0] + " on trouve la lettre " + strs[0].charAt(i) + " a la position " + i);
if (!lastPrefix.equals(strs[j].charAt(i)+"")) {
System.out.println("Mismatch!");
return commonPrefix;
}
}
commonPrefix += lastPrefix; //on ajoute la lettre car on sait qu'elle est commune à tous les mots
}
return "";
}
}
290. Word Pattern
On a un patterm aaba, il faut que des mots correspondent genre "chat chat chien chat" (chat correspondant au a et chien au b).
Première tentative nulle et verbeuse :
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] strings = s.split(" ");
String replacedString = pattern;
String lettersAlreadyReplaced="";
List<String> wordsAlreadyReplaced=new ArrayList();
if(strings.length != pattern.length()) { return false; } //the pattern and word don't match in size
for(int i=0;i<pattern.length();i++) {
System.out.println("Pour la lettre du pattern " + pattern.charAt(i) + ", on va mettre " + strings[i]);
if (!lettersAlreadyReplaced.contains(pattern.charAt(i)+"")) { //si c'est bien une lettre pas deja vue...
if (wordsAlreadyReplaced.contains(strings[i]+"")) {
System.out.println("Hmm ? C'est quoi cette histoire, on nous demande de remplacer un mot qu'on a deja remplace par une lettre");
return false;
}
replacedString = replacedString.replace(pattern.charAt(i)+"", strings[i]);
System.out.println("replacedString devient " + replacedString);
lettersAlreadyReplaced += pattern.charAt(i);
wordsAlreadyReplaced.add(strings[i]);
}else {
System.out.println("Mmm non on l'a déjà remplacée en fait.");
}
}
System.out.println("On s'attend à avoir " + replacedString);
//Ci dessous je recombine la chaine s preallablement decoupée (strings) mais bon je pourrais juste virer les espaces de la chaine s
//C'est juste pour le fun.
//Pour chaque chaine du tableau, en partant d'une chaine vide (initializer), on combine les chaines entre elles
//pas besoin d'accumulator car pas parallele ni type differents entre l'entrée et la sortie de la combinaison
String initializer = "";
String sWithoutSpaces = Arrays.stream(strings).reduce(initializer, (combinedStr, str2) -> combinedStr + str2);
System.out.println("On a " + sWithoutSpaces);
return replacedString.equals(sWithoutSpaces);
}
}
Ne marche pas pour "abc", "b c a" car je remplace la chaine au fur et à mesure :
Pour la lettre du pattern a, on va mettre b
replacedString devient bbc
Pour la lettre du pattern b, on va mettre c
replacedString devient ccc
Pour la lettre du pattern c, on va mettre a
replacedString devient aaa
On s'attend à avoir aaa
On a bca
Meilleur réponse, utiliser une hashmap :
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] strings = s.split(" ");
Map<Character, String> correspondingLetters = new HashMap();
if(strings.length != pattern.length()) { return false; } //the pattern and word don't match in size
for(int i=0;i<pattern.length();i++) {
System.out.println("La lettre du pattern " + pattern.charAt(i) + " sera traduite en " + strings[i]);
if (correspondingLetters.containsKey(pattern.charAt(i))) {
System.out.println("Euh finalement non on a deja traduit cette lettre");
continue;
}
if (correspondingLetters.containsValue(strings[i])) {
System.out.println("Hmmm non, car cette valeur correspond deja a quelque chose. Ya incoherence.");
return false;
}
correspondingLetters.put(pattern.charAt(i), strings[i]);
System.out.println(correspondingLetters);
}
System.out.println("Maintenant on teste la différence entre notre string traduit en langage pattern et le pattern.");
String translatedString = ""; //il faut construire la traduction
for(int i=0;i<pattern.length();i++) {
translatedString += correspondingLetters.get(pattern.charAt(i));
}
System.out.println("La string traduite est " + translatedString);
return translatedString.equals(s.replace(" ",""));
}
}
Il y a sûrement moyen d'optimiser en faisant la verif en même temps que la construction de la hashmap et pas juste à la fin.
3110. Score of a String
Pour chaque lettre d'une chaine convertie en codes ASCII, faire la différence avec la lettre précédente, mettre en absolu, faire le total.
Pour "hello" :
e
104-101
3
--------------
l
101-108
7
--------------
l
108-108
0
--------------
o
108-111
3
--------------
class Solution {
public int scoreOfString(String s) {
int score=0;
for(int i=1;i<s.length();i++) {
System.out.println(s.charAt(i));
System.out.println((int)s.charAt(i-1) + "-" + (int)s.charAt(i));
int calc = Math.abs((int)s.charAt(i-1) - (int)s.charAt(i));
System.out.println(calc);
score += calc;
System.out.println("--------------");
}
return score;
}
}
104. Maximum Depth of Binary Tree
Un arbre où chaque branche a maximum deux autres branches (la droite et la gauche). On parle de noeud, node.
Indiquer sa profondeur maximum. Par exemple a[b, c] (branche droite de a=b, branche gauche=c), b[e,f], c[](c n'a pas de branches),e[g]. a, b, e, g=profondeur de 4.
J'ai zieuté un algo vite fait puis je suis arrivé à de la récursion un peu par hasard en modifiant un while.
L'algo :
-on donne a la fonction exploreNode un node.
-s'il a un node droit, on rappelle la fonction exploreNode sur ce node droit et sauve la valeur de retour.
-s'il a un node gauche, on rappelle la fonction exploreNode sur ce node gauche et sauve la valeur de retour.
-on retourne (la plus grande valeur de retour entre droite et gauche)+1.
Donc les +1 s'accumulent, on retourne le plus grand accumulé et... bizarrement ça marche, un peu de mal à l'expliquer.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return exploreNode(root);
}
private int exploreNode(TreeNode node) {
System.out.println("(Explorons le node "+node.val + "");
TreeNode nodeToExplore = node;
int leftDepth = 0;
int rightDepth = 0;
if(nodeToExplore.right != null) {
System.out.println("On explore :" + nodeToExplore.right.val);
rightDepth = exploreNode(nodeToExplore.right);
}
if(nodeToExplore.left != null) {
System.out.println("On explore :" + nodeToExplore.left.val);
leftDepth = exploreNode(nodeToExplore.left);
}
int toReturn = ((rightDepth>leftDepth?rightDepth:leftDepth)+1);
System.out.println("rightDept : " + rightDepth);
System.out.println("leftDepth : " + leftDepth);
System.out.println("On renvoie " + toReturn + " suite a notre explo du node " + node.val + ")");
return toReturn;
}
}
Divers exercices de recursion
public static void main(String[] args) {
//System.out.println(sum(10));
//System.out.println(findmin(new int[]{33, 9, 1, 2},4));
//System.out.println(findsum(new int[]{10, 4, 2, 1},4));
System.out.println(ispalindrome(new int[]{9, 1, 2, 2, 1, 9},6));
int[] numbers = {5,1,8,4};
System.out.println(minimumInArray(numbers, numbers.length));
}
//Write a recursive function that computes the sum of all numbers from 1 to n, where n is given as parameter.
//return the sum 1+ 2+ 3+ ...+ n
private static int sum(int n) {
int sum=0;
if(n>0) sum=n+sum(n-1);
return sum;
}
// écrite d'instinct, si le nombre est 0 on le renvoie. Sinon on additionne avec la fonction-1.
public static int compute(int number) {
if (number == 0) return number;
return number + compute(number-1);
}
//Write a recursive function that finds and returns the minimum element in an array, where the array and its size are given as parameters.
//return the minimum element in a[]
//int findmin(int a[], int n)
private static int findmin(int a[], int n) {
int min = a[0];
if(n>1) min = findmin(a, n-1);
System.out.println("a[n]="+a[n-1]+", min=" + min);
if(a[n-1] < min) return a[n-1];
return min;
}
//egalement
private static int findmin2(int a[], int n) {
int minimum = a[0];
if (n==0) return minimum;
int previousMin = findmin(a,n-1);
return a[n-1]<previousMin?a[n-1]:previousMin;
}
// autre façon écrite d'instinct
// si le tableau est 5,1,8,4... 4 sera comparé avec minimumInArray
//(où 8 sera comparé avec minimumInArray (où 1 sera comparé avec minimumInArray
//(où 5 sera renvoyé car il est seul dans le tableau), donc 5 on renvoie 1 car plus petit que 5),
//donc 1 on renvoie 1 car plus petit que 8), donc 1 car plus petit que 4.
public static int minimumInArray(int[] numbers, int size) {
if (size == 1) return numbers[0];
if (numbers[size-1] > minimumInArray(numbers, size-1)) {
return minimumInArray(numbers, size-1);
} else {
return numbers[size-1];
}
}
//Write a recursive function that computes and returns the sum of all elements in an array, where the array and its size are given as parameters.
//return the sum of all elements in a[]
//int findsum(int a[], int n)
private static int findsum(int a[], int n) {
if (n==0) return 0;
return a[n-1] + findsum(a,n-1);
}
//Write a recursive function that determines whether an array is a palindrome, where the array and its size are given as parameters.
//returns 1 if a[] is a palindrome, 0 otherwise
//int ispalindrome(char a[], int n)
private static int ispalindrome(int a[], int n) { // je triche car j'utilise a.length.....
if(n==0 && a[0]==a[a.length-1]) return 1; //dernier niveau, on check si palindrome et retourne 0
if (a[n-1]==a[(a.length)-n]) return ispalindrome(a,n-1); //ici on continue le check seulement si ya eu egalité entre a[1] et a[4-3], entre a[1] et a[4-2] etc
return 0;
}
// sans tricher, en coupant les bords du tableau
private static int ispalindrome2(int a[], int n) {
if(n==0 || n==1) return 1; //si un seul element ou 0 element dans le tableau c'est un palindrome
if (a[0] == a[n-1]) { //si le debut du tableau vaut la fin du tableau
//on rogne le tableau des 2 cotés, en enlevant le premier et dernier élément
int[] newTab = new int[n-2];
int j=1;
for(int i=0;i<n-2;i++) {
newTab[i] = a[j++];
}
System.out.println("New tab =" + Arrays.toString(newTab));
return ispalindrome(newTab, n-2); //on interroge avec ce nouveau tableau
}
return 0;
}
//Write a recursive function that searches for a target in a sorted array using binay search, where the array, its size and the target are given as parameters.
}