对称数组问题

一般具有对称性质的数组问题可以通过正向遍历和反向遍历两个方式来解决如162题峰值元素和135题分发糖果

分发糖果

使用Arrays.fill将数组全部初始化为1,正向遍历的时候遍历1到(n-1)的位置,反向遍历的时候遍历(n-2)到0的位置,当当前的数大于上一个数的时候,糖果数量加1,由于题目条件要求满足正向遍历和反向遍历,所以应该取最大值

public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }

最长的连续序列

使用哈希表解决此问题,每次从最小的数字开始数起能够保证不计算重复的结果,上例题的最小数字分别为1.100和200,所以只要计算三次就可以得到结果

public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            //没有比它小的数字时 才进入,确保每次更新序列都是从最小的开始
            if (!num_set.contains(num - 1)) {
                int cur = num;
                int res = 1;
                //从一个序列最小的值开始不断更新序列长度
                while (num_set.contains(cur + 1)) {
                    cur += 1;
                    res += 1;
                }

                longestStreak = Math.max(longestStreak, res);
            }
        }

        return longestStreak;
    }

验证一个句子是回文串

 验证回文串是很简单的,用双指针就行了,但是这题需要把空格等符号也省去,所以要注意的是在双指针移动的时候时刻注意数组越界问题,同时注意到两个Character的API:判断是字母或者数字,转成小写字母

public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }

不同子序列

115题

使用动态规划求解,dp[i][j]的定义为从i-1到j-1的字符有几种方案可以得到,当t为空串的时候,也就是j=0的时候,空集是所有字符串的子集所以算它为1种,当s为空串的时候,因为它除了空串无法匹配任何值,所以dp[0][j]=0;

字符串匹配问题只有两种情况,1是字符相等,2是不相等;对于此题,相等的时候它的状态可以由左上侧和上侧的情况继承而来,不等的时候只能从上侧继承而来;可以这么理解当两个字符相同的时候,可以两个字符串同时去掉一个字符从而继承斜上角的结果,而不论什么情况都可以继承来自减去一个s串得到的结果

举个例子: sasa和sa,当sas和sa进行匹配的时候s和a不等,所以sas和sa的情况就等于sa和sa的情况都为一种,当sasa和sa匹配的时候,a==a,它不仅可以继承sas==s的结果2,还可以继承sas和sa的结果1所以一共是3种

i\j	" "	r	a	b	b	i	t
" "	1	0	0	0	0	0	0
r	1	1	0	0	0	0	0
a	1	1	1	0	0	0	0
b	1	1	1	1	0	0	0
b	1	1	1	2	1	0	0
b	1	1	1	3	3	0	0
i	1	1	1	3	3	3	0
t	1	1	1	3	3	3	3

public int numDistinct(String s, String t) {
        int n1=s.length();
        int n2=t.length();
        //表示s的前i-1个字符 与t的前j-1个字符有几种方案可以得到
        int[][] dp = new int[n1 + 1][n2 + 1];
        //当两者字符相等 dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
        //当两者字符不等 dp[i][j]=dp[i-1][j]
        //base
        for (int i = 0; i < n1 + 1; i++) {
            dp[i][0]=1;//空集是所有字符串的子集
        }
        //自己为空串的时候无法匹配任何字符串
        for (int i = 1; i < n2 + 1; i++) {
            dp[0][i]=0;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n1][n2];
    }

 二叉树最大路径和

 二叉树的问题需要分清每个节点需要干的事情,每次达到一个节点的时候,对路径有三种选择,停在该节点,去他的左子节点,去它的右子节点

我们提供一个深度遍历方法,返回当前节点能为父亲提供的贡献;一个子树内部能提供的最大路径等于它自己的值+左子树的贡献+右子树的贡献;一个节点能为父亲节点提供最大的贡献要么从左子树到自己,要么从右子树到自己,如果贡献小于0,则直接全部舍弃掉

int res =Integer.MIN_VALUE;
    //采用先序遍历,每次到达一个节点有三种选择:停在当前节点,走到左节点,走到右子节点
    public int maxPathSum(TreeNode root) {
       dfs(root);
       return res;
    }

    private int dfs(TreeNode root) {
        if(root==null)return 0;
        int left=dfs(root.left);
        int right=dfs(root.right);
        //一个子树内部提供的最大路径等于左子树提供的最大路径和+右子树提供的最大路径和+当前值
        res =Math.max(res,root.val+left+right);
        //计算当前节点能为父亲提供的最大贡献
        int max=Math.max(root.val+left,root.val+right);
        //如果当前贡献小于0,直接全部舍弃
        return Math.max(max, 0);

    }

