1-20题

1. 两数之和

https://leetcode-cn.com/problems/two-sum/submissions/

思路

建立一个 { 数字: index } 的对象，遍历数组，根据当前数算出省关于的数，通过建立的对象判断剩余的数对应的 index 是否存在。

时间复杂度O(n)，空间复杂度O(n)

function twoSum(nums: number[], target: number): number[] {
    const map = {}
    for (let i = 0; i < nums.length; i++) {
        const rest = target - nums[i]
        if (map[rest] || map[rest] === 0) {
            return [map[rest], i]
        }
        map[nums[i]] = i
    }
    return []
};

2. 两数相加

https://leetcode-cn.com/problems/add-two-numbers/submissions/

思路

1. 需要遍历两个链表，并将相加的结果放到新的链表中。
2. 需要一个变量标记相加结果是否会向前一位进1。
3. 注意在最高时存在节点消耗完，但是进1的情况。

/**
 * Definition for singly-linked list.
 * 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)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let result: ListNode | null = null
    let node1 = l1
    let node2 = l2
    let cur = result
    // 是否需要加1
    let needAddOne = false
    while (node1 || node2 || needAddOne) {
        const sum = (node1 && node1.val) + (node2 && node2.val) + (needAddOne ? 1 : 0)
        needAddOne = sum >= 10
        if (cur === null) {
            result = cur = new ListNode(sum % 10)
        } else {
            cur = cur.next = new ListNode(sum % 10)
        }
        node1 = node1 && node1.next
        node2 = node2 && node2.next
    }

    return result
};

3. 最长不重复字符串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/submissions/

思路

遍历字符串，记录以当前字符串结尾的最长不重复字符串。如果遇到重复的情况，则找到哪一个字符重复，截取下来。

function lengthOfLongestSubstring(s: string): number {
    let curStr = ''
    let max = 0
    for (let i = 0; i < s.length; i++) {
        // 判断内部是否存在，如果存在，说明重复了。
        let index = curStr.indexOf(s[i])
        if (index !== -1) {
            // 不符合要求，找到对应的 index，删除前面的string
            curStr = curStr.slice(index + 1) + s[i]
        } else {
            // 符合要求
            curStr += s[i]
        }
        max = Math.max(curStr.length, max)
    }
    return max
};

4. 两个正序数组的中位数

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

思路

1. 找到中位数对应的 index
2. 遍历两个正序数组，并比较相应元素，找到第 index 个符合要求的元素。
3. 如果总数目是奇数，直接返回结果。如果是偶数，需要计算平均值。

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const total = nums1.length + nums2.length
    const isEven = total % 2 === 0
    const middle = isEven ? total / 2 : (total - 1) / 2 + 1

    let m = 0
    let n = 0
    let cur = 0
    while (m < nums1.length || n < nums2.length) {
        if (nums1[m] === undefined) {
            cur = nums2[n]
            n += 1
        } else if (nums2[n] === undefined) {
            cur = nums1[m]
            m += 1
        } else if (nums1[m] < nums2[n]) {
            cur = nums1[m]
            m += 1
        } else {
            cur = nums2[n]
            n += 1
        }

        if (m + n === middle) {
            if (isEven) {
                const next = nums1[m] === undefined 
                    ? nums2[n] 
                    : nums2[n] === undefined
                        ? nums1[m]
                        : nums1[m] < nums2[n] 
                            ? nums1[m] 
                            : nums2[n]
                return (cur + next) / 2
            } else {
                return cur
            }
        }
    }
};

5. 最长回文字符串

https://leetcode-cn.com/problems/longest-palindromic-substring/

思路

1. 动态规划：记录哪些子字符串是回文字符串。时间O(n2)，空间O(n2)。
2. 中心扩展法：遍历数组，然后以当前元素为中心，向外扩展，得到最大的长度，最终计算出的回文字符串的起始索引。时间O(n2)，空间O(1)。

function longestPalindrome(s: string): string {
    let max = 0
    // 记录最长回文字符串的起始 index
    let result: [number, number] = [0, 0]
    // 记录是否是回文字符串
    const dp: Array<Array<boolean>> = []
    for (let i = 0; i < s.length; i++) {
        dp[i] = []
        for (let j = 0; j < s.length; j++) {
            dp[i][j] = i === j ? true : false
        }
    }

    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i + 1; j < s.length; j++) {
            if (j - i === 1) {
                // 只有两个数时，相等即可
                dp[i][j] = s[i] === s[j]
            } else {
                // 否则依赖于 dp[i+1][j-1]
                dp[i][j] = s[i] === s[j] && dp[i+1][j-1]
            }
            if (dp[i][j] && j - i + 1 > max) {
                // 最长回文字符串
                result = [i, j]
                max = j - i + 1
            }
        }
    }

    return s.substring(result[0], result[1] + 1)
};

6. Z 字形变换

https://leetcode-cn.com/problems/zigzag-conversion/

function convert(s: string, numRows: number): string {
    if (numRows === 1) {
        return s
    }
    // 原本可以根据 i,j 记做二维数组的，但是没有必要，可以直接拼接成字符串
    const data: string[] = []
    let index = 0
    let i = 0
    let j = 0
    while (index < s.length) {
        data[i] = (data[i] || '') + s[index]
        // 判断正确的位置
        if (i + 1 < numRows && j % (numRows - 1) === 0) {
            i += 1
        } else {
            i -= 1
            j += 1
        }
        index++
    }

    let str = ''
    for (let i = 0; i < data.length; i++) {
       str += data[i] || ''
    }
    return str
};

7. 整数翻转

https://leetcode-cn.com/problems/reverse-integer/

// 转换为字符串进行翻转
function reverse(x: number): number {
    const s = x.toString()
    const isMinus = s[0] === '-'
    const str = isMinus ? s.slice(1) : s
    const result = parseInt(str.split('').reverse().join(''))
    if (result < -Math.pow(2, 31) || result > Math.pow(2, 31) - 1) {
        return 0
    }
    return isMinus ? -result : result
};

function reverse(x: number): number {
    let rest = 0
    // 边界条件 x 除完了
    while (x !== 0) {
        // 将最后一位放到最前面
        const digit = x % 10
        rest = rest * 10 + digit
        // 移除小数 
        x = ~~(x / 10)
    }
    if (rest < Math.pow(-2, 31) || rest > Math.pow(2, 31) + 1) {
        return 0
    }
    return rest
};

9. 回文数

https://leetcode-cn.com/problems/palindrome-number/submissions/

function isPalindrome(x: number): boolean {
    // 小于0或者尾部为0，都不会是回文数
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false
    }
    // 翻转一半的数记录下来
    let reverseNum = 0
    while (reverseNum < x) {
        reverseNum = reverseNum * 10 + x % 10
        x = Math.floor(x / 10)
    }
    // 偶数位数时相等，奇数位数时去除一位再判断
    return x === reverseNum  || x === Math.floor(reverseNum / 10)
};