算法面试题汇总

怼烎@ 2022-09-07 04:56 168阅读 0赞

> 大家好，我是哪吒，一个热爱编码的Java工程师，本着“欲速则不达，欲达则欲速”的学习态度，在程序猿这条不归路上不断成长，所谓成长，不过是用时间慢慢擦亮你的眼睛，少时看重的，年长后却视若鸿毛，少时看轻的，年长后却视若泰山，成长之路，亦是渐渐放下执念，内心归于平静的旅程。
> 
> 也许，我们永远都不会知道自己能走到何方，遇见何人，最后会变成什么样的人，但一定要记住，能让自己登高的，永远不是别人的肩膀，而是挑灯夜战的自己，人生的道路刚刚启程，当你累了倦了也不要迷茫，回头看一看，你早已不再是那个年少轻狂的少年。

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70][] ##

大连星海广场

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

## 1、LeetCode.1 两数之和 ##

### 题目 ###

> 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
> 
> 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
> 
> 你可以按任意顺序返回答案。
> 
> 示例 1：
> 
> 输入：nums = \[2,7,11,15\], target = 9  
> 输出：\[0,1\]  
> 解释：因为 nums\[0\] + nums\[1\] == 9 ，返回 \[0, 1\] 。
> 
> 示例2：
> 
> 输入：nums = \[3,2,4\], target = 6  
> 输出：\[1,2\]  
> 示例3：
> 
> 输入：nums = \[3,3\], target = 6  
> 输出：\[0,1\]  
> 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

### 小编菜解 ###

/**
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        for(int i = 0;i<nums.length;i++){
            for (int j = 0; j < nums.length - 1; j++) {
                if((nums[i] + nums[j]) == target){
                    ret[0] = i;
                    ret[1] = j;
                    return ret;
                }
            }
        }
        return null;
    }

### 大佬指点江山 ###

private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static int[] twoSumByMap(int[] nums, int target) {
        int[] indexs = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                indexs[0] = i;
                indexs[1] = map.get(nums[i]);
            }
            map.put(target - nums[i],i);
        }
        return indexs;
    }

## 2、LeetCode.7 整数反转 ##

### 题目 ###

> 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
> 
> 如果反转后整数超过 32 位的有符号整数的范围 \[−231,  231 − 1\] ，就返回 0。

### 小编菜解 ###

private static int reverse01(int param){
        String fh = "";
        String str = String.valueOf(param);
        StringBuilder builder = null;
        if(param < 0){
            fh = "-";
            builder = new StringBuilder(str.substring(1));
        }else{
            builder = new StringBuilder(str);
        }
        String value = builder.reverse().toString();
        return Integer.parseInt(fh + Integer.parseInt(value););
    }

提交失败，存在 Exception in thread "main" java.lang.NumberFormatException: For input string: "9646324351"问题

### 解题思路 ###

> // 弹出 x 的末尾数字 digit  
> digit = x % 10  
> x /= 10
> 
> // 将数字 digit 推入 rev 末尾  
> rev = rev \* 10 + digit

### 大佬指点江山 ###

private static int reverse0(int x){
        int result = 0;
        while(x != 0) {
            int tmp = result; // 保存计算之前的结果
            result = (result * 10) + (x % 10);
            x /= 10;
            // 将计算之后的结果 / 10，判断是否与计算之前相同，如果不同，证明发生溢出，返回0
            if (result / 10 != tmp) return 0;
        }
        return result;
    }

## 3、LeetCode 9.回文数 ##

### 题目 ###

> 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
> 
> 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

### 小编菜解 ###

public static boolean isPalindrome(int x) {
        int compare = x;
        if (x < 0){
            return false;
        }
        int result = 0;
        while(x != 0) {
            int tmp = result; // 保存计算之前的结果
            result = (result * 10) + (x % 10);
            x /= 10;
        }
        if (result == compare) {
            return true;
        }
        return false;
    }

so easy，提交通过了。身为小菜的我，对官方大神的解法很好奇，于是，我打开了官方答案，闪瞎我的双眼，我的解法简直low爆了。

我的解法会有一个致命的问题，那就是如果反转后的数字大于int.MAX，我们将遇到整数溢出问题。

思路及算法  
为了避免数字反转可能导致的溢出问题，为什么不考虑只反转数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？

由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，**当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。**

### 大佬指点江山 ###

public static boolean isPalindrome2(int x) {
        //当为负数或为以0结尾的数，反转肯定不等
        if(x < 0 || (x%10 == 0 && x != 0)){
            return false;
        }
     
        int revert = 0;
        //当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。
        while (x > revert){
            revert = (revert * 10) + (x % 10);
            x /= 10;
        }
     
        // 当数字长度为奇数时，我们可以通过 revert/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revert = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revert || x == revert / 10;
    }

## 4、LeetCode 13.罗马数字转数字 ##

### 题目 ###

> 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
> 
> 字符          数值  
> I             1  
> V             5  
> X             10  
> L             50  
> C             100  
> D             500  
> M             1000
> 
> 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
> 
> 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
> 
> I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。  
> X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。   
> C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。  
> 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

### 小编菜解 ###

/**
     * 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
     */
    public static int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            int value = map.get(s.charAt(i));
            if((i + 1) < s.length() && value < map.get(s.charAt(i + 1))){
                ret = ret - value;
            }else {
                ret = ret + value;
            }
        }
        return ret;
    }

