/**
 * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
 *
 * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
 *
 * 例如，121 是回文，而 123 不是。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/palindrome-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param x 整数x
 * @return 是否为回文数
 */

2、个人解法

解法1、转化为字符数组前后对比

执行用时：6 ms, 在所有 Java 提交中击败了41.76%的用户

内存消耗：41.4 MB, 在所有 Java 提交中击败了7.44%的用户


    public static boolean isPalindrome(int x) {
        char[] xStrArr = (x+"").toCharArray();
        int xStrArrLen=xStrArr.length;
        for (int i = 0; i < xStrArrLen/2; i++) {
            if(xStrArr[i]!=xStrArr[xStrArrLen-i-1]){
                return false;
            }
        }
        return true;
    }

解法2：直接比较

执行用时：14 ms, 在所有 Java 提交中击败了5.62%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了12.85%的用户


public static boolean isPalindrome(int x) {
        boolean flag=true;
        if (x<0){
            return false;
        }
        String xStr=x+"";
        int xLen=xStr.length();
 
        String step="1";
        for (int i = 0; i < xLen-1; i++) {
            step=step+"0";
        }
        int xInt = Integer.parseInt(step);
        for (int i = 0; i < xLen/2; i++) {
            if (x%10!=x/xInt){
                flag=false;
                break;
            }else {
                x=((x%xInt)/10);
                xInt=xInt/100;
            }
        }
 
        return flag;
}

解法3：字符串反转

执行用时：8 ms, 在所有 Java 提交中击败了13.25%的用户

内存消耗：41 MB, 在所有 Java 提交中击败了43.19%的用户


public static boolean isPalindrome(int x) {
    StringBuilder xStr = new StringBuilder(x+"");
    return xStr.reverse().toString().equals(x + "");
}

3、官方解法


/**
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/palindrome-number/solution/hui-wen-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
 
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
 
        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
}

二、罗马数字转数字

1、个人解法


{
        String[] numMapArr=new String[]{"I", "V", "X", "L", "C", "D","M","a","b","c","d","e","f"};
        Integer[] numMapsArr=new Integer[]{1, 5, 10, 50, 100, 500,1000,4, 9, 40, 90, 400, 900};
        String[] specialNumArr=new String[]{"IV", "IX", "XL", "XC", "CD", "CM"};
        String[] specialNumsArr=new String[]{"a", "b", "c", "d", "e", "f"};
        String res=s;
        for (int i = 0; i < specialNumArr.length; i++) {
            res=res.replace(specialNumArr[i],specialNumsArr[i]);
        }
        Map<String,Integer> numMap=new HashMap<>();
        for (int i = 0; i < numMapArr.length; i++) {
            numMap.put(numMapArr[i],numMapsArr[i]);
        }
        int resN=0;
        for (int i = 0; i < res.length(); i++) {
            resN=resN+ numMap.get(res.charAt(i)+"");
        }
        return resN;
    }

2、官方解法


Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};
 
    public int romanToInt(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
 
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/roman-to-integer/solution/luo-ma-shu-zi-zhuan-zheng-shu-by-leetcod-w55p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、第14题，难度：简单

1、题目描述

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串""。
 *
 * 示例 1：
 *
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 *
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param strs
 * @return
 */

2、个人解法

执行用时：4 ms, 在所有 Java 提交中击败了11.92%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了5.02%的用户


    public static String longestCommonPrefix(String[] strs) {
        String res="";
        int strsLen=strs.length;
        int minLen=strs[0].length();
        List<String> resList=new ArrayList<>();
        for (int i = 1; i < strsLen; i++) {
            if (minLen>strs[i].length()){
                minLen=strs[i].length();
            }
        }
        for (int j = 0; j < minLen; j++) {
            for (int i = 0; i < strsLen; i++) {
                resList.add(strs[i].charAt(j)+"");
            }
            boolean flag=true;
            for (int s = 1; s < resList.size(); s++) {
                if (!(resList.get(0)).equals(resList.get(s))){
                    flag=false;
                }
            }
            if (flag){
                res=res+resList.get(0);
            }else {
                return res;
            }
            resList.clear();
        }
        return res;
    }

3、官方解法


public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }
 
    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }

四、第20题难度：简单

1、题目描述

/**
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @param s
 * @return
 */

2、个人解法

模拟栈解法

执行用时：3 ms, 在所有 Java 提交中击败了11.46%的用户

