2.两数之和

leetcode1.两数之和-简单
给定一个整数数组 nums 和一个整数目标值target，请你在该数组中找出 和为目标值target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
①暴力枚举
双重循环：找target-x
时：O(n²)
空：O(1)
②一遍遍历+哈希查找

var twoSum = function(nums, target) {
    //  一遍遍历+哈希查找
    const map=new Map();
    for(let i=0;i<nums.length;i++){
        const x=nums[i];
        if(map.has(target-x)){
            const index=map.get(target-x);
            return [i,index];
        }
        map.set(x,i);
    }
    return [];
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时：O(n)，其中 n 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)地寻找 target - x。
空：O(n)，其中 n 是数组中的元素数量。主要为哈希表的开销。

3.翻转二叉树

leetcode226.翻转二叉树-简单
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

①递归

var invertTree = function(root) {
    if(root==null) return null;
    // if(root.left)
    let temp=root.left;
    root.left=root.right;
    root.right=temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
};
1
2
3
4
5
6
7
8
9
10

时：O(n)
空：O(n)
②DFS（深度优先搜索）
③BFS（广度优先遍历）

4.最长公共前缀

leetcode14.最长公共前缀-简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
①横向扫描
依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
时：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空：O(1)，使用的额外空间复杂度为常数。
②纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

	var longestCommonPrefix = function(strs) {
    // 纵向扫描
    if(!strs) return "";
    let len=strs[0].length;
    for(let i=0;i<len;i++){
        for(let j=1;j<strs.length;j++){
            if(i==strs[j].length||strs[0][i]!==strs[j][i]){
                return strs[0].substring(0,i);
            }
        }
    }
    return strs[0];
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空：O(1)，使用的额外空间复杂度为常数。
③分治
④二分查找

5.无序数组中最大的两个数

参考：无序数组中找出最大的两个（K）数
这道题是室友面用友时问到的（java后端开发）
在网上搜了一下，发现力扣上也有
leetcode215.数组中的第K个最大元素-中等

自己先写了一下，直接排序，然后从数组中取第k大的元素…这也太拉跨了

这题应该用堆解决
练习如何建堆并进行堆排序，大顶堆 & 小顶堆
大顶堆的构建过程：最后一个非叶子结点的位置是：数组长度/2-1
①基于快速排序的选择方法

var findKthLargest = function(nums, k) {
    if(!nums) return;
    if(k>nums.length) return;

    // let random=Math.random();
    return quickSelect(nums,0,nums.length-1,nums.length-k);
};
var quickSelect=function(nums,l,r,index){
    let q=randomPartition(nums,l,r);
    if(q==index){
        return nums[q];
    }else{
        return q<index?quickSelect(nums,q+1,r,index):quickSelect(nums,l,q-1,index);
    }
}
var randomPartition=function(nums,left,right){
// 感觉随机数这里有点问题
    let i=Math.floor(Math.random()*(nums.length))-left;
    swap(nums,i,right);
    return partition(nums,left,right);
}
var partition=function(nums,left,right){
    let x=nums[right],i=left-1;
    for(let j=left;j<right;j++){
        if(nums[j]<=x){
            swap(nums,++i,j);
        }
    }
    swap(nums,i+1,right);
    return i+1;
}
var swap=function(nums,i,j){
    let temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

照着官方题解的java代码写的js，但运行时老有几个测试用例通过不了，执行代码时没问题，一提交就有错…感觉是生成随机数的问题

时：O(n)
空：O(logn)
👆不理解
②基于堆排序的选择方法
大根堆的实现方法：建堆、调整、删除

var findKthLargest = function(nums, k) {
    let len=nums.length;
    buildMaxHeap(nums,len);
    for(let i=len-1;i>=len-k+1;--i){
        swap(nums,0,i);
        --len;
        maxHeapify(nums,0,len);
    }
    return nums[0];
};
var buildMaxHeap=function(nums,len){
    for(let i=Math.floor(len/2);i>=0;--i){
        maxHeapify(nums,i,len);
    }
}
var maxHeapify=function(nums,i,len){
    let l=i*2+1,r=i*2+2,largest=i;
    if(l<len&&nums[l]>nums[largest]){
        largest=l;
    }
    if(r<len&&nums[r]>nums[largest]){
        largest=r;
    }
    if(i!=largest){
        swap(nums,i,largest);
        maxHeapify(nums,largest,len);
    }
}
var swap=function(nums,i,j){
    let temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

这个也报错…我真的会谢…好像是内存的问题

时间复杂度：O(nlogn)，建堆的时间代价是O(n)，删除的总代价是O(klogn)，因为 k < n，故渐进时间复杂为O(n+klogn)=O(nlogn)。
空间复杂度：O(logn)，即递归使用栈空间的空间代价。

补上昨天的…进度太慢了…