Rotting Oranges
class Solution {
int[][] cur;
public int orangesRotting(int[][] grid) {
//뭔가...greedy나...그런걸 써야할 것 같은디 ^^
if (grid == null || grid.length == 0) {
return 0;
}
int min = 0;
int fresh = 0;
Queue<int[]> q = new LinkedList<int[]>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) {
int[] rot = new int[2];
rot = [i, j];
q.add(rot);
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) {
return 0;
}
while (!q.isEmpty()) {
}
}
private void helper(int y, int x) {
while (cur[y][x] != 0) {
cur[y][x] == 2;
x++;
}
while (cur[y][x] != 0) {
cur[y][x] == 2;
x++;
}
}
}시간이 닳아서 다 못풀었읍니다^^ 사실 시간이 무한대로 있었어도 다 풀 수 있었을지는 모른다는점^^
댜충 Queue를 써서 썩히는 놈들을 모아놓고.. fresh 한 애들이 없어질때 까지 bfs로 냅다 돌리려고 했는데 지금 생각해보니 그러면 날짜는 어떻게 잡을지 모르겠네요;;
One of the most distinguished code patterns in BFS algorithms is that often we use a queue data structure to keep track of the candidates that we need to visit during the process.
루션이
class Solution {
public int orangesRotting(int[][] grid) {
Queue<Pair<Integer, Integer>> queue = new ArrayDeque();
// Step 1). build the initial set of rotten oranges
int freshOranges = 0;
int ROWS = grid.length, COLS = grid[0].length;
for (int r = 0; r < ROWS; ++r)
for (int c = 0; c < COLS; ++c)
if (grid[r][c] == 2)
queue.offer(new Pair(r, c));
else if (grid[r][c] == 1)
freshOranges++;
// Mark the round / level, _i.e_ the ticker of timestamp
queue.offer(new Pair(-1, -1));
// Step 2). start the rotting process via BFS
int minutesElapsed = -1;
int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!queue.isEmpty()) {
Pair<Integer, Integer> p = queue.poll();
int row = p.getKey();
int col = p.getValue();
if (row == -1) {
// We finish one round of processing
minutesElapsed++;
// to avoid the endless loop
if (!queue.isEmpty())
queue.offer(new Pair(-1, -1));
} else {
// this is a rotten orange
// then it would contaminate its neighbors
for (int[] d : directions) {
int neighborRow = row + d[0];
int neighborCol = col + d[1];
if (neighborRow >= 0 && neighborRow < ROWS &&
neighborCol >= 0 && neighborCol < COLS) {
if (grid[neighborRow][neighborCol] == 1) {
// this orange would be contaminated
grid[neighborRow][neighborCol] = 2;
freshOranges--;
// this orange would then contaminate other oranges
queue.offer(new Pair(neighborRow, neighborCol));
}
}
}
}
}
// return elapsed minutes if no fresh orange left
return freshOranges == 0 ? minutesElapsed : -1;
}
}머리 대박 안돌아가네요;;
Spiral Matrix II
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int xs = 0;
int ys = 1;
int xe = n - 1;
int ye = n - 1;
int xcur = 0;
int ycur = 0;
boolean changex = true;
boolean pos = true;
for (int i = 1; i <= n * n; i++) {
result[ycur][xcur] = i;
if (changex && pos) {
xcur++;
if (xcur == xe) {
xe--;
changex = false;
}
} else if (! changex && pos) {
ycur++;
if (ycur == ye) {
ye--;
changex = true;
pos = false;
}
} else if (changex && !pos) {
xcur--;
if (xcur == xs) {
xs++;
changex = false;
}
} else if (! changex && !pos) {
ycur--;
if (ycur == ys) {
ys++;
changex = true;
pos = true;
}
}
}
return result;
}
}Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix II.
Memory Usage: 37.2 MB, less than 42.75% of Java online submissions for Spiral Matrix II.
대박 요란한 코드~^^
진짜 짜는데 빡쳐서 죽는줄요
우.아래.좌.위 패턴을 간파한 뒤 만약에 끝까지 갔다면 방향을 살짝 틀어주는 방식으로 풀었읍니다.
루션이
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int cnt = 1;
int dir[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int d = 0;
int row = 0;
int col = 0;
while (cnt <= n * n) {
result[row][col] = cnt++;
int r = Math.floorMod(row + dir[d][0], n);
int c = Math.floorMod(col + dir[d][1], n);
// change direction if next cell is non zero
if (result[r][c] != 0) d = (d + 1) % 4;
row += dir[d][0];
col += dir[d][1];
}
return result;
}
}뭐야??????????????????
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int cnt = 1;
for (int layer = 0; layer < (n + 1) / 2; layer++) {
// direction 1 - traverse from left to right
for (int ptr = layer; ptr < n - layer; ptr++) {
result[layer][ptr] = cnt++;
}
// direction 2 - traverse from top to bottom
for (int ptr = layer + 1; ptr < n - layer; ptr++) {
result[ptr][n - layer - 1] = cnt++;
}
// direction 3 - traverse from right to left
for (int ptr = layer + 1; ptr < n - layer; ptr++) {
result[n - layer - 1][n - ptr - 1] = cnt++;
}
// direction 4 - traverse from bottom to top
for (int ptr = layer + 1; ptr < n - layer - 1; ptr++) {
result[n - ptr - 1][layer] = cnt++;
}
}
return result;
}
}제것과 조금 더 비스한 루션이...
y