汇总：用滑动窗口法秒杀力扣题

た入场券 2023-01-15 05:59 139阅读 0赞

# 一、[教程：滑动窗口算法框架（Java版）][Java] #

# 二、汇总 #

## 1.[38. 外观数列][38.] ##

*  AC代码

class Solution {
        
        public String countAndSay(int n) {
        
            String pre = "1";
            for(int i = 2; i <= n; i++) {
        
                String cur = "";
                int left = 0, right = 0;
                int size = pre.length();
                // 扩大窗口
                for(;right <= size; right++) {
        
                    /* 收缩窗口 */
                    if(right == size || pre.charAt(right) != pre.charAt(left)) {
        
                        cur += String.valueOf(right - left) + pre.charAt(left);
                        left = right;
                    }
                }
                pre = cur;
            }
            return pre;
        }
    }

> 相同字符组成的子串问题，立即推：滑动窗口法

## 2.[443. 压缩字符串][443.] ##

*  AC代码

class Solution {
        
        public int compress(char[] chars) {
        
            int right = 0, left = 0;
            int p = 0; // 原地修改输入数组
            // [left, right) 相同的字符集
            for(; right <= chars.length; right++) {
        
                 //for循环：扩大窗口
    
                if(right == chars.length || chars[right] != chars[left]) {
        
                    /* 压缩，并缩小窗口 */
                    chars[p++] = chars[left];
                    if(right - left > 1) {
        
                        // >1才需要存储字符个数
                        for(char c : String.valueOf(right - left).toCharArray()) {
        
                            chars[p++] = c;
                        }
                    }
                    left = right;
                }
            }
            return p;
        }
    }

> 和38题十分相似！

## 3.[68. 文本左右对齐][68.] ##

*  AC代码

class Solution {
        
        public List<String> fullJustify(String[] words, int maxWidth) {
        
            /* 滑动窗口法 [left, right)*/
            List<String> res = new ArrayList<>();
            int allLength = 0;
            int right = 0, left = 0;
            while(right < words.length) {
        
                // 扩大窗口
                while(right < words.length && allLength + right - left - 1 < maxWidth) {
        
                    allLength += words[right].length();
                    right++;
                    if(right == words.length || allLength + words[right].length() + right - left > maxWidth)
                    	break;
                }
                /* 处理并缩小窗口 */
                StringBuilder sb = new StringBuilder();
                if(allLength + right - left - 1 == maxWidth) {
        
                    for(int i = left; i < right; i++) {
        
                        sb.append(words[i]);
                        if(i != right - 1) sb.append(" ");
                    }
                }
                else {
        
                    if(right == words.length || right - left == 1) {
        
                         //只有1个单词 || 最后1行,则左对齐
                        for(int i = left; i < right; i++) {
        
                            sb.append(words[i]);
                            if(i != right - 1) sb.append(" ");
                        }
                        while(sb.length() != maxWidth)
                            sb.append(" ");
                    }
                    else {
        
                        /* 分空格 
                        ①商：至少有多少空格；
                        ②余数：从左往右，1个1个分；
                        */
                        int countSpace = maxWidth - allLength;
                        int average = countSpace / (right - left - 1);
                        int rest = countSpace % (right - left - 1);
                        for(int i = left; i < right; i++) {
        
                            sb.append(words[i]);
                            if(i != right - 1) {
        
                                int tmp = average + (rest != 0 ? 1 : 0);
                                for(int j = 0; j < tmp; j++)
                                    sb.append(" ");
                                if(rest != 0) rest--;
                            }
                        }
                    }
                }
                res.add(sb.toString());
                left = right;
                allLength = 0;
            }
            return res;
        }
    }

> 这道题也用到了滑动窗口的思想，但毕竟这道题的难度为困难，所以在滑动窗口算法框架的基础上还有如下需要攻克的细节：  
> ①right++后，就需要判断是否要停止扩大窗口了  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]  
> ②如果窗口恰好满足题意：即"单词 单词 单词"  
> ![在这里插入图片描述][20210425142600179.png]  
> ③如果窗口中只有1个单词，或者right == words.length了  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]  
> ④窗口中有多个单词，需要分配空格–尽量左边的空格多一些，比如4个空格，3个间隔，即2，1，1。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 2]

## 未完待续 ##

[Java]: https://blog.csdn.net/weixin_37477009/article/details/115751124
[38.]: https://leetcode-cn.com/problems/count-and-say/
[443.]: https://leetcode-cn.com/problems/string-compression/
[68.]: https://leetcode-cn.com/problems/text-justification/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221022/ccb630af8b2c42ce912c0e1482d63361.png
[20210425142600179.png]: /images/20221022/1c1142cedbaa49e38d8d05c1b86d947e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/2e5e7804ac1a4b3d8cad69079d427ecb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/2f27bfe3da93476e8d1ee7079c4933a2.png