FrankKai.github.io icon indicating copy to clipboard operation
FrankKai.github.io copied to clipboard

Published 20 hours ago • verified publisher icon FrankKai

发现算法之美-暴力遍历

Open FrankKai opened this issue 4 years ago • 3 comments

暴力遍历是一个开发者们较容易想到的(开发速度快)、时间复杂度较高(耗性能)的算法，既有它的优点也有它的缺点。

这种解法常见于以下场景：

  1. 进度时间短、重业务逻辑处理的代码
  2. 性能要求低的代码（例如重渲染不重代码性能的前端、移动端）
  3. 算法和数据结构薄弱，对自身代码质量认识不足，不求更优解只求不出bug的代码，直到出现性能问题

在这篇文章中，我将列举一些我在写前端和刷leetcode的过程中遇到的暴力遍历场景。

  • 什么是暴力遍历？
    • 初识暴力遍历
    • 一个最简单的暴力遍历及算法图
  • 前端开发中的暴力遍历场景
    • 数组类：forEach、map、reduce
    • 对象类：Object.entries()和of
    • DOM类：querySelectorAll
    • Vue渲染同一个类型的节点：v-for
  • leetcode 暴力遍历 解法题目
    • 1.两数之和（easy）
    • 136.只出现一次的数字（easy）
    • 167.两数之和 II - 输入有序数组（easy）
    • 389.找不同（easy）
    • 1431.拥有最多糖果的孩子（easy）
    • 11.盛最多水的容器（medium）
    • 739.每日温度（medium）

FrankKai avatar Jun 02 '20 03:06 FrankKai

什么是暴力遍历？

  • 初识暴力遍历
  • 一个最简单的暴力遍历及算法图

初识暴力遍历

唯心主义有句话叫存在即合理，对于场景1和2，用暴力遍历的方式无可厚非，因为将复杂业务场景抽象成代码已经是一件非常烧脑和耗时的工作了，不仅要考虑自身技术栈的代码实现，还要考虑与服务端联调接口消耗的时间。

上面这种情况下，代码稳定不出bug，代码可读性和可维护性较好，已经属实不易了。

但是对于场景3算法和数据结构薄弱，对自身代码质量认识不足，不求更优解只求不出bug的代码，直到出现性能问题，这种情况属实要好好思考一下了。在大脑中储备了足够多的算法知识后，产出的代码性能或多或少要比只会暴力遍历的同学的代码更加优雅，面对棘手的性能问题也会更加从容。

逻辑直观清晰，开发效率高属于暴力解法的优点，时间和空间复杂度高属于它的缺点。实际开发中，需要根据实际情况去选择合适的实现。

一个最简单的暴力遍历及算法图

const arr = [9,8,1,4,2,5,6,7,3]
for(let i = 0; i<arr.length; i++ ){
    console.log(arr[i]); // 依次打印每一项
}
// 9 8 1 4 2 5 6 7 3

image

FrankKai avatar Jun 02 '20 03:06 FrankKai

前端开发中的暴力遍历场景

  • 数组类：forEach、map、reduce
  • 对象类：Object.entries(), of
  • DOM类：querySelectorAll
  • Vue渲染同一个类型的节点：v-for

数组类：forEach、map、reduce

const arr = [9,8,1,4,2,5,6,7,3]
for(let i = 0; i<arr.length; i++ ){
    console.log(arr[i]); // 依次打印每一项
}
// 9 8 1 4 2 5 6 7 3

用forEach替换for

// forEach
const arr = [9,8,1,4,2,5,6,7,3]
arr.forEach((num)=>{
    console.log(num); // 依次打印每一项
})
// 9 8 1 4 2 5 6 7 3

通常通过map返回一个新数据结构的数组：9 -> {num: 9, numPlus: 10}

