算法面试题汇总

算法面试题汇总大家好,我是哪吒,一个热爱编码的Java工程师,本着“欲速则不达,欲达则欲速”的学习态度,在程序猿这条不归路上不断成长,所谓成长,不过是用时间慢慢擦亮你的眼睛,少时看重的,年长后却视若鸿毛,

大家好,我是哪吒,一个热爱编码的Java工程师,本着“欲速则不达,欲达则欲速”的学习态度,在程序猿这条不归路上不断成长,所谓成长,不过是用时间慢慢擦亮你的眼睛,少时看重的,年长后却视若鸿毛,少时看轻的,年长后却视若泰山,成长之路,亦是渐渐放下执念,内心归于平静的旅程。

也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年。

算法面试题汇总

 大连星海广场


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的区别

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;
}

算法面试题汇总

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

算法面试题汇总

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;
}

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

算法面试题汇总

大连跨海大桥


 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);
    }
}

算法面试题汇总

大连棒棰岛


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);
}

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

算法面试题汇总

思路及算法

“回文串”是一个正读和反读都一样的字符串,比如“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());
}

 算法面试题汇总

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

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框架总结】SSH、SSM、Springboot

超详细的springBoot学习笔记

常见数据结构与算法整理总结

Java设计模式:23种设计模式全面解析

Java面试题总结(附答案)

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

MySql知识体系总结

Linux知识体系总结

【Vue基础知识总结 1】Vue入门

今天的文章算法面试题汇总分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/62696.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注