二分查找+搜索插入位置

[Musings]
今天写的是二分查找+搜索插入位置,二分我以为5分钟能写出来,结果竟然完全忘记用维护指针去做,而是一个劲在那用步长去维护,直接导致边界震荡,最后看了眼思路,才想起来,二分是用指针的…哎.还是得不停的刷题吗….

一开始写的版本
https://leetcode.cn/problems/binary-search/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function search(nums: number[], target: number): number {
    if (nums.length == 0) return -1;
    let lastInd = 0;
    let mid = Math.floor(nums.length / 2);
    while (true) {
        if (nums[mid] == target) return mid;
        if (mid <= lastInd) return -1;
        let step = mid - lastInd;
        lastInd = mid;
        if (nums[mid] > target) {
            mid = Math.floor(mid - Math.abs(step / 2));
        } else {
            mid = Math.floor(mid + Math.abs(step / 2) + 1);
        }
        if (mid < 0 || mid >= nums.length) return -1;
    }
}

偷看解题思路以后用双指针去维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}


// search([-1, 0, 3, 5, 9, 12], 2)
// search([5], -5)
search([0, 3, 5], 1)

写了个快乐数https://leetcode.cn/problems/happy-number/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isHappy(n: number): boolean {
    let set = new Set();
    while (true) {
        let arrayList = n.toString().split('');
        let result = 0;
        arrayList.forEach(s => {
            result += Math.pow(Number.parseFloat(s), 2);
        })
        if (result == 1) return true;
        if (set.has(result)) return false;
        set.add(result);
        n = result;
    }
};
console.log(isHappy(19))

优化下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isHappy(n: number): boolean {
    const seen = new Set<number>();

    const getNext = (num: number): number => {
        let sum = 0;
        while (num > 0) { 
            //1.不做字符转换,直接通过%效率更高
            //2.不用forEach,效率不高,在TS中forEach属于使用callback的高阶函数,在回调中会产生自己的this,闭包绑定
            const digit = num % 10;
            sum += digit * digit;
            num = Math.floor(num / 10);
        }
        return sum;
    };

    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = getNext(n);
    }

    return n === 1;
}

console.log(isHappy(19)); // true

使用快慢指针的思路来判断是否产生循环,从而减少空间复杂度,时间换空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function isHappy(n: number): boolean {
    let fast = n;
    let slow = n;
    while (true) {
        fast = getNext(getNext(fast));
        slow = getNext(slow);
        if (fast == 1) return true;
        if (fast == slow) return false;
    }

    function getNext(val: number): number {
        let result = 0;
        while (val != 0) {
            let x = val % 10;
            result += x * x;
            val = Math.floor(val / 10);
        }
        return result;
    }
};
console.log(isHappy(2))