2020-3-22

946.使数组唯一的最小增量

✒解题思路：

class Solution {
	public int minIncrementForUnique(int[] A) {
		int len = A.length;
		if (len == 0) {
			return 0;
		}
		Arrays.sort(A);
		int preNum = A[0];
		int result = 0;
		for (int i = 1; i < len; i++) {
			if (A[i] >= preNum + 1) {
				preNum = A[i];
			} else {
				result += (preNum + 1 - A[i]);
				preNum++;
			}
		}
		return result;
	}
}

116.填充每个节点的下一个右侧节点指针

✒解题思路：

1. 层次遍历

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
	public Node connect(Node root) {
		if (root == null) {
			return root;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				if (i < size - 1) {
					node.next = queue.peek();
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return root;
	}
}

117.填充每个节点的下一个右侧节点指针II

✒解题思路：

1. 与116思路相同

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
	public Node connect(Node root) {
		if (root == null) {
			return root;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				if (i < size - 1) {
					node.next = queue.peek();
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return root;
	}
}

133.克隆图

✒解题思路：

1. 深度优先遍历

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
	public Node cloneGraph(Node node) {
		if (node == null) {
			return node;
		}
		HashMap<Integer, Node> map = new HashMap<>();
		return dfs(node, map);
	}

	private Node dfs(Node node, HashMap<Integer, Node> map) {
		if (map.containsKey(node.val)) {
			return map.get(node.val);
		}
		Node temp = new Node(node.val, null);
		map.put(temp.val, temp);
		if (node.neighbors != null) {
            temp.neighbors = new ArrayList<>();
			for (Node n : node.neighbors) {
				temp.neighbors.add(dfs(n, map));
			}
		}
		return temp;
	}
}

199.二叉树的右视图

✒解题思路：

1. 层次遍历，保留最右侧的值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<Integer> rightSideView(TreeNode root) {
		if (root == null) {
			return new ArrayList<>();
		}
		Queue<TreeNode> queue = new LinkedList<>();
		List<Integer> result = new ArrayList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (i == size - 1) {
					result.add(node.val);
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return result;
	}
}

200.岛屿数量

✒解题思路：

1. 深度优先遍历

class Solution {
	public int numIslands(char[][] grid) {
		int m = grid.length;
		if (m < 1) {
			return 0;
		}
		int n = grid[0].length;
		int result = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == '1') {
					result++;
					dfs(grid, i, j);
				}
			}
		}
		return result;
	}

	private void dfs(char[][] grid, int i, int j) {
		if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
			return;
		}
		grid[i][j] = '0';
		dfs(grid, i - 1, j);
		dfs(grid, i + 1, j);
		dfs(grid, i, j - 1);
		dfs(grid, i, j + 1);
	}
}