Leetcode Review (1)

Posted on | In |

在Leetcode上也做了一些题目了，但是一直都是在草稿本上写一些思路，感觉不用心写的话，用我的榆木脑袋怎么也记不住难点。所以打算之后每天在blog上记录一下做题的大致思路。（不知道能坚持多久呢T T）

Leetcode 130 Surrounded Regions

Description:

Given a 2D boardcontaining ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region iscaptured by flipping all ‘O’s into ‘X’s in that surrounded region.

Method:

这题是昨天做的，所以印象非常深刻。

  • 所有和边缘的o相邻接的o都不会被包围进去。
  • 把和最边缘的o相邻接的o都变成,最后再把非的o反转。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public void solve(char[][] board) {
        
        int m = board.length;
        if(m==0) return;
        int n = board[0].length;
        
        //只考虑周围一圈的o
        for(int i=0;i<m;i++){
            if(i==0 || i==m-1){
                for(int j = 0;j<n;j++){
                    if(board[i][j]=='O')
                        dfs(board,i,j,m,n);
                }
            }
            else{
                dfs(board,i,0,m,n);
                dfs(board,i,n-1,m,n);
            }
        }
        
        //最后反转
        for(int i=0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(board[i][j]=='O')
                    board[i][j]='X';
                else if(board[i][j]=='*')
                    board[i][j]='O';
            }
        }
        
    }
    public void dfs(char[][] board,int i, int j,int m, int n){
        if(i>=m || i<0 || j>=n || j<0 || board[i][j] != 'O')
            return;
        board[i][j]='*';
        dfs(board,i+1,j,m,n);
        dfs(board,i-1,j,m,n);
        dfs(board,i,j+1,m,n);
        dfs(board,i,j-1,m,n);
    }
}

Leetcode 665 Non-decreasing Array

Description:

Given an array with n integers, your task is to check if it could becomenon-decreasing by modifying at most 1 element.

We define an arrayis non-decreasing if array[i] <= array[i + 1] holds for every i (1<= i < n).

Methods:

遍历数组，然后修改数组以满足condition（数组大小非降）。然后check修改次数是否超过1。

写了半天情况。真的是，如果这种题笔试，我估计要死。

假设有 A B C这三个数分别是num[i-1] num[i] 和 num[i+1].

则为了非降，则有这两种大情况：

1.B>C

2.A>B

首先是B>C。这里有两种改法，一种是令B=C,一种是令C=B。但是要怎么改，取决于A的大小。

If B>C && A>C ===> C=B

else if B>C && A<=C ===> B=C

为什么呢，当然是为了让尽量减少修改次数啦。可以体会一些，嗯嗯。

我最后再考虑A>B的情况，在B修改之后的情况中，可能不需要考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean checkPossibility(int[] nums) {
        
        int count=0;
        int n = nums.length;
        if(n<=2)
            return true;
        
        for(int i=1;i<n-1&&count<2;i++){
            if(nums[i+1]<nums[i]){
                count++;
                if(nums[i-1]>nums[i+1])
                     nums[i+1]=nums[i];
                else
                    nums[i]=nums[i+1];
            }
            if(nums[i-1]>nums[i]){
                nums[i-1]=nums[i];
                count++;
            }
        }
           
        
        return count<=1;
    }
}

闲话：

最近看aldnoah zero。真的是无比心疼小天使Slaine。尽管已经知道他不会有的好的结局，还是希望能好好把他或辉煌或悲惨的过去再好好描绘一遍。