分类: 未分类

  • 线程池异常处理方式

    线程池任务提交方式与异常处理详解

    一、任务提交方式:execute vs submit

    1. execute 方法

      • 特点
        • 直接提交任务到线程池,没有返回值。
        • 如果任务执行过程中抛出未捕获的异常,会直接抛出,可能导致线程终止。
      • 适用场景:适用于不需要获取任务执行结果的场景,且需要立即处理异常。
      • 示例
        executorService.execute(() -> {
         // 可能抛出异常的代码
        });
    2. submit 方法

      • 特点
        • 提交任务后返回一个Future对象,通过它可以获取任务结果或异常。
        • 任务中的异常会被封装在Future中,调用Future.get()时才会抛出。
        • 如果未调用Future.get(),异常可能被静默处理,导致问题难以追踪。
      • 代码解析
        Future future = executorService.submit(() -> {
         // 可能抛出异常的代码
        });
        try {
         future.get(); // 此处会抛出ExecutionException,包含原始异常
        } catch (ExecutionException e) {
         Throwable cause = e.getCause(); // 获取实际异常
        }
      • 适用场景:需要获取任务执行结果或进行异常处理的异步任务。

    二、线程池异常处理方式

    1. try-catch 捕获异常

      • 原理:在任务代码内部显式捕获并处理异常。
      • 优点:简单直接,适用于逻辑明确的异常处理。
      • 缺点:侵入性强,每个任务都需要手动添加try-catch。
      • 示例
        executorService.execute(() -> {
         try {
             // 可能抛出异常的代码
         } catch (Exception e) {
             // 处理异常
         }
        });
    2. 自定义线程工厂设置未捕获异常处理器(UncaughtExceptionHandler)

      • 原理
        • 通过线程工厂为线程设置默认的未捕获异常处理器。
        • 当线程因未捕获异常而终止时,处理器会被触发。
      • 适用性:仅对通过execute提交的任务有效,submit提交的任务异常被封装在Future中,不会被此处理器捕获。
      • 代码解析
        ThreadFactory factory = (Runnable r) -> {
         Thread t = new Thread(r);
         t.setUncaughtExceptionHandler((thread, e) -> {
             System.out.println("捕获异常: " + e.getMessage());
         });
         return t;
        };
        ExecutorService executor = new ThreadPoolExecutor(..., factory);
        executor.execute(() -> { throw new RuntimeException("execute异常"); }); // 触发处理器
        executor.submit(() -> { throw new RuntimeException("submit异常"); });    // 不触发处理器
    3. 重写afterExecute方法

      • 原理
        • afterExecuteThreadPoolExecutor的一个钩子方法,在任务执行完成后调用。
        • 可以在此检查任务执行过程中是否发生了异常。
      • 处理submit异常
        • 由于submit返回的FutureTask会将异常封装,需通过Future.get()提取异常。
      • 代码解析
        ExecutorService executor = new ThreadPoolExecutor(...) {
         @Override
         protected void afterExecute(Runnable r, Throwable t) {
             super.afterExecute(r, t);
             if (t != null) {
                 System.out.println("execute异常: " + t.getMessage());
             }
             if (r instanceof FutureTask) {
                 try {
                     ((Future) r).get();
                 } catch (InterruptedException | ExecutionException e) {
                     System.out.println("submit异常: " + e.getCause().getMessage());
                 }
             }
         }
        };

    三、关键点对比与总结

    方法/方式 异常可见性 返回值支持 适用提交方法 侵入性
    try-catch 立即捕获 execute/submit 高(需修改任务代码)
    UncaughtExceptionHandler 仅execute任务触发 execute 低(全局处理)
    afterExecute 需主动检查Future.get() 支持 execute/submit 中(需扩展线程池)

    最佳实践建议

    • 使用execute时,结合UncaughtExceptionHandler进行全局异常处理。
    • 使用submit时,务必通过Future.get()处理异常,或在afterExecute中统一捕获。
    • 对于复杂的异步任务链,考虑使用CompletableFuture或第三方库(如Guava的ListenableFuture)以更灵活地处理异常。
  • LeetCode-150-数组

    面试150题-数组部分

    📕文章题目选自LeetCode面试150题-数组部分
    😊该文章内容基于作者本人思考总结,如有错误欢迎指正
    🏠题单地址:https://leetcode.cn/studyplan/top-interview-150/

    数组/字符串

    LeetCode150-移除元素-LC27

    /**
     * @Author DSXRIIIII
     * @Project mounts
     * @Package cn.dsxriiiii.LeetCode.LC150
     * @Date 2024/8/20 9:59
     * @Description: 移除元素
     */
    public class LC27 {
        public int removeElement(int[] nums, int val) {
            int left = 0;
            int right = nums.length;
            while(left < right){
                if(nums[left] == val){
                    nums[left] = nums[right - 1];
                    right--;
                }else{
                    left++;
                }
            }
            return left;
        }
    }

    LeetCode150-删除有序数组中的重复项-LC26

    /**
     * @Author DSXRIIIII
     * @Project mounts
     * @Package cn.dsxriiiii.LeetCode
     * @Date 2024/8/20 10:08
     * @Description: 删除有序数组的重复项
     * 快指针匹配相等时会往后一直匹配 当匹配不相同的时候会将快指针的值给慢指针
     */
    public class LC26 {
        public int removeDuplicates(int[] nums) {
            int len = nums.length;
            if(len == 0) return 0;
            int slow = 1;
            int fast = 1;
            while(fast!=len){
                if(nums[fast] != nums[fast-1]){
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }
            return slow;
        }
    }

    LeetCode150-删除有序数组中的重复项II-LC80

    //题目要求将出现两次以上的数让其只出现过两次
    //原地操作(空间复杂度为O(1)) 采用覆盖操作咯  考虑快慢指针
    public static int removeDuplicates(int[] nums){
        int len = nums.length;
        if(len < 2) return 2;
        int fast = 2;
        int slow = 2;
        while(fast != len){
            if(nums[slow-2] !=nums[fast]){ //这个地方就限制了 数组元素只能出现两次
                //这里不是赋值给nums[slow-2]
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow; //翻新后的数组长度
        //println()直接打印
    }
    //如何理解快慢指针逻辑
    //1.快指针每一次循环都会向前++
    //2.慢指针只有当nums[slow - 2] != nums[fast] 此时slow处于位置重复元素长度为3的位置,此时进行快指针的覆盖
    //3.覆盖操作完成 快慢指针都会继续判断 
    //4.慢指针永远记录被修改的位置 快慢指针指向同一位置 也会进行赋值操作 并且原地不变

    LeetCode150-轮转数组-LC189

    //方法一 数组拷贝
    public void rotate(int[] nums,int k){
        int len = nums.length;
        int[] arr = new int[len];
        for(int i = 0; i < len;i++){
            arr[(i + k) % n] = nums[i];
            //使用取余操作进行覆盖
        }
        System.arraycopy(arr,0,nums,0,len);
        //调用拷贝函数 将新数组数据拷贝到旧数组
    }
    
    //方法二 使用翻转数组元素方式
    public void rotate(int nums[],int k){
        k = k % (nums.length);
        reverse(0,nums.length-1,k);
        reverse(0,k - 1,k);
        reverse(k,nums.length,k);
    }
    public static void reverse(int start,int end,int[] nums){
            while(start < end){ // 判断条件是 <
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start+=1;
                end-=1; 
            }
        }
    }

    LeetCode150-买卖股票的最佳时机-LC189

    //暴力枚举每一项时间复杂度为O(n**2)
    //以下方法可以每一次判断当求到最小值时 ,保存最小值
    //往后的每次都按照当前值与最小值的差值 与 保存的最大值进行比较
    //最后求得最大的股票差值
    
    public int maxProfit(int nums[]){
        int minValue = Integer.MAX_VALUE;
        int maxValue = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] < minValue){
                minValue = nums[i];//保存最小值
            }else{
                if(nums[i] - minValue > maxValue){
                    maxValue = nums[i] - minValue;//计算差值
                }
            }
        }
        return maxValue;
    }

    LeetCode150-买卖股票的最佳时机II-LC189

    //动态规划思路
    //讲实话真的很难懂
    //假如股票的价格为{7,1,5,3,6,4}
    //还是很难理解 。。。。。
    public int maxProfit(int[] prices){
        int len = prices.length;
        if(len < 2) return 0;
        int[] cash = new int[len];
        int[] gupiao = new int[len];
        cash[0] = 0;
        gupiao[0] = -prices[i];
        for(int i = 1;i < len;i++){
            cash[i] = Math.max(cash[i-1],gupiao[i - 1] + prices[i]) //买股票和不买股票的最大值
            gupiao[i] = Math.max(gupiao[i - 1],cash[i- 1] - prices[i]);
        }
        return cash[len - 1];
    }
    
    //使用贪心算法 每次计算出差值进行比较 这样的方法比较通俗易懂 时间复杂度O(n) 空间复杂度O(1)
    public int maxProfit(int[] prices){
        int len = prices.length;
        if(len < 2) return 0;
        int res = 0;
        for(int i = 1;i < len;i++){
            int diff = prices[i] - prices[i - 1];
            if(diff > 0){
                res += diff;
            }
        }
        return res;
        }
    

    LeetCode150-跳跃游戏-LC55

    /**
     * 题目:跳跃游戏
     * 算法思路-1:贪心算法
     * 具体思路:遍历每一个位置,思考每一个位置可以到达的最远举例,前提条件是位置i可以到达
     */
    public class LC55 {
        public static void main(String[] args) {
            int[] nums = {3,2,1,0,4};
            System.out.println(canJump(nums));
        }
        public static boolean canJump(int[] nums) {
            int maxIndex = 0;
            for(int i = 0; i < nums.length;i++){
                int curIndex = i + nums[i];
                if(i <= maxIndex){   //这里必须要满足的条件 maxIndex记录的是要到达的最远距离
                    //如果 i > maxIndex 进行操作是无效的 因为永远到达不了这个位置
                    maxIndex = Math.max(curIndex,maxIndex);
                }
                if(maxIndex >= nums.length - 1){  //这里必须满足>=的条件 {0} 这样的情况也是可以到达的
                    return true;
                }
            }
            return false;
        }
    }

    LeetCode150-跳跃游戏II-LC45

    /**
     * 题目:跳跃游戏II
     * 算法思路-1:贪心算法
     * 具体思路:遍历每一个位置,思考每一个位置可以到达的最远距离
     * 当到达边界时此时 res++ 表示跳跃一次 我可以到达的最远距离赋值给边界
     * 边界不断更新 那么跳跃次数也会不断更新 知道最后边界值大于等于数组长度
     * 要注意遍历的范围[0,len - 1] 避免i走到数组末尾再一次+1
     */
    public class LC45 {
        public static int jump(int[] nums) {
            int len = nums.length;
            int maxIndex = 0;
            int Border = 0;
            int res = 0;
            for(int i = 0; i < len;i++){
                /*
                 * 此处i < len - 1
                 * 在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,
                 * 否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下
                 * 我们会增加一次「不必要的跳跃次数」 如何理解呢
                 * 假如数组int[] nums = {2,3,1,1,4}; 此时i走到了最后的位置 i = 4;此时边界border = 4;
                 * 此时会再一次走到i == border判断条件 此时res++ 就多余了
                 */
                maxIndex = Math.max(maxIndex,i+nums[i]);
                if(i == Border){
                    Border = maxIndex;
                    res++;
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] nums = {2,3,1,1,4};
            System.out.println(jump(nums));
        }
    }

    LeetCode150-H指数-LC274

    /**
     * 题目:H指数
     * 算法思路-1:贪心算法
     * 具体思路:对于数组的每一个值 判断大于其值的个数是否等于i
     */
    public int hIndex(int[] citations) {
            Arrays.sort(citations);
            int h = 0, i = citations.length - 1; 
            while (i >= 0 && citations[i] > h) {
                h++; 
                i--;
            }
            return h;
        }

    LeetCode150-O(1)时间插入删除获取随机元素-LC380

    /**
     * 题目:O(1)时间插入删除获取随机元素数
     * 算法思路-1:贪心算法
     * 具体思路:对于数组的每一个值 判断大于其值的个数是否等于i
     */
    class RandomizedSet {
        List<Integer> list;
        Map<Integer,Integer> map;
        Random random;
        public RandomizedSet() {
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }
    
        public boolean insert(int val) {
            if(map.containsKey(val)){
                return false;
            }
            int index = list.size();
            list.add(val);
            map.put(val,index);
            return true;
        }
    
        public boolean remove(int val) {
            if(!map.containsKey(val)){
                return false;
            }
            int index = map.get(val);
            int lastnum = list.get(list.size()-1);
            list.set(index,lastnum);
            map.put(lastnum,index);
            map.remove(val);
            list.remove(list.size()-1);
            return true;
        }
    
        public int getRandom() {
            int randomIndex = random.nextInt(list.size());
            return list.get(randomIndex);
        }
    }
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */

    LeetCode150-除自身以外数组的乘积-LC238

    /**
     * 题目:除自身以外数组的乘积
     * 算法思路:遍历
     * 具体思路:观察测试用例发现结果数组 保存的是除本身之外的左右所有值的乘积
     * 分为两次循环更新数组
     */
    public class LC238 {
        public int[] productExceptSelf(int[] nums) {
            int len = nums.length;
            int[] answer = new int[len];
            answer[0] = 1;
            for(int i = 1; i < len;i++){
                answer[i] = nums[i - 1] * answer[i - 1];
                //对于数组 从左往右遍历 answer保存当前坐标(不包括自己)的所有乘积
            }
            int right = 1;
            for(int i = len - 1;i >= 0;i--){
                answer[i] = answer[i] * right;
                //对于数组从右往左遍历 answer更新 right保存当前坐标(不包括当前坐标的值所有乘积
                right = right * nums[i]; //right实时更新
            }
            return answer;
        }
    }

    LeetCode150-加油站-LC134

    /**
     * 题目:加油站
     * 算法思路:遍历
     * 具体思路:1.循环数组实现 
     *         2.剪枝 更新i时 考虑index
     *         3.计算每次的油量
     */
    public class LC134 {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int len = gas.length;
            int i = 0;
            //思路
            while(i < len) {
                int gasCapacity = 0;
                int costCapacity = 0;
                int index = 0;//保存遍历长度 这个坐标可以表示走了index步 是否成功
                while(index < len){//index表示要走的步数 总共要走len步 走到len步就说明成功了
                    int cur = (index + i) % len;
                    gasCapacity += gas[cur];
                    costCapacity += cost[cur];
                    if(costCapacity > gasCapacity){ //不满足条件会走break退出while循环 下一步index也不会更新
                        break;
                    }
                    index++;
                }
                //长度为len满足条件返回坐标
                if(index == len){
                    return i;
                }else{
                    i = i + 1 + index;//优化手段 
                    //为什么不采用以下的方式
                    //i = i + 1;
                    //因为index已经走了index++自增步数 如果break退出证明index + i这个范围都不合适
                    //为什么不合适 如果下一步还是从i + 1开始走 走到 前一个index + i位置时还是不满足条件 所以选择剪枝
                    //在更新时将i = i + index + 1;此时从这个地方走可以节约很多时间
                }
            }
            return -1;
        }
    }

    LeetCode150-分发糖果-LC135

    /**
     * 题目:分发糖果
     * 算法思路:两次遍历
     * 具体思路:1.从左向右遍历 当i > i-1 数组更新++,否则arr[i] = 1;
     *         2.从右向左遍历 同上 记录right值是为了当不断递增时 res 可以 加上 比较中的最大值
     */
    public class LC135 {
        public static void main(String[] args) {
            int[] nums = {1,0,2};
            System.out.println(candy(nums));
    
        }
        public static int candy(int[] ratings) {
            int res = 0;
            int len = ratings.length;
            int[] arr = new int[len];
            for(int i = 0; i < ratings.length;i++){
                if(i > 0 && ratings[i] > ratings[i - 1]){
                    arr[i] = arr[i - 1] + 1;
                }else{
                    arr[i] = 1;
                }
            }
            int right = 0;
            for(int j = ratings.length - 1;j >= 0;j--){
                if(j < len - 1 && ratings[j] > ratings[j + 1]) {
                    right++;
                }else{
                    right = 1;
                }
                //res += arr[j]; 保存的right值是用来当左边值大于右边值时 right会right++
                //例如下面这个数组{1,3,5,3,2,1} 第三个人比左右两边都要高 但是 从右向左right == 4 arr[i] = 3 所以要取大值4
                res += Math.max(arr[j],right);
    
            }
            //System.out.println(Arrays.toString(arr));
            return res;
        }
    }
    

    LeetCode150-接雨水-LC42

    /**
     * 题目:接雨水
     * 算法思路:双指针
     * 具体思路:1.维护左右leftMax,rightMax记录左右的最大值
     *         2.如果 height[left] < height[right],则必有leftMax < rightMax或者leftMax > rightMax那么此时就可能会有雨水
     *         3.雨水值就为leftMax - height[left] 或者 rightMax - height[right]
     *         4.最后res用来保存雨水值 当左右left与right指针相遇时结束
     */
    public class LC42 {
        public int trap(int[] height) {
            int res = 0;
            int left = 0,right = height.length - 1;
            int leftMax = 0;
            int rightMax = 0;
            while(left < right){
                leftMax = Math.max(height[left],leftMax);
                rightMax = Math.max(height[right],rightMax);
                if(height[left] < height[right]){
                    res+=leftMax - height[left];
                    left++;
                }else{
                    res+=rightMax - height[right];
                    right--;
                }
            }
            return res;
        }
    }
    

    LeetCode150-罗马数字转整数-LC13

    import java.util.HashMap;
    import java.util.Map;
    /**
     * 题目:罗马数字转整数
     * 算法思路:遍历找特殊条件
     * 具体思路:1.列举特殊条件即可
     */
    public class LC13 {
        public static void main(String[] args) {
            String s = "LVIII";  //1000 + 900 + 90 + 4
            System.out.println(romanToInt(s));
        }
        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 res = 0;
            res  += map.get(s.charAt(0));
            for(int i = 1;i < s.length();i++){
                if(
                        (s.charAt(i) == 'V' || s.charAt(i) == 'X') && s.charAt(i - 1) == 'I' ||
                        (s.charAt(i) == 'L' || s.charAt(i) == 'C') && s.charAt(i - 1) == 'X' ||
                        (s.charAt(i) == 'D' || s.charAt(i) == 'M') && s.charAt(i - 1) == 'C'
                        //记得加()维持条件
                ){
                    res -= map.get(s.charAt(i - 1));
                    res += map.get(s.charAt(i)) - map.get(s.charAt(i - 1));
                }else{
                    res  += map.get(s.charAt(i));
                }
    
            }
            return res;
        }
    }

    LeetCode150-整数转罗马数字-LC12

    /**
     * 题目:整数转罗马数字
     * 算法思路:遍历找特殊条件
     * 具体思路:1.列举特殊条件即可 使用StringBuilder拼接
     */
    public class LC12 {
        public static void main(String[] args) {
            System.out.println(intToRoman(58));
        }
        public static String intToRoman(int num) {
            int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
            String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < values.length; i++) {
                while(num >= values[i]){
                    num-=values[i];
                    sb.append(symbols[i]);
                }
                if(num == 0){
                    break;
                }
    
            }
            return sb.toString();
        }
    }
    

    LeetCode150-最后一个单词的长度-LC58

    /**
     * 题目:最后一个单词的长度
     * 算法思路:遍历
     * 具体思路:1.去掉前后的空格 trim()方法
     *         2.遍历到‘ ’处停止
     */
    public class LC58 {
        public static void main(String[] args) {
            String s = "a";
            System.out.println(lengthOfLastWord(s));
        }
        public static int lengthOfLastWord(String s) {
            s = s.trim();
            int res = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if(s.charAt(i) != ' '){
                    res++;
                }else{
                    break;
                }
            }
            return res;
        }
    }
    

    LeetCode150-最长公共前缀-LC14

    /**
     * 题目:最长公共前缀
     * 算法思路:遍历
     * 具体思路:1.字符数组的第一个字符串为比较串
     *          2.横向比较法 两两比较
     *          3.纵向比较法 全部比较
     *          4.时间复杂度都为O(mn) 空间复杂度为O(1) 常数
     */
    public class LC14 {
        /**
         * 横向比较法 每一次取两个字符串比较 取得的相似值放到下一次比较中
         */
        public String longestCommonPrefix(String[] strs) {
            int len = strs.length;
            if(len == 0) return "";
            String SameString = strs[0];
            for(int i = 1; i < len;i++){
                SameString = getSameString(SameString,strs[i]); //返回得到两个字符串的最长序列 在进入到下一次循环中
    //            if(SameString == null){
    //                break;
    //            }
            }
            return SameString;
        }
    
        /**
         * 纵向比较法 将初始字符串的每一个字符与后续的所有字符串进行比较
         */
        public String longestCommonPrefix_2(String[] strs) {
            int len = strs[0].length();
            if(len == 0) return "";
            for(int i = 0; i < len;i++){
                char c = strs[0].charAt(i);
                for(int j = 1;j < strs.length;j++){
                    if(i == strs[j].length() || strs[j].charAt(i) != c){
                        //i == strs[j].length() 此时短的字符串走完了
                        //strs[j].charAt(i) != c 与当前字符比较不相等 i为公共最长长度
                        //i 记录公共长度
                        strs[0] = strs[0].substring(0,i);
                    }
                }
            }
            return strs[0];
        }
    
        private String getSameString(String sameString, String str) {
            int index = 0;
            int length = Math.max(sameString.length(),str.length());
            while(index < length && sameString.charAt(index) == str.charAt(index)){
                index++;
            }
            return sameString.substring(0,index);
        }
    
    }
    

    LeetCode150-反转字符串中的单词-LC151

    /**
     * 题目:反转字符串中的单词
     * 算法思路:调用方法(正则表达式)
     * 具体思路:1.字符数组的第一个字符串为比较串
     *          2.横向比较法 两两比较
     *          3.纵向比较法 全部比较
     *          4.时间复杂度都为O(mn) 空间复杂度为O(1) 常数
     * 补充:正则表达式:
     *          1.“_”  匹配任何单个字符
     *          2."*"  匹配0个或者多个在它面前的字符
     *          3."%"  匹配任意数字字符
     *          4."[]" 匹配方括号中的任意字符
     */
    public class LC151 {
        public static void main(String[] args) {
            String s = "the sky is blue";
            System.out.println(reverseWords_queue(s));
        }
        public static String reverseWords_function(String s) {
            s = s.trim();
            List<String> list = Arrays.asList(s.split("\\s+"));
            // "\\s+" 表示一个或者多个连续的空白字符串
            Collections.reverse(list);//翻转list中的所有单词
            System.out.println(list);//[blue, is, sky, the]
            return String.join(" ",list);
        }
    
        /**
         * 使用双端队列Deque在头部插入新数据
         */
        public static String reverseWords_queue(String s) {
            s = s.trim();
            Deque<String> queue = new LinkedList<>();
            StringBuilder word = new StringBuilder();
            int left = 0;
            int right = s.length() - 1;
            while(left <= right){ //从左向右遍历 遇到字符添加进入word 当遇到空白字符时添加进入队列并且重置word
                char c = s.charAt(left);
                if(word.length() != 0 && c == ' '){
                    queue.offerFirst(word.toString());
                    word.setLength(0);
                }else if(c != ' '){//"example   good a" 确保这样的方式也能通过 避免中间的多余空格
                    word.append(c);
                }
                left++;
            }
            queue.offerFirst(word.toString());
            return String.join(" ",queue);
        }
    }

    LeetCode150-Z字形变换-LC6

    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 题目:Z字形变换
     * 算法思路:StringBuilder拼接字符串
     * 具体思路:1.flag 用于调转方向 比如 1,2,3 -> 3,2,1 -> 1,2,3
     */
    public class LC6 {
        public String convert(String s, int numRows) {
            if (numRows < 2) return s;
            List<StringBuilder> res = new ArrayList<>();
            int index = 0,flag = 1;
            for(int i = 0; i < numRows;i++){
                res.add(new StringBuilder());
            }
            for(char c : s.toCharArray()){
                res.get(index).append(c);
                index+=flag;
                if(index == 0 || index == numRows - 1){
                    flag = - flag;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (StringBuilder stringBuilder : res){
                sb.append(stringBuilder.toString());
            }
            return sb.toString();
        }
    }

    LeetCode150-找出字符串中第一个匹配项的下标-LC28

    /**
     * 题目:找出字符串中第一个匹配项的下标
     * 算法:KMP
     * 思路  1.KMP算法计算出needle的具体数值
     *       2.利用next数组进行回退 当遇到字符不匹配时 
     *       3.j坐标回退 如果j == m说明此时已经匹配到了主串
     *       4.返回结果i - m + 1
     */
    public class LC28 {
        public static void main(String[] args) {
            String haystack = "mississippi", needle = "issip";
            System.out.println(strStr_kmp(haystack,needle));
        }
        public static int strStr_kmp(String haystack, String needle) {
            int j = 0;
            int[] next = new int[needle.length()];
            for(int i = 1;i < needle.length();i++){
                while(j > 0 && needle.charAt(i) != needle.charAt(j)){
                    j = next[j - 1];
                }
                if(needle.charAt(i) == needle.charAt(j)){
                    j++;
                }
                next[i] = j;
            }
            for(int i = 0,k = 0;i < haystack.length();i++){
                while(j > 0 && needle.charAt(j) != haystack.charAt(i)){
                    j = next[j - 1];
                }
                if(needle.charAt(j) == haystack.charAt(i)){
                    j++;
                }
                if(j == needle.length()){
                    return i - needle.length() + 1;
                }
            }
            return -1;
        }
    
        @Deprecated
        public static int strStr_index(String haystack, String needle) {
            int targetLen = needle.length();
            int index = 0;
            for(int i = 0;i < haystack.length();i++){
                if(haystack.charAt(i) == needle.charAt(index)){
                    index++;
                }else{
                    index = 0;
                }
                if(index == targetLen){
                    return i - targetLen + 1;
                }
            }
            return -1;
        }
    }

    数组字符串总结

    1.移除元素

    2.删除有序数组中的重复项

    双指针->if(nums[fast-1]!=nums[fast])

    3.删除有序数组中的重复项II

    双指针->if(nums[slow-2]!=nums[fast]) -> nums[slow] = nums[fast]

    4.轮转数组

    arr[(i+k)%n]=arr[i] -> System.arraycopy()

    5.买卖股票的最佳时机

    for循环-> 保存最小值pre -> 当前节点-pre不断保存最大ans

    6.买卖股票的最佳时机II

    贪心 保存每一次的差值

    7.跳跃游戏

    满足i <= maxIndex 才会更新最大坐标 如果不满足代表当前位置不可达 return true的条件 满足>=最后一位即可

    8.跳跃游戏II

    记录每一次的最大边界值 当到达最大边界值时 ans++ 并且更新最新的最大边界值 但是注意最后一个坐标可能会重复++ 修改区间[0,length-2]

    9.H指数

    len >= 0 && h < citations[len]条件下 寻找h的最大值 h++ len--

    10.O(1) 时间插入、删除和获取随机元素

    Set+List+Random

    11.除自身以外数组的乘积

    从左到右将结果数字相乘[1,len) 从右到左将结果数组相乘 [len-1,0]

    12.加油站

    记录坐标位置i 步数index 记录对应每一个坐标每一步所需要的开销和油量 坐标更替要用到(i+k)%n 开销大于油量break index走到len说明走到了原位返回即可 剪枝优化i=i+1+index [i,j]不行 [i+1,j]也不行

    13.分发糖果

    ans数组从左到右更新当前值 从右到左比对 起点为1 right不断++ res记录right值和ans[i] 谁最大添加谁

    14.接雨水

    双指针 [left,right]区间 记录最大的left_maxright_max 使用最大的max值减去当前值即可获取水池的大小 保证水池是最小的 左右指针每次只移动一个

    15.罗马数字转整数

    罗马数字保存到map中 如果匹配到特殊组合将其从结果减去并添加特殊值

    16.整数转罗马数字

    values对应上字母symbols for循环对于每一位字符使用while循环不断减去 sb添加坐标位置字符

    17.最后一个单词的长度

    trim()去掉首尾空格 匹配或者split()

    18.最长公共前缀

    两两比较放到下一次比较中

    19.反转字符串中的单词

    双端队列

    20.Z字形变换

    反转flag 对应多个StringBuilder stringBuilder的坐标位置根据index变化

    21.找出字符串中第一个匹配项的坐标

    KMP算法的简单应用
    KMP模版

    int[] next = new int[haystack.length()];
    // i 从 1 开始 0号坐标没有前后缀
    for(int i = 1,j = 0; i < haystack.length();i++){
        while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
            j = next[j - 1];
        }
        if(haystack.charAt(i) == needle.charAt(j)){
            j++;
        }
        next[i] = j;
    }