无情啊，居然和大神解答的一模一样，有进步。

## 5、LeetCode 14.最大公共前缀 ##

### 题目 ###

> 编写一个函数来查找字符串数组中的最长公共前缀。
> 
> 如果不存在公共前缀，返回空字符串 `""`。

### 小编菜解 ###

/**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * 输入：strs = ["flower","flow","flight"]
     * 输出："fl"
     */
    public static String longestCommonPrefix(String[] strs) {
        Integer index = 0;
        int suffixNum = 0;
        //key为第一位到最后一位的下角标，value为对应位置的值
        Map<Integer, Character> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            if(!map.containsKey(index)){
                map.put(index, strs[i].charAt(index));
            }
            if(map.containsKey(index)){
                int equalNum = 0;
                for (int j = i+1; j < strs.length; j++) {
                    if(map.get(index) == strs[j].charAt(i)){
                        equalNum++;
                    }
                }
                if(equalNum == strs.length-1){
                    suffixNum++;
                }
            }
            index++;
        }
        return strs[0].substring(0,suffixNum);
    }

### 大佬指点江山 ###

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

## 6、LeetCode 20.有效的括号 ##

### 题目 ###

> 给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串 s ，判断字符串是否有效。
> 
> 有效字符串需满足：
> 
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。

### 小编菜解 ###

public static boolean isValid(String s) {
        if (s.length()%2 != 0) return false;
        Map<Character,Character> hashMap = new HashMap<Character,Character>(){
       {
            put(')','(');
            put('}','{');
            put(']','[');
        }};
        //"{[]}"
        Queue<Character> queue = new LinkedList<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(hashMap.containsKey(c)){
                char t = queue.peek();
                System.out.println(t);//这个地方弹出的是{
                char tt = hashMap.get(c);//而这个对应的是],,上一处peek应该取得[
                System.out.println(tt);
                System.out.println(queue.peek() != hashMap.get(c));
                if (queue.isEmpty() || queue.peek() != hashMap.get(c)){
                    return false;
                }
                queue.poll();
            }else{
                queue.offer(c);
            }
        }
        return queue.isEmpty();
    }

### 思路及算法 ###

> 判断括号的有效性可以使用「栈」这一数据结构来解决。
> 
> 当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 ss 无效，返回 \\text\{False\}False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
> 
> 在遍历结束后，如果栈中没有左括号，说明我们将字符串 ss 中的所有左括号闭合，返回True，否则返回False。
> 
> 注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回False，省去后续的遍历判断过程。

