當前位置:網站首頁>面試題 01.05. 一次編輯 / 劍指 Offer II 041. 滑動窗口的平均值

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

2022-05-14 02:53:52彼淇梁

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

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

假如一次編輯就能讓兩個字符串相等,那麼除了這個編輯比特置外的其餘字符,應該對應比特置是相等的。因此,字符串長度大於1的肯定不可能通過一次編輯實現字符串相等,直接排除。
如果first長度大於second,就將兩個傳入參數比特置調換,確保第一個字符串first長度 <= second長度
通過指針i錶示字符串first的字符,通過指針j錶示字符串second的字符,同時遍曆兩個字符串,當i比特置字符和j比特置字符相等時,ij同時右移判斷下一個比特置字符;否則,如果first長度和second長度相等,說明firstsecond如果想成功一次編輯相等,則除了這個比特置之後,再不能出現字符不等的情况,於是ij同時右移,且cnt++(cnt為异常比特置數量),如果firstsecond長度不等,那麼從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); */

版權聲明
本文為[彼淇梁]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205140253042952.html

隨機推薦