本文主要是介绍Leetcode 第671，680，693，696，697，704，705，720，744，766题(Java解法)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Java解leetcode，助力面试之简单10道题（九）

• 第671题 二叉树中第二小的节点
• • 解题思路
  • 代码
• 第680题 验证回文字符串 Ⅱ
• • 解题思路
  • 代码
• 第693题 交替位二进制数
• • 解题思路
  • 代码
• 第696题 计数二进制子串
• • 解题思路
  • 代码
• 第697题 数组的度
• • 解题思路
  • 代码
• 第704题 二分查找
• • 解题思路
  • 代码
• 第705题 设计哈希集合
• • 解题思路
  • 代码
• 第720题 词典中最长的单词
• • 解题思路
  • 代码
• 第744题 寻找比目标字母大的最小字母
• • 解题思路
  • 代码
• 第766题 托普利茨矩阵
• • 解题思路
  • 代码

第671题 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，root.val = min(root.left.val, root.right.val) 总成立。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

示例 1：

解释：最小的值是 2 ，第二小的值是 5 。

示例 2：

解释：最小的值是 2, 但是不存在第二小的值。

解题思路

本题使用dfs求解，首先根节点的值等于或小于它的左右子节点的值，因此判断左右子节点是否为空，都不为空则返回左右子节点中值最小的那个值。如果都为空，则不存在第二小的值。如果一个为空，则返回另一个节点值，还有一种情况就是左右子节点可能等于根节点的值，所以要继续递归找第二小的值

代码

// 二叉树中第二小的节点：dfs
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;//如果根节点为空，返回-1
        return help(root, root.val);//否则调用help函数，将根节点的值定为最小值
    }
    private int help(TreeNode root, int min) {
        if (root == null) return -1;//当前节点为空返回-1
        if (root.val > min) return root.val;//找第二小的值
        int left = help(root.left, min);//当左子树的值等于根节点的值或为空时递归左子树
        int right = help(root.right, min);//同理递归右子树
        if (left == -1) return right;//如果左子树为空，则返回右子树
        if (right == -1) return left;//如果右子树为空，则返回左子树
        return Math.min(left, right);//返回左右子树中最小的值，因为左右子树的值都大于根节点的值，因此左右子树中最小的那个，即是整个树中第二小的值
    }
}

时间复杂度为O(n),n为树的节点数
空间复杂度为O(n),存储树的节点

第680题 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1：

示例 2：

解释: 你可以删除c字符。

解题思路

本题使用双指针来解决，移动双指针判定左右指针指的字符是否相等，如果全相等则代表原字符串是回文字符串，如果移动过程中有一次左右指针所指字符不相等，则跳过左边这个字符或者右边这个字符继续匹配，如果后续都相等则还是回文字符串，如果再一次遇到字符不相等，则不是回文字符串。

代码

// 验证回文字符串 Ⅱ：双指针
class Solution {
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {//定义双指针，先判断原字符串是否为回文字符串
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) {
                ++low;
                --high;//如果左右指针所指的字符相等，则移动左右指针继续判断
            } else {
                return validPalindrome(s, low, high - 1) || validPalindrome(s, low + 1, high);//否则执行validPalindrome函数继续判断
            }
        }
        return true;
    }
    public boolean validPalindrome(String s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;//如果跳过一个字符后，左右字符仍不相等，则代表不是回文字符串
            }
        }
        return true;
    }
}

时间复杂度为O(n),n为字符串长度
空间复杂度为O(1)

第693题 交替位二进制数

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

5 的二进制表示是：101

示例 2：

解释：7 的二进制表示是：111.

示例 3：

解释：11 的二进制表示是：1011.

示例 4：

解释：10 的二进制表示是：1010.

示例 4：

解释：3 的二进制表示是：11.

解题思路

使用n&1来获取数字n的第一位数，然后将n的二进制数向右移一位，再使用n&1来和第一次获取的数相比较，如果相等，则代表不是交替二进制数，否则，将当前的n&1设为新的判断数，然后再将n的二进制数右移，循环判断，直到n为0，如果一直满足n&1与先前的n&1不相等，则代表时交替二进制数

代码

