《剑指Offer》笔记题解思路技巧优化_Part

《剑指Offer》笔记&题解&思路&技巧&优化_Part_7

😍😍😍 相知
🙌🙌🙌 相识
😢😢😢 开始刷题
- 🟢1. LCR 179. 查找总价格为目标值的两个商品——和为s的两个数字
- 🟢2. LCR 180. 文件组合——和为s的连续正数序列
- 🟢3. LCR 181. 字符串中的单词反转——翻转单词顺序
- 🟢4. LCR 182. 动态口令——左旋转字符串
- 🔴5. LCR 183. 望远镜中最高的海拔——滑动窗口的最大值
- 🟡6. LCR 185. 统计结果概率——n个骰子的点数
- 🟢7. LCR 186. 文物朝代判断——扑克牌中的顺子
- 🟢8. LCR 187. 破冰游戏——圆圈中最后剩下的数字
- 🟡9. LCR 188. 买卖芯片的最佳时机——股票的最大利润
- 🟡10. LCR 189. 设计机械累加器——求1+2+n
- 🟢11. LCR 193. 二叉搜索树的最近公共祖先——二叉搜索树的最近公共祖先

在这里插入图片描述

😍😍😍 相知

刷题不要一上来就直接干，先看题，明白题说的什么意思，然后想一下用什么现成的算法和数据结构可以快速解决，如果还是无从下手，建议先去看视频，不要直接翻评论或官方代码实现，看完视频，自己在idea中模拟敲几遍代码，如果跑通了，先别急着上leetcode黏贴，而是再回顾一下要点，然后确定自己完全懂了后，在leetcode中手敲，注意是手敲下来！！！目前我就是采用的这种方法，虽然慢，但是可以维持一周忘不掉它，如果要想长期不忘，只能隔段时间就review一下了，就算是大牛，知道方法，长时间不碰，也不可能保证一次到位把代码敲完一遍过！！！

这是我上一篇博客的，也希望大家多多关注！

《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_1
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_2
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_4
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_5
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_6

🙌🙌🙌 相识

根据题型可将其分为这样几种类型：

结构概念类（数组，链表，栈，堆，队列，树）
搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）
双指针定位类（快慢指针，指针碰撞，滑动窗口）
排序类（快速排序，归并排序）
数学推理类（动态规划，数学）

😢😢😢 开始刷题

🟢1. LCR 179. 查找总价格为目标值的两个商品——和为s的两个数字

题目跳转：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

class Solution {
    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length-1;
        while(left<right){
            if(target-price[left]==price[right])
            	return new int[]{price[left],price[right]};
            else if(target-price[left]<price[right]) right--;
            else left++;
        }
        return null;
    }
}

🟢2. LCR 180. 文件组合——和为s的连续正数序列

题目跳转：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/description/

class Solution {
    public int[][] fileCombination(int target) {
        if(target<=2)return new int[0][0];
        //思路，双指针
        //刚开始 left 在位置 1， right 在位置 2， 定义左右指针之间的数字和为 sum = n*(a1+an)/2
        //1.类似二分查找的逻辑，当 sum 等于 target 时，将左右指针之间的这种数组加入结果，然后左指针右移
        //2.当 sum 小于 target 时，右指针右移增大 sum
        //3.当 sum 大于 target 时，说明以 left 为起点组成的数组不符要求，左指针右移

        //创建结果数组
        List<int[]> list = new ArrayList<>();

        int left = 1;
        int right = 2;

        //终止条件是左指针移动到右指针位置，说明此时已经不存在两个数之和能小于 target 了
        while (left < right) {

            int sum = (right - left + 1) * (left + right) / 2;

            if (sum == target) {
                //创建数组存储左右指针之间的数组组合
                int[] tmp = new int[right - left + 1];

                for (int i = 0; i < right - left + 1; i++) {
                    tmp[i] = left + i;
                }

                //将临时数组结果存储入List
                list.add(tmp);

                //继续探索下一种方案
                ++left;
            }else if (sum<target){
                ++right;
            }else {
                ++left;
            }

        }
        
        //掌握此种二维list转数组方法
        return list.toArray(new int[list.size()][]);
    }

}

🟢3. LCR 181. 字符串中的单词反转——翻转单词顺序

题目跳转：https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/description/

class Solution {
    public String reverseMessage(String message) {
        message = message.trim();
        String [] temp = message.split("\\s+");
        StringBuilder stringbuilder = new StringBuilder();
        for(int i = 0;i<temp.length;i++){
            stringbuilder.append(temp[temp.length-1-i]);
            if(i!=temp.length-1)stringbuilder.append(" ");
        }

        return stringbuilder.toString();
    }
}

🟢4. LCR 182. 动态口令——左旋转字符串

题目跳转：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/description/

