Skip to content

Arrays #105

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 13 commits into from
6 changes: 3 additions & 3 deletions 1-js/05-data-types/04-array/1-item-value/solution.md
Original file line number Diff line number Diff line change
@@ -1,8 +1,8 @@
The result is `4`:
O resultado é `4`:


```js run
let fruits = ["Apples", "Pear", "Orange"];
let fruits = ["Maçã", "Pera", "Laranja"];

let shoppingCart = fruits;

Expand All @@ -13,5 +13,5 @@ alert( fruits.length ); // 4
*/!*
```

That's because arrays are objects. So both `shoppingCart` and `fruits` are the references to the same array.
Isto, porque *arrays* são objetos. Assim ambas `shoppingCart` e `fruits` são referências para o mesmo *array*.

10 changes: 5 additions & 5 deletions 1-js/05-data-types/04-array/1-item-value/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,18 +2,18 @@ importance: 3

---

# Is array copied?
# Foi o *array* copiado?

What is this code going to show?
O que irá este código mostrar?

```js
let fruits = ["Apples", "Pear", "Orange"];
let fruits = ["Maçã", "Pera", "Laranja"];

// push a new value into the "copy"
// adicione um novo valor à "cópia"
let shoppingCart = fruits;
shoppingCart.push("Banana");

// what's in fruits?
// o que existe em fruits?
alert( fruits.length ); // ?
```

