java零基础入门-经典算法题解(十六)

一、前言

上一期我们是讲了三道算法题，分别如下：

       不知道小伙伴们，掌握的如何，有没有自己独立写出来，如果没有写出来的小伙伴，没关系，你可以再好好研究我写的，然后看懂思路。如果有小伙伴对以上三道感兴趣，也无妨自己可以试试。java零基础入门-经典算法题解(十五)

       接下来，我要把上期遗留的 课后作业进行一个全面剖析， 包括代码实现及解题思路。希望能给 小伙伴们带来算法乐趣。

上期课后作业算法题如下：

• 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
  
• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

二、算法实现

第一题：

题目：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

解题思路：

       得知什么是回文数，那我们将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。但是，如果反转后的数字大于int.MAX，我们将遇到整数溢出问题。为了避免数字反转可能导致的溢出问题，为那我们为什么不考虑只反转int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。对不对，所以我们 只需要考虑对折数字，将两半进行 整体比较即可。

算法：

       由于数字为负数，一定不可能是回文数，所以我们直接pass掉，统一返回false。然后除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字也返回 false。

       现在，让我们来考虑如何反转后半部分的数字。先将 数字转为字符串 ，然后将字符串分割为数组，只需要循环数组的一半长度进行判断对应元素是否相等即可。

具体代码实现：

public static boolean isPalindrome(int num) {

    //数字为负数
    if (num < 0) {
        return false;
    }

    //个位数是0
    int g = num % 10;
    if (g == 0 && num != 0) {
        return false;
    }

    //转成字符串
    String strNum = String.valueOf(num);
    for (int i = 0; i < strNum.length() / 2; i++) {
        if (strNum.charAt(i) != strNum.charAt(strNum.length() - 1 - i)) {
            return false;
        }
    }
    return true;
}

第二步，还是老样子，定义一个main主函数，进行调用刚实现的函数，然后进行判断输出即可。

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    System.out.println("请输入你要验证的数字：");
    int num = scanner.nextInt();
    boolean palindrome = isPalindrome(num);
    if (palindrome) {
        System.out.println(num + "是回文数");
        return;
    }
    System.out.println(num + "不是回文数");
}

具体控制台打印如下：

请输入你要验证的数字：
12321
12321是回文数

请输入你要验证的数字：
-12321
-12321不是回文数

请输入你要验证的数字：
1010
1010不是回文数

请输入你要验证的数字：
12221
12221是回文数

第二题：

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

解题思路：

       假设题意是叫你在排序数组中寻找是否存在一个目标值，那么训练有素的读者肯定立马就能想到利用二分法在 O(logn) 的时间内找到是否存在目标值。

       但这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，那我们还能用二分法么？答案是可以的，我们只需要稍作修改即可。 考虑这个插入的位置 pos，它成立的条件为：nums[pos-1]<target≤nums[pos] 

       其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 target 的下标」。

算法：

       直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 target 的下标 。下文给出的代码是笔者习惯的二分写法，ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是target 大于数组中的所有数，此时需要插入到数组长度的位置。 

具体算法实现：

public static int searchInsert(int[] nums, int target) {

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

第二步，还是老样子，定义一个main主函数，进行调用刚实现的函数，然后进行判断输出即可。

public static void main(String[] args) {

    int[] nums = {1, 2, 4, 5, 6, 8, 9};
    for (int num : nums) {
        System.out.print(num + " ");
    }
    System.out.println();
    int target = 7;
    int i = searchInsert(nums, target);
    System.out.println(target + ",位于nums中的第" + (i + 1) + "位");
}

具体控制台打印如下：

1 2 4 5 6 8 9 
4,位于nums中的第3位

1 2 4 5 6 8 9 
7,位于nums中的第6位

三、结尾

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

wished for you successed ！！！

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

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。

⭐️若有疑问，就请评论留言告诉我叭。

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