Flashcards
Sem título
Flashcards do conjunto (2)
- 1The Dutch national flag Solution 1 (brute force):
o Create 3 new arrays: smaller, equal, greater
o Loop through each item and move to appropriate array
o Time complexity: O(n), space complexity: O(n)
Solution 2: (dumb)
Solution 3:
o 2 passes
o First pass: loop through and check if element is smaller than pivot then swap with the “wall”
o Second pass: similar but do with greater items
o Time complexity: O(n), space complexity: O(1)
Solution 4: (concise)
o Consider 4 sub arrays: smaller, equal, unclassified, greater
o Loop through all elements, if smaller then swap with smaller’s wall & increase smaller’s wall, if equal then increase equal’s wall, else if larger then swap with larger’s wall (inverse way) & decrease larger’s wall
o Time complexity: O(n), space complexity: O(1) - 2Increment an arbitrary-precision integer Solution 1 (brute force):
o Convert array to actual integer, increment, then convert back
o Cons: what if integer out of range
Solution 2:
o Increase from the last digit, if > 10 then get the least significant digit, and increment the previous digit
o If out of space of array, set first digit as 0, and add(0,1) so that all remaining digits follow
Informações
- Descrição
- FlashCards sobre Sem título, criado por Duc Tran em 22-05-2018.
- Criado por
- Duc Tran · mai 2018
- Atualizado
- 22 mai 2018
- Visualizações
- 0
- Avaliação