class Solution {
    public String dynamicPassword(String password, int target) {
        String temp = password.substring(0,target);
        StringBuilder stringBuilder = new StringBuilder(password.substring(target,password.length()));
        stringBuilder.append(temp);
        return stringBuilder.toString();
    }
}

🔴5. LCR 183. 望远镜中最高的海拔——滑动窗口的最大值

题目跳转：https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/description/

在这里插入图片描述

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length==0||limit==0) return new int [0];
        int [] result = new int[heights.length-limit+1];
        LinkedList<Integer> queue = new LinkedList<>();
        int index = 0;
        for( int i =0;i <heights.length;i++){
            
            while(!queue.isEmpty()&&heights[queue.peekLast()]<=heights[i]){
                queue.pollLast();
            }
            queue.add(i);
            if(queue.peekLast()-limit==queue.peek()){
                queue.poll();
            }
            if(i + 1 >= limit){
                result[index++] = heights[queue.peek()];
            }
        }
        return result;
    }
}

🟡6. LCR 185. 统计结果概率——n个骰子的点数

题目跳转：https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/description/

在这里插入图片描述

class Solution {
    public double[] statisticsProbability(int num) {
        double[] result=new double[5*num+1];
        int[][] dp = new int[num+1][6*num+1];
            for(int i = 1; i <= 6; i++){
            dp[1][i] = 1;
        }
        for(int i = 2;i <= num;i++){
            for(int j = i;j<=6*i;j++){
                for(int k = 1;k<=6;k++){
                    if(j < k)break;
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        int index = 0;
        double sum = Math.pow(6,num);

        for(int i = num;i<=6*num;i++){
            result[index++] = dp[num][i]/sum;
        }
        return result;

    }
}

🟢7. LCR 186. 文物朝代判断——扑克牌中的顺子

题目跳转：https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/description/

class Solution {
    public boolean checkDynasty(int[] places) {
        Arrays.sort(places);
        int left = 0;
        int right =4;
        while(left<right){
            if(places[right]==0)return true;
            if(places[right]-1==places[right-1]){
                right--;
                continue;
            }
            if(places[left]==0){
                left++;
                places[right] = places[right]-1;
                continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

🟢8. LCR 187. 破冰游戏——圆圈中最后剩下的数字

题目跳转：https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/

/*
    思路：使用数学方法(先举例)
            你要知道最后的结果是3，带着结果去看问题

        第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
        (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
        第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
        第三次，【1, 3, 4】，本轮要踢出4                                        看1
        第四次，【1, 3】 本轮要踢出1                                            看3
        第五次，【3】
        最后返回3

        我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
        你从第二次，向上看第一次
        你会发现，原来3在0的位置
                现在，3在(0 + 3) % 5
                        => +3 回到上次的位置
                        => %5 防止数组溢出，并且数组本来就是循环数组

        f(n) = ( f(n - 1) + m ) % n
        解释意思：
            f(n) 表示上一次
            f(n - 1) 表示这次，因为我们要从这次回推上一次
            m 表示隔几个
            n表示上一次的数组长度

     */

class Solution {
    public int iceBreakingGame(int num, int target) {
        int res = 0;// 最后只剩下一位，坐标肯定是0
        for (int i = 2; i <= num; i++) {
            res = (res + target) % i;
        }
        return res;
    }
}

🟡9. LCR 188. 买卖芯片的最佳时机——股票的最大利润

题目跳转：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/description/

class Solution {
    public int bestTiming(int[] prices) {
        if(prices.length<2)return 0;
        int max = 0;
        int [] result = new int[prices.length];
        result[prices.length-1]=0;
        for(int i = prices.length-2;i>=0;i--){
            result[i] = Math.max(result[i+1],prices[i+1]);
            max = Math.max(max,result[i]-prices[i]);
        }
        return max;
    }
}

class Solution {
    public int bestTiming(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price: prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit,price-cost);
        }
        return profit;
    }
}

🟡10. LCR 189. 设计机械累加器——求1+2+n

题目跳转：https://leetcode.cn/problems/qiu-12n-lcof/description/

等差数列求和公式

class Solution {
    
    public int sumNums(int n) {
        return (int) (Math.pow(n, 2) + n) >> 1;
    }
}

递归

class Solution {

    public int sumNums(int n) {
        int sum = n;
        boolean flag = n > 0 && (sum += sumNums(n - 1)) > 0;
        return sum;
    }
}

异常

class Solution {
    int[] temp = {0};
    public int sumNums(int n) {
        try {
            // n不等于0的时候都会报错，进入catch方法
            return temp[n];
        } catch(Exception e) {
            return n + sumNums(n-1);
        }
    }
}

🟢11. LCR 193. 二叉搜索树的最近公共祖先——二叉搜索树的最近公共祖先

题目跳转：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/

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);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);

    return root;
}