Aller au contenu

Longueur maximale d'un intervalle équilibré⚓︎

On considère une liste bits constituée uniquement de 0 et 1. Écrire une fonction telle que l_max_equilibree(bits) renvoie la longueur maximale d'une tranche qui contient autant de 0 que de 1.

Exemples

🐍 Console Python
>>> bits = [0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
>>> l_max_equilibree(bits)
6
En effet, la tranche [1, 0, 0, 0, 1, 1] est équilibrée et de longueur maximale.

🐍 Console Python
>>> bits = [1, 1, 1, 1]
>>> l_max_equilibree(bits)
0
En effet, la tranche [] est équilibrée et de longueur maximale.

🐍 Console Python
>>> bits = [1, 0, 1, 0, 1]
>>> l_max_equilibree(bits)
4
En effet, la tranche [1, 0, 1, 0] est équilibrée et de longueur maximale. Il y a également [0, 1, 0, 1] équilibrée et aussi de longueur maximale.

⚠ On attend un algorithme qui fait une simple boucle. Il faudra sauvegarder une information utile à chaque tour de boucle.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0lyq n7apS.r1-me,(P2=4:+twki9][5hx)6050j0E0N0w0Q0q0b0t0i0q0w0b0b0J010N0Q0x010406050b0k0D0D0w0A0r040y0d0q0k0?0d0u050o0}0 11130{0x041c1j051m0o1m1o1j0{0j0Q0m0+0-0/0;0V0Q0n0V0q1C0V0N0_050$0h0q0E1x0.0:011B1D1F1D0N1L1N1J0N0h0d0j131K0A1k0N0V0+160b0x0w0u0;0I011P1z010l0(0E0u0w0D0E1J1;1?1{1R1~1N21230_0a0t0H0A0d0x0d0b0Q190u0t0!1/0A0A0E0i2o1c260u1k0o1-2B0N1+1*1,0j280;1F0u202l1J1u1w0,1Q2L0Q2N0u1%1v1J0x2u1k2z2B2)0|1=2p2T1|2Y0A100q0_0t0B2y2-0`2,272/1R2;2?2^0I2{1?2}2z2K01320w2@040t0c362A0{39300;3c3e0t0K3i382-3a3o2^0U3s3k3u3m3b0d2=3d2^0Y3z2~2.1y313E333f0v3J3l3M3n3O3G3f0f3S3B3U3D3F3p0R3!2 3$3w040B0p3+3L2U3%3P0B2`1d2|3A3,3@3.0B353|373~3?2:3W3e0B3h443j3K3v490_0B3r4d3t3 483(4i3y4l464g4p3/3I4s4f3C413R4y3T404h3/3Z4D3#4F4v0B3*4J4n3N4v0I3;4P474R3P0I3{2+1p2%1c2R2E0j2I3a0i1%241k4)1n4%4#2+4.0!2(4K1|0P0_0!0l3s4z3$0O2^534E2:0l0_0q0e100W0e0E0s0k0(0Q0h2u0E584}1R0^040G5q4Q3n0_0h2n0b5w4W0;5t0X0L3z0t5K0t54400_0Q0e1$0u0k0b0e4!2|5M591R0d0_0J3s5Z5r5F0_0T5D3a0D0Q0_4U2+5!5,040S5J5L5N2:5P5R1a5U0e5@5Y5 5#5%5)685`5.4l6c015;5?5/3C5t5|4s5L5*5x3b5c5e0w0W6b5_015$045(4l6q5E6h5=0466456p6g0u500E0q0$6x5+6z6a6D6g6i6I5}5K6g4 040l3E6S6r6N040Q6k3$5t0F6+6F6-6w6W6y0d566.1b6{6T0u0h0_200~0E0A0w0N5p6f6y5t5v7d725z5B6:3@5G5I6o6p5~6y6%0Q52716,0_6`2)6E3a6A0J6C7A6X6H5X376g5t7o2)067q7Q7B4A6O6Q0w6@7C0_0M7F676y6Y7J3j7R7S3$6%6P0b7c5^6T7M6!7+7,5O040!7V7X3C6A0C7#377`1|7(7^6L7s5P7v7G6y6-7}6R7w6F6A020n0N0g7 3-74042b7l1|7f8u31615S647)4|6r5G8p3@818G867I8x5`7N3}7_7r7i6.625T5V8C6g6A0z8M6s040w0x0x200j8#8w7h7x6.8-0_0X888R6r7.1F8c7$6T8I8/6^7U8h8d8 0_8l8n8J318r8t913a8.7=8:5Q8A5V6J2A7L8?9a0;90956r879e6l0_8O6K8Q858y8T9k658#8Z8#6-8(8*0u8,9w6;0_7g9h928;9P7m9p7p7Q6$758|9q8$8g7W8i7Y04980g832A9C0;6Y9m8D6F7@9Z7_9#6.8}846M5P9(9s8~9i8U8B8=046e9T3v939+ae9x5{a5978m8o9,7T8s6u7z2|9o049z7*9B898S5d5fal6B9(6-6/ap3$a6a28e8z638WabadauaN7|6P94aT7?0_6n7O7+9 7/7;aY8E9y9(0i0B0_032qaW0w0t026Q9:0t0pax0`az9 7uaGa4aJ8H0_0Cb49EaP9G9W8v5-9Hb89Jagaba#a78jam99b660araDbe5sa-9}b1aUaC6vaE9;3fa39V9tbo04b9br9D9jbc9_avaS7K6|bibv5yaV7~bW016m7^9 2u0N0k0A70bIafbtbC4y0o4`0E2B2$b^4(1v4*2E2G2C1$1(2E0w1Mb{0o4)0{c80#0%0)04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0lyq n7apS.r1-me,(P2=4:+twki9][5hx)6050j0E0N0w0Q0q0b0t0i0q0w0b0b0J010N0Q0x010406050b0k0D0D0w0A0r040y0d0q0k0?0d0u050o0}0 11130{0x041c1j051m0o1m1o1j0{0j0Q0m0+0-0/0;0V0Q0n0V0q1C0V0N0_050$0h0q0E1x0.0:011B1D1F1D0N1L1N1J0N0h0d0j131K0A1k0N0V0+160b0x0w0u0;0I011P1z010l0(0E0u0w0D0E1J1;1?1{1R1~1N21230_0a0t0H0A0d0x0d0b0Q190u0t0!1/0A0A0E0i2o1c260u1k0o1-2B0N1+1*1,0j280;1F0u202l1J1u1w0,1Q2L0Q2N0u1%1v1J0x2u1k2z2B2)0|1=2p2T1|2Y0A100q0_0t0B2y2-0`2,272/1R2;2?2^0I2{1?2}2z2K01320w2@040t0c362A0{39300;3c3e0t0K3i382-3a3o2^0U3s3k3u3m3b0d2=3d2^0Y3z2~2.1y313E333f0v3J3l3M3n3O3G3f0f3S3B3U3D3F3p0R3!2 3$3w040B0p3+3L2U3%3P0B2`1d2|3A3,3@3.0B353|373~3?2:3W3e0B3h443j3K3v490_0B3r4d3t3 483(4i3y4l464g4p3/3I4s4f3C413R4y3T404h3/3Z4D3#4F4v0B3*4J4n3N4v0I3;4P474R3P0I3{2+1p2%1c2R2E0j2I3a0i1%241k4)1n4%4#2+4.0!2(4K1|0P0_0!0l3s4z3$0O2^534E2:0l0_0q0e100W0e0E0s0k0(0Q0h2u0E584}1R0^040G5q4Q3n0_0h2n0b5w4W0;5t0X0L3z0t5K0t54400_0Q0e1$0u0k0b0e4!2|5M591R0d0_0J3s5Z5r5F0_0T5D3a0D0Q0_4U2+5!5,040S5J5L5N2:5P5R1a5U0e5@5Y5 5#5%5)685`5.4l6c015;5?5/3C5t5|4s5L5*5x3b5c5e0w0W6b5_015$045(4l6q5E6h5=0466456p6g0u500E0q0$6x5+6z6a6D6g6i6I5}5K6g4 040l3E6S6r6N040Q6k3$5t0F6+6F6-6w6W6y0d566.1b6{6T0u0h0_200~0E0A0w0N5p6f6y5t5v7d725z5B6:3@5G5I6o6p5~6y6%0Q52716,0_6`2)6E3a6A0J6C7A6X6H5X376g5t7o2)067q7Q7B4A6O6Q0w6@7C0_0M7F676y6Y7J3j7R7S3$6%6P0b7c5^6T7M6!7+7,5O040!7V7X3C6A0C7#377`1|7(7^6L7s5P7v7G6y6-7}6R7w6F6A020n0N0g7 3-74042b7l1|7f8u31615S647)4|6r5G8p3@818G867I8x5`7N3}7_7r7i6.625T5V8C6g6A0z8M6s040w0x0x200j8#8w7h7x6.8-0_0X888R6r7.1F8c7$6T8I8/6^7U8h8d8 0_8l8n8J318r8t913a8.7=8:5Q8A5V6J2A7L8?9a0;90956r879e6l0_8O6K8Q858y8T9k658#8Z8#6-8(8*0u8,9w6;0_7g9h928;9P7m9p7p7Q6$758|9q8$8g7W8i7Y04980g832A9C0;6Y9m8D6F7@9Z7_9#6.8}846M5P9(9s8~9i8U8B8=046e9T3v939+ae9x5{a5978m8o9,7T8s6u7z2|9o049z7*9B898S5d5fal6B9(6-6/ap3$a6a28e8z638WabadauaN7|6P94aT7?0_6n7O7+9 7/7;aY8E9y9(0i0B0_032qaW0w0t026Q9:0t0pax0`az9 7uaGa4aJ8H0_0Cb49EaP9G9W8v5-9Hb89Jagaba#a78jam99b660araDbe5sa-9}b1aUaC6vaE9;3fa39V9tbo04b9br9D9jbc9_avaS7K6|bibv5yaV7~bW016m7^9 2u0N0k0A70bIafbtbC4y0o4`0E2B2$b^4(1v4*2E2G2C1$1(2E0w1Mb{0o4)0{c80#0%0)04.

Indice 1

On pourra calculer pour chaque indice la différence delta entre le nombre de 1 et le nombre de 0 depuis le début de la liste.

Lorsqu'on rencontre à nouveau une même valeur de delta, on déduit une tranche équilibrée.

Indice 2

On va alors stocker le premier indice où l'on rencontre delta. On pourra noter i_bonus_1[k] le premier indice où delta est égal à +k, et i_bonus_0[k] le premier indice où delta est égal à -k.

On pourra utiliser un dictionnaire i_bonus, ou deux listes i_bonus_1 et i_bonus_0.