#刷题

LeetCode（简单）的笔记

两数之和

我的题解：

首先判断临界可能，若原数组的长度小于2，则返回空数组即可。
创建2个前后指针，第一个index指针遍历length-1次，第二个指针由第一个指针的位置+ 1到整个数组长度的遍历

当判断出两个指针的和等于target时，返回对应index即可。

function twoSum(nums: number[], target: number): number[] {
    if(nums.length < 2) {
        return []
    }
    let result: number[] = []
    let numsLength = nums.length;
    for(let i = 0; i < numsLength - 1; i++) {
        for(let j = i + 1; j < numsLength; j++ ) {
            if(nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
    return result
};

别人的题解：

新建一个map(key为数值的值，value为数组下标），map里面放的是之前已经比较过的数字，nums[i]是当前的值，target-nums[i]得到的值，如果在之前的数字有出现，则说明能够查找到。注意map里面放的是下标比i小的值，所以map[target-nums[i]]是返回数组的第一项。

function twoSum(nums: number[], target: number): number[] {
    let map = {}
    for(let i = 0; i < nums.length; ++i) {
        const rest = target - nums[i];
        if(map[rest] !== undefined) {
            // 注意这里map里面的是下标比较小的值。
            return [map[rest], i]
        }  
        map[nums[i]] = i   
    }
    return []
};

回文数

我的题解：

先将number类型转为string类型，方便操作下标
回文数的临界值时length/2，所以我们遍历到length/2即可
每次遍历将前后index对应的值做比较即可

function isPalindrome(x: number): boolean {
    let str = x + ''
    let strLength = str.length
    
    for(let i = 0; i < strLength / 2; i++) {
       if(str[strLength - i - 1] !== str[i]){
           return false
       }
    }
    return true
}

别人的题解：

这应该是最经典的双指针题目之一了吧，思路还是很明显的。先转换成字符串，然后从两端向中间靠近，遇到不同的就返回false，全部相同则返回true。
可能有几个需要注意的点：

负数一定不是回文。因为负号永远不会出现在数字的最后，不会存在-121-这种数字。
只需要判断到b < e时即可。如果是奇数，最中间的字符不会影响回文结果。

function isPalindrome(x: number): boolean {
  if (x < 0) return false;
  const s = x.toString();
  let b = 0, e = s.length - 1;
  while (b < e) {
    if (s[b] !== s[e]) return false;
    ++b, --e;
  }
  return true;
}

标签：数学
如果是负数则一定不是回文数，直接返回 false
如果是正数，则将其倒序数值计算出来，然后比较和原数值是否相等
如果是回文数则相等返回 true，如果不是则不相等 false
比如 123 的倒序 321，不相等；121 的倒序 121，相等

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
            return false;
        int cur = 0;
        int num = x;
        while(num != 0) {
            cur = cur * 10 + num % 10;
            num /= 10;
        }
        return cur == x;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

别人的题解：

思路就是，每一层都有一个容器，并且每一个节点要知道自己在那一层，将自己的元素放到对应的容器中然后继续遍历，遍历简单 DFS

class Solution {
    
    private List<List<Integer>> res = new ArrayList<>();
    
    // 方案二：递归层序打印
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 1); 
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        // 递归截至条件
        if (root == null){
            return;
        }
        // 如果该深度，在res中没有容器存放，res就添加一个容器
        if (res.size() < depth){
            res.add(new ArrayList<>());
        }
        // 添加该节点，到对应的深度容器中
        res.get(depth - 1).add(root.val);
        // 继续遍历 左子节点 和 右子节点
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

const res = []

function levelOrder(root: TreeNode | null): number[][] {
    res.length = 0
    dfs(root, 1)
    return res
};

function dfs(root: TreeNode, deep: number): void{
    if(root === null || root?.val === null) {
        return 
    }
    if(res.length < deep) {
        res.push([])
    }
    res[deep-1].push(root?.val)
    dfs(root?.left, deep + 1)
    dfs(root?.right, deep + 1)
}

官方题解

特例处理：当根节点为空，则返回空列表 [] ；
初始化：打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
BFS 循环：当队列 queue 为空时跳出；
1. 新建一个临时列表 tmp ，用于存储当前层打印结果；
2. 当前层打印循环：循环次数为当前层节点数（即队列 queue 长度）；
  1. 出队：队首元素出队，记为 node；
  2. 打印：将 node.val 添加至 tmp 尾部；
  3. 添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
3. 将当前层结果 tmp 添加入 res 。
返回值：返回打印结果列表 res 即可。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

剑指 Offer 28. 对称的二叉树

别人的题解：

检查根节点，没毛病就依次进行2个字节点的比较

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return check(root.left, root.right); // 检查root的左右子树
    }

    private boolean check(TreeNode a, TreeNode b) { 
        if (a == null && b == null) return true; // 都为空, 对称
        if (a != null && b == null) return false;
        if (a == null && b != null) return false; // 只有一边为空, 不对称
        if (a.val != b.val) return false; // 都不为空, 但值不相等

        boolean outside = check(a.left, b.right); // 比较a, b两棵树的外侧
        boolean inside = check(a.right, b.left); // 比较a, b两颗树的内测
        return outside && inside; // a, b内外侧都相等才对称
    }
}

面试题40. 最小的k个数

我的题解：
正排序后，取出前k个数

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function(arr, k) {
    arr.sort((a,b)=>a-b)
    return arr.splice(0, k)
};

125. 验证回文串

题解：

先使用正则过滤出数字和字母
然后使用首位指针进行匹配

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const newStr = s.replace(/([^a-zA-Z0-9])/g, '').toLocaleLowerCase();
    for(let i = 0; i < newStr.length / 2; i++ ){
        if(newStr[i] !== newStr[newStr.length - i - 1]) {
            return false
        }
    }
    return true;
};

todo

算法 LeetCode 简单

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

可选链的使用 Previous

断言与非空断言 Next