// 另一个树的子树：位运算
class Solution {
    public boolean hasAlternatingBits(int n) {
        int pre = n & 1;//首先获取第一位数
        n >>>= 1;//右移一位
        while(n != 0){//当数字右移一位不为0时
            if((n & 1) == pre)//如果右移之后的数与先前的数一样则代表不是交替二进制数
                return false;
            pre = n & 1;//否则将当前最右边的数保存
            n >>>= 1;//右移一位
        }
        return true;
    }
}

时间复杂度为O(n)n为字符串的长度
空间复杂度为O(1)

第696题 计数二进制子串

给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
重复出现的子串要计算它们出现的次数。

示例 1：

解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2：

解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

解题思路

将每一次连续的0和1的次数记录下来，因为是分组记录的，所以只要统计相邻的0和1中出现次数最小的数，将它加到结果中，比如00111011，可以记为{2,3,1,2},因此0和1之间三组最小数分别为2，1，1，所以具有相同数量的连续1和0的数为2+1+1为4

代码

// 计数二进制子串：字符串
class Solution {
    public int countBinarySubstrings(String s) {
        int ptr = 0, n = s.length(), last = 0, ans = 0;//ptr记录当前遍历到的数，last记录当前位置的前一个位置，ans为输出结果
        while (ptr < n) {
            char c = s.charAt(ptr);//当前后两数不相等时，更新ptr
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;//记录连续0或1的个数
            }
            ans += Math.min(count, last);//比较前后连续0或1的次数，将最小的值加入结果中
            last = count;//last记录之前连续0或1的个数
        }
        return ans;
    }
}

时间复杂度为O(n),n为字符串长度
空间复杂度为O(1)

第697题 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

示例 2：

解题思路

使用一个哈希表，遍历数组，如果数字再哈希表中不存在，则将该数字记录为出现1次，第一次出现位置为当前索引，最后一次出现位置为当前索引，如果该数字已经在哈希表中存在，则将出现次数加1，并更新最后一次出现位置为当前索引。遍历完之后进行比较次数，出现次数最多的数直接返回第一次和最后一次出现的差，如果有多个数的出现次数一致，则进行比较位置差，返回最小差。

代码

// 数组的度：哈希表
class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();//建立哈希表
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;//用哈希表记录出现数字的次数
                map.get(nums[i])[2] = i;//用哈希表记录最后一次出现该数字的位置
            } else {
                map.put(nums[i], new int[]{1, i, i});//记录第一次出现的位置索引
            }
        }
        int maxNum = 0, minLen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            if (maxNum < arr[0]) {
                maxNum = arr[0];//找到出现次数最多的数
                minLen = arr[2] - arr[1] + 1;//如果只有一个，则返回它最后一次出现的下标减去第一次出现的下标再减1
            } else if (maxNum == arr[0]) {//如果有多个数的出现次数相同，则进行比较
                if (minLen > arr[2] - arr[1] + 1) {
                    minLen = arr[2] - arr[1] + 1;
                }
            }
        }
        return minLen;
    }
}

时间复杂度为O(n),n为数组长度
空间复杂度为O(n)

第704题 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1：

解释: 9 出现在 nums 中并且下标为 4

示例 2：

解释: 2 不存在 nums 中因此返回 -1

解题思路

经典二分查找，取首尾两个数，再取中间值，如果中间值大于目标值，则将尾数更新为中间数前一个数，否则将首数更新为中间数后一个数，再取它们的中间值与目标值比较，直到找到中间数与目标值相等，或者首数大于尾数。

代码

// 二分查找：二分查找法
class Solution {
  public int search(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;//设left和right指向数组首尾
    while (left <= right) {
      pivot = left + (right - left) / 2;//中间数
      if (nums[pivot] == target) return pivot;//判断中间值是否等于目标值
      if (target < nums[pivot]) right = pivot - 1;//如果目标值小于中间数，则将right置为中间数前一个数
      else left = pivot + 1;//否则将left置为中间数后一个数
    }
    return -1;
  }
}

时间复杂度为O(log n),n为数组长度
空间复杂度为O(1)

第705题 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例 1：

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

解题思路

一种最简洁的方法，直接对值赋予true和false，如果执行插入操作，则将该数的返回值置为true，如果是删除操作，则将该数的返回值置为false，如果是判断是否存在该数，则同样返回先前对该数操作过的结果。

