一些算法题

雨点打透心脏的1/2处 2022-12-17 05:21 153阅读 0赞

### 1、生成1到1000之间的质数/素数 ###

> 质数：除了1和它本身之外不能被其他的数整除。  
> 最小的质数是2

### 2、生成嵌套数组 ###

如题，生成`[0,[1,[2,[3]]]]`这样的嵌套数组。

let result;
    for(let i=3;i>=0;i--){ 
      if(i==3){ 
         result=[i];
      }else{ 
         result=[i,[result]]
      }
    }
    console.log(result)

### 3、统计一下从1到n中 0出现的次数 ###

**注意**：10，出现了1次；；；；；；； 100，出现了2次，1001，出现了2次

> 先将0到n拼接成一个字符串，然后用0分割

let str=(new Array(10).fill(1)).map(function(item,index){ 
        return index
    })
    str=str.toString();
    const count=str.split("0").length-1;

### 4、求两个数的最大公约数 ###

var a=3;
    var b=2;
    var result;
    var ys=1;
    while(ys<=a && ys<=b){ 
       if(a%ys===0  && b%ys===0){ 
          result=ys;
       }
       ys++;
    }
    console.log(result)

### 5、最小公倍数 ###

var a=3;
    var b=2;
    var min=Math.max(a,b);
    var max=a*b;
    var result;
    for(let i=min;i<=max;i++){ 
      if(i%a===0 && i%b===0){ 
          result=i;
          break;
      }
    }

### 6、生成指定长度的字符串 ###

const chars="1234567890qwertyuiopasdfghjklzxcvbnm";
    const length=12;
    let result="";
    for(let i=0;i<length;i++){ 
       result+=chars[Math.floor(Math.random()*chars.length)]
    }
    console.log(result)

### 7、将数组的顺序打乱 ###

现在有数组 `[1,2,3,4,5,6,7,8,9,10]`，希望把整个数组项的顺序打乱

> 遍历数组，产生数组长度范围内的随机数，  
> 交换

let arr=[1,2,3,4,5,6,7,8,9,10];
    const len=arr.length;
    for(let i=0;i<len;i++){ 
       const index=Math.floor(Math.random()*len);
       const temp=arr[i];
       arr[i]=arr[index];
       arr[index]=temp;
    }
    console.log(arr)

### 8、从未排序的整数数组中找出缺失的数字。 ###

比如，有1到100的整数，现在缺少了其中一个，怎么找出这个数字？

> 解决方式：先求得1到100的和。然后计算出现在存在的这些所有数字的和，两者相减。。 。。得出缺失的数字

// 先 求 1到100之间的整数和

### 9、检查是否有任何两个数字(整数)的和是给定的数字 ###

其他条件：

*  整数
 *  大于等于零

### 10、sort()函数的使用 ###

sort()，将数组项进行排序，直接修改的原数组。sort()会调用每一项的toString()，然后比较得到的字符串，即使数组中的每一项都是数字，sort()比较的也是字符串。

**10.1. 日期的大小排序**

> 现有一组日期，格式yyyy-mm-dd，想要从小到大进行排序

const dateArr = ['2018-01-20', '2017-02-19', '2016-08-08', '2018-12-09']
    date.sort()// 返回一个新数组

![在这里插入图片描述][2020102419002883.png_pic_center]

**10.2. 版本号的排序**

> 现有一组版本号,格式为 1.2.3.2 这样的，想要从小到大进行排序

const banben=["1.32.12","1.32.134.3","2.2.23.1","2.3","0.21.1","0.29.1"];
    banben.sort();

![在这里插入图片描述][20201024190042962.png_pic_center]  
**10.3. 对象数组按照某个字段值的大小排序**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYW5nTGl0dGxlQmFp_size_16_color_FFFFFF_t_70_pic_center]

### 11、找出数组中第N大的数字 ###

其实这个题目给出的条件是很少的，可以进一步提问。这个数组是有序的吗？ 排过序的话是升序还是降序？ 这个数组中有没有重复项呢？

> 1、好吧，现在设定题目是这样的，数组未排序，然后数组项没有重复项

// ... 数组排序就不写了啊。。。。
            var paoxuarr = [1, 2, 3, 4, 5, 6, 7];  // 排序 过后的数组
            var count = 0;
            function getNmax(arr, n) { 
                for (let i = arr.length - 1; i >= 0; i--) { 
                    count += 1;
                    if (count == n) { 
                        console.log(arr[i])
                    }
                }
            }
            getNmax(paoxuarr, 3); // 获取第三大的元素

> 2、数组未排序，数组中有重复项。

