LeetCode: 206 反转链表

示例:
1->2->3->4->5->null
5->4->3->2->1->null

解题思路:
1. 先思考如何反转2个节点,将n+1的next指向n
2. 双指针遍历链表,然后重复上面的动作

解题步骤:
1. 双指针遍历
2. 反转双指针

var reverseList = function (head) {
    let p1 = head
    let p2 = null
    while (p1) {
        const tmp = p1.next
        p1.next = p2
        p2 = p1
        p1 = tmp
    }
    return p2
};

二分查找

题目:例如这样一个[1,3,4,5,7]有序的数组,如何快速找到某个值的下标?
这是一个经典的二分查找算法题。

解题思路:

  1. 先找到数组的中间下标值
  2. 然后判断目标值如果大于中间值,就在数组的右半边继续查找
  3. 如果目标值小于中间值,就在数组的左半边继续查找
  4. 然后不断的重复上面的步骤。

时间复杂度是O(logN) 因为遍历减半了就是n的一半=logN,如果遍历了全部就是N

let binarySeach = function (arr, target) {
    let s = 0 // 开始下标
    let e = arr.length - 1 //结束下标
    while (s <= e) { // 如果开始下标小于等于结束下标就标识区间内有值
        let mid = Math.floor((s + e) / 2) //当前数组的中间值下标
        let item = arr[mid] // 中间值
        if (item < target) { //如果中间的值小于目标值
            s = mid + 1 // 把开始下标移动到中间值的后面,在2叉树的右边继续搜索了
        } else if (item > target) { //如果中间值大于目标值
            e = mid - 1 // 把结束下标移动到中间值的前面一位,在2叉树的左边数组继续搜索
        } else { // 如果中间值等于目标值直接返回当前下标
            return mid
        }
    }
    return -1 // 找不到就返回-1
}
let res = binarySeach([1, 2, 3, 4, 5], 2)
console.log(res)

js 快速排序

问题:一个值未知的数组,如何快速根据值的大小进行排序。
思路:
先找到数组的中位数pivot作为参照物
遍历数组中的每一项与其比较,然后小的放到一个Left的空数组里面,比它大的放点right的空数组里面
再递归左边的数组和右边的组数,最后把2个数组和中位数连接到一个数组里面去

let arr = [11, 82, 4, 44, 20]
var quickSort = function (arr) {
    if (arr.length <= 1) { return arr }
    var pivotIndex = Math.floor(arr.length / 2)
    var pivot = arr.splice(pivotIndex, 1)[0]
    var left = []
    var right = []
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}
console.info(quickSort(arr))

力扣算法第1题:两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
例如:
给定 nums = [2, 7, 11, 15], target = 9 。 ·8
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路:
1. 把nums想象成相亲者
2. 把target想象成匹配条件
3. 用字典建立一个婚姻介绍所,存储相亲者的数字和下标

解题步骤:
新建一个字典作为婚姻介绍所
遍历nums里的值,有合适的就牵手成功,没有就先登记,字典里面Key就是nums里的值,value就是下标。

var twoSum = function (nums, target) {
    let map = new Map() // 婚姻介绍所
    for (let i = 0; i < nums.length; i++) {
        const n = nums[i] //自己
        const n2 = target - n //对象
        if (map.has(n2)) { //是否有合适的对象
            return [map.get(n2), i] //有就返回对象的下标和自己的下标
        } else {
            map.set(n, i) // 没有合适的对象就把自己登记到介绍所
        }
    }
}
let res = twoSum([2, 7, 11, 15], 9)