算法题

阅读神三元博客进行归纳总结

对于链表进行操作的题目

1、反转链表

例题

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

申明链式结构为

function ListNode(val) {
  this.val = val;
  this.next = null;
}

可以通过循环来进行

let reservelist = (head) => {
    if(!head){
        return
    }
    let pre = null 
    let cur = head
    while(cur){
        //将元素的上一个节点保存
        let next = cur.next
        //将元素的下一个节点保存为上一个节点
        cur.next = pre 
        //将这个节点保存为pre
        pre = cur
        //进入下一个节点
        cur = next
    }
    return pre
}

可以使用循环递归进行

let reservelist = (head) => {
    let reserve = (pre,cur) => {
        //现将下一个节点进行保存
        let next = cur.next
        //将节点的指针指向上一个节点
        cur.next = pre
        //递归
       	reserve(cur,next)
    }
    return reserve(null,head)
}

力扣上的题目解决

1、有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？

连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。

输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。

var fraction = function(cont) {
    let up = 1
    let down = cont[cont.length-1];
    for(let i = cont.length-2 ; i>=0;--i){
        up = up + down*cont[i];
        [up,down] = [down,up];
    }
    return [down, up];
}
//每一次就是分数相加在进行倒

2、给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

示例 1：

输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

var findNumbers = function(nums) {
    let num = 0 
    nums.map(item =>{
        if(item.toString().length%2===0){
            num =num +1
        }
    })
    return num
};
//数字的长度可以先将它转换为字符串

3、根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

方法一 、暴力破解

var dailyTemperatures = function(T) {
    let a = []
    for(let i = 0;i<T.length;i++){
        let b = 0
        for(let j = i+1;j<T.length;j++){
            if(T[j]>T[i]){
                b = j-i
                break
            }
        }
        a.push(b)
    }
    return a 
};

方法二、使用栈

还不会

4、给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc" 输出: 3 解释: 三个回文子串: "a", "b", "c". 示例 2:

输入: "aaa" 输出: 6 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

var countSubstrings = function(s) {
    let num = 0 
    function find(s,i,j){
        while(i>=0 && j<s.length && s[i]==s[j]){
            i= i-1
            j=j+1
            num =num+1
        }
    }
    for(let i = 0; i < s.length; i++){
        find(s, i , i) //检查abba这种
        find(s, i , i+1)//检查aabaa这种
    }
    return num
};

5、给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

var findUnsortedSubarray = function(nums) {
    let a = [...nums]
    let satrt = 0
    let end = 0 
    nums.sort((a, b) => a - b);
    let i = 0 
    let j = nums.length-1
     while (i < nums.length) {
        if (nums[i] != a[i]) {
            start = i;
            break;
        }
        i++;
    }

    while (j >= 0) {
        if (nums[j] != a[j]) {
            end = j;
            break;
        }
        j--;
    }
    return end - satrt
};
先对数组进行排序
对排序过后的数组与原数组比较
前后两个指针

5、