Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitceef087

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent6cafc3d commitceef087

4 files changed

+314
-0
lines changed
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
##323. Number of Connected Components in an Undirected Graph
2+
3+
###Question
4+
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
5+
6+
```
7+
Example 1:
8+
9+
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
10+
11+
0 3
12+
| |
13+
1 --- 2 4
14+
15+
Output: 2
16+
17+
Example 2:
18+
19+
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
20+
21+
0 4
22+
| |
23+
1 --- 2 --- 3
24+
25+
Output: 1
26+
```
27+
28+
Note:
29+
You can assume that no duplicate edges will appear in edges. Since all edges are undirected,[0, 1] is the same as[1, 0] and thus will not appear together in edges.
30+
31+
###Solutions
32+
* Method 1: Union-find O(lg*N)
33+
```Java
34+
class Solution {
35+
private int[] uf;
36+
public int countComponents(int n, int[][] edges) {
37+
this.uf = new int[n];
38+
for(int i = 0; i < n; i++) this.uf[i] = i;
39+
for(int[] e : edges){
40+
union(e[0], e[1]);
41+
}
42+
int res = 0;
43+
for(int i = 0; i < n; i++){
44+
if(uf[i] == i) res++;
45+
}
46+
return res;
47+
}
48+
private int find(int i){
49+
if(uf[i] != i){
50+
uf[i] = find(uf[i]);
51+
}
52+
return uf[i];
53+
}
54+
private void union(int i, int j){
55+
int p = find(i);
56+
int q = find(j);
57+
uf[p] = q;
58+
}
59+
}
60+
```
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
##373. Find K Pairs with Smallest Sums
2+
3+
###Question
4+
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
5+
6+
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
7+
8+
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
9+
10+
```
11+
Example 1:
12+
13+
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
14+
Output: [[1,2],[1,4],[1,6]]
15+
Explanation: The first 3 pairs are returned from the sequence:
16+
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
17+
18+
Example 2:
19+
20+
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
21+
Output: [1,1],[1,1]
22+
Explanation: The first 2 pairs are returned from the sequence:
23+
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
24+
25+
Example 3:
26+
27+
Input: nums1 = [1,2], nums2 = [3], k = 3
28+
Output: [1,3],[2,3]
29+
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
30+
```
31+
32+
###Thinking:
33+
* Method: pq O(n^2)
34+
```Java
35+
classSolution {
36+
publicList<int[]>kSmallestPairs(int[]nums1,int[]nums2,intk) {
37+
PriorityQueue<int[]> pq=newPriorityQueue<>(newComparator<int[]>(){
38+
@Override
39+
publicintcompare(int[]a,int[]b){
40+
return nums1[a[0]]+ nums2[a[1]]- nums1[b[0]]- nums2[b[1]];
41+
}
42+
});
43+
for(int i=0; i< nums1.length; i++){
44+
for(int j=0; j< nums2.length; j++){
45+
pq.offer(newint[]{i, j});
46+
}
47+
}
48+
List<int[]> result=newArrayList<>();
49+
int count=0;
50+
while(!pq.isEmpty()&& count< k){
51+
++count;
52+
int[] cur= pq.poll();
53+
result.add(newint[]{nums1[cur[0]], nums2[cur[1]]});
54+
}
55+
return result;
56+
}
57+
}
58+
```
59+
60+
*Method2:
61+
![Imgur](https://i.imgur.com/7wumtms.png)
62+
```Java
63+
classSolution {
64+
publicList<int[]>kSmallestPairs(int[]nums1,int[]nums2,intk) {
65+
List<int[]> result=newArrayList<>();
66+
if(nums1.length==0|| nums2.length==0|| k==0)return result;
67+
PriorityQueue<int[]> pq=newPriorityQueue<>((a, b)->{
68+
return a[0]+ a[1]- b[0]- b[1];
69+
});
70+
//[0]: number from first arr
71+
//[1]: number from second arr
72+
//[2]: index of number in second arr
73+
for(int i=0; i< nums1.length; i++) pq.offer(newint[]{nums1[i], nums2[0],0});
74+
while(k-->0&&!pq.isEmpty()){
75+
int[] cur= pq.poll();
76+
result.add(newint[]{cur[0], cur[1]});
77+
if(cur[2]+1== nums2.length)continue;
78+
pq.offer(newint[]{cur[0], nums2[cur[2]+1], cur[2]+1});
79+
}
80+
return result;
81+
}
82+
}
83+
```
84+
85+
###Reference
86+
1. [simpleJava O(KlogK) solution with explanation](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/discuss/84551/simple-Java-O(KlogK)-solution-with-explanation)
Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
##863. All Nodes Distance K in Binary Tree
2+
3+
###Question
4+
We are given a binary tree (with root node root), a target node, and an integer value K.
5+
6+
Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.
7+
8+
```
9+
Example 1:
10+
11+
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
12+
13+
Output: [7,4,1]
14+
15+
Explanation:
16+
The nodes that are a distance 2 from the target node (with value 5)
17+
have values 7, 4, and 1.
18+
```
19+
20+
21+
Note that the inputs "root" and "target" are actually TreeNodes.
22+
The descriptions of the inputs above are just serializations of these objects.
23+
24+
Note:
25+
1. The given tree is non-empty.
26+
2. Each node in the tree has unique values 0 <= node.val <= 500.
27+
3. The target node is a node in the tree.
28+
4. 0 <= K <= 1000.
29+
30+
###Thinking:
31+
* Method: Undirected graph, tree
32+
```Java
33+
/**
34+
* Definition for a binary tree node.
35+
* public class TreeNode {
36+
* int val;
37+
* TreeNode left;
38+
* TreeNode right;
39+
* TreeNode(int x) { val = x; }
40+
* }
41+
*/
42+
classSolution {
43+
privateMap<TreeNode,List<TreeNode>> graph;
44+
publicList<Integer>distanceK(TreeNoderoot,TreeNodetarget,intK) {
45+
this.graph=newHashMap<>();
46+
dfs(root);// Construct a undirected graph
47+
// Use bfs to find the result;
48+
int level=0;
49+
Queue<TreeNode> q=newLinkedList<>();
50+
q.offer(target);
51+
Set<TreeNode> visited=newHashSet<>();
52+
visited.add(target);
53+
while(!q.isEmpty()&& level<K){
54+
int size= q.size();
55+
for(int sz=0; sz< size; sz++){
56+
TreeNode cur= q.poll();
57+
List<TreeNode> neighbours= graph.get(cur);
58+
for(TreeNode node: neighbours){
59+
if(visited.contains(node))continue;
60+
visited.add(node);
61+
q.offer(node);
62+
}
63+
}
64+
level++;
65+
}
66+
List<Integer> result=newArrayList<>();
67+
if(level==K){
68+
while(!q.isEmpty()) result.add(q.poll().val);
69+
}
70+
return result;
71+
}
72+
privatevoiddfs(TreeNodenode){
73+
List<TreeNode> neighbours= graph.getOrDefault(node,newArrayList<>());
74+
if(node.left!=null){
75+
neighbours.add(node.left);
76+
List<TreeNode> lefts= graph.getOrDefault(node.left,newArrayList<>());
77+
lefts.add(node);
78+
graph.put(node.left, lefts);
79+
dfs(node.left);
80+
}
81+
if(node.right!=null){
82+
neighbours.add(node.right);
83+
List<TreeNode> rights= graph.getOrDefault(node.right,newArrayList<>());
84+
rights.add(node);
85+
graph.put(node.right, rights);
86+
dfs(node.right);
87+
}
88+
graph.put(node, neighbours);
89+
}
90+
}
91+
```
Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
##993. Cousins in Binary Tree
2+
3+
###Question
4+
In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
5+
6+
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
7+
8+
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
9+
10+
Return true if and only if the nodes corresponding to the values x and y are cousins.
11+
12+
```
13+
Example 1:
14+
15+
Input: root = [1,2,3,4], x = 4, y = 3
16+
Output: false
17+
18+
Example 2:
19+
20+
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
21+
Output: true
22+
23+
Example 3:
24+
25+
Input: root = [1,2,3,null,4], x = 2, y = 3
26+
Output: false
27+
```
28+
29+
Note:
30+
* The number of nodes in the tree will be between 2 and 100.
31+
* Each node has a unique integer value from 1 to 100.
32+
33+
34+
###Thinking:
35+
* Method: Bfs
36+
```Java
37+
/**
38+
* Definition for a binary tree node.
39+
* public class TreeNode {
40+
* int val;
41+
* TreeNode left;
42+
* TreeNode right;
43+
* TreeNode(int x) { val = x; }
44+
* }
45+
*/
46+
classSolution {
47+
publicbooleanisCousins(TreeNoderoot,intx,inty) {
48+
if(root==null|| root.val== x|| root.val== y)returnfalse;
49+
Queue<TreeNode> q=newLinkedList<>();
50+
Set<Integer> set=newHashSet<>();
51+
set.add(root.val);
52+
q.offer(root);
53+
while(!q.isEmpty()){
54+
int size= q.size();
55+
for(int p=0; p< size; p++){
56+
TreeNode node= q.poll();
57+
// check if left and right belongs to same parent
58+
if(node.left!=null&& node.right!=null){
59+
if((node.left.val== x&& node.right.val== y)
60+
|| (node.left.val== y&& node.right.val== x))returnfalse;
61+
}
62+
if(node.left!=null){
63+
q.offer(node.left);
64+
set.add(node.left.val);
65+
}
66+
if(node.right!=null){
67+
q.offer(node.right);
68+
set.add(node.right.val);
69+
}
70+
}
71+
if((!set.contains(x)&& set.contains(y))|| (set.contains(x)&&!set.contains(y)))returnfalse;
72+
elseif(set.contains(x)&& set.contains(y))returntrue;
73+
}
74+
returntrue;
75+
}
76+
}
77+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp