InterviewBit-Day6

发表于 | 分类于
| 字数统计 528 | 阅读时长 3

Practice

Set Matrix Zeros

Given an m x n matrix of 0s and 1s, if an element is 0, set its entire row and column to 0.

Do it in place.

Example

Given array A as

1
2
3
1 0 1
1 1 1 
1 1 1

On returning, the array A should be :

1
2
3
0 0 0
1 0 1
1 0 1
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
public class Solution {
    public void setZeroes(ArrayList<ArrayList<Integer>> a) {
        ArrayList<Integer> cols = new ArrayList<>();
        boolean flag = false;
        for (int i = 0; i < a.size(); i++) {
            ArrayList<Integer> b = a.get(i);
            for (int j = 0; j < b.size(); ) {
                if (flag) {
                    if (a.get(i).get(j) == 0) {
                        cols.add(j);
                    }
                    a.get(i).set(j, 0);
                    j++;
                } else {
                    if (b.get(j) == 0) {
                        flag = true;
                        j = 0;
                    } else {
                        j++;
                    }
                }
            }
            flag = false;
        }

        for (int i = 0; i < a.size(); i++) {
            ArrayList<Integer> b = a.get(i);
            for (int j = 0; j < b.size(); j++) {
                if (cols.contains(j)) {
                    a.get(i).set(j, 0);
                }
            }
        }
    }
}

First Missing Integer

Given an unsorted integer array, find the first missing positive integer.

Example:

Given [1,2,0] return 3,

[3,4,-1,1] return 2,

[-8, -7, -6] returns 1

Your algorithm should run in O(n) time and use constant space.

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
public class Solution {
    public int firstMissingPositive(ArrayList<Integer> A) {
        Collections.sort(A);
        if (A.size() == 1) {
            if (A.get(0) <= 0 || A.get(0) != 1) {
                return 1;
            } else {
                return 2;
            }
        }
        
        boolean flag = false;
        
        for (int i = 0; i < A.size() - 1; i++) {
            if (A.get(i) <= 0) {
                flag = true;
                continue;
            } else {
                if (i == 0 || flag) {
                    if (A.get(i) != 1) {
                        return 1;
                    }
                }
                
                if ((A.get(i) + 1) != A.get(i + 1)) {
                    return A.get(i) + 1;
                }
                
                flag = false;
            }
        }
        
        if (flag) {
            return 1;
        }
        
        return A.get(A.size() - 1) + 1;
    }
}

Rotate Matrix

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

You need to do this in place.

Note that if you end up using an additional array, you will only receive partial score.

Example:

If the array is

1
2
3
4
[
    [1, 2],
    [3, 4]
]

Then the rotated array becomes:

1
2
3
4
[
    [3, 1],
    [4, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solutoion {
    public void rotate(ArrayList<ArrayList<Integer>> a) {
        int n = a.size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int temp = a.get(i).get(j);
                a.get(i).set(j, a.get(n - 1 - j).get(i));
                a.get(n - 1 - j).set(i, a.get(n - 1 - i).get(n - 1 - j));
                a.get(n - 1 - i).set(n - 1 - j, a.get(j).get(n - 1 - i));
                a.get(j).set(n - 1 - i, temp);
            }
        }
    }
}
0%