[Algorithm] Reverse array of Chars by word

For example we have:

["p", "r", "e", "f", "e", "t", " ", "m", "a", "k", "e", " ", "p", "r", "a", "t", "i", " c", "e"]

We want to get:

["p", "r", "a", "t", "i", " c", "e", " ", "m", "a", "k", "e", " ", "p", "r", "e", "f", "e", "t"]

Requirement:

　　You can only do in array swap, you cannot create a new array.

The way to do it:

　　1. Reverse whole string to get:

["e", " c", "i", "t", "a", "r", "p", " ", "e", "k", "a", "m", " ", "t", "e", "f", "e", "r", "p"]

　　2. Then we reverse each word to get final result:

["p", "r", "a", "t", "i", " c", "e", " ", "m", "a", "k", "e", " ", "p", "r", "e", "f", "e", "t"]

So the main function should looks like this:

let data = [

  "p","r","e","f","e","t"," ",

  "m","a","k","e"," ",

  "p","r","a","t","i","c","e"

];

function main(_data) {

  let data = _data.slice();

  reverseWholeString(data);

  reverseWords(data, );

  return data;

}

console.log(main(data));

The reverseWholeString function would be:

function reverseWholeString(data) {

  let start = ,

    end = data.length - ;

  reverseChars(data, start, end);

}

function reverseChars(data, start, end) {

  while (start < end) {

    [data[start], data[end]] = [data[end], data[start]];

    start++;

    end--;

  }

}

reverseWords function would be:

function reverseWords(data, start) {

  let index = findEmptyIndex(data, start);

  let end = index - ;

  while (index !== -) {

    reverseChars(data, start, end);

    start = index + ;

    index = findEmptyIndex(data, start);

    end = index - ;

  }

  reverseChars(data, start, data.length - );

}

function findEmptyIndex(data, start) {

  let index;

  for (let i = start; i < data.length; i++) {

    if (data[i] === " ") {

      index = i;

      break;

    } else {

      index = -;

    }

  }

  return index;

}

------------

Full code:

let data = [

  "p",

  "r",

  "e",

  "f",

  "e",

  "t",

  " ",

  "m",

  "a",

  "k",

  "e",

  " ",

  "p",

  "r",

  "a",

  "t",

  "i",

  " c",

  "e"

];

function reverseWholeString(data) {

  let start = 0,

    end = data.length - 1;

  reverseChars(data, start, end);

}

function reverseChars(data, start, end) {

  while (start < end) {

    [data[start], data[end]] = [data[end], data[start]];

    start++;

    end--;

  }

}

function findEmptyIndex(data, start) {

  let index;

  for (let i = start; i < data.length; i++) {

    if (data[i] === " ") {

      index = i;

      break;

    } else {

      index = -1;

    }

  }

  return index;

}

function reverseWords(data, start) {

  let index = findEmptyIndex(data, start);

  let end = index - 1;

  while (index !== -1) {

    reverseChars(data, start, end);

    start = index + 1;

    index = findEmptyIndex(data, start);

    end = index - 1;

  }

  reverseChars(data, start, data.length - 1);

}

function main(_data) {

  let data = _data.slice();

  reverseWholeString(data);

  reverseWords(data, 0);

  return data;

}

console.log(main(data));

巴特西

[Algorithm] Reverse array of Chars by word

最新文章

热门文章