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

Latest Time by Replacing Hidden Digits

给一个string, 表示时间, 里面有若干个?, 求把?替换成数字后的最大时间.

class Solution {
    public String maximumTime(String time) {
        String[] strs = time.split(":");
        String mins = strs[0];
        String secs = strs[1];
        if(mins.charAt(0) == '?'){
            if(mins.charAt(1) == '?'){
                mins = "23";
            }
            else{
                if('0' <= mins.charAt(1) && mins.charAt(1) <= '3'){
                    mins = "2" + mins.charAt(1);
                }
                else{
                    mins = "1" + mins.charAt(1);
                }
            }
        }else if(mins.charAt(0) == '0' || mins.charAt(0) == '1'){
            if(mins.charAt(1) == '?'){
                mins = mins.charAt(0) + "9";
            }
        } 
        else if(mins.charAt(0) == '2'){
            if(mins.charAt(1) == '?'){
                mins = "23";
            }
        }
        // secs
        if(secs.charAt(0) == '?'){
            if(secs.charAt(1) == '?'){
                secs = "59";
            }
            else{ 
                secs = "5" + secs.charAt(1); 
            }
        }
        else {
             if(secs.charAt(1) == '?'){
                secs = secs.charAt(0) + "9";
            }
        }
        return mins+":"+secs;
    }
}

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

class Solution {

public String maximumTime(String time) {

String[] strs = time.split(":");

String mins = strs[0];

String secs = strs[1];

if(mins.charAt(0) == '?'){

if(mins.charAt(1) == '?'){

mins = "23";

}

else{

if('0' <= mins.charAt(1) && mins.charAt(1) <= '3'){

mins = "2" + mins.charAt(1);

}

else{

mins = "1" + mins.charAt(1);

}

}else if(mins.charAt(0) == '0' || mins.charAt(0) == '1'){

if(mins.charAt(1) == '?'){

mins = mins.charAt(0) + "9";

}

else if(mins.charAt(0) == '2'){

if(mins.charAt(1) == '?'){

mins = "23";

}

// secs

if(secs.charAt(0) == '?'){

if(secs.charAt(1) == '?'){

secs = "59";

}

else{

secs = "5" + secs.charAt(1);

}

else {

if(secs.charAt(1) == '?'){

secs = secs.charAt(0) + "9";

}

return mins+":"+secs;

}

Date January 26, 2021
Category Leetcode
Comments No Comments

Find Kth Largest XOR Coordinate Value

给一个2d矩阵, 求矩阵每个元素xor后的最大元素.

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 int kthLargestValue(int[][] matrix, int k) {

int n = matrix.length;

int m = matrix[0].length;

PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());

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

matrix[i][0] ^= matrix[i - 1][0];

}

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

matrix[0][j] ^= matrix[0][j - 1];

}

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

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

matrix[i][j] ^= matrix[i - 1][j];

matrix[i][j] ^= matrix[i][j - 1];

matrix[i][j] ^= matrix[i - 1][j - 1];

}

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

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

pq.add(matrix[i][j]);

}

while(--k != 0){

pq.poll();

}

return pq.peek();

}

Date January 24, 2021
Category Leetcode
Comments No Comments

Shortest Path to Get Food

给一个2d数组, 找两个格子之间的步数.

class Solution {
    public int getFood(char[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '*')
                    return bfs(grid, i, j);
            }
        }
        return -1;//never reach
    }
    public int bfs(char[][] grid, int i, int j){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j, 0}); 
        int[][] dirs = new int[][]{
            {0,1},
            {1,0},
            {-1,0},
            {0,-1}
        };
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int[] d : dirs) {
                int newX = cur[0] + d[0];
                int newY = cur[1] + d[1];
                if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length)
                    continue;
                else if(grid[newX][newY] == '#')
                    return cur[2] + 1;
                else if(grid[newX][newY] == 'O'){ 
                    grid[newX][newY] = 'X';
                    q.add(new int[]{newX, newY, cur[2] + 1});
                }
            }
        }
        return -1;
    }
}

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 int getFood(char[][] grid) {

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

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

if(grid[i][j] == '*')

return bfs(grid, i, j);

}

return -1;//never reach

}

public int bfs(char[][] grid, int i, int j){

Queue<int[]> q = new LinkedList<>();

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

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

{0,1},

{1,0},

{-1,0},

{0,-1}

};

