发布日期: 2020-07-21

1、字符串反转 ‘123abc’ -> ‘cba321’

var str = "123abc";
// 字符串拆成数组方法：split('按照什么去拆')
// 数组倒置: reverse()
// 拼接成字符串:join('用什么拼');
console.log(str.split("").reverse().join("")); //cba321

for 笨方法

var str = "123abc456";
arr = str.split("");
// [1 2 3 a b c]
function strReverse(arr) {
  var arrn = [];
  for (var i = arr.length - 1; i > 0; i--) {
    arrn.push(arr[i]);
  }
  arrn.push(arr[0]); //最后一位补上
  return arrn;
}
console.log(strReverse(arr));

2、在有序的数组里找出指定的值，返回该值在数组中的索引，（二分查找）

方法一

// 有序 [1,2,3,4,5,5,5,6]不符合
如果不是有序，就不能使用二分查找
var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15];	//5=>2

function getIndex(arr, val) {
    //....
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] == val) {
            return i;
        }
    }
    return -1;//考虑到不存在的情况
}

变式
数组不是有序

var arr = [1, 3, 5, 7, 5, 9, 10, 11, 12, 14, 15];
//返回2,4怎么实现

var arr = [1, 3, 5, 7, 5, 9, 10, 11, 12, 14, 15];
var count = 0;
function find(n) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == n) {
      count++;
      return i;
    }
    // return count;
    return 123;
  }
}
console.log(find(5));
// console.log(count);
// 我想计数:几次，目前没有实现

方法二

function getIndex(arr, val) {
  return arr.findIndex(function (value) {
    //es6方法
    return value == val; //return后面的值为true，返回索引值。后面的值为false，返回-1
  });
}
// console.log(getIndex(arr, 5));//2

方法三

// 二分查找/折半查找  必须有序数组
/*
		[1, 3, 5, 7, 9, 10, 11, 12, 14, 15] 
		[1, 3, 5, 7, 9]
		[1, 3]
		[7, 9]
		效率高
*/
function getIndex(arr, val) {
  var start = 0;
  var end = arr.length - 1;
  /* for		//次数循环
			while	//条件循环 */
  while (start <= end) {
    //=:z最后三个了，一persInt()肯定相等	<：剩下两个数字
    var middle = parseInt((start + end) / 2);
    if (arr[middle] == val) {
      return middle;
    } else if (val < arr[middle]) {
      //这个条件成立说明要找的数据在中间数据的左边，要更新end的值
      end = middle - 1; //这里的更新值实际上是用middle的值替换了end
    } else if (val > arr[middle]) {
      //这个条件成立说明要找的数据在中间数据的右边，要更新start的值
      start = middle + 1;
    }
  }
  return -1;
}
console.log(getIndex(arr, 5)); //2

3.判断数组是否为对称数组，对称数组形式如：[a, b, c, b, a]、[a, b, c, c, b, a]

var arr1 = ["a", "b", "c", "d", "c", "b", "a"];
var arr2 = ["a", "b", "c", "c", "b", "a"];
var arr3 = ["a", "b", "c", "a", "b", "c"];

方法一

function symmetry(arr) {
  var newArr = [];
  for (var i = arr.length - 1; i >= 0; i--) {
    newArr.push(arr[i]);
  }
  // 颠倒后对比
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] != newArr[i]) {
      return false;
    }
  }

  return true;
}

方法二

function symmetry(arr) {
  var start = 0;
  var end = arr.length - 1;
  for (var i = 0; i < arr.length; i++) {
    //console.log(start,end);
    if (arr[start] != arr[end]) {
      return false;
    }
    start++;
    end--;
  }
  return true;
}

// 判断数组是否为对称数组，对称数组形式如：[a, b, c, b, a]、[a, b, c, c, b, a]
var arr = [1, 2, 3, 4, 1, 3, 2, 1];
function isBalance(arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == arr[arr.length - 1 - i]) {
      return true;
    } else {
      return false;
    } //这代码含义：只要有一个对上，就true了;我想要得是全循环完后都对上才行
  }
}
console.log(isBalance(arr));
// 1        2        3      3       2       1
// arr[0]  arr[1]  arr[2]  arr[3]  arr[4]  arr[5]
// arr.length = 6
// arr[0] == arr[length - 1]
// arr[1] == arr[length - 2]
// arr[2] == arr[length - 3]
// arr[i] == arr[length - i - 1]

function symmetry(arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] != arr[arr.length - 1 - i]) {
      return false;
    }
  }
  return true;
}
console.log(symmetry(arr));

优化

function symmetry(arr) {
  var start = 0;
  var end = arr.length - 1;

  for (var i = 0; i < arr.length; i++) {
    if (start >= end) {
      //减少了一半
      break;
    }
    if (arr[start] != arr[end]) {
      return false;
    }
    start++;
    end--;
  }
  return true;
}

继续优化

function symmetry(arr) {
  var start = 0;
  var end = arr.length - 1;

  while (start < end) {
    if (arr[start] != arr[end]) {
      return false;
    }
    start++;
    end--;
  }

  return true;
}

