每日刷题记录 (十四)

第一题: 剑指 Offer 62. 圆圈中最后剩下的数字

LeetCode: 剑指 Offer 62. 圆圈中最后剩下的数字

描述:
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

解题思路:

1. 这里使用数学思路
2. 第一次删除的时候, 0 1 2 3 4, 删除 2
3. 第二次删除的时候, 3 4 0 1 , 删除 0
4. 第三次删除的时候, 1 3 4 , 删除 4
5. 第四次删除的时候, 1 3 , 删除 1
6. 第五次不需要删除, 3, 返回3
    
   这里可以利用反推发,
   例如在第五次的时候, 初始位置下标位置是 0 , 要想知道第四次的下标位置, 通过 index = (index + m) % i, 这里是index是当前的下标, m 是删除的下标, i 是从后往前的次数(例如这里的第四次, 反着就是第二次).
   所以计算下标得到 index = (0 + 3) % 2 = 1 , 所以在第四次的时候, 最后剩余的下标为 1
   

代码实现:

class Solution {
    
    public int lastRemaining(int n, int m) {
    
    	// 最后所剩下的元素, 下标只可能是0
        int index = 0;
        for (int i = 2; i <= n; i++) {
    
        	// 通过数学反推法求得上一次坐标位置
            index = (index + m) % i;
        }
        // 计算得到最初的时候, 下标位置
        return index;
    }
}

第二题: 剑指 Offer 63. 股票的最大利润

LeetCode: 剑指 Offer 63. 股票的最大利润

描述:
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

解题思路:

1. 初始情况, 让min = prices[0], 记录最大值 max
2. 遍历数组,
3. 如果当前 prices[i] 大于 min, 记录最大值, max = Math.max(max, prices[i] - min)
4. 如果当前 prices[i] 小于 min, 就更换 min

代码实现:

class Solution {
    
    public int maxProfit(int[] prices) {
    
        if(prices.length == 0) return 0;
        int min = prices[0];
        int max = 0;
        for(int price : prices) {
    
            if (min > price) {
    
                min = price;
            }else{
    
                max = Math.max(max,price-min);
            }
        }
        return max;
    }
}

第三题: 剑指 Offer 64. 求1+2+…+n

LeetCode: 剑指 Offer 64. 求1+2+…+n

描述:
求1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路:

1. 由于不能使用for循环
2. 这里使用递归的方式求值
3. 利用 boolean flg = (A) && (B), 这里 如果 A 为 false 就结束递归.所以 A 起到 if 作用, B 起到for作用

代码实现:

class Solution {
    
    public int sumNums(int n) {
    
        boolean flg = n > 0 && (n += sumNums(n - 1)) >0;
        return n;
    }
}

第四题: 剑指 Offer 66. 构建乘积数组

LeetCode: 剑指 Offer 66. 构建乘积数组

描述:
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

解题思路:

1. 由于不能使用除法, 这里不能除去自己
2. 先从左到右乘一遍, 每次不成自己
3. 再从右到做乘一遍, 每次不成自己
   

代码实现:

class Solution {
    
    public int[] constructArr(int[] a) {
    
        int[] res = new int[a.length];
        int ret = 1;
        for(int i = 0; i < a.length; i++) {
    
            res[i] = ret;
            ret *= a[i];
        }
        ret = 1;
        for(int i = a.length-1; i >=0 ; i--) {
    
            res[i] *= ret;
            ret *= a[i];
        }
        return res;
    }
}

第五题: 剑指 Offer 67. 把字符串转换成整数

LeetCode: 剑指 Offer 67. 把字符串转换成整数
描述:
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明:
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

解题思路:

1. 首先去除前后的空格
2. 然后判断当前是否为空了, 去除之后可能有空的情况
3. 判断第一个字符, 是否是数字, 或者是否是符号, 如果不是直接返回0
4. 如果第一个字符是负号, 记录当前的符号
5. 循环记录当前的数字字符,
6. 用一个long类型去计算当前的数字大小
   • 如果当前数字大于 Integer.MAX_VALUE , 且符号为正, 返回 Integer.MAX_VALUE
   • 如果当前数字大于 Integer.MAX_VALUE , 且符号为负, 返回 Integer.MIN_VALUE
7. 如果循环结束, 没有超过 Integer.MAX_VALUE, 返回当前res, 正号返回 res, 负号返回 -res

代码实现:

class Solution {
    
    public int strToInt(String str) {
    
        str = str.trim();
        int index = 0;
        if(index>=str.length()) return 0;
        if(!Character.isDigit(str.charAt(0)) && str.charAt(0)!='-' && str.charAt(0)!='+'){
    
            return 0;
        }
        int flg = 1;
        if(str.charAt(0) == '-'){
    
            flg = -1;
            index++;
        }else if(str.charAt(0) == '+'){
    
            index++;
        }
        long res = 0;
        while(index < str.length() && Character.isDigit(str.charAt(index))){
    
            res = res * 10 + str.charAt(index)-'0';
            if(res > Integer.MAX_VALUE && flg == 1){
    
                return Integer.MAX_VALUE;
            }else if (res > Integer.MAX_VALUE && flg == -1) {
    
                return Integer.MIN_VALUE;
            }
            index++;
        }
        res = flg==1?res:-res;
        return (int)res;
    }
}

第六题: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

LeetCode: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

描述:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

解题思路:

注意这里的几种情况.

1. root 为 空的 时候, 直接返回 null
2. 如果当前 root 节点的值, 大于 p 的值, 且 大于 q 的值, 那么就在左子树.
3. 如果当前 root 节点的值, 小于 p 的值, 且 小于 q 的值, 那么就在右子树.
4. 否者, p , q 在左右两侧, 或者为根节点, 直接返回 root

代码实现:

class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root == null) return null;
        if(root.val > p.val && root.val > q.val) {
    
            return lowestCommonAncestor(root.left,p,q);
        }else if(root.val < p.val && root.val < q.val) {
    
            return lowestCommonAncestor(root.right,p,q);
        }else{
    
            return root;
        }
    }
}