This is a record of my craking process for Leetcode.
1. Leftmost Column with at Least a One (#1428)
1.1 Soulution1
The most simple way is two use brute-force (which takes $n^2$ time) But we can optimize it with binary-search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
int rows = binaryMatrix.dimensions().get(0);
int columns = binaryMatrix.dimensions().get(1);
int res = columns;
for(int row = 0; row < rows; row++) {
int lo = 0;
int hi = columns - 1;
while(lo < hi) {
int mid = lo + (hi - lo) / 2;
if(binaryMatrix.get(row, mid) == 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
if(binaryMatrix.get(row, lo) == 1) {
res = Math.min(lo, res);
}
}
return res == columns ? -1 : res;
}
}
|
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
| use std::cmp;
impl Solution {
pub fn left_most_column_with_one(binaryMatrix: &BinaryMatrix) -> i32 {
let rows = binaryMatrix.dimensions()[0];
let cols = binaryMatrix.dimensions()[1];
let mut res = cols;
for row in (0..rows) {
let mut lo = 0;
let mut hi = cols - 1;
while(lo < hi) {
let mid = lo + (hi - lo) / 2;
if(binaryMatrix.get(row, mid) == 0) {
lo = mid + 1;
}else {
hi = mid;
}
}
if(binaryMatrix.get(row, lo) == 1) {
res = cmp::min(res, lo);
}
}
if(res == cols){
-1
} else{
res
}
}
}
|
1.1 Soulution2
An alternate way is doing one loop (going thorugh the two-dimension table) starting from right-top corner.
When we reach a ‘1’ we choose to go left otherwise go down
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
List<Integer> dimensions = binaryMatrix.dimensions();
int r = dimensions.get(0) - 1;
int c = dimensions.get(1) - 1;
while (r >= 0 && c >= 0) {
if (binaryMatrix.get(r, c) == 0) {
r--;
} else {
c--;
}
}
if (c == dimensions.get(1) - 1) {
return -1;
}
return c + 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| use std::cmp;
impl Solution {
pub fn left_most_column_with_one(binaryMatrix: &BinaryMatrix) -> i32 {
let rows = binaryMatrix.dimensions()[0];
let cols = binaryMatrix.dimensions()[1];
let mut current_row = 0;
let mut current_col = cols - 1;
while(current_row < rows && current_col >= 0) {
if(binaryMatrix.get(current_row, current_col) == 0) {
current_row += 1;
} else {
current_col -= 1;
}
}
if(current_col == cols - 1) {
-1
} else {
current_col + 1
}
}
}
|
2. Move Zeroes (#283)
2.1 Soulution1
A very straight-forward 2-point method
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public void moveZeroes(int[] nums) {
for(int p = 0, q = 0; p < nums.length; p++) {
if(nums[p] != 0) {
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
q++;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| impl Solution {
pub fn move_zeroes(nums: &mut Vec<i32>) {
let mut i = 0;
let mut j = 0;
while i < nums.len(){
if nums[i] != 0{
let temp: i32 = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j += 1;
}
i += 1;
}
}
}
|