填充二叉树的右侧指针

116-填充完美二叉树的右侧指针

 使用深度有限遍历,由于是完美二叉树while循环里的条件可以是左指针也可以是右指针,对于每次dfs来说它需要连接自己的左右节点随后让自己的左子节点靠右走,右子节点靠左走,继续循环

 public Node connect(Node root) {
       dfs(root);
       return root;
    }

    private void dfs(Node root) {

        if(root==null)return;
        Node left=root.left;
        Node right=root.right;
        while (left!=null){
            left.next=right;//左指针指向右指针
            left=left.right;//左指针走向右边
            right=right.left;//右指针走向左边
        }
        //递归调用左右节点
        dfs(root.left);
        dfs(root.right);
    }

117-非完美二叉树填充右指针

 这里主要使用的是bfs广度有限遍历,bfs的框架如下

public void levelOrder(TreeNode tree) {
        if (tree == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);//相当于把数据加入到队列尾部
        while (!queue.isEmpty()) {
            //poll方法相当于移除队列头部的元素
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

 依靠该框架容易写出以下代码,在层序遍历的时候连接每个节点即可

public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //每一层的数量
            int levelCount = queue.size();
            //前一个节点
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {
                //出队
                Node node = queue.poll();
                //如果pre为空就表示node节点是这一行的第一个，
                //没有前一个节点指向他，否则就让前一个节点指向他
                if (pre != null) {
                    pre.next = node;
                }
                //然后再让当前节点成为前一个节点
                pre = node;
                //左右子节点如果不为空就入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }

上述算法效率并不高因为队列加入的缘故,其实也没必要用队列来做,可以直接使用上一层已经连接号的next节点,把每行都当成是一个链表,利用上一层的链表完成下一行的指针连接工作,cur在结束完一层的连接后,重新赋值到该层的头节点处,准备下一行的操作

 public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候，为了方便操作在下一
            //层前面添加一个哑结点（注意这里是访问
            //当前层的节点，然后把下一层的节点串起来）
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空，就让pre节点
                    //的next指向他，也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后，让他赋值给cur，
            //后续继续循环，直到cur为空为止
            cur = dummy.next;//跳到下一行操作
        }
        return root;
    }

二叉树的层序遍历

也叫广度优先遍历,一般要使用一个队列结构来帮助我们进行层序遍历类似的题有,102,103,107

普通层序遍历

 属于是最基本的层序遍历框架了,在for循环结束后加入层序遍历的list,在for循环里向list填充数据

 public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        //帮助我们获取分层结构的工具人
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if(root!=null)queue.add(root);//添加root
        while (!queue.isEmpty()){
            int n=queue.size();
            //最后要加入res的list
            List<Integer> level=new ArrayList<>();
            //对当前层的所有节点进行出队操作并且将下一层的节点加入queue
            for (int i = 0; i < n; i++) {
                TreeNode node=queue.poll();//弹出当前节点
                level.add(node.val);//添加当前层的所有节点
                //加入左右节点
                if(node.left!=null) queue.add(node.left);//对于第一次进入queue的都是第二层的节点

                if(node.right!=null)queue.add(node.right);
            }
            res.add(level);
        }
        return res;
    }

锯齿形层序遍历

 使用一个变量count来决定我们当前是从尾部加入节点还是从头部加入节点

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new LinkedList<>();
        //帮助我们获取分层结构的工具人
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if(root!=null)queue.add(root);//添加root
        int count=0;
        while (!queue.isEmpty()){
            int n=queue.size();
            //最后要加入res的list
            LinkedList<Integer> level=new LinkedList<>();
            //对当前层的所有节点进行出队操作并且将下一层的节点加入queue
            for (int i = 0; i < n; i++) {
                TreeNode node=queue.poll();//弹出当前节点
                if(count%2==0)level.add(node.val);
                else level.addFirst(node.val);
                //加入左右节点
                if(node.left!=null) queue.add(node.left);//对于第一次进入queue的都是第二层的节点

                if(node.right!=null)queue.add(node.right);
            }
            count++;
            res.add(level);
        }
        return res;
    }

