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

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

给一个树和一个target node, 找早cloned里边的这个node.

这个题已知这个node一定存在, 并且唯一.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null)
            return null;
        if(original.val == target.val){
            return cloned;
        }
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        TreeNode right = getTargetCopy(original.right, cloned.right, target);
        if(left != null)
            return left;
        else
            return right;
    }
}

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

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {

if(original == null)

return null;

if(original.val == target.val){

return cloned;

}

TreeNode left = getTargetCopy(original.left, cloned.left, target);

TreeNode right = getTargetCopy(original.right, cloned.right, target);

if(left != null)

return left;

else

return right;

}

Date February 26, 2021
Category Leetcode
Comments No Comments

Subrectangle Queries

给一个2d矩阵, 和一个update, 一个getValue方法, 实现这两个方法,

class SubrectangleQueries {
    int[][] rectangle;
    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i = row1; i <= row2; i++) {
            for(int j = col1; j <= col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rectangle[row][col];
    }
}

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries obj = new SubrectangleQueries(rectangle);
 * obj.updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj.getValue(row,col);
 */

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

int[][] rectangle;

public SubrectangleQueries(int[][] rectangle) {

this.rectangle = rectangle;

}

public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {

for(int i = row1; i <= row2; i++) {

for(int j = col1; j <= col2; j++) {

rectangle[i][j] = newValue;

}

public int getValue(int row, int col) {

return rectangle[row][col];

}

/**

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

* SubrectangleQueries obj = new SubrectangleQueries(rectangle);

* obj.updateSubrectangle(row1,col1,row2,col2,newValue);

* int param_2 = obj.getValue(row,col);

*/

Date February 26, 2021
Category Leetcode
Comments No Comments

Dot Product of Two Sparse Vectors

给一个spare vector的类, 求dot product

class SparseVector {
    int[] nums;
    SparseVector(int[] nums) {
        this.nums = nums;
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i] * vec.nums[i];
        }
        return sum;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class SparseVector {

int[] nums;

SparseVector(int[] nums) {

this.nums = nums;

}

// Return the dotProduct of two sparse vectors

public int dotProduct(SparseVector vec) {

int sum = 0;

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

sum += nums[i] * vec.nums[i];

}

return sum;

}

// Your SparseVector object will be instantiated and called as such:

// SparseVector v1 = new SparseVector(nums1);

// SparseVector v2 = new SparseVector(nums2);

// int ans = v1.dotProduct(v2);

Date February 26, 2021
Category Leetcode
Comments No Comments

Print Immutable Linked List in Reverse

给一个接口逆序打印.

/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * interface ImmutableListNode {
 *     public void printValue(); // print the value of this node.
 *     public ImmutableListNode getNext(); // return the next node.
 * };
 */

class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        if(head == null)
            return;
        printLinkedListInReverse(head.getNext());
        head.printValue();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

/**

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

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

* interface ImmutableListNode {

* public void printValue(); // print the value of this node.

* public ImmutableListNode getNext(); // return the next node.

* };

*/

class Solution {

public void printLinkedListInReverse(ImmutableListNode head) {

if(head == null)

return;

printLinkedListInReverse(head.getNext());

head.printValue();

}

Date February 26, 2021
Category Leetcode
Comments No Comments

Map of Highest Peak

给一个数组, 里边是哪里有水, 哪里是陆地, 求最大的height的地图, 满足每个格子之间最多差1.

这个题用单源bfs做, 会超时

class Solution {
    int[][] dirs = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    int n;
    int m;
    public int[][] highestPeak(int[][] isWater) {
        n = isWater.length;
        m = isWater[0].length; 
        List<int[]> points = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(isWater[i][j] == 1){
                    isWater[i][j] = 0; 
                    points.add(new int[]{i,j});
                }
                else{
                    isWater[i][j] = -1;
                }
            }
        }
        for(int[] p : points){
            bfs(isWater, p[0], p[1]);
        }
        return isWater;
    }
    public void bfs(int[][] isWater, int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int[] d : dirs){
                int newX = d[0] + cur[0];
                int newY = d[1] + cur[1];
                if(newX < 0 || newY < 0 || newX >= n || newY >= m || isWater[newX][newY] == 0)
                    continue;
                if(isWater[newX][newY] == -1){
                    isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1;
                    q.add(new int[]{newX, newY});
                }else{
                    if(isWater[cur[0]][cur[1]] + 1 == isWater[newX][newY] || isWater[cur[0]][cur[1]] == isWater[newX][newY])
                        continue;
                    else{
                        isWater[newX][newY] = Math.min(isWater[cur[0]][cur[1]] + 1, isWater[newX][newY]);
                        q.add(new int[]{newX, newY});
                    }
                }
            }
        }
    }
}

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 {

int[][] dirs = {

{0,1},

{0,-1},

{-1,0},

{1,0}

};

int n;

int m;

public int[][] highestPeak(int[][] isWater) {

n = isWater.length;

m = isWater[0].length;

List<int[]> points = new ArrayList<>();

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

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

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

isWater[i][j] = 0;

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

}

else{

isWater[i][j] = -1;

}

for(int[] p : points){

bfs(isWater, p[0], p[1]);

}

return isWater;

}

