自学内容网 自学内容网

力扣爆刷第161天之TOP100五连刷71-75(搜索二叉树、二维矩阵、路径总和)

力扣爆刷第161天之TOP100五连刷71-75(搜索二叉树、二维矩阵、路径总和)

一、98. 验证二叉搜索树

题目链接:https://leetcode.cn/problems/validate-binary-search-tree/description/
思路:验证二叉搜索树,二叉搜索数要求任意节点大于左孩子,小于右孩子。这么来看二叉搜索树的中序遍历正好是单调递增序列,所以要判断是否是二叉搜索树,只需要使用中序遍历,并且记录前一个节点的值,用来比较即可。

class Solution {
    TreeNode pro = null;
    boolean flag = true;
    public boolean isValidBST(TreeNode root) {
        traverse(root);
        return flag;
    }

    void traverse(TreeNode root) {
        if(root == null || !flag) return ;

        traverse(root.left);
        if(pro != null && pro.val >= root.val) {
            flag = false;
            return;
        }
        pro = root;
        traverse(root.right);
    }
}

二、394. 字符串解码

题目链接:https://leetcode.cn/problems/decode-string/description/
思路:类似于拼接字符串,又带有左右括号,一般看到左右括号类型的题目都要考虑一下,能不能使用栈来做,因为一般左右匹配都是使用栈。本题仔细思考可以发现确实是的,类似于计算表达式,使用两个栈,一个是数字栈,一个是字符串栈,每次遇到左括号就把收集到的字符串和数字压栈,然后启用一个新的字符串和数字记录最新的左括号内的内容,直到遇到右括号,就可以根据数字栈内的内容复制次数,然后拼接字符串栈栈顶元素,以此往复即可。
在这里插入图片描述

class Solution {
    
    public String decodeString(String s) {
        LinkedList<Integer> stk1 = new LinkedList<>();
        LinkedList<String> stk2 = new LinkedList<>();
        StringBuilder res = new StringBuilder();
        int num = 0;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') {
                num = num * 10 + Integer.parseInt(c + "");
            }else if(c == '[') {
                stk1.push(num);
                num = 0;
                stk2.push(res.toString());
                res = new StringBuilder();
            }else if(c == ']') {
                StringBuilder t = new StringBuilder();
                int count = stk1.pop();
                for(int i = 0; i < count; i++) {
                    t.append(res);
                }
                res = new StringBuilder(stk2.pop() + t);
            }else{
                res.append(c);
            }
        }
        return res.toString();
    }

    
}

三、34. 在排序数组中查找元素的第一个和最后一个位置

题目链接:https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
思路:求排序数组中目标元素出现的最左位置和最右位置,其实就是采用二分查找,分开查找,先查找左边界再查找右边界。然后注意边界条件,即元素是否存在,查出来的边是否超界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findLeft(nums, target);
        int right = findRight(nums, target);
        return new int[]{left, right};
    }

    int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) {
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        if(left < 0 || left >= nums.length) return -1;
        return nums[left] == target ? left : -1;
    }


    int findRight(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        if(right < 0 || right >= nums.length) return -1;
        return nums[right] == target ? right : -1;
    }
    
}

四、113. 路径总和 II

题目链接:https://leetcode.cn/problems/path-sum-ii/description/
思路:求和满足目标的路径,相当于在二叉树上做回溯,从上往下进行搜索,本质还是回溯,只需要把前序位置收集,在后序位置丢弃,对应了回溯的开始与结束,后序位置表示左右子树都遍历完了要返回上一级,自然需要删除收集的元素完成回溯。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        backTracking(root, targetSum);
        return result;
    }

    void backTracking(TreeNode root, int targetSum) {
        if(root == null) return;
        
        sum += root.val;
        list.add(root.val);

        if(root.left == null && root.right == null && sum == targetSum) {
            result.add(new ArrayList(list));
        }
        backTracking(root.left, targetSum);
        backTracking(root.right, targetSum);

        list.remove(list.size()-1);
        sum -= root.val;
        
    }
}

五、240. 搜索二维矩阵 II

题目链接:https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
思路:搜索二维矩阵,这个二维矩阵有一个特点,就是从左往右是递增的,从上往下是递增,那么也就在右上角构成了一个分界线,可以从这个位置开始深度优先搜索,如果当前元素小于目标元素,那就向下搜索,如果当前元素大于目标元素,那就是向左搜索。
在这里插入图片描述

class Solution {
    boolean flag = false;
    public boolean searchMatrix(int[][] matrix, int target) {
        dfs(matrix, target, 0, matrix[0].length-1);
        return flag;
    }

    void dfs(int[][] matrix, int target, int x, int y) {
        if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) return;
        if(matrix[x][y] == target) {
            flag = true;
            return;
        }else if(matrix[x][y] > target) dfs(matrix, target, x, y-1);
        else dfs(matrix, target, x+1, y);
    }
}

原文地址:https://blog.csdn.net/qq_43511039/article/details/140268295

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!