while(!q.isEmpty()){

int[] cur = q.poll();

for(int[] d : dirs) {

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

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

if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length)

continue;

else if(grid[newX][newY] == '#')

return cur[2] + 1;

else if(grid[newX][newY] == 'O'){

grid[newX][newY] = 'X';

q.add(new int[]{newX, newY, cur[2] + 1});

}

return -1;

}

Date January 24, 2021
Category Leetcode
Comments No Comments

Find the Highest Altitude

给一个数组, 从0开始,问最大多少.

1

2

3

4

5

6

7

8

9

10

11

class Solution {

public int largestAltitude(int[] gain) {

int res = 0;

int cur = 0;

for(int g : gain) {

cur += g;

res = Math.max(res, cur);

}

return res;

}

Date January 24, 2021
Category Leetcode
Comments No Comments

Remove All Adjacent Duplicates in String II

给一个string, 只移除k次重复的substring.

这个题因为要多次移除, 还有merge的可能, 所以要用stack存一下前序, 我是用Pair先预处理了一下string, 把string换成词频格式, 然后再用stack. 其实也可以不用pair, 直接算.

class Solution {
    class Pair{
        char a;
        int b;
        Pair(char a, int b){
            this.a = a;
            this.b = b;
        }
        public String toString(){
            return this.a +"|" + this.b;
        }
    }
    public String removeDuplicates(String s, int k) {
        List<Pair> pairs = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            if(pairs.isEmpty() || pairs.get(pairs.size() - 1).a != s.charAt(i)){
                Pair p = new Pair(s.charAt(i), 1);
                pairs.add(p);
            } else if(pairs.get(pairs.size() - 1).a == s.charAt(i)){
                Pair p = new Pair(pairs.get(pairs.size() - 1).a, pairs.get(pairs.size() - 1).b + 1);
                pairs.remove(pairs.size() - 1);
                pairs.add(p);
            }
        }
        Stack<Pair> st = new Stack<>(); 
        for(int i = 0; i < pairs.size(); i++){ 
            if(st.isEmpty()){
                st.push(pairs.get(i));
            }
            else if(st.peek().a == pairs.get(i).a){
                Pair p = st.pop();
                p.b += pairs.get(i).b;
                st.push(p);
            }else{
                st.push(pairs.get(i));
            }        
            if(!st.isEmpty()){
                Pair p = st.pop();
                if(p.b % k != 0){
                    p.b = p.b % k;
                    st.push(p);
                }
            } 
        }
        StringBuilder sb = new StringBuilder();
        while(!st.isEmpty()){
            Pair p = st.pop();
            for(int i = 0; i < p.b; i++) {
                sb.insert(0, p.a);
            }
        }
        return sb.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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

class Solution {

class Pair{

char a;

int b;

Pair(char a, int b){

this.a = a;

this.b = b;

}

public String toString(){

return this.a +"|" + this.b;

}

public String removeDuplicates(String s, int k) {

List<Pair> pairs = new LinkedList<>();

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

if(pairs.isEmpty() || pairs.get(pairs.size() - 1).a != s.charAt(i)){

Pair p = new Pair(s.charAt(i), 1);

pairs.add(p);

} else if(pairs.get(pairs.size() - 1).a == s.charAt(i)){

Pair p = new Pair(pairs.get(pairs.size() - 1).a, pairs.get(pairs.size() - 1).b + 1);

pairs.remove(pairs.size() - 1);

pairs.add(p);

}

Stack<Pair> st = new Stack<>();

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

if(st.isEmpty()){

st.push(pairs.get(i));

}

else if(st.peek().a == pairs.get(i).a){

Pair p = st.pop();

p.b += pairs.get(i).b;

st.push(p);

}else{

st.push(pairs.get(i));

}

if(!st.isEmpty()){

Pair p = st.pop();

if(p.b % k != 0){

p.b = p.b % k;

st.push(p);

}

StringBuilder sb = new StringBuilder();

while(!st.isEmpty()){

Pair p = st.pop();

for(int i = 0; i < p.b; i++) {

sb.insert(0, p.a);

}

return sb.toString();

}

Date January 20, 2021
Category Leetcode
Comments No Comments

Max Area of Island

给一个grid里面是0和1, 求最大面积的1.

典型的搜索问题. 用-1标visitied.

class Solution {
    class Pair{
        int a;
        int b;
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1){
                   res = Math.max(res, bfs(grid, i, j)); 
                }
            }
        }
        return res;
    }
    public int bfs(int[][] g, int row, int col) {
        int res = 1;
        g[row][col] = -1;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(row, col));
        int[][] dirs = new int[][]{
            {0,1},
            {-1,0},
            {1,0},
            {0,-1}
        };
        while(!q.isEmpty()){
            Pair p = q.poll();
            for(int[] d : dirs) {
                int newRow = p.a + d[0];
                int newCol = p.b + d[1];
                if(0 <= newRow && newRow < g.length && 0 <= newCol && newCol < g[0].length && g[newRow][newCol] == 1){
                    res++;
                    g[newRow][newCol] = -1;
                    q.add(new Pair(newRow, newCol));
                }
            }
        }
        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

class Solution {

class Pair{

int a;

int b;

Pair(int a, int b) {

this.a = a;

this.b = b;

}

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

int res = 0;

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

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

if(grid[i][j] == 1){

res = Math.max(res, bfs(grid, i, j));

}

return res;

}

public int bfs(int[][] g, int row, int col) {

int res = 1;

g[row][col] = -1;

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

q.add(new Pair(row, col));

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

{0,1},

{-1,0},

{1,0},

{0,-1}

};

while(!q.isEmpty()){

Pair p = q.poll();

for(int[] d : dirs) {

int newRow = p.a + d[0];

int newCol = p.b + d[1];

if(0 <= newRow && newRow < g.length && 0 <= newCol && newCol < g[0].length && g[newRow][newCol] == 1){

res++;

g[newRow][newCol] = -1;

q.add(new Pair(newRow, newCol));

}

return res;

}

Date January 20, 2021
Category Leetcode
Comments No Comments

Leftmost Column with at Least a One

给一个2d数组, 里面全是1和0, 里面的row是按照升序排列的. 给一个api, 需要调这个api求最左边第一次出现1的列.

这个一看就是二叉.

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface BinaryMatrix {
 *     public int get(int row, int col) {}
 *     public List<Integer> dimensions {}
 * };
 */

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int row =  binaryMatrix.dimensions().get(0);
        int col =  binaryMatrix.dimensions().get(1);
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < row; i++) {
            res = Math.min(res, find(binaryMatrix, i, col));
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    private int find(BinaryMatrix binaryMatrix, int row, int col) {
        int left = 0;
        int right = col - 1;
        int res = Integer.MAX_VALUE;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(binaryMatrix.get(row, mid) == 1){
                right = mid - 1;
                res = mid;
            }
            else 
                left = mid + 1;
        }
        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

/**

* // This is the BinaryMatrix's API interface.

* // You should not implement it, or speculate about its implementation

* interface BinaryMatrix {

* public int get(int row, int col) {}

* public List<Integer> dimensions {}

* };

*/

class Solution {

public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {

int row = binaryMatrix.dimensions().get(0);

int col = binaryMatrix.dimensions().get(1);

int res = Integer.MAX_VALUE;

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

res = Math.min(res, find(binaryMatrix, i, col));

}

return res == Integer.MAX_VALUE ? -1 : res;

}

private int find(BinaryMatrix binaryMatrix, int row, int col) {

int left = 0;

int right = col - 1;

int res = Integer.MAX_VALUE;

while(left <= right) {

int mid = left + (right - left) / 2;

if(binaryMatrix.get(row, mid) == 1){

right = mid - 1;

res = mid;

}

else

left = mid + 1;

}

return res;

}

Date January 20, 2021
Category Leetcode
Comments No Comments

Minimum Knight Moves

给一个无限大的棋盘(2d数组), 在0,0有一个马, 马走日, 求到x,y的步数

这个就是搜索问题. 因为无限大, 所以只能是bfs, 稍微剪枝一下就可以, 不过我的答案虽然过了, 但是好慢啊.

class Solution {
    public int minKnightMoves(int x, int y) {
        Set<String> set = new HashSet<>();
        x = Math.abs(x);
        y = Math.abs(y);
        int[][] dirs = new int[][]{
            {1,2},
            {2,1},
            {-1,2},
            {1,-2},
            {-2,1},
            {2,-1},
            {-2,-1},
            {-1,-2}
        }; 
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        set.add("0|0");
        int res = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++) {
                int[] cur = q.poll();
                if(cur[0] == x && cur[1] ==y)
                    return res;
                for(int[] d : dirs){
                    int newX = d[0] + cur[0];
                    int newY = d[1] + cur[1];
                    if(set.contains(newX+"|"+newY)){
                        continue;
                    }
                    else if(newX < 0 && newY < 0){
                        set.add(newX+"|"+newY);
                        continue;
                    }
                    else{
                        q.add(new int[]{newX, newY});
                        set.add(newX+"|"+newY);
                    }
                }
            }
            res++;
        }
        return 0;//never reach 
    }
}

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 int minKnightMoves(int x, int y) {

Set<String> set = new HashSet<>();

x = Math.abs(x);

y = Math.abs(y);

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

{1,2},

{2,1},

{-1,2},

{1,-2},

{-2,1},

{2,-1},

{-2,-1},

{-1,-2}

};

Queue<int[]> q = new LinkedList<>();

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

set.add("0|0");

int res = 0;

while(!q.isEmpty()){

int size = q.size();

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

int[] cur = q.poll();

if(cur[0] == x && cur[1] ==y)

return res;

for(int[] d : dirs){

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

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

if(set.contains(newX+"|"+newY)){

continue;

}

else if(newX < 0 && newY < 0){

set.add(newX+"|"+newY);

continue;

}

else{

q.add(new int[]{newX, newY});

set.add(newX+"|"+newY);

}

res++;

}

return 0;//never reach

}

Date January 19, 2021
Category Leetcode
Comments No Comments

Number of Provinces

给一个无向图, 求几个强连通组件.

并查集的例题.

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int size = isConnected.length;
        DSU dsu = new DSU(size);
        for(int i = 0; i < isConnected.length; i++) {
            for(int j = 0; j < isConnected.length; j++) {
                if(isConnected[i][j] == 1){
                    dsu.union(i, j);
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < size; i++) {
            set.add(dsu.get(i));
        }
        return set.size();
    }
    class DSU{
        int[] p;
        public DSU(int size) {
            this.p = new int[size];
            for(int i = 0; i < size; i++) {
                p[i] = i;
            }
        }
        int get(int v) {
            if(p[v] == v)
                return v;
            return p[v] = get(p[v]);
        }
        boolean union(int a, int b) {
            a = get(a);
            b = get(b);
            if(a == b)
                return false;
            p[a] = b;
            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

38

39

40

class Solution {

public int findCircleNum(int[][] isConnected) {

int size = isConnected.length;

DSU dsu = new DSU(size);

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

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

if(isConnected[i][j] == 1){

dsu.union(i, j);

}

Set<Integer> set = new HashSet<>();

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

set.add(dsu.get(i));

}

return set.size();

}

class DSU{

int[] p;

public DSU(int size) {

this.p = new int[size];

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

p[i] = i;

}

int get(int v) {

if(p[v] == v)

return v;

return p[v] = get(p[v]);

}

boolean union(int a, int b) {

a = get(a);

b = get(b);

if(a == b)

return false;

p[a] = b;

return true;

}

Date January 19, 2021
Category Leetcode
Comments No Comments

Tuples with Same Product

给一个数组, 里面的数字不同, 求多少种a*b=c*d, abcd都是数组的数字, 但是不相同.

算下乘积的频率即可, 答案是n*(n-1),从频率中任意选2个的个数, 然后再乘以4, 4种互换可能.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int tupleSameProduct(int[] nums) {

Map<Integer, Integer> f = new HashMap<>();

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

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

f.put(nums[i] * nums[j], f.getOrDefault(nums[i] * nums[j], 0) + 1);

}

int res = 0;

for(Map.Entry<Integer, Integer> m : f.entrySet()){

int n = m.getValue();

res += (n) * (n - 1) * 4;

}

return res;

}

Date January 19, 2021
Category Leetcode
Comments No Comments

Latest Time by Replacing Hidden Digits

Find Kth Largest XOR Coordinate Value

Shortest Path to Get Food

Find the Highest Altitude

Remove All Adjacent Duplicates in String II

Max Area of Island

Leftmost Column with at Least a One

Minimum Knight Moves

Number of Provinces

Tuples with Same Product

书脊

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

Categories

Tags