自底向上的层序遍历

 使用Collections的api轻易解决,也可以使用LinkedList代替ArrayList进行头插(arraylist头插增加额外开销)

 public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null)return res;
        Deque<TreeNode> deque=new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()){
            int n=deque.size();
            ArrayList<Integer> list= new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode pop = deque.pop();
                list.add(pop.val);
                if(pop.left!=null)deque.add(pop.left);
                if(pop.right!=null)deque.add(pop.right);
            }
            res.add(list);
        }
        Collections.reverse(res);
        return res;
    }

二叉树的路径总和问题

112题和113题

判断是否有路径总和

终止条件为root==null,此时一定不成功,直接return false

对于每个节点,如果该节点是叶子节点那么需要判断它的值是不是和已经削减过的sum值一致了

如果不是叶子节点需要在左子树或者右子树中继续寻找结果

 public boolean hasPathSum(TreeNode root, int sum) {
        //到最后一个节点都没有找到
        if(root == null){
            return false;
        }
        //如果已经是叶子节点了,看当前值是不是和sum相等
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        //只要左边和右边有一边成功就行
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

    }

求出路径总和

 要求出具体值的集合基本就是用回溯算法来做,只在叶子节点增加结果

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new ArrayDeque<>();
        dfs(root,targetSum,path,res);
        return res;
    }

    private void dfs(TreeNode root, int targetSum, Deque<Integer> path, List<List<Integer>> res) {
        if(root==null)return;
        path.add(root.val);
        if(root.left==null&root.right==null){
            if(targetSum==root.val){
                res.add(new ArrayList<>(path));
            }
        }
        dfs(root.left,targetSum-root.val,path,res);
        dfs(root.right,targetSum-root.val,path,res);
        path.removeLast();
    }

判断是否为平衡二叉树

题目已经说的很明确了,其定义是两个子树的高度差不能超过1,对于每个节点来说就是计算左子树和右子树的高度差,<=1则返回true;

此题使用后序遍历 左右根的遍历方式使其自底向上开始计算,因为一旦有一个不符合要求就应该直接return -1,-1会传递到最后的函数使得return false

height这个函数的定义是返回改节点子树的高度,只要最后的结果不是-1就说明运算完毕没有发现子树高度差大于1的情况

public boolean isBalanced(TreeNode root) {
        return height(root) !=-1;
    }
    //后序遍历自底向上
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

判断是否是对称的二叉树

 使用深度优先遍历,dfs返回两个节点是否是对称的

 public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return dfs(root.left,root.right);
    }

    private boolean dfs(TreeNode left, TreeNode right) {
        if(left==null&&right==null)return true;
        if(left==null||right==null)return false;
        if(left.val!=right.val)return false;
        return dfs(left.left,right.right)&&dfs(left.right,right.left);
    }

二叉搜索树

又称BST树

将有序数组转换成二叉搜索树

 找到中点递归的进行左子树和右子树的构建就行

 public TreeNode sortedArrayToBST(int[] nums) {
      return  helper(nums,0,nums.length-1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        if(left>right)return null;
        int mid=(left+right)>>1;
        TreeNode node = new TreeNode(nums[mid]);
        node.left=helper(nums,left,mid-1);
        node.right=helper(nums,mid+1,right);
        return node;
    }

有序链表转高度平衡的二叉搜索树

 由于是有序链表,其中点可以作为二叉搜索树的节点,使用快慢指针法求出链表的中点

在构建二叉搜索树的过程,我们让断开链表,使其刚好分成两份,如果是奇数链表前面会短后面会长,然后递归的调用左子节点和右子节点,由于我们是从中点开始分的所以它肯定是高度平衡的

 public TreeNode sortedListToBST(ListNode head) {
        if(head == null)return null;
        if(head.next == null)return new TreeNode(head.val);
        //slow指向当前中点 pre指向中点的前驱
        ListNode slow = head, fast = head, pre = head;
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //right指向中点的后继
        ListNode right = slow.next;
        //断开链表(此题的核心)
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);//构建左树
        root.right = sortedListToBST(right);//构建右树

        return root;
    }

判断是否是相同的树

