剑指offer：55-58记录

落日映苍穹つ 2023-07-13 04:18 3阅读 0赞

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 \[3,9,20,null,null,15,7\]，

3  
/ \\  
9 20  
/ \\  
15 7  
返回它的最大深度 3 。

思路：递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }

--------------------

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 \[3,9,20,null,null,15,7\]

3  
/ \\  
9 20  
/ \\  
15 7  
返回 true 。

示例 2:

给定二叉树 \[1,2,2,3,3,null,null,4,4\]

1  
/ \\  
2 2  
/ \\  
3 3  
/ \\  
4 4  
返回 false 。

递归，-1代表不是。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return depth(root) != -1;
        }
        private int depth(TreeNode root) {
            if (root == null) return 0;
            int left = depth(root.left);
            if(left == -1) return -1;
            int right = depth(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }

--------------------

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = \[2,7,11,15\], target = 9  
输出：\[2,7\] 或者 \[7,2\]  
示例 2：

输入：nums = \[10,26,30,31,47,60\], target = 40  
输出：\[10,30\] 或者 \[30,10\]

限制：

1 <= nums.length <= 10^5  
1 <= nums\[i\] <= 10^6

双指针

class Solution {
        public int[] twoSum(int[] nums, int target) {
            int left=0,right=nums.length-1;
            while(left<right){
                if (nums[left]+nums[right]==target){
                    return new int[]{nums[left],nums[right]};
                }
                else if (nums[left]+nums[right]<target)
                    left++;
                else
                    right--;
            }
            return null;
        }
    }

--------------------

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：

输入: "the sky is blue"  
输出: "blue is sky the"  
示例 2：

输入: " hello world! "  
输出: "world! hello"  
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。  
示例 3：

输入: "a good example"  
输出: "example good a"  
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。  
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。  
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

py大法好。

class Solution(object):
    
        def reverseWords(self, s):
    
            return " ".join(s.split()[::-1])

--------------------

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。