### 大佬指点江山 ###

public static boolean isValid(String s){
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
     
        Map<Character, Character> pairs = new HashMap<Character, Character>() {
       {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

思路和我的思路完全一致，就是我使用的是单向队列，结果就是失败，加油吧！

[Java中Queue和Deque的区别][Java_Queue_Deque]

## 7、LeetCode 26.删除有序数组中的重复项 ##

### 题目 ###

> 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
> 
> 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
> 
> 说明:
> 
> 为什么返回数值是整数，但输出的答案是数组呢?
> 
> 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

### 小编菜解 ###

public static Integer[] removeDuplicates(Integer[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        List<Integer> tempList = Arrays.asList(nums);
        for (int i = tempList.size() - 1; i >= 0; i--) {
            Integer current = tempList.get(i);
            if(i-1>0){
                Integer next = tempList.get(i - 1);
                if(next == current){
                    tempList.remove(current);
                }
            }
        }
        Integer[] ret = new Integer[tempList.size()];
        tempList.toArray(ret);
        return ret;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1][]

为什么为这样呢？我记得list是可以remove的啊，百思不得其解，查一下源码，猛然发现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2][]

Arrays的内部类ArrayList和java.util.ArrayList都是继承AbstractList，remove、add等方法在AbstractList中是默认throw UnsupportedOperationException而且不作任何操作。java.util.ArrayList重写这些方法而Arrays的内部类ArrayList没有重写，所以会抛出异常。

### 小编菜解改进版  ###

public static Integer[] removeDuplicates(Integer[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        List<Integer> tempList = Arrays.asList(nums);
        List<Integer> list = new ArrayList<>(tempList);
        for (int i = list.size() - 1; i >= 0; i--) {
            Integer current = list.get(i);
            if(i-1>0){
                Integer next = list.get(i - 1);
                if(next == current){
                    list.remove(current);
                }
            }
        }
        Integer[] ret = new Integer[list.size()];
        list.toArray(ret);
        return ret;
    }

不报错了，结果也对，perfect！

### 思路及算法 ###

相等的元素在数组中的下标一定是连续的。利用数组有序的特点，可以通过双指针的方法删除重复元素。

### 大佬指点江山 ###

public static int removeDuplicates2(Integer[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }

我去，无情。我的解法果然很菜，题意都没读懂，人家要的是长度，你返回一个数组，作甚？？

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3][] ##

大连跨海大桥

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

##  8、LeetCode 28.实现strStr ##

### 题目 ###

> 实现 strStr() 函数。
> 
> 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
> 
> 说明：
> 
> 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
> 
> 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

### 小编菜解 ###

public static int strStr(String haystack, String needle) {
        if(haystack == null || !haystack.contains(needle)){
            return -1;
        }
        if(needle == ""){
            return 0;
        }
     
        int strLg = haystack.length();
        int findLg = needle.length();
        for (int i = 0; i < strLg; i++) {
            char c = haystack.charAt(i);
            if (c == needle.charAt(0) && i+findLg <= strLg){
                String temp = haystack.substring(i,i + findLg);
                if (temp.equals(needle)){
                    return i;
                }
            }
        }
        return -1;
    }

没看出有什么问题，可是提交总是提示解答错误，也是无奈。

### 大佬指点江山 ###

public static int strStr(String haystack, String needle) {
        int strLg = haystack.length();
        int findLg = needle.length();
        for (int i = 0; i+findLg <= strLg; i++) {
            boolean flag = true;
            for (int j = 0; j < findLg; j++) {
                if (haystack.charAt(i+j)!=needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            if (true == flag){
                return i;
            }
        }
        return -1;
    }

感觉大神的解法还没我的解法简单呢？可我的为何一直提交都是出错，哎，无奈。

## 9、LeetCode 35.搜索插入位置 ##

### 题目 ###

> 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
> 
> 请必须使用时间复杂度为 O(log n) 的算法。

### 小编菜解  ###

/**
     * 输入: nums = [1,3,5,6], target = 5
     * 输出: 2
     *
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     */
    public static int searchInsert(int[] nums, int target){
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target){
                return i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < target){
                if(i < nums.length - 1 && nums[i+1] > target){
                    return i+1;
                }
                if(nums[nums.length - 1] <target){
                    return nums.length;
                }
            }else if(nums[0] > target){
                return 0;
            }
        }
        return -1;
    }

### 思路及算法 ###

> 题意为寻找一个目标值，此类问题都可以使用二分查找。

### 大佬指点江山 ###

public static int searchInsert2(int[] nums, int target){
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int index = n;
        while (left <= right){
            int mid = left + (right - left)/2;
            if (target <= nums[mid]) {
                index = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return index;
    }

## 10、LeetCode 58.最后一个单词的长度 ##

### 题目 ###

> 给你一个字符串 `s`，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
> 
> **单词** 是指仅由字母组成、不包含任何空格字符的最大子字符串。

### 小编菜解 ###

public static int lengthOfLastWord(String s) {
        String temp = s.trim();
        String[] arr = temp.split(" ");
        String find = arr[arr.length-1];
        return find.length();
    }

### 大佬指点江山 ###

public int lengthOfLastWord(String s) {
        int end = s.length() - 1;
        int start = 0;
        while (end > 0 && s.charAt(end) == ' '){
            end--;
        }
        start = end;
        while (start >= 0 &&s.charAt(start) != ' '){
            start--;
        }
        return end - start;
    }

## 11、LeetCode 94.二叉树的中序遍历 ##

### 题目 ###

给定一个二叉树的根节点 `root` ，返回它的 中序 遍历。

### 大佬指点江山 ###

/**
     * 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<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            inorder(root, res);
            return res;
        }
     
        public void inorder(TreeNode root, List<Integer> res) {
            if (root == null) {
                return;
            }
            inorder(root.left, res);
            res.add(root.val);
            inorder(root.right, res);
        }
    }

## 12、LeetCode 100.相同的树 ##

### 题目 ###

> 给你两棵二叉树的根节点 `p` 和 `q` ，编写一个函数来检验这两棵树是否相同。
> 
> 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

### 小编菜解 ###

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

## 13、121.买卖股票的最佳时机 ##

### 题目 ###

> 给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。
> 
> 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
> 
> 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

### 小编菜解 ###

public static int maxProfit(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int temp = nums[j] - nums[i];
                if (temp > max){
                    max = temp;
                }
            }
        }
        return max;
    }

### 大佬指点江山 ###

public class Solution {
        public int maxProfit(int prices[]) {
            int minprice = Integer.MAX_VALUE;
            int maxprofit = 0;
            for (int i = 0; i < prices.length; i++) {
                if (prices[i] < minprice) {
                    minprice = prices[i];
                } else if (prices[i] - minprice > maxprofit) {
                    maxprofit = prices[i] - minprice;
                }
            }
            return maxprofit;
        }
    }

## 14、LeetCode 101.对称二叉树 ##

### 题目 ###

> 给定一个二叉树，检查它是否是镜像对称的。

### 小编菜解 ###

class Solution {
        public boolean isSymmetric(TreeNode root) {
            return check(root,root);
        }
     
        private boolean check(TreeNode p, TreeNode q){
            if(p == null && q == null){
                return true;
            }
            if(p == null || q == null){
                return false;
            }
            return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
        }
    }

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 4][] ##

大连棒棰岛

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

## 15、LeetCode 104.二叉树的最大深度 ##

### 题目 ###

> 给定一个二叉树，找出其最大深度。
> 
> 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
> 
> **说明:** 叶子节点是指没有子节点的节点。

### 小编菜解 ###

class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            //要算二叉树的最大深度，可以递归算出左右子树的最大深度，然后+1就可以了
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return left > right ? left + 1 : right + 1;
        }
    }

## 16、LeetCode 108.将有序数组转换为二叉搜索树 ##

### 题目 ###

> 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
> 
> 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

### 小编解题思路 ###

> 选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡。
> 
> 确定平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树，因此可以通过递归的方式创建平衡二叉搜索树。

### 小编菜解 ###

class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return transfer(nums, 0, nums.length - 1);
        }
     
        private TreeNode transfer(int[] nums, int left, int right){
            if(left > right){
                return null;
            }
            int mid = left + (right - left)/2;
            TreeNode root  = new TreeNode(nums[mid]);
            root.left = transfer(nums, left, mid - 1);
            root.right = transfer(nums, mid + 1, right);
            return root;
        }
    }

## 17、LeetCode 125.验证回文串 ##

### 题目 ###

> 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
> 
> 说明**：**本题中，我们将空字符串定义为有效的回文串。

### 小编菜解 ###

public static boolean isPalindrome(String s) {
        // 通过正则表达式只获取数字和字母部分
        s=s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
        // 回文串是指中间分隔，前面的和后面的revert一样
        int length = s.length();
        String left = "";
        String right = "";
        if (length%2 != 0){
            left = s.substring(0,length/2);
            right = s.substring(length/2+1,length);
            right = new StringBuilder(right).reverse().toString();
        }else{
            int mid = length/2;
            left = s.substring(0,mid);
            right = s.substring(mid,length);
            right = new StringBuilder(right).reverse().toString();
        }
        return left.equals(right);
    }

### 虽然执行通过了，但效率堪忧啊。 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 5][]

### 思路及算法 ###

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

所以为什么要中间分隔呢，直接反转，对比反转后的和初始的，不就完事了？菜啊。

### 小菜改进版 ###

public static boolean isPalindrome3(String s) {
        // 通过正则表达式只获取数字和字母部分
        s=s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
        return s.equals(new StringBuilder(s).reverse().toString());
    }

效率依旧很低，因为正则的缘故吧。

### 大佬指点江山 ###

public static boolean isPalindrome(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)){
                builder.append(Character.toLowerCase(c));
            }
        }
        return builder.toString().equals(builder.reverse().toString());
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 6][]

差距还是很明显的，能不用正则就不要用正则表达式。

## 18、LeetCode 136.只出现一次的数字 ##

### 题目 ###

> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
> 
> 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

### 小编菜解 ###

/**
     * 暴力算法，当前元素与其它元素进行比较，如果有相等的，则表示出现不止一遍，不等，则表示唯一
     */
    public static int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for (int j = 0; j < nums.length; j++) {
                if (i != j){
                    if (nums[i] == nums[j]){
                        flag = false;
                        break;
                    }
                }
            }
            if (flag){
                return nums[i];
            }
        }
        return 0;
    }

### 大佬指点江山 ###

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

public static int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

## 19、LeetCode 169.多数元素 ##

### 题目 ###

> 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
> 
> 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

### 小编菜解 ###

public static int majorityElement(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
     
        for (int i = 0; i < nums.length; i++) {
            int sum = 1;
            for (int j = 0; j < nums.length; j++) {
                if (i != j){
                    if (nums[i] == nums[j]){
                        sum++;
                    }
                }
            }
     
            if (sum > nums.length/2){
                return nums[i];
            }
        }
        return 0;
    }

### 小编菜解改进版 ###

public static int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i]) + 1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > nums.length/2){
                return entry.getKey();
            }
        }
        return 0;
    }

