题目538题
把二叉搜素树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
思路
深度优先遍历
实现
class Solution {
public TreeNode convertBST(TreeNode root) {
int a = dfs(root,0);
return root;
}
private int dfs(TreeNode node, int bigger){
int right = 0;
if(node == null){
return 0;
}
right = dfs(node.right, bigger);
if(node.right == null)
node.val += bigger;
node.val += right;
int left = dfs(node.left, node.val);
if(left != 0){
return left;
}
return node.val;
}
}
题目539题
最小时间差
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
思路实现
class Solution {
public int findMinDifference(List<String> timePoints) {
if (timePoints.size()>=1440){
return 0;
}
int[] timeList = new int[timePoints.size()];
for(int index=0; index < timePoints.size(); index++){
String[] time = timePoints.get(index).split(":");
int hour = Integer.parseInt(time[0]);
int minute = Integer.parseInt(time[1]);
timeList[index] = hour*60 + minute;
}
Arrays.sort(timeList);
int res = 1440;
for(int index=1; index < timePoints.size(); index++){
res = Math.min(res, timeList[index]- timeList[index-1]);
if(res == 0){
return 0;
}
}
res = Math.min(res, 1440 - timeList[timeList.length - 1] + timeList[0]);
return res;
}
}
题目540题
有序数组中的单一元素
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
思路
二分法
实现
class Solution {
public int singleNonDuplicate(int[] nums) {
int left =0, right = nums.length -1;
int mid=0;
while(left < right){
if(nums[left] != nums[left+1]){
mid = left;
break;
}else if(nums[right] != nums[right-1]){
mid = right;
break;
}else{
mid = left + (right-left)/2;
}
int halflen = (right - left)/2;
if(halflen %2==0 && nums[mid]==nums[mid-1]){
right = mid - 2;
}else if(halflen %2==0 && nums[mid]==nums[mid+1]){
left = mid + 2;
}else if(halflen %2==1 && nums[mid]==nums[mid-1]){
left = mid + 1;
}else if(halflen %2==1 && nums[mid]==nums[mid+1]){
right = mid - 1;
}else{
break;
}
}
return nums[mid];
}
}
题目541题
反转字符串II
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路实现
class Solution {
public String reverseStr(String s, int k) {
char[] c = s.toCharArray();
for(int index = 0; index < c.length; index += 2*k){
int i = index, j = Math.min(index + k - 1, c.length - 1);
while (i < j) {
char tmp = c[i];
c[i++] = c[j];
c[j--] = tmp;
}
}
return String.valueOf(c);
}
}
题目542题
01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：
[[0,0,0],
[0,1,0],
[0,0,0]]
输出：
[[0,0,0],
[0,1,0],
[0,0,0]]
思路
1. 深度优先遍历
实现
class Solution {
private int[][] matrix;
private int row, col;
int [][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
public int[][] updateMatrix(int[][] matrix) {
this.matrix = matrix;
row = matrix.length;
col = matrix[0].length;
for(int i=0; i < row; i++){
for(int j=0; j < col; j++ ){
if(this.matrix[i][j] ==1 && !hasNeighbors0(i,j)){
this.matrix[i][j] = Integer.MAX_VALUE;
}
}
}
for(int i=0; i < row; i++){
for(int j=0; j < col; j++ ){
if(this.matrix[i][j] == 1){
dfs(i, j);
}
}
}
return this.matrix;
}
boolean hasNeighbors0(int x,int y){
for(int[] dir:dirs){
int new_x=x+dir[0];
int new_y=y+dir[1];
if(new_x>=0 && new_x<row && new_y>=0 && new_y<col && matrix[new_x][new_y]==0)
return true;
}
return false;
}
private void dfs(int x ,int y){
for(int[] dir:dirs){
int new_x=x+dir[0];
int new_y=y+dir[1];
if(new_x>=0 && new_x<row && new_y>=0 && new_y<col && matrix[new_x][new_y]>matrix[x][y]+1 ){
matrix[new_x][new_y] = matrix[x][y]+1;
dfs(new_x, new_y);
}
}
}
}
题目543题
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路实现
class Solution {
int res = 1;
public int diameterOfBinaryTree(TreeNode root) {
calcLen(root);
return res-1;
}
private int calcLen(TreeNode node){
if (node == null){
return 0;
}
int resleft = calcLen(node.left);
int resright = calcLen(node.right);
res = Math.max(resleft + resright+ 1, res);
return Math.max(resleft, resright)+1;
}
}
题目547题
朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
思路
1.广度优先遍历
2.Union-Find算法
实现
1.
class Solution {
public int findCircleNum(int[][] M) {
int N = M.length;
int res = 0;
boolean[] visited = new boolean[N];
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=0; i < N; i++){
if(visited[i] == false){
res +=1;
queue.offer(i);
while(queue.size()!= 0){
int j = queue.poll();
visited[j] = true;
for(int k=0; k <N; k++){
if(M[j][k] == 1 && visited[k] == false){
queue.offer(k);
}
}
}
}
}
return res;
}
}
2.
class Solution {
class UF {
// 记录连通分量个数
private int count;
// 存储若干棵树
private int[] parent;
// 记录树的“重量”
private int[] size;
public UF(int n) { this.count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } /* 将 p 和 q 连通 */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // 小树接到大树下面，较平衡 if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; }
/* 判断 p 和 q 是否互相连通 */ public boolean connected(int p, int q) { int rootP = find(p); int rootQ = find(q); // 处于同一棵树上的节点，相互连通 return rootP == rootQ; }
/* 返回节点 x 的根节点 */ private int find(int x) { while (parent[x] != x) { // 进行路径压缩 parent[x] = parent[parent[x]]; x = parent[x]; } return x; } public int count() { return count; } }
public int findCircleNum(int[][] M) { int n = M.length; UF uf = new UF(n); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (M[i][j] == 1) uf.union(i, j); } } return uf.count(); }
}
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现
题目539题
思路实现