console.log(symmetry(arr1), symmetry(arr2), symmetry(arr3));

4.查询子串首次出现的位置，如：原串 abccbaxzabc 子串为 axz 结果为 5

方法一

var str = "abccbaxzabc";
var subStr = "axz";
console.log(str.indexOf(subStr)); //5  正则

方法二

function getIndex(str, sub) {
  for (var i = 0; i <= str.length - sub.length; i++) {
    //这个是原串的循环
    for (var j = 0; j < sub.length; j++) {
      //这个是子串的循环
      /* 
						子串的索引为j
						对应原串的索引为j+i
					 */
      //核心： 原串的索引=子串的索引+移动次数
      if (sub[j] != str[j + i]) {
        //这个条件是要对应的数据
        //这个条件成立说明子串与原串中对应的数据不匹配
        break;
      }

      //找到是有条件的，代码能走到这里说明已经匹配到了
      //能走到这里说明if没有发生
      if (j == sub.length - 1) {
        //这个条件成立说明子串里的所有数据在原串里都匹配到了
        return i;
      }
    }
  }

  return -1; //一个也没找到
}

学员创新揭发基础强数组-字符串
把 str 的 sub 长度截出来，拿字符串去对比

function getIndex(str, sub) {
  var start = 0;
  var end = str.length - sub.length;
  while (start <= end) {
    if (str.slice(start, sub.length + start) === sub) {
      //玩转JS方法
      return start;
    }
    start++;
  }
  return -1;
}
console.log(getIndex(str, subStr));

5.计算数组中，最大连续增长子序列的长度，如：[1,2,3,4,1,2,3,4,5,1,2,3] 结果为 5

单纯的思路

var arr = [1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 6, 7];
function getMaxLength(arr) {
  var addNum = 0; //每个序列增长的次数
  var len = 0; //增长最大序列的长度
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] > arr[i - 1]) {
      addNum++;
    } else {
      len = addNum > len ? addNum : len;
      addNum = 0;
    }
  }
  return len;
}
console.log(getMaxLength(arr)); //4,应该5

几个坑

if (arr[i] > arr[i - 1])，第一个 arr[0]>arr[-1]，arr[-1]=undefined，现在成了 0>undefined?—>false（不能比较）

谈到这里了，我们来说一下那些年见过的变态的比较题

console.log([] + {});
console.log(![] + 0 + !![] + {});
console.log(0 > false);
// undefined转数字==NaN

解决方案 1
问题无非就是 if 没走，addNum 没有加，让 addNum 变成 1 就好了 2.

var arr = [1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 6, 7, 90, 98, 99];
function getMaxLength(arr) {
  var addNum = 0; //每个序列增长的次数
  var len = 0; //增长最大序列的长度
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] > arr[i - 1]) {
      addNum++;
    } else {
      len = addNum > len ? addNum : len;
      addNum = 1;
    }
  }
  return len;
}
console.log(getMaxLength(arr)); //应该7

分析：如果 99 后面加上一个 0/10，就成 7 了，如果加 99 也不对了，因为没有对比最后一个。
序列在持续增长中，不知道是否已经断了
新方法：

var arr = [1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 6, 7, 90, 98, 99];
function getMaxLength(arr) {
  var addNum = 0; //每个序列增长的次数
  var len = 0; //增长最大序列的长度
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < arr[i + 1]) {
      //巧点：最后0>NaN==false，走else
      addNum++;
    } else {
      len = addNum > len ? addNum : len;
      addNum = 1;
    }
  }
  return len;
}
console.log(getMaxLength(arr));

老方法：不就是最后的 else 没有走吗，最后在加上 len = addNum > len ? addNum : len

var arr = [1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 6, 7, 90, 98, 99];
function getMaxLength(arr) {
  var addNum = 0; //每个序列增长的次数
  var len = 0; //增长最大序列的长度
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] > arr[i - 1]) {
      addNum++;
    } else {
      len = addNum > len ? addNum : len;
      addNum = 1;
    }
  }
  len = addNum > len ? addNum : len;
  return len;
}
console.log(getMaxLength(arr));

方法 3

for (var i = 0; i <= arr.length; i++)
  //与新方法套路一致 undefined

Sunny

http://example.com/2020/07/21/%E6%95%B0%E7%BB%84%E7%AE%97%E6%B3%95%E9%A2%98/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Sunny !

algorithm

前端必会算法

2020-07-23 Sunny

algorithm

2020-07-03 Sunny

Front end article

数组算法题

1、字符串反转 ‘123abc’ -> ‘cba321’

2、在有序的数组里找出指定的值，返回该值在数组中的索引，（二分查找）

3.判断数组是否为对称数组，对称数组形式如：[a, b, c, b, a]、[a, b, c, c, b, a]

4.查询子串首次出现的位置，如：原串 abccbaxzabc 子串为 axz 结果为 5

5.计算数组中，最大连续增长子序列的长度，如：[1,2,3,4,1,2,3,4,5,1,2,3] 结果为 5

你的赏识是我前进的动力