三月份的题解

📅 2026-03-01 📂 2026年归档

102.二叉树的层序遍历

原题

运用队列的性质，来进行遍历。

初始化队列（把跟节点放到队列里），队列里有几个元素就内循环（内循环的循环次数就是某层有多少个）几次，把同层的每一个元素都访问到，之后把val放到数组里，判断left和right是否为空，不是空继续放到队列里。当队列的元素为0时外循环结束（外循环其实就是层数）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list =new ArrayList<>();
        if(root==null) return list; //防止root为空，下面报错
        Queue<TreeNode> queue=new ArrayDeque<>(); 
        queue.offer(root);  //队列初始化
        while(queue.size()!=0){
            int size=queue.size();
            List<Integer> integerList =new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode treeNode=queue.poll();
                integerList.add(treeNode.val);
                if(treeNode.left!=null) queue.offer(treeNode.left);
                if(treeNode.right!=null) queue.offer(treeNode.right);
            }
            list.add(integerList);
        }
        return list;
    }
}

用栈实现队列

import java.util.Stack;

public class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    //放进来一个
    public void push(int x) {
        stackIn.push(x);
    }

    //拿出来
    public int pop() {
        while (!stackIn.empty()) {
            stackOut.push(stackIn.pop());
        }
        int i = stackOut.pop();
        while (!stackOut.empty()) {
            stackIn.push(stackOut.pop());
        }
        return i;
    }

    //查看要拿出来的，但不拿出来
    public int peek() {
        while (!stackIn.empty()) {
            stackOut.push(stackIn.pop());
        }
        int i = stackOut.peek();
        while (!stackOut.empty()) {
            stackIn.push(stackOut.pop());
        }
        return i;
    }

    //检查是否为空
    public boolean empty() {
        return stackIn.empty();
    }
}

98.验证二叉搜索树

原题

设树的每一个节点都可以找出来最大和最小值，没有最大值或最小值的就存null（根节点就都是null）。由此条件看代码，画一画即可明白。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return test(root, null, null);
    }

    public boolean test(TreeNode root, Integer lower, Integer upper) {
        if (root == null) {
            return true;
        }

        int val = root.val;
        if (lower != null && lower >= val) return false;
        if (upper != null && upper <= val) return false;

        if(!test(root.left,lower,val)) return false;
        if(!test(root.right,val,upper)) return false;
        return true;
    }
}

349.两个数组的交集

原题 利用哈希表的原理，题目0 <= nums1[i], nums2[i] <= 1000所以我创建了一个有1001个空间的数组，但其实可以用HashSet来应对更多场景。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Integer[] array=new Integer[1001];
        ArrayList<Integer> arrayList=new ArrayList<>();
        for (int i : nums1) {
            array[i]=1;
        }
        for (int i : nums2) {
            if(array[i]!=null){
                arrayList.add(i);
                array[i]=null;
            }
        }
        int[] arr=arrayList.stream()
                .mapToInt(Integer::intValue) 
                .toArray();
        return arr;
    }
}

1.两数之和

原题

用两数的和减去当前的遍历到的数即可得到需要的另外一个数，再在map里get如果get的结果不为null，即代表可以返回数组了，如果为null则把当前数存入map中

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            int num=target-nums[i];
            Integer index=(Integer)map.get(num);
            if(index!=null){
                int [] arr={i,index};
                return arr;
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

18.四数之和

原题

首先把这个数组进行排序，从小到大。 固定两个数，在用另外两个对撞。四数和如果等于target则加入进lists集合里，如果小于target让left++，如果大于target让right–。这里最复杂的是如何进行去重复（看代码）。之后还有一点要注意的是，sum有可能会大于Integer.MAX_VALUE所以sum用long类型！！！

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length < 4) return lists;
        for (int i = 0; i < nums.length - 1; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.length; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long sum = (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right];
                    if (sum > target) right--;
                    else if (sum < target) left++;
                    else {
                        lists.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return lists;
    }
}

76.最小覆盖字串

原题

这个运用到滑动窗口的思想，该解题思路里最重要的是用来记录符合要求的数量conform 我第一遍写好之后遇到的三个问题：

  1. while循环里的left一定要++因为这时候已经有合适的字符串了可以试着从左边缩减窗口，看看能不能达到要求，不要–要不然会出现超出索引异常（我第一遍写的时候没注意到这个问题）
  2. 记录最小的子串初始值一定要用一个特别大的数最好是Integer.MAX_VALUE，如果用0的话还得单独去判断
  3. while里的条件一定是左指针<=右指针，这样是防止t为一个字符
class Solution {
        public String minWindow(String s, String t) {
        //返回字符的索引
        int start=0;
        int end=0;

        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            Integer integer = map.get(c) == null ? 1 : map.get(c) + 1;
            map.put(c, integer);
        }
        //窗口里符合要求的字符
        Map<Character, Integer> windows = new HashMap<>();
        //记录符合了几个字符
        int conform = 0;
        //记录最短长度 2.这里长度取极限取0的话就坏了
        int length = Integer.MAX_VALUE;
        //滑动窗口的左指针
        int left = 0;
        //字符串s的char[]
        char[] sArray = s.toCharArray();

        //这里的i相当于右指针
        for (int i = 0; i < sArray.length; i++) {
            char c = sArray[i];
            if (map.get(c) == null) {
                continue;
            }
            Integer integer = windows.get(c) == null ? 0 : windows.get(c);
            if (map.get(c) > integer) {
                if (map.get(c) <= integer + 1) {
                    conform++;
                }
            }
            windows.put(c, integer + 1);

            //3.左右指针可以相等
            while (left <= i) {
                if (map.size() == conform) {
                    int size = i - left + 1;
                    if (size < length) {
                        start=left;
                        end=i+1;
                        length = size;
                    }
                    Integer a = windows.get(sArray[left]);
                    if (a != null) {
                        a = a - 1;
                        windows.put(sArray[left], a);
                        if (map.get(sArray[left]) > a)
                            conform--;
                    }
                    //1.这里是往右走别--了
                    left++;
                } else {
                    break;
                }
            }
        }
        return s.substring(start,end);
    }
}

1456.定长子串中元音的最大数目

原题

我第一次写的时候，每循环一次就重新判断有多少个是符合的，导致超出时间限制，才有的如下一版

class Solution {
    public int maxVowels(String s, int k) {
        int size = 0;
        char[] chars = s.toCharArray();
        int[] array = new int[128];
        array['a'] = 1;
        array['e'] = 1;
        array['i'] = 1;
        array['o'] = 1;
        array['u'] = 1;
        //int left = 0; 由i-k代替left
        for (int i = 0; i < k; i++) {
            if (array[chars[i]] == 1) {
                size++;
            }
        }
        int length = size;
        for (int i = k; i < chars.length; i++) {
            if (array[chars[i-k]] == 1) length--;
            //left++;
            if (array[chars[i]] == 1) length++;
            if (size < length) size = length;
        }
        return size;
    }
}

136.只出现一次的数字

原题

这道题真是巧妙地运用了位运算符异或（^）的特性，我自己也是把吝啬发挥到了极致，能不弄新的空间就不弄。

class Solution {
    public int singleNumber(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[0]^=nums[i];
        }
        return nums[0];
    }
}
🏠 返回首页 · 查看完整交互体验