内存消耗：39.4 MB, 在所有 Java 提交中击败了66.26%的用户


public static boolean isValid(String s) {
        int sLen = s.length();
        if (sLen % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < sLen; i++) {
            if (map.containsKey(s.charAt(i))) {
                list.add(s.charAt(i));
            } else {
                if (list.size() != 0) {
                    if (s.charAt(i) != map.get(list.get(list.size() - 1))) {
                        return false;
                    }
                    list.remove(list.size() - 1);
                } else {
                    return false;
                }
            }
            System.out.println("--" + list);
        }
        if (list.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

3、官方解法


public 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();
    }
 
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

五、第58题：最后一个单词的长度，难度：简单

1、题目描述

/**
 * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
 *
 * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
 *
 * 示例 1：
 *
 * 输入：s = "Hello World"
 * 输出：5
 * 解释：最后一个单词是“World”，长度为5。
 * 示例 2：
 *
 * 输入：s = "   fly me   to   the moon  "
 * 输出：4
 * 解释：最后一个单词是“moon”，长度为4。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/length-of-last-word
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param s
 * @return
 */

2、个人解法

去掉字符串两边的空格，然后返回最后一个空格的位置到字符串结尾位置的长度。

0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.5 MB, 在所有 Java 提交中击败了78.57%的用户


public static int lengthOfLastWord(String s) {
    s = s.trim();
    return s.substring(s.lastIndexOf(" ") + 1).length();
}

3、官方解法


class Solution {
    public int lengthOfLastWord(String s) {
        int index = s.length() - 1;
        while (s.charAt(index) == ' ') {
            index--;
        }
        int wordLength = 0;
        while (index >= 0 && s.charAt(index) != ' ') {
            wordLength++;
            index--;
        }
        return wordLength;
    }
}

六、第66题：加一，难度：简单

1、题目描述

/**
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
 *
 * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
 *
 * 你可以假设除了整数 0 之外，这个整数不会以零开头。
 *
 * 示例1：
 *
 * 输入：digits = [1,2,3]
 * 输出：[1,2,4]
 * 解释：输入数组表示数字 123。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/plus-one
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param digits
 * @return
 */

2、个人解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了79.14%的用户


public int[] plusOne(int[] digits) {
        int len=digits.length;
        digits[len-1]+=1;
        for (int i = len-1; i >0; i--) {
            if(digits[i]==10){
                digits[i]=0;
                digits[i-1]+=1;
            }
        }
        if (digits[0]==10){
            int[] a=new int[len+1];
            a[0]=1;digits[0]=0;
            for (int i = 0; i < len; i++) {
                a[i+1]=digits[i];
            }
            return a;
        }
        return digits;
}

3.官方解法


    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }
 
        // digits 中所有的元素均为 9
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }
 
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/plus-one/solution/jia-yi-by-leetcode-solution-2hor/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

七、第69题：x的平方根，难度：简单

1、题目描述

/**
 * 给你一个非负整数 x ，计算并返回x的 算术平方根 。
 * <p>
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * <p>
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sqrtx
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @param x
 * @return
 */

2、个人解法

解法1：从0开始平方

执行用时：22 ms, 在所有 Java 提交中击败了9.30%的用户

内存消耗：38.7 MB, 在所有 Java 提交中击败了58.13%的用户


    public static int mySqrt(int x) {
        int y=0;
        if (x>=2147395600){
            return 46340;
        }
        for (int i = 0; i < x+1; i++) {
            if (i*i==x){
                return i;
            }else if (i*i>x){
                return i-1;
            }
            System.out.println("i:"+i+",y:"+y);
        }
        return y;
    }

解法2 类似二分搜索

执行用时：7 ms, 在所有 Java 提交中击败了11.20%的用户

内存消耗：38.6 MB, 在所有 Java 提交中击败了79.20%的用户


public static int mySqrt(int x) {
        int y = 0;
        if (x >= 2147395600) {
            return 46340;
        }
        if (x == 1 || x == 2) {
            return 1;
        }
        if (x == 0) {
            return 0;
        }
        int flag = 0;
        for (int i = x / 2; i < x + 1; i = i / 2) {
            if (i * i == x) {
                return i;
            } else if (i * i > x) {
            } else if (i < 46340) {
                flag = i;
                break;
            }
        }
        if (flag != 0) {
            for (int i = flag; i < x; i++) {
                if (i * i == x) {
                    return i;
                } else if (i * i > x) {
                    return i - 1;
                } else if (i >= 46340) {
                    return 46340;
                }
            }
        }
        return y;
    }