执行用时少了不止一点点啊，进步显著，加油。

### 大佬指点江山 ###

public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int mid = nums.length/2;
        return nums[mid];
    }

纳尼？还可以这样玩？思考思考，还真是这样，因为要取得众数，众数一定大于半数，如果排序完之后，这个数组的最中间肯定属于众数，牛逼plus。

## 20、LeetCode 704.二分查找 ##

### 题目 ###

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

### 小编菜解 ###

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

### 大佬指点江山 ###

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

差了一个等号，差之毫厘谬以千里啊。

## 21、LeetCode 278.第一个错误的版本 ##

### 题目 ###

> 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
> 
> 假设你有 n 个版本 \[1, 2, ..., n\]，你想找出导致之后所有版本出错的第一个错误的版本。
> 
> 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

### 示例 ###

> 输入：n = 5, bad = 4  
> 输出：4  
> 解释：  
> 调用 isBadVersion(3) -> false   
> 调用 isBadVersion(5) -> true   
> 调用 isBadVersion(4) -> true  
> 所以，4 是第一个错误的版本。

### 思路及算法 ###

> 因为题目要求尽量减少调用检查接口的次数，所以不能对每个版本都调用检查接口，而是应该将调用检查接口的次数降到最低。
> 
> 注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。
> 
> 这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O(\\log n)O(logn) 次。

