463. Island Perimeter
class Solution {
public int islandPerimeter(int[][] grid) {
//the number of neighbors is all we should care about
int total = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
int neighbors = 0;
if (grid[i][j] == 1) {
if (i == 0) {
neighbors++;
} else if (grid[i-1][j] == 0) {
neighbors++;
}
if (j == 0) {
neighbors++;
} else if (grid[i][j-1] == 0) {
neighbors++;
}
if (i == grid.length - 1) {
neighbors++;
} else if (grid[i+1][j] == 0) {
neighbors++;
}
if (j == grid[0].length - 1) {
neighbors++;
} else if (grid[i][j+1] == 0) {
neighbors++;
}
total = total + neighbors;
}
}
}
return total;
}
}Runtime: 6 ms, faster than 65.65% of Java online submissions for Island Perimeter.
Memory Usage: 40.2 MB, less than 64.55% of Java online submissions for Island Perimeter.
그림을 그려보니깐 위, 아래, 왼, 오 가 비어있다면 그 상자의 perimeter이 count가 된다는 점을 발견하고
끄트머리에 있음 자동적으로 비어있는거니깐 그 친구들을 세주는 방식으로 풀었읍니다
루션이
class Solution {
public int islandPerimeter(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int result = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
result += 4;
if (r > 0 && grid[r-1][c] == 1) {
result -= 2;
}
if (c > 0 && grid[r][c-1] == 1) {
result -= 2;
}
}
}
}
return result;
}
}Runtime: 5 ms, faster than 99.52% of Java online submissions for Island Perimeter.
Memory Usage: 40.5 MB, less than 47.89% of Java online submissions for Island Perimeter.
사방을 보지 않고 전꺼만 봐도 ㄱㄴ하다는 점~
143. Reorder List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode start = head;
ListNode cur = head;
ListNode end = head;
ListNode scur = head;
while (end.next != null) {
while (cur.next.next != null) {
cur = cur.next;
}
end = cur.next.next;
cur.next.next = null;
scur = start.next;
start.next = end;
end.next = scur;
start = scur.next;
}
}
}처음에는 대충 data strcture 없이 진짜 linkedlist 그 자체로만 풀려고 했는데
시간 내에 절대 못할 각이더라구요... 생각할게 너무 많음
그래서 deque를 써서 간단하게 풀었읍니다
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
Deque<Integer> q = new ArrayDeque<Integer>();
ListNode cur = head;
while (cur != null) {
q.add(cur.val);
cur = cur.next;
}
ListNode result = new ListNode(-1);
cur = result;
int order = 0;
while (! q.isEmpty()) {
head.val = q.pollFirst();
head = head.next;
if (q.size() != 0) {
head.val = q.pollLast();
head = head.next;
}
}
}
}Runtime: 4 ms, faster than 13.41% of Java online submissions for Reorder List.
Memory Usage: 41.3 MB, less than 87.80% of Java online submissions for Reorder List.
deque에다가 넣어줘서 앞부분은 그대로 뒷부분은 거꾸로 부터 넣었읍니다
근데 좀 많이 느리네요..^^
루션이
이놈의 circle detecting algorithm...
class Solution {
public void reorderList(ListNode head) {
if (head == null) return;
// find the middle of linked list [Problem 876]
// in 1->2->3->4->5->6 find 4
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// reverse the second part of the list [Problem 206]
// convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
// reverse the second half in-place
ListNode prev = null, curr = slow, tmp;
while (curr != null) {
tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
// merge two sorted linked lists [Problem 21]
// merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4
ListNode first = head, second = prev;
while (second.next != null) {
tmp = first.next;
first.next = second;
first = tmp;
tmp = second.next;
second.next = first;
second = tmp;
}
}
}Runtime: 1 ms, faster than 99.83% of Java online submissions for Reorder List.
Memory Usage: 41.1 MB, less than 96.33% of Java online submissions for Reorder List.
ㅎㅎ....
저는 언제쯤 이런 코드를 짤 수 있게 될까요~
133. Clone Graph
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
//return node; 희망사항..ㅎ
int _val = node.val;
List<Node> neigh = new ArrayList<Node>();
neigh = node.neighbors;
Node result = new Node(_val, new ArrayList<Node>(neigh));
return result;
}
}Node with value 2 was not copied but a reference to the original one.
새로 만들었는데 이게 왜 클론이 아닌건지...ㅠ 모르겠어요
뭘 바라는건지 잘 모르겠음
루션이: DFS
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
private HashMap <Node, Node> visited = new HashMap <> ();
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
// If the node was already visited before.
// Return the clone from the visited dictionary.
if (visited.containsKey(node)) {
return visited.get(node);
}
// Create a clone for the given node.
// Note that we don't have cloned neighbors as of now, hence [].
Node cloneNode = new Node(node.val, new ArrayList());
// The key is original node and value being the clone node.
visited.put(node, cloneNode);
// Iterate through the neighbors to generate their clones
// and prepare a list of cloned neighbors to be added to the cloned node.
for (Node neighbor: node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}Runtime: 26 ms, faster than 44.71% of Java online submissions for Clone Graph.
Memory Usage: 39.1 MB, less than 57.55% of Java online submissions for Clone Graph.
루션이: BFS
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
// Hash map to save the visited node and it's respective clone
// as key and value respectively. This helps to avoid cycles.
HashMap<Node, Node> visited = new HashMap();
// Put the first node in the queue
LinkedList<Node> queue = new LinkedList<Node> ();
queue.add(node);
// Clone the node and put it in the visited dictionary.
visited.put(node, new Node(node.val, new ArrayList()));
// Start BFS traversal
while (!queue.isEmpty()) {
// Pop a node say "n" from the from the front of the queue.
Node n = queue.remove();
// Iterate through all the neighbors of the node "n"
for (Node neighbor: n.neighbors) {
if (!visited.containsKey(neighbor)) {
// Clone the neighbor and put in the visited, if not present already
visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
// Add the newly encountered node to the queue.
queue.add(neighbor);
}
// Add the clone of the neighbor to the neighbors of the clone node "n".
visited.get(n).neighbors.add(visited.get(neighbor));
}
}
// Return the clone of the node from visited.
return visited.get(node);
}
}Runtime: 27 ms, faster than 25.69% of Java online submissions for Clone Graph.
Memory Usage: 38.9 MB, less than 91.05% of Java online submissions for Clone Graph
ㅎㅎ???
y