// map
const arr = [9,8,1,4,2,5,6,7,3]
const arrMap = arr.map((num)=>{
    return {num, numPlus: num+1};
})
console.log(arrMap);
/*
0: {num: 9, numPlus: 10}
1: {num: 8, numPlus: 9}
2: {num: 1, numPlus: 2}
3: {num: 4, numPlus: 5}
4: {num: 2, numPlus: 3}
5: {num: 5, numPlus: 6}
6: {num: 6, numPlus: 7}
7: {num: 7, numPlus: 8}
8: {num: 3, numPlus: 4}
*/

通过reduce做一些累加计算：求和、替代filter()和map()等

// reduce：求和
const arr = [9,8,1,4,2,5,6,7,3]
const sum = arr.reduce((acc, cur)=>{
   return acc+cur;
}, 0)
console.log(sum);// 45

// reduce：替代filter()和map()
// 对大于等于5的数求和
const arr = [9,8,1,4,2,5,6,7,3]
const sum = arr.reduce((acc, cur)=>{
   if(cur>=5){
       return acc+cur;
   }
   return acc;
}, 0)
console.log(sum);// 35

对象类：Object.entries()和for...of

Object.entries和for...of通常用来遍历key，value类型的Object。 Object.entries返回一个item为[key, value]的数组。 for...of遍历可迭代数据。

// Object.entries返回一个item为[key, value]的数组
const obj = { foo: 'bar', baz: 42 };
Object.entries(obj).forEach(([key, value]) => console.log(`${key}: ${value}`)); // "foo: bar", "baz: 42"

// for...of遍历可迭代数据
const obj = { foo: 'bar', baz: 42 };
for( const [key, value] of Object.entries(obj) ){
    console.log(`${key}: ${value}`)); // "foo: bar", "baz: 42"
};

of也可以用于遍历数组，非常方便。

// 普通数组
for(let value of  [2,8,3]){
    console.log(value);
}
// CSSOM: 通过CSSOM获取@keyframe的规则
// https://codepen.io/impressivewebs/pen/MzybxL
let myRules = document.styleSheets[0].cssRules,
    p = document.querySelector('.output');

for (i of myRules) {
  if (i.type === 7) {
    for (j of i.cssRules) {
     p.innerHTML += `<c​ode>${j.keyText}</c​ode><br>`;
    }
  }
}

DOM类：querySelectorAll

this.tableCells通过forEach，for之类数组遍历方法去遍历

// 获取所有class以custom-alpha开头的table cell
this.tableCells = document.querySelectorAll('td[class^="custom-alpha"]');

this.tableCells通过forEach，for之类数组遍历方法去遍历

// 查出所有日期格子
const dateCells = document.querySelectorAll('td[class="date-cell"]');

Vue渲染同一个类型的节点：v-for

<ul id="example-2">
  <li v-for="(item, index) in items">
    {{ parentMessage }} - {{ index }} - {{ item.message }}
  </li>
</ul>
var example2 = new Vue({
  el: '#example-2',
  data: {
    parentMessage: 'Parent',
    items: [
      { message: 'Foo' },
      { message: 'Bar' }
    ]
  }
})
  • Parent-0-Foo
  • Parent-1-Bar

用of替换v-for中的in是一种更好的实践:你也可以用 of 替代 in 作为分隔符，因为它更接近 JavaScript 迭代器的语法。

<div v-for="item of items"></div>

更多关于js中in和of的信息，可以查看：js中的of和in那些事儿

FrankKai avatar Jun 02 '20 03:06 FrankKai

leetcode 暴力遍历 解法题目

几乎所有不用栈、双指针、二分、递归等解法的题目，直接for或者for for循环的解法，都是暴利解法。 通常来说，暴利遍历解法的时间复杂度为O(n^x)，x通常为1，2，在时间复杂度评估中处于糟糕。

  • 1.两数之和（easy）
  • 136.只出现一次的数字（easy）
  • 167.两数之和 II - 输入有序数组（easy）
  • 389.找不同（easy）
  • 1431.拥有最多糖果的孩子（easy）
  • 11.盛最多水的容器（medium）
  • 739.每日温度（medium）

1.两数之和（easy）