代码

// 设计哈希集合：哈希表
class MyHashSet {
    boolean[] nodes = new boolean[1000009];    
    public void add(int key) {
        nodes[key] = true;//插入置为true
    }    
    public void remove(int key) {
        nodes[key] = false;//删除置为false
    }   
    public boolean contains(int key) {
        return nodes[key];//存在操作返回先前更新的值
    }
}

时间复杂度为O(1)
空间复杂度为O(1)

第720题 词典中最长的单词

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。

示例 1：

解释：
单词"world"可由"w", “wo”, “wor”, 和 "worl"添加一个字母组成。

示例 2：

解释：
“apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply”。

解题思路

本题较难理解，大致思想是使用前缀树和dfs解决，首先建立前缀树，将各个单词的字母依次插入到前缀树上，然后进行dfs，不断更新长度和单词，最后输出最长的单词

代码

// 词典中最长的单词：前缀树
class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();//前缀树
        int index = 0;//记录长度
        for (String word: words) {
            trie.insert(word, ++index); //如果该单词存在于字符串中，则插入到前缀树上，并将长度增加1
        }
        trie.words = words;
        return trie.dfs();//用优先搜索来搜索前缀树
    }
}
class Node {
    char c;
    HashMap<Character, Node> children = new HashMap();//建立哈希表
    int end;
    public Node(char c){
        this.c = c;
    }
}
class Trie {//前缀树
    Node root;
    String[] words;
    public Trie() {
        root = new Node('0');//根设为0
    }
    public void insert(String word, int index) {//将单词和索引插入
        Node cur = root;
        for (char c: word.toCharArray()) {
            cur.children.putIfAbsent(c, new Node(c));
            cur = cur.children.get(c);
        }
        cur.end = index;
    }
    public String dfs() {//深度搜索
        String ans = "";
        Stack<Node> stack = new Stack();//建立栈
        stack.push(root);//根节点入栈
        while (!stack.empty()) {//当栈不为空时
            Node node = stack.pop();//根节点出栈
            if (node.end > 0 || node == root) {//当前节点为根节点时
                if (node != root) {//访问非根节点
                    String word = words[node.end - 1];//如果当前的单词是原单词添加一个字母形成
                    if (word.length() > ans.length() ||
                            word.length() == ans.length() && word.compareTo(ans) < 0) {
                        ans = word;//取代原单词
                    }
                }
                for (Node nei: node.children.values()) {
                    stack.push(nei);
                }
            }
        }
        return ans;
    }
}

时间复杂度为O(∑wi),wi指的是words[i]的长度
空间复杂度为O(∑wi)

第744题 寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 'a’

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

示例 6：

解题思路

本题使用二分查找，找到最左边的数，结束条件是目标数小于左边大于右边

代码

// 寻找比目标字母大的最小字母：二分查找
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int lo = 0, hi = letters.length;//lo为最低数，hi为最高数
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;//mi为中间数
            if (letters[mi] <= target) lo = mi + 1;//如果中间值不大于目标值，则将lo设为中间数加1
            else hi = mi;//否则将hi设为中间数减1
        }
        return letters[lo % letters.length];//考虑到下一个数超过了数组最大的数，因此要跳到数组第一个数，所以用lo除去数组长度
    }
}

时间复杂度为O(log n),n为数组长度
空间复杂度为O(1)

第766题 托普利茨矩阵

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

示例 1：

解释：
在上述矩阵中, 其对角线为:
“[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”。
各条对角线上的所有元素均相同, 因此答案是 True 。

示例 2：

对角线 “[1, 2]” 上的元素不同。

解题思路

遍历数组，比较斜线方向的数是否相等

代码

// 托普利茨矩阵：遍历数组
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;//m,n为行和列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] != matrix[i - 1][j - 1]) {//遍历行列，判断斜线方向是否相等
                    return false;
                }
            }
        }
        return true;
    }
}

时间复杂度为O(mn)，m，n为行和列的长度
空间复杂度为O(1)

这篇关于Leetcode 第671，680，693，696，697，704，705，720，744，766题(Java解法)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！