书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Positions of Large Groups

找到一个string上连续长度超过3个同样字符的位置. 返回的是index.

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        while(i < S.length()) {
            List<Integer> cur = new ArrayList<>();
            char c = S.charAt(i);
            cur.add(i); // add start position first
            while(i < S.length() && S.charAt(i) == c)
                i++;
            if(i - cur.get(0) > 2) {
                cur.add(i-1);//add end position only if it is a large group
                res.add(cur);
            }
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution {

public List<List<Integer>> largeGroupPositions(String S) {

List<List<Integer>> res = new ArrayList<>();

int i = 0;

while(i < S.length()) {

List<Integer> cur = new ArrayList<>();

char c = S.charAt(i);

cur.add(i); // add start position first

while(i < S.length() && S.charAt(i) == c)

i++;

if(i - cur.get(0) > 2) {

cur.add(i-1);//add end position only if it is a large group

res.add(cur);

}

return res;

}

Date September 22, 2019
Category Leetcode
Comments No Comments

Flipping an Image

先左右翻转, 然后0/1互换

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        rev(A);
        inv(A);
        return A;
    }
    
    private void inv(int[][] A) {
        for(int i = 0 ; i < A.length; i++) {
            for(int j = 0; j < A[0].length; j++) {
                if(A[i][j] == 0)
                    A[i][j] = 1;
                else
                    A[i][j] = 0;
            }
        }
    }
    
    private void rev(int[][] A) {
        for(int k = 0; k < A.length; k++) {
            swap(A, k);
        }
    }
    
    private void swap(int[][]A, int k) {
        int i = 0;
        int j = A[0].length - 1;
        while(i < j) {
            int t = A[k][i];
            A[k][i] = A[k][j];
            A[k][j] = t;
            i++;
            j--;
        }
    }
}

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

class Solution {

public int[][] flipAndInvertImage(int[][] A) {

rev(A);

inv(A);

return A;

}

private void inv(int[][] A) {

for(int i = 0 ; i < A.length; i++) {

for(int j = 0; j < A[0].length; j++) {

if(A[i][j] == 0)

A[i][j] = 1;

else

A[i][j] = 0;

}

private void rev(int[][] A) {

for(int k = 0; k < A.length; k++) {

swap(A, k);

}

private void swap(int[][]A, int k) {

int i = 0;

int j = A[0].length - 1;

while(i < j) {

int t = A[k][i];

A[k][i] = A[k][j];

A[k][j] = t;

i++;

j--;

}

Date September 20, 2019
Category Leetcode
Comments No Comments

Shortest Distance to a Character

扫两次, 用count记录非C的字符的个数, 这时候注意两边的corn case, 开始扫的时候要把count设置为MAX, 因为如果是0, 那么是意味着当前i的位置的字符是C. 所以要设置成MAX

class Solution {
    public int[] shortestToChar(String S, char C) {
        int[] res = new int[S.length()];
        int count = Integer.MAX_VALUE / 2;
        for (int i = 0 ; i < S.length(); i++) {
            if(S.charAt(i) == C) {
                count = 0;
            }
            res[i] = count++;
        }
        count = Integer.MAX_VALUE / 2;
        for(int i = S.length() - 1; i >= 0; i--) {
            if(S.charAt(i) == C) {
                count = 0;
            }
            res[i] = Math.min(count++, res[i]);
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public int[] shortestToChar(String S, char C) {

int[] res = new int[S.length()];

int count = Integer.MAX_VALUE / 2;

for (int i = 0 ; i < S.length(); i++) {

if(S.charAt(i) == C) {

count = 0;

}

res[i] = count++;

}

count = Integer.MAX_VALUE / 2;

for(int i = S.length() - 1; i >= 0; i--) {

if(S.charAt(i) == C) {

count = 0;

}

res[i] = Math.min(count++, res[i]);

}

return res;

}

Date September 4, 2019
Category Leetcode
Comments No Comments

Rectangle Overlap

给两个矩形, 判断是不是重合. 开始我是算面积判断的, code很长, 因为算面积的时候, 需要判断两个矩阵的相对位置, 所以要判断很多次. 答案是依靠判断几个角的坐标位置.

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
       if (rec1[0]>=rec2[2]) {
           return false;
       }
        if(rec2[0]>=rec1[2]) {
            return false;
       }
       if (rec1[1]>=rec2[3]) {
           return false;
       }
       if (rec2[1]>=rec1[3]) {
           return false;
       }
    return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public boolean isRectangleOverlap(int[] rec1, int[] rec2) {

if (rec1[0]>=rec2[2]) {

return false;

}

if(rec2[0]>=rec1[2]) {

return false;

}

if (rec1[1]>=rec2[3]) {

return false;

}

if (rec2[1]>=rec1[3]) {

return false;

}

return true;

}

Date August 23, 2019
Category Leetcode
Comments No Comments

Backspace String Compare

看两个string是不是相同, string里的#号是删除下一个字符.

class Solution {
    public boolean backspaceCompare(String S, String T) {
        StringBuffer sb1 = new StringBuffer(S);
        StringBuffer sb2 = new StringBuffer(T);
        sb1.reverse();
        sb2.reverse();
        return modify(sb1).equals(modify(sb2));
    }
    
    private String modify(StringBuffer sb) {
        int skip = 0;
        StringBuffer tmp = new StringBuffer();
        for(int i = 0 ; i < sb.length(); i++) {
            if(sb.charAt(i) == '#') {
                skip++;
                continue;
            }
            else if(skip > 0){
                skip--;
                continue;
            }
            else{
                   tmp.append(sb.charAt(i));
            }
        }
        System.out.println(tmp.toString());
        return tmp.toString();
    }
}

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

class Solution {

public boolean backspaceCompare(String S, String T) {

StringBuffer sb1 = new StringBuffer(S);

StringBuffer sb2 = new StringBuffer(T);

sb1.reverse();

sb2.reverse();

return modify(sb1).equals(modify(sb2));

}

private String modify(StringBuffer sb) {

int skip = 0;

StringBuffer tmp = new StringBuffer();

for(int i = 0 ; i < sb.length(); i++) {

if(sb.charAt(i) == '#') {

skip++;

continue;

}

else if(skip > 0){

skip--;

continue;

}

else{

tmp.append(sb.charAt(i));

}

System.out.println(tmp.toString());

return tmp.toString();

}

Date August 13, 2019
Category Leetcode
Comments No Comments

Maximize Distance to Closest Person

给一个数组, 找其中的0到两边1最短距离. 这个题N^2还是很好做的, 就是一个扫一边内嵌一个while双指针.

但是N的做法就需要点考虑, 我是用counting的方法, 遇到0就记录一下0的个数, 遇到1就知道前边0的个数, 这样除一下2就知道中间的位置.

class Solution {
    public int maxDistToClosest(int[] seats) {
        int res = 0;
        int cur = 0;
        for (int i=0;i<seats.length;i++){
            if (seats[i]==0){
                cur++; // count the number of 0
            }
            else {
                if (i-cur>0){
                    cur=cur/2 + cur%2;
                }
                res = Math.max(res,cur);   
                cur=0;
            }
            
        }
        res = Math.max(res,cur);
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution {

public int maxDistToClosest(int[] seats) {

int res = 0;

int cur = 0;

for (int i=0;i<seats.length;i++){

if (seats[i]==0){

cur++; // count the number of 0

}

else {

if (i-cur>0){

cur=cur/2 + cur%2;

}

res = Math.max(res,cur);

cur=0;

}

res = Math.max(res,cur);

return res;

}

Date August 8, 2019
Category Leetcode
Comments No Comments

Peak Index in a Mountain Array

给一个数组, 找一个index,比左大比右小, 这个题前提是这个index一定存在, 省去很多corn cases的判断, 直接二分找

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int start = 0, end = A.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < A[mid + 1])
                start = mid + 1;
            else
                end = mid;
        }
        return start;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution {

public int peakIndexInMountainArray(int[] A) {

int start = 0, end = A.length - 1;

while (start < end) {

int mid = start + (end - start) / 2;

if (A[mid] < A[mid + 1])

start = mid + 1;

else

end = mid;

}

return start;

}

Date August 8, 2019
Category Leetcode
Comments No Comments

Buddy Strings

给两个字符串, 问交换其中一个字符串的两个字符后能不能变成另一个字符串. 这个题corn case很多….

class Solution {
    public boolean buddyStrings(String A, String B) {
        if(A.length() != B.length())
            return false;
        if(A.equals(B)){
            int[] count = new int[26];
            for (int i = 0; i < A.length(); ++i)
                count[A.charAt(i) - 'a']++;
            for (int c: count)
                if (c > 1) return true;
            return false;
        }
        int first = -1, second = -1;
            for (int i = 0; i < A.length(); ++i) {
                if (A.charAt(i) != B.charAt(i)) {
                    if (first == -1)
                        first = i;
                    else if (second == -1)
                        second = i;
                    else
                        return false;
                }
            }
        return (second != -1 && A.charAt(first) == B.charAt(second) &&
                    A.charAt(second) == B.charAt(first));
    }
}

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

class Solution {

public boolean buddyStrings(String A, String B) {

if(A.length() != B.length())

return false;

if(A.equals(B)){

int[] count = new int[26];

for (int i = 0; i < A.length(); ++i)

count[A.charAt(i) - 'a']++;

for (int c: count)

if (c > 1) return true;

return false;

}

int first = -1, second = -1;

for (int i = 0; i < A.length(); ++i) {

if (A.charAt(i) != B.charAt(i)) {

if (first == -1)

first = i;

else if (second == -1)

second = i;

else

return false;

}

return (second != -1 && A.charAt(first) == B.charAt(second) &&

A.charAt(second) == B.charAt(first));

}

Date August 8, 2019
Category Leetcode
Comments No Comments

Lemonade Change

买东西, 价值5块, 一共有三种货币5,10,20. 问能不能找开. 这个遇到20$先找大的($10 + $5), 再找小的($5 x 3).

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int[] t = new int[2]; // t[0] = 5$, t[1] = 10$
        for(int i = 0; i < bills.length; i++) {
            if(bills[i] == 5)
                t[0]++;
            else if(bills[i] == 10){
                if(t[0] >= 1){
                    t[0]--;
                    t[1]++;
                }
                else{
                    return false;
                }
            }
            else{
                 if(t[0] > 0 && t[1] > 0) { // 1 $10 + 1 $5
                     t[0] --;
                     t[1] --;
                 }
                 else if(t[0] >= 3) { // 3 $5
                     t[0] -= 3;
                 }
                 else {
                     return false;
                 }
            }
        }
        return true;
    }
}

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

class Solution {

public boolean lemonadeChange(int[] bills) {

int[] t = new int[2]; // t[0] = 5$, t[1] = 10$

for(int i = 0; i < bills.length; i++) {

if(bills[i] == 5)

t[0]++;

else if(bills[i] == 10){

if(t[0] >= 1){

t[0]--;

t[1]++;

}

else{

return false;

}

else{

if(t[0] > 0 && t[1] > 0) { // 1 $10 + 1 $5

t[0] --;

t[1] --;

}

else if(t[0] >= 3) { // 3 $5

t[0] -= 3;

}

else {

return false;

}

return true;

}

Date August 2, 2019
Category Leetcode
Comments No Comments

Transpose Matrix

转置矩阵. 常规操作

class Solution {
    public int[][] transpose(int[][] A) {
        int[][] res = new int[A[0].length][A.length];
        int row = 0;
        int col = 0;
        for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < A[0].length; j++) {
                res[row++][col] = A[i][j];
            }
            row = 0;
            col++;
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

public int[][] transpose(int[][] A) {

int[][] res = new int[A[0].length][A.length];

int row = 0;

int col = 0;

for(int i = 0; i < A.length; i++) {

for(int j = 0; j < A[0].length; j++) {

res[row++][col] = A[i][j];

}

row = 0;

col++;

}

return res;

}

Date August 2, 2019
Category Leetcode
Comments No Comments

Positions of Large Groups

Flipping an Image

Shortest Distance to a Character

Rectangle Overlap

Backspace String Compare

Maximize Distance to Closest Person

Peak Index in a Mountain Array

Buddy Strings

Lemonade Change

Transpose Matrix

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags

Links

September 2019
M	T	W	T	F	S	S
« Aug
						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