18 changes: 9 additions & 9 deletions 1-js/05-data-types/04-array/10-maximal-subarray/_js.view/test.js
Original file line number Diff line number Diff line change
@@ -1,37 +1,37 @@
describe("getMaxSubSum", function() {
it("maximal subsum of [1, 2, 3] equals 6", function() {
it("máxima subsoma de [1, 2, 3] igual a 6", function() {
assert.equal(getMaxSubSum([1, 2, 3]), 6);
});

it("maximal subsum of [-1, 2, 3, -9] equals 5", function() {
it("máxima subsoma de [-1, 2, 3, -9] igual a 5", function() {
assert.equal(getMaxSubSum([-1, 2, 3, -9]), 5);
});

it("maximal subsum of [-1, 2, 3, -9, 11] equals 11", function() {
it("máxima subsoma de [-1, 2, 3, -9, 11] igual a 11", function() {
assert.equal(getMaxSubSum([-1, 2, 3, -9, 11]), 11);
});

it("maximal subsum of [-2, -1, 1, 2] equals 3", function() {
it("máxima subsoma de [-2, -1, 1, 2] igual a 3", function() {
assert.equal(getMaxSubSum([-2, -1, 1, 2]), 3);
});

it("maximal subsum of [100, -9, 2, -3, 5] equals 100", function() {
it("máxima subsoma de [100, -9, 2, -3, 5] igual a 100", function() {
assert.equal(getMaxSubSum([100, -9, 2, -3, 5]), 100);
});

it("maximal subsum of [] equals 0", function() {
it("máxima subsoma de [] igual a 0", function() {
assert.equal(getMaxSubSum([]), 0);
});

it("maximal subsum of [-1] equals 0", function() {
it("máxima subsoma de [-1] igual a 0", function() {
assert.equal(getMaxSubSum([-1]), 0);
});

it("maximal subsum of [-1, -2] equals 0", function() {
it("máxima subsoma de [-1, -2] igual a 0", function() {
assert.equal(getMaxSubSum([-1, -2]), 0);
});

it("maximal subsum of [2, -8, 5, -1, 2, -3, 2] equals 6", function() {
it("máxima subsoma de [2, -8, 5, -1, 2, -3, 2] igual a 6", function() {
assert.equal(getMaxSubSum([2, -8, 5, -1, 2, -3, 2]), 6);
});
});
44 changes: 22 additions & 22 deletions 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
Original file line number Diff line number Diff line change
@@ -1,43 +1,43 @@
# Slow solution
# Solução lenta

We can calculate all possible subsums.
Nós podemos calcular todas as possíveis subsomas.

The simplest way is to take every element and calculate sums of all subarrays starting from it.
A forma mais simples será tomar cada elemento e calcular as somas de todos os *subarrays* que comecem por ele.

For instance, for `[-1, 2, 3, -9, 11]`:
Por exemplo, para `[-1, 2, 3, -9, 11]`:

```js no-beautify
// Starting from -1:
// Começando por -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Starting from 2:
// Começando por 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Starting from 3:
// Começando por 3:
3
3 + (-9)
3 + (-9) + 11

// Starting from -9
// Começando por -9
-9
-9 + 11

// Starting from 11
// Começando por 11
11
```

The code is actually a nested loop: the external loop over array elements, and the internal counts subsums starting with the current element.
Na verdade, o código é um laço aninhado (*nested loop*): o externo percorre os elementos do *array*, e o interno calcula as subsomas que começam pelo elemento corrente.

```js run
function getMaxSubSum(arr) {
let maxSum = 0; // if we take no elements, zero will be returned
let maxSum = 0; // se não tomarmos nenhum elemento, zero será retornado

for (let i = 0; i < arr.length; i++) {
let sumFixedStart = 0;
Expand All @@ -57,25 +57,25 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
```

The solution has a time complexity of [O(n<sup>2</sup>)](https://en.wikipedia.org/wiki/Big_O_notation). In other words, if we increase the array size 2 times, the algorithm will work 4 times longer.
A solução tem um tempo de complexidade de [O(n<sup>2</sup>)](https://pt.wikipedia.org/wiki/Grande-O). Por outras palavras, se aumentarmos o tamanho do *array* para o dobro, o algoritmo demorará 4 vezes mais.

For big arrays (1000, 10000 or more items) such algorithms can lead to serious sluggishness.
Para grandes *arrays* (1000, 10000 ou mais itens) tais algoritmos podem levar a sérias lentidões.

# Fast solution
# Solução rápida

Let's walk the array and keep the current partial sum of elements in the variable `s`. If `s` becomes negative at some point, then assign `s=0`. The maximum of all such `s` will be the answer.
Vamos percorrer o *array* e guardar a corrente soma partial dos elementos na variável `s`. Se, a certa altura, `s` se tornar negativo, então faça a atribuição `s=0`. O máximo de todos os `s` será a resposta.

If the description is too vague, please see the code, it's short enough:
Se a descrição for demasiado vaga, por favor veja o código, é realmente curto:

```js run demo
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;

for (let item of arr) { // for each item of arr
partialSum += item; // add it to partialSum
maxSum = Math.max(maxSum, partialSum); // remember the maximum
if (partialSum < 0) partialSum = 0; // zero if negative
for (let item of arr) { // por cada item de arr
partialSum += item; // adicione-o a partialSum ('s' na descrição)
maxSum = Math.max(maxSum, partialSum); // guarde o máximo
if (partialSum < 0) partialSum = 0; // zero se negativo
}

return maxSum;
Expand All @@ -89,6 +89,6 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0
```

The algorithm requires exactly 1 array pass, so the time complexity is O(n).
O algoritmo requere exatamente 1 passagem pelo *array*, portanto o tempo de complexidade é O(n).

You can find more detailed information about the algorithm here: [Maximum subarray problem](http://en.wikipedia.org/wiki/Maximum_subarray_problem). If it's still not obvious why that works, then please trace the algorithm on the examples above, see how it works, that's better than any words.
Pode encontrar informação mais detalhada sobre o algoritmo aqui: [Sublista contígua de soma máxima](https://pt.wikipedia.org/wiki/Sublista_cont%C3%ADgua_de_soma_m%C3%A1xima). Se, ainda não for óbvio porque isso funciona, então por favor rasteie o algoritmo nos exemplos acima e veja como trabalha, é melhor do que quaisquer palavras.
18 changes: 9 additions & 9 deletions 1-js/05-data-types/04-array/10-maximal-subarray/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,29 +2,29 @@ importance: 2

---

# A maximal subarray
# Um *subarray* máximo

The input is an array of numbers, e.g. `arr = [1, -2, 3, 4, -9, 6]`.
A entrada é um *array* de números, ex. `arr = [1, -2, 3, 4, -9, 6]`.

The task is: find the contiguous subarray of `arr` with the maximal sum of items.
A tarefa é: encontrar o contíguo *subarray* de `arr` com a máxima soma de itens.

Write the function `getMaxSubSum(arr)` that will return that sum.
Escreva a função `getMaxSubSum(arr)` que irá retornar essa soma.

For instance:
Por exemplo:

```js
getMaxSubSum([-1, *!*2, 3*/!*, -9]) == 5 (the sum of highlighted items)
getMaxSubSum([-1, *!*2, 3*/!*, -9]) == 5 (a soma dos itens em destaque)
getMaxSubSum([*!*2, -1, 2, 3*/!*, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, *!*11*/!*]) == 11
getMaxSubSum([-2, -1, *!*1, 2*/!*]) == 3
getMaxSubSum([*!*100*/!*, -9, 2, -3, 5]) == 100
getMaxSubSum([*!*1, 2, 3*/!*]) == 6 (take all)
getMaxSubSum([*!*1, 2, 3*/!*]) == 6 (tome todos)
```

If all items are negative, it means that we take none (the subarray is empty), so the sum is zero:
Se todos os itens forem negativos, significa que não tomamos nenhum (o *subarray* está vazio), então a soma é zero:

```js
getMaxSubSum([-1, -2, -3]) = 0
```

Please try to think of a fast solution: [O(n<sup>2</sup>)](https://en.wikipedia.org/wiki/Big_O_notation) or even O(n) if you can.
Por favor, tente pensar numa solução rápida: [O(n<sup>2</sup>)](https://pt.wikipedia.org/wiki/Grande-O), ou mesmo O(n) se puder.
2 changes: 1 addition & 1 deletion 1-js/05-data-types/04-array/2-create-array/solution.md
Original file line number Diff line number Diff line change
Expand Up @@ -3,7 +3,7 @@
```js run
let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
styles[Math.floor((styles.length - 1) / 2)] = "Clássicos";
alert( styles.shift() );
styles.unshift("Rap", "Reggae");
```
Expand Down
22 changes: 11 additions & 11 deletions 1-js/05-data-types/04-array/2-create-array/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,23 +2,23 @@ importance: 5

---

# Array operations.
# Operações com *arrays*.

Let's try 5 array operations.
Vamos tentar 5 operações com *arrays*.

1. Create an array `styles` with items "Jazz" and "Blues".
2. Append "Rock-n-Roll" to the end.
3. Replace the value in the middle with "Classics". Your code for finding the middle value should work for any arrays with odd length.
4. Strip off the first value of the array and show it.
5. Prepend `Rap` and `Reggae` to the array.
1. Crie um *array* `styles` com os itens "Jazz" e "Blues".
2. Adicione "Rock-n-Roll" ao fim.
3. Substitua o valor do meio por "Clássicos". O seu código, para encontrar o valor do meio, deverá funcionar para quaisquer *arrays* com um comprimento ímpar.
4. Elimine o primeiro valor do *array* e o mostre.
5. Adicione `Rap` e `Reggae` ao inicio do *array*.

The array in the process:
O *array* ao longo do processo:

```js no-beautify
Jazz, Blues
Jazz, Blues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll
Jazz, Clássicos, Rock-n-Roll
Clássicos, Rock-n-Roll
Rap, Reggae, Clássicos, Rock-n-Roll
```

6 changes: 3 additions & 3 deletions 1-js/05-data-types/04-array/3-call-array-this/solution.md
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
The call `arr[2]()` is syntactically the good old `obj[method]()`, in the role of `obj` we have `arr`, and in the role of `method` we have `2`.
A chamada `arr[2]()` é sintaticamente a antiga `obj[method]()`; no papel de `obj` temos `arr`, e no papel de `method` temos `2`.

So we have a call of the function `arr[2]` as an object method. Naturally, it receives `this` referencing the object `arr` and outputs the array:
Assim, temos uma chamada da função `arr[2]` como um método de objeto. Naturalmente, como ela recebe em `this` a referência ao objeto `arr`, ela exibe o *array*:

```js run
let arr = ["a", "b"];
Expand All @@ -12,4 +12,4 @@ arr.push(function() {
arr[2](); // a,b,function(){...}
```

The array has 3 values: initially it had two, plus the function.
O *array* tem 3 valores: inicialmente tinha dois, e a função foi adicionada.
4 changes: 2 additions & 2 deletions 1-js/05-data-types/04-array/3-call-array-this/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,9 +2,9 @@ importance: 5

---

# Calling in an array context
# Chamando uma função no contexto de um *array*

What is the result? Why?
Qual é o resultado? Porquê?

```js
let arr = ["a", "b"];
Expand Down
8 changes: 4 additions & 4 deletions 1-js/05-data-types/04-array/5-array-input-sum/solution.md
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
Please note the subtle, but important detail of the solution. We don't convert `value` to number instantly after `prompt`, because after `value = +value` we would not be able to tell an empty string (stop sign) from the zero (valid number). We do it later instead.
Por favor repare nos subtis, mas importantes detalhes da solução. Nós não convertemos `value` para número imediatamente após `prompt`, porque depois de `value = +value` não teríamos como ver a diferença entre uma *string* vazia (o sinal para parar) e zero (um número válido). Assim, nós o fazemos mais tarde.


```js run demo
Expand All @@ -8,9 +8,9 @@ function sumInput() {

while (true) {

let value = prompt("A number please?", 0);
let value = prompt("Um número, por favor?", 0);

// should we cancel?
// nós devemos cancelar?
if (value === "" || value === null || !isFinite(value)) break;

numbers.push(+value);
Expand All @@ -23,6 +23,6 @@ function sumInput() {
return sum;
}

alert( sumInput() );
alert( sumInput() );
```

12 changes: 6 additions & 6 deletions 1-js/05-data-types/04-array/5-array-input-sum/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,14 +2,14 @@ importance: 4

---

# Sum input numbers
# Some números entrados pelo usuário

Write the function `sumInput()` that:
Escreva a função `sumInput()` que:

- Asks the user for values using `prompt` and stores the values in the array.
- Finishes asking when the user enters a non-numeric value, an empty string, or presses "Cancel".
- Calculates and returns the sum of array items.
- Peça ao usuário por valores usando `prompt`, e os guarde num *array*.
- Não peça mais quando o utilizador fornecer um valor não-numérico, uma *string* vazia, ou pressione "*Cancel*".
- Calcule e retorne a soma dos itens no *array*.

P.S. A zero `0` is a valid number, please don't stop the input on zero.
P.S. Um zero `0` é um número válido, por favor não pare de pedir com zero.

[demo]
Loading