public void bfs(int[][] isWater, int x, int y){

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

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

while(!q.isEmpty()){

int[] cur = q.poll();

for(int[] d : dirs){

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

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

if(newX < 0 || newY < 0 || newX >= n || newY >= m || isWater[newX][newY] == 0)

continue;

if(isWater[newX][newY] == -1){

isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1;

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

}else{

if(isWater[cur[0]][cur[1]] + 1 == isWater[newX][newY] || isWater[cur[0]][cur[1]] == isWater[newX][newY])

continue;

else{

isWater[newX][newY] = Math.min(isWater[cur[0]][cur[1]] + 1, isWater[newX][newY]);

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

}

感觉用了多源也卡的要死, 虽然过了,但是速度不是很快

class Solution {
    int[][] dirs = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    int n;
    int m;
    public int[][] highestPeak(int[][] isWater) {
        n = isWater.length;
        m = isWater[0].length; 
        Set<String> set = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(isWater[i][j] == 1){
                    isWater[i][j] = 0; 
                    q.add(new int[]{i, j}); 
                    set.add(i+"|"+j);
                } 
            }
        } 
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int[] d : dirs){
                int newX = d[0] + cur[0];
                int newY = d[1] + cur[1];
                if(newX < 0 || newY < 0 || newX >= n || newY >= m || set.contains(newX+"|"+newY))
                    continue;                  
                isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1;   
                q.add(new int[]{newX, newY});
                set.add(newX+"|"+newY);
            }
        }
        return isWater;
    } 
}

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

