面試題 01.05. 一次編輯 / 劍指 Offer II 041. 滑動窗口的平均值

面試題 01.05. 一次編輯 【中等題】【每日一題】

思路：【雙指針模擬】【注解三葉】

假如一次編輯就能讓兩個字符串相等，那麼除了這個編輯比特置外的其餘字符，應該對應比特置是相等的。因此，字符串長度大於1的肯定不可能通過一次編輯實現字符串相等，直接排除。
如果first長度大於second，就將兩個傳入參數比特置調換，確保第一個字符串first長度 <= second長度。
通過指針i錶示字符串first的字符，通過指針j錶示字符串second的字符，同時遍曆兩個字符串，當i比特置字符和j比特置字符相等時，i和j同時右移判斷下一個比特置字符；否則，如果first長度和second長度相等，說明first和second如果想成功一次編輯相等，則除了這個比特置之後，再不能出現字符不等的情况，於是i和j同時右移，且cnt++(cnt為异常比特置數量)，如果first和second長度不等，那麼從i比特置(包括i)往後，必須跟j比特置(不包括j)往後字符全部相等，即這裏只有j右移1比特，cnt++。

代碼：

class Solution {
    
    public boolean oneEditAway(String first, String second) {
    
        int n1 = first.length(),n2 = second.length();
        //如果兩個字符串長度差大於1，則必不可能通過一次編輯使兩個字符串相等
        if (Math.abs(n1-n2)>1){
    
            return false;
        }
        //保持函數的第一個參數為長度較短的字符串
        if (n1 > n2){
    
            return oneEditAway(second,first);
        }
        //定義第一個字符串指針 i ，第二個字符串指針 j ，异常字符數量 cnt (初值為0)
        int i = 0,j = 0,cnt = 0;
        //終止條件為 first 遍曆結束 或者 second 遍曆結束 或者 异常字符數量 大於 1 三者滿足任意一個，循環都將終止
        while (i < n1 && j < n2 && cnt <= 1){
    
            //同時遍曆兩個字符串，求出當前比特置的字符 c1 c2
            char c1 = first.charAt(i),c2 = second.charAt(j);
            //如果 c1 == c2 說明當前比特置first和second字符相同，繼續遍曆兩個字符串的下一個比特置
            if (c1 == c2){
    
                i++;
                j++;
            }else {
    //如果 c1 != c2，說明當前比特置出現异常
                //如果兩個字符串長度相同，那麼我們想維持一次編輯就能成功，必須默認後邊不可能再出現异常，於是i指針和j指針必須同時右移
                if (n1 == n2){
    
                    i++;
                    j++;
                    //异常字符數量+1
                    cnt++;
                }else {
    
                    //如果兩個字符串長度不等，那麼較長單詞當前比特置可以允許一次失誤，但較短單詞這個比特置不能出現失誤，因此j指針右移，i指針不動
                    j++;
                    //异常字符數量+1
                    cnt++;
                }
            }
        }
        //當循環結束後，如果此時异常字符數量小於等於1，那麼說明我們可以通過一次編輯的方式實現兩個字符串相同
        return cnt <= 1;
    }
}

劍指 Offer II 041. 滑動窗口的平均值【簡單題】

思路；【隊列】

定義一個隊列來存儲進入滑動窗口的值，每執行依次next，就將傳入的元素值加入隊列，並將值累加進sum，當隊列中元素個數大於滑動窗口長度時，將隊列左端元素移除，並在sum中减掉隊列左端的元素值，next返回sum / 隊列中元素個數 ,用cnt來統計隊列中的元素個數。

代碼：

class MovingAverage {
    

    int size;
    int sum;
    Deque<Integer> deque;
    int cnt;
    
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
    
        this.deque = new ArrayDeque<>();
        this.size = size;
        this.sum = 0;
        this.cnt = 0;
    }
    
    public double next(int val) {
    
        deque.offer(val);
        sum += val;
        cnt++;
        if(cnt > size){
    
            sum -= deque.removeFirst();
        }
        return (double) sum / (Math.min(cnt, size));
    }
}

/** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */