跳到主要内容

高频算法

1、从一个长度10万的数组中，随机取出100条数据（取出的数据不能重复）;​

  • 原理：随机获取100个索引，每一次获取的时候，都把对应的项获取，为了避免数组中的项重复，每获取一个数把原有数组中的这一项删除；
  • 为了方便演示从20个里取5个随机数；

为了方便掩饰从20个里取5个随机数；

  • 第一种比较耗性能的写法；
js
    var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
    function selectOption(ary,optionNumber){
        var targetAry=[];
        if(!optionNumber){
            console.log("请指定需要删选的数量!");
        }
        for(var i=0;i<optionNumber;i++){
            var ran=Math.round(Math.random()*(ary.length));//获取0-数组最大索引的一个随机数；
            targetAry.push(ary[ran]);//按照获取的随机索引，把对应的值取出来，放到新书组中；
            ary.splice(ran,1);//数组中实现删除的时候比较耗性能，为了牵扯到数组长度的改变，数组被删除的项，后面所有数据都前进一位；
        }
        return targetAry;
    }
    var newAry=selectOption(ary,2);
    console.log(newAry);

确定在代码后面已经说明，这种的比较耗性能；

js
    var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
    function selectOption(ary,optionNumber){
        var targetAry=[];
        if(!optionNumber){
            console.log("请指定需要删选的数量!");
        }
        for(var i=0;i<optionNumber;i++){
            var ran=Math.round(Math.random()*(ary.length));//获取0-数组最大索引的一个随机数；
            targetAry.push(ary[ran]);//按照获取的随机索引，把对应的值取出来，放到新数组中；
            ary[ran]=ary[ary.length-1];//把数组最后一项放到当前要删除索引的这一项；
            ary.length=ary.length-1;//删除最后一项；
        }
        return targetAry;
    }
    var newAry=selectOption(ary,10);
    console.log(newAry);

这种的写法，是操作数组的常用处理方式；借助数组length可修改的性能；

2、找出数组重复次数最多的元素​

思路：

用对象来处理，将元素赋值到属性上，判断之前有没有这个属性。

js
const highestFrequency = function(ipLines) {
  var [obj, max, name] = [{}, 1, ''];
  ipLines.forEach(value => {
    if (obj[value]) {
      // 已经有值了 就把值+1
      obj[value]++;
      if (obj[value] > max) { // 判断重复次数有没有超过当前最高的
        max = obj[value]; // 重复次数
        name = value; // 当前元素
      }
    } else {
      // 没有值 就初始化一个值
      obj[value] = 1;
    }
  });
  return name;
};

3、姓名去重​

js
[
  'James',
  'james',
  'Bill Gates',
  'bill Gates',
  'Hello World',
  'HELLO WORLD',
  'Helloworld'
];

返回

js
['james', 'bill gates', 'hello world', 'helloworld'];

思路：

  • 去重和转小写

相关api

  • toLowerCase()：字符串值转为小写
  • toUpperCase：字符串转换为大写
js
const nameDeduplication = names => {
  names.forEach((value, index) => {
    names[index] = value.toLowerCase(); // 全部转小写
  });
  return [...new Set(names)]; // 去重
};

4、第一个只出现一次的字符​

方式一：【推荐】

  • 只需要判断第一次出现的位置和最后的位置是否相等
js
 var firstUniqChar = function (s) {
     for (let x of s) {
         if (s.indexOf(x) === s.lastIndexOf(x)) return x
     }
              return ' '
  }

方式二：

js
var firstUniqChar = function (str) {
                // 使用 map 缓存值
                const map = new Map()
                // 临时字符
                let tempChar
                // 临时 map 中的值
                let tempMapItem
                for (let i = 0; i < str.length; i++) {
                    tempChar = str[i]
                    tempMapItem = map.get(tempChar)
                    if (tempMapItem) {
                        // 如果 map 中有值值 +1
                        map.set(tempChar, tempMapItem + 1)
                    } else {
                        // 如果 map 中没值，加入
                        map.set(tempChar, 1)
                    }
                }
                // 遍历 map 找出第一个值为 1 的 key，即是想要找的字符
                for (let [k, v] of map) {
                    if (v === 1) {
                        return k
                    }
                }
                return ' '
            }

5、返回整数逆序后的字符串​

用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。

  • 获取整数的最后一位 : num % 10
    • 利用%取余技巧
    • 获取最后一位%10， 获取最后2位%100，以此类推
  • 去除整数最后一位：num / 10
    • 利用除以10技巧，然后向下取整 Math.floor
js
function fun(num){
    let num1 = num / 10;
    let num2 = num % 10;
    if(num1<1){
        return num;
    }else{
        num1 = Math.floor(num1)
        return `${num2}${fun(num1)}`
    }
}
var a = fun(12345)
console.log(a)
console.log(typeof a)

5、反转字符串​

js
//给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变
//字串：Chinese
const str = "this is trussan's Chinese site: https://www.trussan.com/cn"
const child = 'Chinese'
const arr = str.split('').reverse()
const reverseChild = child
  .split('')
  .reverse()
  .join('')
let newStr = ''
arr.forEach(v => {
  newStr = newStr.concat(v)
})
const start = newStr.indexOf(reverseChild)
const end = newStr.indexOf(reverseChild) + reverseChild.length
const result = newStr
  .slice(0, newStr.indexOf(reverseChild))
  .concat(
    child,
    newStr.slice(end)
  )
console.log(result)

6、非递减数列​

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3] 输出: true 解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。 示例 2:

输入: nums = [4,2,1] 输出: false 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。 【要改变2次】

思路​

需要注意的地方：

  • nums[i] <= nums[i + 1]，要满足数组的每个元素都符合条件，下个元素要大于上一个元素
js
var checkPossibility = function (arr) {
  let count = 0
  let index
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > arr[i + 1]) {
      count++
      index = i
    }
  }
  if (count === 0) return true
  if (count > 1) return false //大于表示至少需要改变2次
  // count等于1 的情况下, 分为边界上断掉，和中间部分断掉两种情况
  if (index === 0 || index === arr.length - 2) return true
  if (arr[index] <= arr[index + 2] || arr[index - 1] <= arr[index + 1]) {
    return true
  } else {
    return false
  }
}

7、求数组最大值​

apply​

使用 apply 是另一种。

  • apply

    • 由于用不到this 就传个null
    • 其中的数组元素将作为单独的参数传给 func 函数,即Math.max
text
var arr = [6, 4, 1, 8, 2, 11, 23];
console.log(Math.max.apply(null, arr))
ES6 ...​

使用 ES6 的扩展运算符：

text
var arr = [6, 4, 1, 8, 2, 11, 23];
console.log(Math.max(...arr))

8、实现一个函数，判断输入是不是回文字符串。​

  • 回文字符串:正着读和反着读都一样 例如noon、 abcba
js
//回文字符串:正着读和反着读都一样 例如noon、  abcba
function run (str) {
  return (
    str
      .split('')
      .reverse()
      .join('') === str
  )
}
console.log('abc'.split('')) //每个字符串以空进行分割 ['a','b','c']
console.log(['a', 'b', 'c'].join('')) //数字每个元素以空 (中间没有东西)进行连接 abc
console.log(run('abcba'))