class Solution {

int[][] dirs = {

{0,1},

{0,-1},

{-1,0},

{1,0}

};

int n;

int m;

public int[][] highestPeak(int[][] isWater) {

n = isWater.length;

m = isWater[0].length;

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

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

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

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

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

isWater[i][j] = 0;

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

set.add(i+"|"+j);

}

while(!q.isEmpty()){

int[] cur = q.poll();

for(int[] d : dirs){

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

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

if(newX < 0 || newY < 0 || newX >= n || newY >= m || set.contains(newX+"|"+newY))

continue;

isWater[newX][newY] = isWater[cur[0]][cur[1]] + 1;

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

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

}

return isWater;

}

Date February 26, 2021
Category Leetcode
Comments No Comments

Sort Features by Popularity

给一个features数组, 和一个responses数组, 求responses出现每个feature的次数, 从大到小.

class Solution {
    Map<String, Integer> map = new HashMap<>();
    public String[] sortFeatures(String[] features, String[] responses) {
        for(String f : features) {
            map.put(f, 0);
        }
        for(String r : responses){
            String[] strs = r.split(" ");
            Set<String> set = new HashSet<>();
            for(String s : strs) {
                if(map.containsKey(s) && !set.contains(s)){
                    set.add(s);
                    map.put(s, map.get(s) + 1);
                }
            }
        }
        Arrays.sort(features, (a,b) ->(appearances(b) - appearances(a)));
        return features;
    }
    private int appearances(String s) {
        return map.get(s);
    }
}

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 {

Map<String, Integer> map = new HashMap<>();

public String[] sortFeatures(String[] features, String[] responses) {

for(String f : features) {

map.put(f, 0);

}

for(String r : responses){

String[] strs = r.split(" ");

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

for(String s : strs) {

if(map.containsKey(s) && !set.contains(s)){

set.add(s);

map.put(s, map.get(s) + 1);

}

Arrays.sort(features, (a,b) ->(appearances(b) - appearances(a)));

return features;

}

private int appearances(String s) {

return map.get(s);

}

Date February 26, 2021
Category Leetcode
Comments No Comments

Kirchhoff’s theorem

这个算法又叫matrix tree theorem. 是一种计算一个无向图上生成树的个数的矩阵运算方法.

给一个图G, 这个图可连续也可不连续, 啥样子都可以. 设G的拉普拉斯矩阵(又名: 调和矩阵)为Q. 则我们可以通过计算Q11(删除第一行和第一列)的行列式, 得知G的生成树个数.

Date February 25, 2021
Category Algorithm
Comments No Comments

Minimum Limit of Balls in a Bag

给一个数组, 问如何通过maxOperations个操作, 让数字中最大数字变得最小, 操作是把一个数分割成两个数字的和.

这个题上来肯定用优先队列来一个个找最大的数, 然后分, 但是这里有个问题是, 如何分才能在给出的maxOperations的操作下, 确保最小, 这个策略比较难定. 于是换个思路: 在maxOperations个操作下, 如果结果得到的数字中最大的数字是x, 那么x+1也可以, 所以可以用二分搜索找lower bound.

class Solution {
    public int minimumSize(int[] nums, int maxOperations) { 
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Arrays.sort(nums); 
        int left = 1;
        int right = nums[nums.length - 1]; 
         while(left < right) {
            int mid = left + (right - left) / 2;
            if(check(nums, mid, maxOperations)) {
                 right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left; // never 
    }
    //11       4
    // 4 7     4
    // 4 3 4 4
          
    private boolean check(int[] nums, int m,int max) {
        int count = 0;
        for(int i = nums.length - 1; i >= 0; i--) {
            if(nums[i] <= m)
                break;
            count += (nums[i] - 1) / m;
        }
        return count <= max;
    }
}

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 minimumSize(int[] nums, int maxOperations) {

int min = Integer.MAX_VALUE;

int max = Integer.MIN_VALUE;

Arrays.sort(nums);

int left = 1;

int right = nums[nums.length - 1];

while(left < right) {

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

if(check(nums, mid, maxOperations)) {

right = mid;

}

else{

left = mid + 1;

}

return left; // never

}

//11 4

// 4 7 4

// 4 3 4 4

private boolean check(int[] nums, int m,int max) {

int count = 0;

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

if(nums[i] <= m)

break;

count += (nums[i] - 1) / m;

}

return count <= max;

}

Date February 24, 2021
Category Leetcode
Comments No Comments

Buildings With an Ocean View

给一个数组, 里面是房子高度, 默认右侧是大海, 问那些房子能看到海.

这个题主要是问一个数后边有没有数字大于它. 直接从后往前扫即可.

class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> list = new ArrayList<>(); 
        int n = heights.length;
        int highest = Integer.MIN_VALUE;
        for(int i = n - 1; i >= 0; i--) {
            if(heights[i] > highest)
                list.add(i);
            highest = Math.max(highest, heights[i]);
        }
        Collections.sort(list); 
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution {

public int[] findBuildings(int[] heights) {

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

int n = heights.length;

int highest = Integer.MIN_VALUE;

for(int i = n - 1; i >= 0; i--) {

if(heights[i] > highest)

list.add(i);

highest = Math.max(highest, heights[i]);

}

Collections.sort(list);

int[] res = new int[list.size()];

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

res[i] = list.get(i);

}

return res;

}

Date February 24, 2021
Category Leetcode
Comments No Comments

Minimum Number of Operations to Move All Balls to Each Box

给一个string, 里面是0和1, 给一个操作是移动一个1到相邻位置, cost为1, 求把所有1的位置挪到当前位置的cost.

就是两个循环算一下.

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j)
                    continue;
                res[i] += Math.abs(i - j) * (boxes.charAt(j) - '0');
            }
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution {

public int[] minOperations(String boxes) {

int n = boxes.length();

int[] res = new int[n];

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

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

if(i == j)

continue;

res[i] += Math.abs(i - j) * (boxes.charAt(j) - '0');

}

return res;

}

Date February 24, 2021
Category Leetcode
Comments No Comments

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Subrectangle Queries

Dot Product of Two Sparse Vectors

Print Immutable Linked List in Reverse

Map of Highest Peak

Sort Features by Popularity

Kirchhoff’s theorem

Minimum Limit of Balls in a Bag

Buildings With an Ocean View

Minimum Number of Operations to Move All Balls to Each Box

书脊

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

Categories

Tags