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

Redundant Connection

并查集模板题

class Solution {
    class uf{
        int[] p;
        int n;
        public uf(int n){
            this.n = n + 1;
            this.p = new int[n + 1];
            for(int i = 1; i <= n; i++)
                this.p[i] = i;
        }
        public int find(int n){
            if(p[n] == n)
                return n;
            p[n] = find(p[n]);
            return p[n];
        }
        
        public void union(int a, int b){
            int ra = find(a);
            int rb = find(b);
            if(ra == rb)
                return;
            if(ra < rb)
                p[ra] = rb;
            else
                p[rb] = ra;
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        uf u = new uf(n);
        for(int[] e : edges){
            if(u.find(e[0]) != u.find(e[1]))
                u.union(e[0], e[1]);
            else
                return e;
        }
        return null;
    }
}

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

class Solution {

class uf{

int[] p;

int n;

public uf(int n){

this.n = n + 1;

this.p = new int[n + 1];

for(int i = 1; i <= n; i++)

this.p[i] = i;

}

public int find(int n){

if(p[n] == n)

return n;

p[n] = find(p[n]);

return p[n];

}

public void union(int a, int b){

int ra = find(a);

int rb = find(b);

if(ra == rb)

return;

if(ra < rb)

p[ra] = rb;

else

p[rb] = ra;

}

public int[] findRedundantConnection(int[][] edges) {

int n = edges.length;

uf u = new uf(n);

for(int[] e : edges){

if(u.find(e[0]) != u.find(e[1]))

u.union(e[0], e[1]);

else

return e;

}

return null;

}

Date June 2, 2022
Category Leetcode
Comments No Comments

Swim in Rising Water

class Solution {
    int[][] dirs = new int[][]{
        {-1,0},
        {1,0},
        {0, 1},
        {0, -1}
    };
    public int swimInWater(int[][] grid) {
        boolean[][] v = new boolean[grid.length][grid[0].length];
        int res = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (a[2] - b[2]));
        q.add(new int[]{0,0,grid[0][0]});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(v[cur[0]][cur[1]])
                continue;
            res = Math.max(res, cur[2]);
            if(cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1)
                break;
            v[cur[0]][cur[1]] = true;
            for(int[] d : dirs){
                int nr = d[0] + cur[0];
                int nc = d[1] + cur[1];
                if(0 <= nr && nr < grid.length && 0 <= nc && nc < grid[0].length && !v[nr][nc]){
                    q.add(new int[]{nr, nc,grid[nr][nc]});
                }
            }
        }
        return 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

29

30

31

class Solution {

int[][] dirs = new int[][]{

{-1,0},

{1,0},

{0, 1},

{0, -1}

};

public int swimInWater(int[][] grid) {

boolean[][] v = new boolean[grid.length][grid[0].length];

int res = 0;

PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (a[2] - b[2]));

q.add(new int[]{0,0,grid[0][0]});

while(!q.isEmpty()){

int[] cur = q.poll();

if(v[cur[0]][cur[1]])

continue;

res = Math.max(res, cur[2]);

if(cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1)

break;

v[cur[0]][cur[1]] = true;

for(int[] d : dirs){

int nr = d[0] + cur[0];

int nc = d[1] + cur[1];

if(0 <= nr && nr < grid.length && 0 <= nc && nc < grid[0].length && !v[nr][nc]){

q.add(new int[]{nr, nc,grid[nr][nc]});

}

return res;

}

Date June 1, 2022
Category Leetcode
Comments No Comments

Keys and Rooms

给一个rooms的列表, 里面只有第一个room是开锁的, 其他room的锁的钥匙在各个房间, 求是否能访问所有的room

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        visited[0] = true;
        for(int nn : rooms.get(0)){
            q.add(nn);
        }
        while(!q.isEmpty()){
            int t = q.poll();
            if(!visited[t]){
                visited[t] = true;
                for(int nn : rooms.get(t))
                    q.add(nn);
            }
        }
        for(boolean b : visited)
            if(!b)
                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

class Solution {

public boolean canVisitAllRooms(List<List<Integer>> rooms) {

int n = rooms.size();

boolean[] visited = new boolean[n];

Queue<Integer> q = new LinkedList<>();

visited[0] = true;

for(int nn : rooms.get(0)){

q.add(nn);

}

while(!q.isEmpty()){

int t = q.poll();

if(!visited[t]){

visited[t] = true;

for(int nn : rooms.get(t))

q.add(nn);

}

for(boolean b : visited)

if(!b)

return false;

return true;

}

Date May 28, 2022
Category Leetcode
Comments No Comments

Custom Sort String

给一个字符串是序列的order, 求排序一个字符串.

class Solution {
    public String customSortString(String order, String s) {
        Map<Character, Integer> m = new HashMap<>();
        int k = 100;
        for(char c : order.toCharArray())
            m.put(c, k--);
        List<Character> list = new ArrayList<>();
        for(char c : s.toCharArray())
            list.add(c);
        Collections.sort(list, (a,b) ->{
            int aa = m.getOrDefault(a, Integer.MAX_VALUE / 2);
            int bb = m.getOrDefault(b, Integer.MAX_VALUE / 2);
            return bb - aa;
        });
        StringBuilder sb = new StringBuilder();
        for(char c : list)
            sb.append(c);
        return sb.toString();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public String customSortString(String order, String s) {

Map<Character, Integer> m = new HashMap<>();

int k = 100;

for(char c : order.toCharArray())

m.put(c, k--);

List<Character> list = new ArrayList<>();

for(char c : s.toCharArray())

list.add(c);

Collections.sort(list, (a,b) ->{

int aa = m.getOrDefault(a, Integer.MAX_VALUE / 2);

int bb = m.getOrDefault(b, Integer.MAX_VALUE / 2);

return bb - aa;

});

StringBuilder sb = new StringBuilder();

for(char c : list)

sb.append(c);

return sb.toString();

}

Date May 28, 2022
Category Leetcode
Comments No Comments

Projection Area of 3D Shapes

给一个grids, 里面是3d的unit tube, 求三面投影.

这题读懂这个grids的设计即可. 还有个测试是value = 0…

class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int xy = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++){
                if(grid[i][j] != 0)
                   xy++; 
            }
        }      
        int xz = 0; 
        for(int i = 0; i < n; i++) {
            int max = 0;
            for(int j = 0; j < m; j++){
                if(grid[i][j] != 0)
                    max = Math.max(max,grid[i][j]);
            }
            xz += max;
        }
        int zy = 0;
        for(int j = 0; j < m; j++) {
            int max = 0;
            for(int i = 0; i < n; i++){
                if(grid[i][j] != 0)
                    max = Math.max(max,grid[i][j]);
            }
            zy += max;
        }
        return xy + xz + zy;
    }
}

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

class Solution {

public int projectionArea(int[][] grid) {

int n = grid.length;

int m = grid[0].length;

int xy = 0;

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

for(int j = 0; j < m; j++){

if(grid[i][j] != 0)

xy++;

}

int xz = 0;

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

int max = 0;

for(int j = 0; j < m; j++){

if(grid[i][j] != 0)

max = Math.max(max,grid[i][j]);

}

xz += max;

}

int zy = 0;

for(int j = 0; j < m; j++) {

int max = 0;

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

if(grid[i][j] != 0)

max = Math.max(max,grid[i][j]);

}

zy += max;

}

return xy + xz + zy;

}

Date May 28, 2022
Category Leetcode
Comments No Comments

Partition Array for Maximum Sum

给一个数组和一个数字k, 可以有一种操作, 把k个数组变成最大的数字. 求最大的数组.

这题动态规划直接做, 然后注意一下边界.

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        int res = 0;
        for(int i = 0; i <= n; i++) {
            int max = 0;
            int t = Math.max(0, i - k);
            for(int j = i - 1; t <= j; j--) {
                max = Math.max(max, arr[j]); 
                dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); // dp[i - 1] dp[i - 2]
            }
        }
        return dp[n];
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int maxSumAfterPartitioning(int[] arr, int k) {

int n = arr.length;

int[] dp = new int[n + 1];

int res = 0;

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

int max = 0;

int t = Math.max(0, i - k);

for(int j = i - 1; t <= j; j--) {

max = Math.max(max, arr[j]);

dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); // dp[i - 1] dp[i - 2]

}

return dp[n];

}

Date May 28, 2022
Category Leetcode
Comments No Comments

Swap Adjacent in LR String

这题就是看L和R的特性, 有三个特性, L不能往右走,R不能往左走, 去掉X两个string一样.

class Solution {
    public boolean canTransform(String start, String end) {
        int i = 0;
        int j = 0;
        int n = start.length();
        int m = end.length();
        while(i < n && j < m){
            if(start.charAt(i) == 'X'){
                i++;
            }else if(end.charAt(j) == 'X'){
                j++;
            }else{ // no X
                if(start.charAt(i) != end.charAt(j))
                    return false;
                if(start.charAt(i) == 'R' && i > j)
                    //  s[i] == e[j]   start = xxR (i == 2) end = xRx (i == 1)
                    return false;
                if(start.charAt(i) == 'L' && i < j)
                    //  s[i] == e[j]  start = xLx (i == 1) end = xxL (i == 2)
                    return false;
                i++;
                j++;
            }       
        }
        while(i < n){
            if(start.charAt(i) != 'X') // xxxxLRLRLxxxxxL false
                return false;
            i++;
        }
        while(j < m){
            if(end.charAt(j) != 'X')
                return false;
            j++;
        }
        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

32

33

34

35

36

37

class Solution {

public boolean canTransform(String start, String end) {

int i = 0;

int j = 0;

int n = start.length();

int m = end.length();

while(i < n && j < m){

if(start.charAt(i) == 'X'){

i++;

}else if(end.charAt(j) == 'X'){

j++;

}else{ // no X

if(start.charAt(i) != end.charAt(j))

return false;

if(start.charAt(i) == 'R' && i > j)

// s[i] == e[j] start = xxR (i == 2) end = xRx (i == 1)

return false;

if(start.charAt(i) == 'L' && i < j)

// s[i] == e[j] start = xLx (i == 1) end = xxL (i == 2)

return false;

i++;

j++;

}

while(i < n){

if(start.charAt(i) != 'X') // xxxxLRLRLxxxxxL false

return false;

i++;

}

while(j < m){

if(end.charAt(j) != 'X')

return false;

j++;

}

return true;

}

Date May 27, 2022
Category Leetcode
Comments No Comments

Encode Number

class Solution {
    public String encode(int num) {
        return Integer.toBinaryString(num + 1).substring(1);
    }
}

1

2

3

4

5

class Solution {

public String encode(int num) {

return Integer.toBinaryString(num + 1).substring(1);

}

Date May 27, 2022
Category Leetcode
Comments No Comments

Count Substrings That Differ by One Character

给两个字符串s和t, 求有多少个s和t的子字符串差一个字符.

这题和数相同子串不同的就是数差一个字符的子串个数. 首先先数一下相同的子串个数, 然后再数不同的.

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        int[][] allMatch = new int[n][m]; // # of substring all match for s and t untill i,j
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < t.length(); j++) {
                boolean ma = s.charAt(i) == t.charAt(j);
                if(i == 0 || j == 0){
                    if(ma){
                        allMatch[i][j] = 1;
                    }
                }
                else
                {
                    if(ma){
                        allMatch[i][j] = allMatch[i - 1][j - 1] + 1;
                    }
                    else{
                        allMatch[i][j] = 0;
                    }
                }
            }
        }
        int[][] missOne = new int[n][m];
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < t.length(); j++) {
                boolean ma = s.charAt(i) == t.charAt(j);
                if(i == 0 || j == 0){
                    if(!ma){
                        missOne[i][j] = 1;
                    }
                }
                else
                {
                    if(ma){
                        missOne[i][j] = missOne[i - 1][j - 1];
                    }
                    else{
                        missOne[i][j] = allMatch[i - 1][j - 1] + 1;
                    }
                }
                res += missOne[i][j];
            }
        }
        return 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

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

class Solution {

public int countSubstrings(String s, String t) {

int n = s.length();

int m = t.length();

int[][] allMatch = new int[n][m]; // # of substring all match for s and t untill i,j

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

for(int j = 0; j < t.length(); j++) {

boolean ma = s.charAt(i) == t.charAt(j);

if(i == 0 || j == 0){

if(ma){

allMatch[i][j] = 1;

}

else

{

if(ma){

allMatch[i][j] = allMatch[i - 1][j - 1] + 1;

}

else{

allMatch[i][j] = 0;

}

int[][] missOne = new int[n][m];

int res = 0;

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

for(int j = 0; j < t.length(); j++) {

boolean ma = s.charAt(i) == t.charAt(j);

if(i == 0 || j == 0){

if(!ma){

missOne[i][j] = 1;

}

else

{

if(ma){

missOne[i][j] = missOne[i - 1][j - 1];

}

else{

missOne[i][j] = allMatch[i - 1][j - 1] + 1;

}

res += missOne[i][j];

}

return res;

}

Date May 26, 2022
Category Leetcode
Comments No Comments

Detect Squares

求设计一个数据结构，里面有add,添加一个点, 和count,算有多少个可以用这个点和其他的点围成的正方形.

因为是正方形, 所以边长都一样, 而且题目要求是以轴为基准的正方形, 所以只需要判断有多少个正方形是同y和同x, 即可.

class DetectSquares {
    int[][] g = new int[1001][1001];
    public DetectSquares() {
        
    }
    
    public void add(int[] point) {
        g[point[0]][point[1]]++;
    }
    
    public int count(int[] point) {
        int res = 0;
        for(int i = 0; i < 1001; i++){
            if(Math.abs(point[0] - i) > 0){
                int j1 = point[1] + Math.abs(point[0] - i);
                if(0 <= j1 && j1 <= 1000){
                    res += g[i][j1] * g[i][point[1]] * g[point[0]][j1];
                }
                int j2 = point[1] - Math.abs(point[0] - i);
                if(0 <= j2 && j2 <= 1000){
                    res += g[i][j2] * g[i][point[1]] * g[point[0]][j2];
                }
            }
        }
        return res;
    }
}

 

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares obj = new DetectSquares();
 * obj.add(point);
 * int param_2 = obj.count(point);
 */

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 DetectSquares {

int[][] g = new int[1001][1001];

public DetectSquares() {

}

public void add(int[] point) {

g[point[0]][point[1]]++;

}

public int count(int[] point) {

int res = 0;

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

if(Math.abs(point[0] - i) > 0){

int j1 = point[1] + Math.abs(point[0] - i);

if(0 <= j1 && j1 <= 1000){

res += g[i][j1] * g[i][point[1]] * g[point[0]][j1];

}

int j2 = point[1] - Math.abs(point[0] - i);

if(0 <= j2 && j2 <= 1000){

res += g[i][j2] * g[i][point[1]] * g[point[0]][j2];

}

return res;

}

/**

* Your DetectSquares object will be instantiated and called as such:

* DetectSquares obj = new DetectSquares();

* obj.add(point);

* int param_2 = obj.count(point);

*/

Date May 25, 2022
Category Leetcode
Comments No Comments

Redundant Connection

Swim in Rising Water

Keys and Rooms

Custom Sort String

Projection Area of 3D Shapes

Partition Array for Maximum Sum

Swap Adjacent in LR String

Encode Number

Count Substrings That Differ by One Character

Detect Squares

书脊

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

Categories

Tags