### 12、找出数组中重复的数组项 ###

好吧，这个问题的解法有很多

**解法一**

> 解法一的思路是，使用一个空的新数组a，依次将数组arr的项推入数组a中，如果a中没有这一项，直接推入，，，，， 如果数组a中已经有了这一项，那么说明这一项是重复的，直接推入结果数组中

**解法二**

> 突然想到，之前数组去重的时候就用到了filter，，，，那反过来也可以使用它来得到重复的数组项。。。。。

const arr = [1, 2, 3, 2, 5, 4, 6, 7, 5, 8,3];
                let koko=[];
                koko=arr.filter(function(item,index){ 
                   return arr.indexOf(item)!==index
                });
                console.log(koko);

### 13、空格替换 ，将字符串中的每一个空格替换为`%20` ###

粗略想了一下，

*  使用函数`encodeURIComponent()`或者`encodeURI()`，好吧，这个方法有风险，万一这个字符串中有其他的符号（空格、中文、特殊字符什么的也会被转译。。。那这就偏离了题目了。。。）所以这个方法不建议用
 *  使用正则进行替换
 *  新声明一个变量res,遍历当前字符串，如果当前字符是空格，将其替换为20%，写入到变量res中

### 14、连续子数组的最大和 ###

输入一个整型数组，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组和的最大值。  
例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。

### 15、二分查找 ###

二分查找一般是针对一个排序数组的，

### 16、实现一个简单的模板渲染 ###

写一个函数，根据下面的模板和输入的值，生成`我是坤坤，特长是篮球，代表作姬霓太美`

> 现有模板内容：`我是{ {name}}，爱好是{ {address}}，代表作{ {dw}}`  
> 输入data，`data={name:"坤坤",address:"篮球",dw:"姬霓太美"}`

> 解决方式：写个正则 替换一下吧。。。。。

![在这里插入图片描述][20201025015043827.png_pic_center]

### 17、数组的翻转 ###

解释：现有数组`[1,2,3,4,5]`，将这个数组的项的顺序整个翻转，得到`[5,4,3,2,1`。不可以使用reverse() 等函数。原生发生实现

> 解题思路：找到数组的中间位置，按顺序依次将中间位置的前面和后面的数字交换。直到数组的边界处

### 18、使用堆栈实现队列先进先出的效果 ###

堆栈：先进后出，每次只能从队列的顶部取数据，存数据时也只能从放到顶部。

队列：先进先出，就像是排队，排在前面的先出去，排在后面的后出来。

> 如果想要用堆栈去模拟队列的效果的话，至少需要2个堆栈A和堆栈B。  
> 当有数据输入时，就往堆栈A里插入push()。当有是数据输出时，就将堆栈A中的数据依次拿出来放入堆栈B中，再从堆栈B的顶部取出数据。由此，便通过2个堆栈实现了队列的先进先出的效果了。

[添加链接描述][Link 1]

### 19、使用队列实现堆栈先进后出的效果 ###

队列：先进先出，就像是排队买票，排在队列前面的先出去，不可以插队。

堆栈：后劲先出，就像是一个桶，每次存数据时总是存放到最上面，取数据时也是从上面取数据

> 如果想要用队列实现堆栈先进后出的效果

### 20、找出数组的项的最大差值 ###

题目解释：在一个整数数组中，求两个数组项相减之后的最大差值

> 不让用array 数组自带的方法的话， 就遍历，求出最小值和最大值，相减

### 21、若無序数组中存在两项的和等于目标值，返回其下标(只返回一組就行) ###

> 好吧，这个问题，一开始想到的是双层for循环，同时从数组的第一项和最后一项遍历，判断两项的和是否等于目标值，是的话，返回下标。。。。。。。 但是这个方法 时间复杂度 o(n²)。。。。 有没有更好的方法呢？

### 22、有序数组 中存在两项的和等于目标值，返回其下标（只返回一組就行） ###

> 好吧，有序数组的话，就简单的一些

### 23、判断一组括号的嵌套是否合法 ###

> `()[]{}`、`{ {}()[()]}`等等这样的是合法的  
> `(()`、`[[}](`、`][`、`}}[])`等等这样的是不合法的

首先，如果括号的个数是奇数，那肯定不合法 。 合法的括号都是成对出现、、、

### 24、返回两个数组的交集 ###

解释：数组项同时存在于数组a和数组b中。\[1,2,3,4\]和\[3,4,5,6\]的交集就是\[4\]

> 好吧，求数组交集的方法还是比较多的。。。for循环，filter