var twoSum = function(nums, target) {
  /**
   * 解法1：暴力迭代 580ms
   */
  var numsMaster = nums;
  var numsSlave = nums.map(e => e);
  var idxArr = [];
  numsMaster.forEach((nm, idxm, arrm) => {
    numsSlave.forEach((ns, idxs, arrs) => {
      if (nm + ns === target && idxm < idxs) {
        idxArr.push(idxm);
        idxArr.push(idxs);
      }
    });
  });
  return idxArr;
}

136.只出现一次的数字（easy）

var singleNumber = function (nums) {
  /** 解法1：暴力遍历
   *  性能：704ms 40.5MB
   */
  let numsSet = Array.from(new Set(nums));
  let numsMap = numsSet.map((num) => ({
    num,
    count: 0,
  }));
  nums.forEach((num, i) => {
    numsMap.forEach((numM, j) => {
      if (numM.num === num) {
        numM.count++;
      }
    });
  });
  let filterArr = numsMap.filter((num) => num.count === 1);
  return filterArr[0].num;
}

167.两数之和 II - 输入有序数组（easy）

var twoSum = function (numbers, target) {
  /**
   * 解法1：暴力遍历
   * 性能：416ms 34.9 MB
   */
  var i = 0;
  for (; i < numbers.length; i++) {
    var j = 1;
    for (; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target && i !== j) {
        return [i + 1, j + 1];
      }
    }
  }
}

389.找不同（easy）

var findTheDifference = function (s, t) {
  /**
   * 解法1：暴力删除法
   * 性能：148ms 35.2MB
   */
  let sArr = s.split("");
  let tArr = t.split("");
  for (let i = 0; i < sArr.length; i++) {
    for (let j = 0; j < tArr.length; j++) {
      if (tArr[j] === sArr[i]) {
        tArr[j] = null;
        break;
      }
    }
  }
  return tArr.find((item) => item);
};

1431.拥有最多糖果的孩子（easy）

var kidsWithCandies = function (candies, extraCandies) {
  /**
   * 解法1：暴力遍历-forEach
   * extraCandies与candie[i]求和之后，若sum >= max(candies, sum)为true
   */
  let results = [];
  candies.forEach((candy, _index, arr) => {
    const sum = candy + extraCandies;
    const result = sum >= Math.max.apply(null, arr);
    results.push(result);
  });
  return results;
  /**
   * 解法1: 暴力遍历-reduce
   */
  return candies.reduce((acc, cur) => {
    acc.push(cur + extraCandies >= Math.max.apply(null, candies));
    return acc;
  }, []);
};

11.盛最多水的容器（medium）

var maxArea = function (height) {
  /**
   * 解法2：快慢指针法（暴力遍历法）
   * 性能：788ms 35.7MB
   */
  var maxCapacity = 0;
  for (var slow = 0; slow < height.length; slow++) {
    for (var fast = slow + 1; fast < height.length; fast++) {
      maxCapacity = Math.max(
        Math.min(height[slow], height[fast]) * (fast - slow),
        maxCapacity
      );
    }
  }
  return maxCapacity;
};

739.每日温度（medium）

var dailyTemperatures = function(T) {
  if (T.length < 1 || T.length > 30000) return false;
  /**
   * 解法1：暴力检索法 2284ms 9.48% 48.1MB 15.69%
   *  */
  var result = [];
  var copyT = Array.from(T);
  var helperIdx = 0;
  for (var i = 0; i < T.length; i++) {
    for (var j = helperIdx || 0; j < copyT.length; j++) {
      if (copyT[j] > T[i]) {
        result.push(j - i);
        helperIdx++;
        break;
      }
      if (j === copyT.length - 1) {
        result.push(0);
        helperIdx++;
      }
    }
  }
  return result;
}

题目可查看：https://leetcode-cn.com/problemset/all/ 题解可查看：https://github.com/FrankKai/leetcode-js

FrankKai avatar Jun 02 '20 03:06 FrankKai