7 142
订阅者
-224 小时
-327 天
-11830 天
帖子存档
AMAZON SDE ROUND-2✅✅
ROUND-1 CLEARED✅
Contact : @MLCODER2
import java.io.*;
import java.util.*;
public class TestClass {
public static void droneservicesschedule(int[][] arr, int M, int N) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adj.add(new ArrayList<>());
}
int[] degree = new int[N + 1];
for (int i = 0; i < M; i++) {
int u = arr[i][0];
int v = arr[i][1];
adj.get(u).add(v);
adj.get(v).add(u);
degree[u]++;
degree[v]++;
}
boolean[] visited = new boolean[N + 1];
List<List<Integer>> components = new ArrayList<>();
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
List<Integer> comp = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
visited[i] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
comp.add(curr);
for (int neighbor : adj.get(curr)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
components.add(comp);
}
}
if (components.size() > 2) {
System.out.println("Not a Complete Day");
return;
}
for (List<Integer> comp : components) {
int K = comp.size();
for (int vertex : comp) {
if (degree[vertex] != K - 1) {
System.out.println("Not a Complete Day");
return;
}
}
}
System.out.println("Complete Day");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int T = sc.nextInt();
for (int j = 0; j < T; j++) {
int N = sc.nextInt();
int M = sc.nextInt();
int[][] arr = new int[M][2];
for (int i = 0; i < M; ++i) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
droneservicesschedule(arr, M, N);
}
}
}
import java.io.*;
import java.util.*;
public class TestClass {
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int minNumOfwalls(int[][] a, int m, int n) {
int totalWalls = 0;
while (true) {
boolean[][] visited = new boolean[m][n];
List<Set<Integer>> regions = new ArrayList<>();
List<Set<Integer>> frontiers = new ArrayList<>();
List<Integer> wallsNeeded = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && !visited[i][j]) {
Set<Integer> region = new HashSet<>();
Set<Integer> frontier = new HashSet<>();
int[] walls = new int[1];
dfs(i, j, a, m, n, visited, region, frontier, walls);
regions.add(region);
frontiers.add(frontier);
wallsNeeded.add(walls[0]);
}
}
}
if (regions.isEmpty()) {
break;
}
int maxFrontierIdx = -1;
int maxFrontierSize = -1;
for (int i = 0; i < frontiers.size(); i++) {
if (frontiers.get(i).size() > maxFrontierSize) {
maxFrontierSize = frontiers.get(i).size();
maxFrontierIdx = i;
}
}
if (maxFrontierSize == 0) {
break;
}
totalWalls += wallsNeeded.get(maxFrontierIdx);
for (int i = 0; i < regions.size(); i++) {
if (i == maxFrontierIdx) {
for (int code : regions.get(i)) {
int r = code / n;
int c = code % n;
a[r][c] = -1;
}
} else {
for (int code : frontiers.get(i)) {
int r = code / n;
int c = code % n;
a[r][c] = 1;
}
}
}
}
return totalWalls;
}
static void dfs(int r, int c, int[][] a, int m, int n, boolean[][] visited,
Set<Integer> region, Set<Integer> frontier, int[] walls) {
visited[r][c] = true;
region.add(r * n + c);
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (a[nr][nc] == 1 && !visited[nr][nc]) {
dfs(nr, nc, a, m, n, visited, region, frontier, walls);
} else if (a[nr][nc] == 0) {
walls[0]++;
frontier.add(nr * n + nc);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
System.out.print(minNumOfwalls(a, m, n));
}
}
FLIPKART ✅
q4
import java.util.Scanner;
public class TestClass
{
static int countOccurrence(int n, String grid[], String word)
{
int count = 0;
int wordLen = word.length();
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
{
for (int dir = 0; dir < 8; dir++)
{
int k;
int currR = r;
int currC = c;
for (k = 0; k < wordLen; k++)
{
if (currR < 0 currR >= n currC < 0 || currC >= n)
{
break;
}
if (grid[currR].charAt(currC) != word.charAt(k))
{
break;
}
currR += dx[dir];
currC += dy[dir];
}
if (k == wordLen)
{
count++;
}
}
}
}
return count;
}
public static void main(String args[])
{
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.nextLine();
String grid[] = new String[n];
for(int i=0; i<n; i++)
{
grid[i] = sc.nextLine();
}
String word;
word = sc.nextLine();
System.out.println(countOccurrence(n,grid,word));
}
}
FLIPKART✅
q4✅
import java.util.*;
public class TestClass {
public static int cureTheVirus(int n, int[] impact, int[] numOfPre, int[][] precells) {
int source = 0;
int sink = n + 1;
List<Edge>[] graph = new List[sink + 1];
for (int i = 0; i <= sink; i++) {
graph[i] = new ArrayList<>();
}
int totalPositiveImpact = 0;
for (int i = 0; i < n; i++) {
int w = impact[i];
int u = i + 1;
if (w > 0) {
totalPositiveImpact += w;
addEdge(graph, source, u, w);
} else if (w < 0) {
addEdge(graph, u, sink, -w);
}
for (int k = 0; k < numOfPre[i]; k++) {
int v = precells[i][k];
addEdge(graph, u, v, Integer.MAX_VALUE);
}
}
int minCut = dinicMaxFlow(graph, source, sink);
return totalPositiveImpact - minCut;
}
private static class Edge {
int to;
int rev;
int cap;
int flow;
Edge(int to, int rev, int cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
this.flow = 0;
}
}
private static void addEdge(List<Edge>[] graph, int from, int to, int cap) {
Edge a = new Edge(to, graph[to].size(), cap);
Edge b = new Edge(from, graph[from].size(), 0);
graph[from].add(a);
graph[to].add(b);
}
private static int dinicMaxFlow(List<Edge>[] graph, int src, int dest) {
int flow = 0;
int[] level = new int[graph.length];
while (bfs(graph, src, dest, level)) {
int[] ptr = new int[graph.length];
while (true) {
int pushed = dfs(graph, src, dest, Integer.MAX_VALUE, level, ptr);
if (pushed == 0) {
break;
}
flow += pushed;
}
}
return flow;
}
private static boolean bfs(List<Edge>[] graph, int src, int dest, int[] level) {
Arrays.fill(level, -1);
level[src] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(src);
while (!q.isEmpty()) {
int v = q.poll();
for (Edge e : graph[v]) {
if (level[e.to] < 0 && e.flow < e.cap) {
level[e.to] = level[v] + 1;
q.add(e.to);
}
}
}
return level[dest] >= 0;
}
private static int dfs(List<Edge>[] graph, int v, int dest, int pushed, int[] level, int[] ptr) {
if (pushed == 0 v == dest) {
return pushed;
}
for (int cid = ptr[v]; ptr[v] < graph[v].size(); cid = ++ptr[v]) {
Edge e = graph[v].get(cid);
int tr = e.to;
if (level[v] + 1 != level[tr] e.flow == e.cap) {
continue;
}
int trPushed = dfs(graph, tr, dest, Math.min(pushed, e.cap - e.flow), level, ptr);
if (trPushed == 0) {
continue;
}
e.flow += trPushed;
graph[tr].get(e.rev).flow -= trPushed;
return trPushed;
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numberOfCells = sc.nextInt();
int[] impact = new int[numberOfCells];
int[] numOfPre = new int[numberOfCells];
int[][] precells = new int[numberOfCells][];
for (int j = 0; j < numberOfCells; j++) {
impact[j] = sc.nextInt();
numOfPre[j] = sc.nextInt();
precells[j] = new int[numOfPre[j]];
for (int k = 0; k < numOfPre[j]; k++) {
precells[j][k] = sc.nextInt();
}
}
System.out.println(cureTheVirus(numberOfCells, impact, numOfPre, precells));
sc.close();
}
}
FLIPKART✅
Q3