3、官方解法

（另有二分查找法和牛顿迭代法）


public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
 
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

八、第125题：验证回文数，难度：简单

1、题目描述

/**
 * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
 *
 * 字母和数字都属于字母数字字符。
 *
 * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入: s = "A man, a plan, a canal: Panama"
 * 输出：true
 * 解释："amanaplanacanalpanama" 是回文串。
 * 示例 2：
 *
 * 输入：s = "race a car"
 * 输出：false
 * 解释："raceacar" 不是回文串。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

2、个人解法

执行用时: 19 ms

内存消耗: 42.6 MB

先大写转小写，再根据ACSII码值替换不满足要求的字符


    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
            if (String.valueOf(s.charAt(i)).hashCode() < 48 || (String.valueOf(s.charAt(i)).hashCode() > 57 && String.valueOf(s.charAt(i)).hashCode() < 97) || String.valueOf(s.charAt(i)).hashCode() > 122) {
                s = s.replace(s.charAt(i) + "", " ");
            }
        }
        s = s.replaceAll(" ", "");
        StringBuilder str = new StringBuilder(s);
        return (str + "").equals((str.reverse() + ""));
    }

3、官方解法

双指针


class Solution {
    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;
    }
}

九、第35题：搜索插入位置，难度：简单

1、题目描述

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * <p>
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例2:
 * <p>
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/search-insert-position
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @param nums
 * @param target
 * @return
 */

2、个人解法

暴力解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40.8 MB, 在所有 Java 提交中击败了85.08%的用户


    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] >= target) {
                return i;
            }
            if (i == len - 1) {
                return len;
            }
        }
        return 0;
    }

3、官方解法

二分搜索


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

十、第374题：猜数字大小

1、题目描述

/**
 * 猜数字游戏的规则如下：
 *
 * 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
 * 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
 * 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
 *
 * -1：我选出的数字比你猜的数字小 pick < num
 * 1：我选出的数字比你猜的数字大 pick > num
 * 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
 * 返回我选出的数字。
 *
 * 示例 1：
 *
 * 输入：n = 10, pick = 6
 * 输出：6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/guess-number-higher-or-lower
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

2、个人解法

二分查找

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.2 MB, 在所有 Java 提交中击败了55.51%的用户


    public int guessNumber(int n) {
        int low=1,high=n;
        while (low<=high){
//            try{ Thread.currentThread().sleep(1000);//毫
//                 }catch(Exception e){}
            int mid=(high-low)/2+low;
 
            int guess = guess(mid);
            if (guess==1){
                System.out.println("猜的数是："+mid+"，返回了："+guess+",代表小了");
                low=mid+1;
            } else if (guess == -1) {
                System.out.println("猜的数是："+mid+"，返回了："+guess+",代表大了");
                high=mid-1;
            }else {
                System.out.println("猜的数是："+mid+"，返回了："+guess+",猜对了");
                return mid;
            }
        }
        return -1;
    }
    public int guess(int num){
        int target=6;
        return Integer.compare(target, num);
    }

3、官方解法


 public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (guess(mid) <= 0) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
}
public int guess(int num){
        int target=6;
        return Integer.compare(target, num);
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/1017544

力扣算法题解析_力扣的解析

一、第9题，难度：简单

1、题目描述

2、个人解法

3、官方解法

二、罗马数字转数字

1、个人解法

2、官方解法

三、第14题，难度：简单

1、题目描述

2、个人解法

3、官方解法

四、第20题 难度：简单

1、题目描述

2、个人解法

3、官方解法

五、第58题：最后一个单词的长度，难度：简单

1、题目描述

2、个人解法

3、官方解法

六、第66题：加一，难度：简单

1、题目描述

2、个人解法

3.官方解法

七、第69题：x的平方根，难度：简单

1、题目描述

2、个人解法

3、官方解法

八、第125题：验证回文数，难度：简单

1、题目描述

2、个人解法

3、官方解法

九、第35题：搜索插入位置，难度：简单

1、题目描述

2、个人解法

3、官方解法

十、第374题：猜数字大小

1、题目描述

2、个人解法

3、官方解法

四、第20题难度：简单