### 25、有6个人为一个运动员打分、分数都是整数、最低分是1分，最高分是5分。求一个平均分。问。。。这个运动员可能拿到的平均分有多少种情况。。。 ###

> 那首先，平均分是在总分的基础上计算出的。。 那可以先思考下总分的情况。。。如果6个人都打1分，那总分是6分。 如果6个人都打5分，那么总分是30分。 也就是说，总分的范围是6~30分。共有25种总分

> 那么平均分 也是 25种了。。。

### 26、在一个给定的数组中，找出由三个数组项得到的最大乘积， 有负数的话得考虑负负得正的情况。假设数组长度至少是3 ###

> 解题思路一：先数组从小到大排序，如果都是正数，最大乘积等于最后3个数组项的乘积； 如果都是负数，最大乘积等于最前面3个数组项的乘积。 如果有正数有负数，最大乘积要不是最小两个负数和最大整数的乘积 就是 最大三个整数的乘积

> 解题思路二：根据解题思路1可以在知道，最大乘积一定是在 最大的前3项和 最小的后2项之间相乘得到，，， 那只要得到这几项就不需要排序了

### 27、两个排序数组的合并 ###

现在，有两个数组a和b 都是升序的，想要将这两个数组合并为一个新数组之后仍然保持升序，不要使用sort()、concat()之类的方法

**解决方法**

*  新建一个数组用于保存结果，
 *  声明两个变量x、y用于记录遍历到数据a和b的哪个位置了
 *  同时 遍历数组a和数组b
 *  当数组a的项小于数组b的项时，push数组a的当前项，x++
 *  当数组b的项小于数组a的项时，push数组b的当前项，y++
 *  当 两个数相等时，同时push，x++, y++
 *  当x>=数组a的长度并且 y>=数组b的长度时，退出循环

### 28、求数组项的最长公共前缀 ###

现有数组 `arr=["flop","flex","flow"]`。求三个数组项的最长公共前缀。

**解题思路**

*  拿到数组的第一项的第一个字符。
 *  依次和数组的其他项的 第一个字符比较。
 *  如果都相等，则第一个字符是公共前缀，将第一个字符添加到结果res中。
 *  再去拿到数组第一项的第二个字符，依次和数组的其他项的第二个字符比较， 重复这个过程。
 *  比较过程中，只要出现不相等的情况，就立即结束比较

### 29、输出一个数组中出现前三个出现次数最多的项 ###

**解题思路**

1.  声明两个数组`item`和`times`
2.  遍历数组
3.  `item`保存重复出现的项
4.  `times`保存重复出现的次数
5.  遍历数组`times`，找到最大值对应的index，`item[index]`就是出现次数第一多的数组项了，，，将`times[index]`置为0
6.  步骤5重复执行`3`次，即可得到出现次数前三多的数组项

### 30、一个数组，只遍历一次得到重复出现次数最多的项和重复出现次数最少的项 ###

**解题思路**

1.  声明一个数组`noRepeatArr`保存去重后的数组项
2.  声明一个变量`arrstr`，保存原数组的拼接
3.  声明两个变量`min`和`max`记录最小值和最大值
4.  声明两个变量`minIndex`和`maxIndex`记录最小值和最大值对应的index
5.  遍历数组`noRepeatArr`
6.  根据当前项的情况，给`min`、`max`、`minIndex`和`maxIndex`赋值
7.  根据最大值和最小值的index 在 数组`noRepeatArr`中找出对应的项。

### 31、获取一个字符串中由连续的不相同的字符组成的最长子串 ###

**解题思路**

1.  声明两个变量`temp`和`result`，用于分别暂存当前和最终的结果
2.  遍历字符串
3.  `temp`中是否包含当前字符，不包含，直接在尾部加上该字符。。。。包含：从该字符所在位置+1 处开始截取到`temp`的末尾，然后尾部加上该字符
4.  比较`temp`和`result`的长度，，当`temp`的长度更长时，将其赋值给`result`
5.  持续遍历，直到字符串的尾部

### 32、获取一个字符串的最长子串，子串的第一个字符和最后一个字符相同 ###

[2020102419002883.png_pic_center]: /images/20221123/3fec2f7f3fc2422082485d53df8e98ac.png
[20201024190042962.png_pic_center]: /images/20221123/809ef2e9579047349ebeb55c4af61bc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYW5nTGl0dGxlQmFp_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/28ccd9592d754c88829443e322812814.png
[20201025015043827.png_pic_center]: /images/20221123/29355c020f264466b36ce75b09c78014.png
[Link 1]: http://www.lucklnk.com/godaddy/details/aid/165008932