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

Largest Local Values in a Matrix

就是挨个找最大

class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] res = new int[n - 2][n - 2];
        for(int i = 1; i < n - 1; i++) {
            for(int j = 1; j < n - 1; j++) {
                res[i - 1][j - 1] = val(grid,i,j);
            }
        }
        return res;
    }
    
    public int val(int[][] g, int a, int b) {
        int res = Integer.MIN_VALUE;
        for(int i = a - 1; i <= a + 1; i++){
            for(int j = b - 1; j <= b + 1; j++){
                res = Math.max(res, g[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

class Solution {

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

int n = grid.length;

int[][] res = new int[n - 2][n - 2];

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

for(int j = 1; j < n - 1; j++) {

res[i - 1][j - 1] = val(grid,i,j);

}

return res;

}

public int val(int[][] g, int a, int b) {

int res = Integer.MIN_VALUE;

for(int i = a - 1; i <= a + 1; i++){

for(int j = b - 1; j <= b + 1; j++){

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

}

return res;

}

Date August 17, 2022
Category Leetcode
Comments No Comments

Calculate Amount Paid in Taxes

算税

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        int prev = 0;
        double tax = 0d;
        for(int[] b : brackets){ 
            int d = b[0] - prev;
            if(d <= income)
                tax += ((double)b[1] / 100d) * d;
            else
                tax += ((double)b[1] / 100d) * (double)income;
            income -= d;
            if(income <= 0)
                break;
            prev = b[0];
        }
        return tax;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution {

public double calculateTax(int[][] brackets, int income) {

int prev = 0;

double tax = 0d;

for(int[] b : brackets){

int d = b[0] - prev;

if(d <= income)

tax += ((double)b[1] / 100d) * d;

else

tax += ((double)b[1] / 100d) * (double)income;

income -= d;

if(income <= 0)

break;

prev = b[0];

}

return tax;

}

Date August 16, 2022
Category Leetcode
Comments No Comments

1-bit and 2-bit Characters

这题好煞笔

class Solution {
    public boolean isOneBitCharacter(int[] bits) { 
        int i = 0;
        while(i < bits.length - 1) {
            if(bits[i] == 1) 
                i+=2;
            else
                i++;
        }
        return i == bits.length - 1;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

class Solution {

public boolean isOneBitCharacter(int[] bits) {

int i = 0;

while(i < bits.length - 1) {

if(bits[i] == 1)

i+=2;

else

i++;

}

return i == bits.length - 1;

}

Date August 16, 2022
Category Leetcode
Comments No Comments

Best Poker Hand

扑克判断，没啥可说的

class Solution {
    public String bestHand(int[] ranks, char[] suits) { 
        if(flush(ranks, suits))
            return "Flush";
        if(three(ranks, suits))
            return "Three of a Kind";
        if(pair(ranks, suits))
            return "Pair";
        return "High Card";        
    }
    public boolean pair(int[] r, char[] s) {
        int[] rk = new int[15];
        for(int rr : r){
            rk[rr - 1]++;
        }
        for(int rrk : rk){
            if(rrk >= 2)
                return true;
        }
        return false;
    }
    
    public boolean flush(int[] r, char[] s) {
        int[] c = new int[6];
        for(char ss : s) {
            c[ss - 'a']++;
        }
        for(int cc : c){
            if(cc == 5)
                return true;
        }
        return false;
    }
    
    public boolean three(int[] r, char[] s){
        int[] rk = new int[15];
        for(int rr : r){
            rk[rr - 1]++;
        }
        for(int rrk : rk){
            if(rrk >= 3)
                return true;
        }
        return false;
    }
}

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

class Solution {

public String bestHand(int[] ranks, char[] suits) {

if(flush(ranks, suits))

return "Flush";

if(three(ranks, suits))

return "Three of a Kind";

if(pair(ranks, suits))

return "Pair";

return "High Card";

}

public boolean pair(int[] r, char[] s) {

int[] rk = new int[15];

for(int rr : r){

rk[rr - 1]++;

}

for(int rrk : rk){

if(rrk >= 2)

return true;

}

return false;

}

public boolean flush(int[] r, char[] s) {

int[] c = new int[6];

for(char ss : s) {

c[ss - 'a']++;

}

for(int cc : c){

if(cc == 5)

return true;

}

return false;

}

public boolean three(int[] r, char[] s){

int[] rk = new int[15];

for(int rr : r){

rk[rr - 1]++;

}

for(int rrk : rk){

if(rrk >= 3)

return true;

}

return false;

}

Date August 16, 2022
Category Leetcode
Comments No Comments

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

Largest Local Values in a Matrix

Calculate Amount Paid in Taxes

1-bit and 2-bit Characters

Best Poker Hand

Redundant Connection

Swim in Rising Water

Keys and Rooms

Custom Sort String

Projection Area of 3D Shapes

Partition Array for Maximum Sum

书脊

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

Categories

Tags