200

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/**
 * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。
返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 * @param s 
 * @returns 
 */
function reverseWords(s: string): string {
    // trim删除前后空格/\s+/匹配若干个空格
    return s.trim().split(/\s+/).reverse().join(" ");
}

 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
37
38

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

/**
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 * @param headA
 * @param headB
 * @returns
 */
function getIntersectionNode(
    headA: ListNode | null,
    headB: ListNode | null,
): ListNode | null {
    if (headA == null && headB == null) return null;
    let pa: ListNode | null = headA,
        pb: ListNode | null = headB;
    for (; pa != pb; ) {
        if (pa == null) {
            pa = headB;
        } else {
            pa = pa.next;
        }
        if (pb == null) {
            pb = headA;
        } else {
            pb = pb.next;
        }
    }
    return pa;
}

 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

/**
 * 给你一个下标从 1 开始的整数数组 numbers ，
 * 该数组已按 非递减顺序排列  ，
 * 请你从数组中找出满足相加之和等于目标数 target 的两个数。
 * 如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，
 * 则 1 <= index1 < index2 <= numbers.length 。
 *
 * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 * 你所设计的解决方案必须只使用常量级的额外空间。
 * @param numbers
 * @param target
 * @returns
 */
function twoSum(numbers: number[], target: number): number[] {
    //双指针夹逼
    let low = 0,
        high = numbers.length - 1;
    while (low < high) {
        let sum = numbers[low] + numbers[high];
        if (sum == target) {
            return [low + 1, high + 1];
        } else if (sum < target) {
            low++;
        } else {
            high--;
        }
    }
    return [-1, -1];
}

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
 * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
 
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
 
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 */

// hash
function majorityElement(nums: number[]): number {
    let half = nums.length / 2;
    let map = new Map();
    let tmp = 0;
    for (let i = 0; i < nums.length; i++) {
        const element = nums[i];
        if (map.has(element)) {
            tmp = map.get(element);
            map.set(element, ++tmp);
        } else {
            map.set(element, 1);
        }

        if (map.get(element) > half) return element;
    }
    return 0;
}

// sort
function majorityElement(nums: number[]): number {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
}

// Boyer-Moore
function majorityElement(nums: number[]): number {
    let count = 1;
    let candidate = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
        }
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 */

function reverse(nums: number[], start: number, end: number): void {
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start += 1;
        end -= 1;
    }
}

function rotate(nums: number[], k: number): void {
    let tmp = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, tmp - 1);
    reverse(nums, tmp, nums.length - 1);
}