### 小编菜解 ###

public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int left = 1, right = n;
            while (left < right) { // 循环直至区间左右端点相同
                int mid = left + (right - left) / 2; // 防止计算时溢出
                if (isBadVersion(mid)) {
                    right = mid; // 答案在区间 [left, mid] 中
                } else {
                    left = mid + 1; // 答案在区间 [mid+1, right] 中
                }
            }
            // 此时有 left == right，区间缩为一个点，即为答案
            return left;
        }
    }

**复杂度分析**

*  时间复杂度：O(\\log n)O(logn)，其中 nn 是给定版本的数量。
 *  空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量。

往期精彩内容：

[Java知识体系总结][Java]

[【全栈最全Java框架总结】SSH、SSM、Springboot][Java_SSH_SSM_Springboot]

[超详细的springBoot学习笔记][springBoot]

[常见数据结构与算法整理总结][Link 1]

[Java设计模式：23种设计模式全面解析][Java_23]

[Java面试题总结（附答案）][Java 1]

[10万字208道Java经典面试题总结(附答案，建议收藏)][10_208_Java]

[MySql知识体系总结][MySql]

[Linux知识体系总结][Linux]

[【Vue基础知识总结 1】Vue入门][Vue_ 1_Vue]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70]: /images/20220829/448435426e11440aa0d65dd2faddd3c0.png
[Java_Queue_Deque]: https://blog.csdn.net/guorui_java/article/details/119738150
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1]: /images/20220829/7bedf1d764354aafaf0c324fd191987a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2]: /images/20220829/826ae3ba617549d0bea844cc3ae09e28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3]: /images/20220829/4f5dc46f8dea4f6eb04d58ff78308ac8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 4]: /images/20220829/79e19a8d973c43968ea67643231e96d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 5]: /images/20220829/250acbd0480a441c9645b56a042cf546.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 6]: /images/20220829/4c7dd532afd64d4489aa80fa4703e0c7.png
[Java]: https://blog.csdn.net/guorui_java/article/details/112391105
[Java_SSH_SSM_Springboot]: https://blog.csdn.net/guorui_java/article/details/104018528
[springBoot]: https://blog.csdn.net/guorui_java/article/details/104137262
[Link 1]: https://blog.csdn.net/guorui_java/article/details/106217472
[Java_23]: https://blog.csdn.net/guorui_java/article/details/104026988
[Java 1]: https://blog.csdn.net/guorui_java/article/details/107803283
[10_208_Java]: https://blog.csdn.net/guorui_java/article/details/119299329
[MySql]: https://blog.csdn.net/guorui_java/article/details/118558095
[Linux]: https://blog.csdn.net/guorui_java/article/details/117430091
[Vue_ 1_Vue]: https://blog.csdn.net/guorui_java/article/details/106917601