Problem 1: Find the degree of each vertex.
You are given a 2D integer array matrix of size n x n representing the adjacency matrix of an undirected graph with n vertices labeled from 0 to n - 1.
• matrix[i][j] = 1 indicates that there is an edge between vertices i and j.
• matrix[i][j] = 0 indicates that there is no edge between vertices i and j.
The degree of a vertex is the number of edges connected to it.
Return an integer array ans of size n where ans[i] represents the degree of vertex i.
Example 1:
1
/ \
0--2
Input: matrix = [[0,1,1],[1,0,1],[1,1,0]]
Output: [2,2,2]
Explanation:
• Vertex 0 is connected to vertices 1 and 2, so its degree is 2.
• Vertex 1 is connected to vertices 0 and 2, so its degree is 2.
• Vertex 2 is connected to vertices 0 and 1, so its degree is 2.
Thus, the answer is [2, 2, 2].
Example 2:
0 --- 1
2cc
Input: matrix = [[0,1,0],[1,0,0],[0,0,0]]
Output: [1,1,0]
Explanation:
• Vertex 0 is connected to vertex 1, so its degree is 1.
• Vertex 1 is connected to vertex 0, so its degree is 1.
• Vertex 2 is not connected to any vertex, so its degree is 0.
Thus, the answer is [1, 1, 0].
Example 3:
Input: matrix = [[0]]
Output: [0]
Explanation:
There is only one vertex and it has no edges connected to it. Thus, the answer is [0].
Constraints:
• 1 <= n == matrix.length == matrix[i].length <= 100
• matrix[i][i] == 0
• matrix[i][j] is either 0 or 1
• matrix[i][j] == matrix[j][i]
class Solution {
public int[] findDegrees(int[][] matrix) {
int[] degree = new int[matrix.length];
for (int i = 0; i < matrix.length; i++) {
degree[i] = 0;
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1) {
degree[i] += 1;
}
}
}
return degree;
}
}
Test cases:
Case 0:
Input
matrix =
[[0,1,1],[1,0,1],[1,1,0]]
Output
[2,2,2]
Expected
[2,2,2]
Case 1:
Input
matrix =
[[0,1,0],[1,0,0],[0,0,0]]
Output
[1,1,0]
Expected
[1,1,0]
Case 2:
Input
matrix =
[[0]]
Output
[0]
Expected
[0]
Problem 2:
Sides of a triangle
You are given a positive integer array sides of length 3.
Determine if there exists a triangle with positive area whose three side lengths are given by the elements of sides.
If such a triangle exists, return an array of three floating-point numbers representing its internal angles (in degrees), sorted in non-decreasing order. Otherwise, return an empty array.
Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: sides = [3,4,5]
Output: [36.86990,53.13010,90.00000]
Explanation:
You can form a right-angled triangle with side lengths 3, 4, and 5. The internal angles of this triangle are approximately 36.869897646, 53.130102354, and 90 degrees respectively.
Example 2:
Input: sides = [2,4,2]
Output: []
Explanation:
You cannot form a triangle with positive area using side lengths 2, 4, and 2.
Constraints:
• sides.length == 3
• 1 <= sides[i] <= 1000
class Solution {
public double[] internalAngles(int[] sides) {
Arrays.sort(sides);
if (sides[0] + sides[1] > sides[2] &&
sides[1] + sides[2] > sides[0] &&
sides[0] + sides[2] > sides[1]) {
double A = angleFromSides(sides[1], sides[2], sides[0]);
double B = angleFromSides(sides[0], sides[2], sides[1]);
double C = angleFromSides(sides[0], sides[1], sides[2]);
double[] angles = {A, B, C};
Arrays.sort(angles); // non-decreasing order
return angles;
} else {
return new double[0];
}
}
private static double angleFromSides(int side1, int side2, int opposite) {
double numerator = (side1 * side1) + (side2 * side2) - (opposite * opposite);
double denominator = 2.0 * side1 * side2;
double cosValue = numerator / denominator;
// Numerical safety: clamp to [-1, 1]
cosValue = Math.max(-1.0, Math.min(1.0, cosValue));
return Math.toDegrees(Math.acos(cosValue));
}
}
Test cases:
Case 0:
Input
sides =
[3,4,5]
Output
[36.86990,53.13010,90.00000]
Expected
[36.86990,53.13010,90.00000]
Case 1:
Input
sides =
[2,4,2]
Output
[]
Expected
[]
No comments:
Post a Comment