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

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

Binary Gap

找一个int中两个1之间最大的距离. 先把int变成string, 然后找每个1的gap, 然后取最大.

class Solution {
    public int binaryGap(int N) {
        if(N < 0 || N == 0)
            return 0;
        String s = Integer.toBinaryString(N);
        int g = 0;
        int[] tmp = new int[s.length()];
        int t = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1'){
                tmp[t++] = i;
            }
        }
        for(int i = 1; i < s.length(); i++) {
            g = Math.max(g, tmp[i] - tmp[i-1]); 
        }
        return g;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public int binaryGap(int N) {

if(N < 0 || N == 0)

return 0;

String s = Integer.toBinaryString(N);

int g = 0;

int[] tmp = new int[s.length()];

int t = 0;

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

if(s.charAt(i) == '1'){

tmp[t++] = i;

}

for(int i = 1; i < s.length(); i++) {

g = Math.max(g, tmp[i] - tmp[i-1]);

}

return g;

}

Date August 2, 2019
Category Leetcode
Comments No Comments

Number of 1 Bits

给个整数, 数一. 因为是Integer,所以一共32位. 1 << i 就是每个位上的1.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        for(int i = 0 ; i < 32; i++) {
            if((n & (1 << i)) != 0)
                res++;
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

public class Solution {

// you need to treat n as an unsigned value

public int hammingWeight(int n) {

int res = 0;

for(int i = 0 ; i < 32; i++) {

if((n & (1 << i)) != 0)

res++;

}

return res;

}

Date August 1, 2019
Category Leetcode
Comments No Comments

Leaf-Similar Trees

比较两棵树的叶子顺序是不是一样. 这个就是traverse一下, 然后比较.

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<Integer>();
        List<Integer> l2 = new ArrayList<Integer>();
        find(root1, l1);
        find(root2, l2);
        if(l1.size() != l2.size())
            return false;
        int size = l1.size();
        for(int i = 0 ; i < size; i++) {
            if(l1.get(i) != l2.get(i))
                return false;
        }
        return true;
    }
    
    private void find(TreeNode root, List<Integer> list) {
        if(root == null)
            return;
        find(root.left,list);
        if(root.left == null && root.right == null)
            list.add(root.val);
        find(root.right,list);
    }
}

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

class Solution {

public boolean leafSimilar(TreeNode root1, TreeNode root2) {

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

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

find(root1, l1);

find(root2, l2);

if(l1.size() != l2.size())

return false;

int size = l1.size();

for(int i = 0 ; i < size; i++) {

if(l1.get(i) != l2.get(i))

return false;

}

return true;

}

private void find(TreeNode root, List<Integer> list) {

if(root == null)

return;

find(root.left,list);

if(root.left == null && root.right == null)

list.add(root.val);

find(root.right,list);

}

Date August 1, 2019
Category Leetcode
Comments No Comments

Middle of the Linked List

找链表中间的点. 用快慢指针

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

1

2

3

4

5

6

7

8

9

10

class Solution {

public ListNode middleNode(ListNode head) {

ListNode slow = head, fast = head;

while (fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

}

return slow;

}

Date July 31, 2019
Category Leetcode
Comments No Comments

Backspace String Compare

Maximize Distance to Closest Person

Peak Index in a Mountain Array

Buddy Strings

Lemonade Change

Transpose Matrix

Binary Gap

Number of 1 Bits

Leaf-Similar Trees

Middle of the Linked List

书脊

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

Categories

Tags

Links

August 2019
M	T	W	T	F	S	S
« Jul
			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