此题与与判断是否是对称二叉树很像,只不过传入的不是左右节点而是两棵树的跟节点

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p == null || q == null) return false;

        if (p.val != q.val) return false;
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
    }

判断是否是二叉搜索树

判断二叉搜索树需要时时刻刻验证二叉搜索树的性质,根节点是否大于左子树节点,根节点是否小于右子树节点,使用两个变量min和max分别记录最小和最大值;

对于左节点来说,根节点就是最大值,最小值不需要管可以直接从上层函数中继承,反之对于右节点也一样

//是否是合理的bst 由于bst要求所有的节点都比右子树的节点小,所以添加两个节点min和max用于比较
    boolean isValidBST(TreeNode node) {
        return isValidBST(node, null, null);
    }

    boolean isValidBST(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) return true;
        if (min != null && node.val <= min.val) return false;
        if (max != null && node.val >= max.val) return false;
        //比较左边的节点是否比当前最小节点要小并且比最小节点要大
        return isValidBST(node.left, min, node) && isValidBST(node.right, node, max);
    }

通过BST查找一个数是否存在

查找一个数,根据二叉树左小右大的性质找就行,在root==null 的时候就说明该数不存在

//通过BST查找一个数是否存在
    boolean isInBST(TreeNode root, int target) {
        if (root == null) return false;
        if (root.val == target) return true;
        if (root.val > target) return isInBST(root.left, target);
        else return isInBST(root.right, target);
    }

通过BST插入一个数

插入一个数的特殊之处在于需要找到一个空的位置return 一个新的节点值,然后通过函数递归进行插入

//通过BST插入一个数
    TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);//找到空位置插入新的节点
        //BST中一般不会插入已经存在的元素
        if (root.val < val) root.right = insertIntoBST(root.right, val);
        if (root.val > val) root.left = insertIntoBST(root.left, val);
        return root;
    }

通过BST删除一个数

如果找到了这个子节点:

• 删除一个二叉搜索树节点有三种情况:如果该节点
• 两个子节点都为空或者只有一个子节点:直接使用这个子节点来代替自己的位置
• 如果当前节点有左子树和右子树:需要找到最大的左子树或者最小的右子树来代替自己的位置

如果当前值大于目标值,从左子树进行删除递归调用

如果当前值小于目标值,从右子树进行删除递归调用

//在BST删除一个数
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            //恰好是末端节点,两个子节点都为空,直接删除该节点 或者说只有一个非空子节点,那么使用它直接代替自己的位置
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            //如果当前节点有左子树和右子树
            TreeNode minNode=getMin(root.right);
            root.val=minNode.val;//交换节点
            //删除已经替换掉值的节点
            root.right=deleteNode(root.right,minNode.val);
        }else if(root.val>key)root.left=deleteNode(root.left,key);
        else root.right=deleteNode(root.right,key);
        return root;
    }

 //获得左子树中最大的那个节点或者右子树最小的那个节点来代替自己(这里使用右子树最小的那个节点)
    TreeNode getMin(TreeNode node){
        while (node.left!=null) node=node.left;
        return node;
    }

恢复二叉搜索树

以中序遍历的方式添加二叉搜索树的节点值得到的数组是升序排列的,这题的难点就在于如何确定两个被交换的节点,其找到x,y节点是这么找的,首先找到第一个不满足升序的节点,将其定位x,再找到最后一个不满足升序的节点将其定义为y,然后交换位置就可以了

List<TreeNode> res;
    public void recoverTree(TreeNode root) {
        res=new ArrayList<>();
        helper(root);
        TreeNode x=null;
        TreeNode y=null;
        //扫描遍历的结果,找出可能存在错误节点交换的节点x和y
        for (int i = 0; i < res.size() - 1; i++) {
            if(res.get(i).val>res.get(i+1).val){
                y=res.get(i+1);//找到最后一个不满足升序的节点
                if(x==null){
                    x=res.get(i);//锁定第一个不满足升序的节点
                }
            }
        }
        //如果xy不为空交换两个节点值
        if(x!=null&&y!=null){
            int temp=x.val;
            x.val=y.val;
            y.val=temp;
        }
    }

    private void helper(TreeNode root) {
        if(root==null)return;
        helper(root.left);
        res.add(root);
        helper(root.right);
    }