1.重构字符串

题目：

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

/**
 * @param {string} S
 * @return {string}
 */
var reorganizeString = function(S) {
     const len=S.length;
    if(len===0) return ""
    //用于存放字符及其数量
    let hashArr = new Array(26).fill(0);
    for(let i=0;i<S.length;i++){
        let item = hashArr[S[i].charCodeAt()-97];
        if(item){
            item.count++;
        }else{
            hashArr[S[i].charCodeAt()-97] = {name:S[i],count:1}
        }
    }
    hashArr = hashArr.filter((v)=>v!=0); //，过滤，把没出现的数字去掉，减少后面遍历次数
    hashArr.sort((a,b)=>(b.count-a.count)); //按count大小降序排列
    if(hashArr[0].count>Math.ceil(S.length/2)){
        //这里是无法构造的情况
        return ""
    }else{
        //这里是可以构造的
        let res=new Array(hashArr[0].count).fill(hashArr[0].name)
        // let cur = 1;//表示hashArr的索引
        let i = 1;
        //开始构造输出的数据，隔一个插入一个
        for(let cur=1;cur<hashArr.length;){
            res.splice(i,0,hashArr[cur].name);
            hashArr[cur].count--;
            if(hashArr[cur].count===0){
                cur++;
            }
            //隔一个插入
            i=i+2>res.length?1:i+2
        }
         return res.join('');
    }

};

2.最多能完成排序的块

题目：

数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

思路：和之前一题划分字母区间的很像。每个块排序之后连接，要和原数组相同，那么这个区块内的数字必须是连续的，所以记录当前的最大值和下标比较即可，相等时则可以划分为块

时间复杂度O(n)，空间复杂度O(1)

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
  const l = arr.length;
  let c = 0;
  let max = 0;
  for (let i = 0; i < l; i++) {
    max = Math.max(arr[i], max);
    if (max === i) {
      c++;
      max = 0;
    }
  }
  return c;
};

3.全局倒置与局部倒置

题目：

数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。

当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 true 。

思路：最开始的思路是动态规划。局部倒置一次遍历即可计算出数量，全局倒置，是遍历数组，然后将当前数字用插入排序的方式推入到之前的栈内，栈的数字降序排列，此时下标就是以该数字为i+1的全局倒置的数量

时间复杂度O(n2)，空间复杂度O(1)

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isIdealPermutation = function(A) {
  const l = A.length;
  const stack = [A[0]];
  let c = 0;
  let c1 = 0;
  for (let i = 1; i < l; i++) {
    if (A[i] < A[i - 1]) {
      c++;
    }
    const index = stack.findIndex((item) => item < A[i]);
    if (index < 0) {
      c1 += stack.length;
      stack.push(A[i]);
    } else {
      c1 += index;
      stack.splice(index, 0, A[i]);
    }
  }

  return c === c1;
};

仔细观察，局部倒置均为全局倒置，所以找一个非局部倒置的全局倒置即可，即list[i]与i相差大于1

时间复杂度O(n)，空间复杂度O(1)

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isIdealPermutation = function(A) {
  const l = A.length;

  for (let i = 0; i < l; i++) {
    if (Math.abs(A[i] - i) > 1) return false;
  }
  return true;
};

4.在LR字符串中交换相邻字符

题目：

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

思路：L字符可左移，R字符可右移，且移动前提是对应方向的字符是X。所以其实L、R的相对顺序是不能变的，相当于只能移动X字符。且开始字符串的L字符的下标一定要大于等于结束字符串L的下标。，R的下标则是小于等于

时间复杂度O(n)，空间复杂度O(1)

/**
 * @param {string} start
 * @param {string} end
 * @return {boolean}
 */
var canTransform = function(start, end) {
  const l = start.length;
  let i1 = 0,
    i2 = 0;
  while (i1 < l && i2 < l) {
    while (start[i1] === "X" && i1 < l) {
      i1++;
    }
    while (end[i2] === "X" && i2 < l) {
      i2++;
    }
    if (start[i1] !== end[i2]) return false;
    if (start[i1] === "L" && i1 < i2) return false;
    if (start[i1] === "R" && i1 > i2) return false;
    i1++;
    i2++;
  }
      while (start[i1] === "X" && i1 < l) {
      i1++;
    }
    while (end[i2] === "X" && i2 < l) {
      i2++;
    }
  if(i1<l||i2<l)return false
  return true;
};

5.第K个语法符号

题目：

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

思路：第K的字符，由上一行的第~~（（K+1）/2）得到，所以往上一行递归。上一行的元素是0，则k是偶数，结果是1，k是奇数，结果是0，反之上一行元素是1，那么k是偶数结果是0，k是奇数结果是1

时间复杂度O(N)，空间复杂度O(N)

/**
 * @param {number} N
 * @param {number} K
 * @return {number}
 */
var kthGrammar = function(N, K) {
  if (K===1) return 0;
  const pre = ~~((K + 1) / 2);
  const prev = kthGrammar(N - 1, pre);
  return prev === 0 ? 1 - (K % 2) : K % 2;
};