劍指offer計劃25（模擬中等）—java

• 2021 年 9 月 25 日
• 筆記
• 面試和leetcode技巧

1.1、題目1

劍指 Offer 29. 順時針列印矩陣

1.2、解法

常規開頭，先判斷特殊情況，然後創建四個變數存放矩陣四邊的長度限制。
創建res數組存放結果。
循壞開始，遍歷完一行或者一列，就將該行從矩陣的範圍內刪除，
最終判斷左邊是否大於右邊，上邊是否大於下邊來判斷循環是否應該結束。

1.3、程式碼

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length==0) return new int[0];
        int l = 0, r=matrix[0].length-1,t=0,b=matrix.length-1,x=0;
        int []res = new int[(r+1)*(b+1)];
        while(true){
            for(int i=l;i<=r;i++) res[x++]=matrix[t][i];
            if(++t>b) break;
            for(int i=t;i<=b;i++) res[x++]=matrix[i][r];
            if(--r<l) break;
            for(int i=r;i>=l;i--) res[x++]=matrix[b][i];
            if(--b<t) break;
            for(int i=b;i>=t;i--) res[x++]=matrix[i][l];
            if(++l>r) break;
        }
        return res;
    }
}

2.1、題目2

劍指 Offer 31. 棧的壓入、彈出序列

2.2、解法

這題我還以為要用什麼數學方法，結果發現用一個棧來實現這個操作就行了。
遍歷pushed數組，每個數都判斷是否為pop的數組裡的當前元素。是的話就推出，並且pop數組的索引+1
最終判斷棧里是否為空則可知道順序是否正確。

2.3、程式碼

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack();
        int x=0;
        for(int i:pushed){
            stack.push(i);
            while(!stack.isEmpty() &&stack.peek()==popped[x]  ) {
                stack.pop();
                x++;
            }
        }
        return stack.isEmpty();
    }
}