Given an array of size n, find the majority element.
The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Input: [3,2,3]
Output: 3
Reverse a singly linked list.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode toBeCurrent = head.next;
ListNode toBePrev = head;
toBePrev.next = null;
while (toBeCurrent != null) {
ListNode temp = toBeCurrent.next;
toBeCurrent.next = toBePrev;
toBePrev = toBeCurrent;
toBeCurrent = temp;
}
return toBePrev;
}
Need to Retry
public ListNode reverseList(ListNode head) {
ListNode first = null;
ListNode second = null;
ListNode third = null;
if (head == null) {
return null;
}
first = head;
if (first.next == null) {
return first;
}
second = first.next;
first.next = null;
if (second.next == null) {
second.next = first;
return second;
}
third = second.next;
while (third != null) {
second.next = first;
first = second;
second = third;
third = second.next;
}
second.next = first;
return second;
}
25분가량 소요
깔끔하게 풀 수 있을 텐데 생각이 들었는데 떠오르지 않아서
일단 머릿속에 아이디어를 구현했고 맞췄다.
다시 풀어봐도 좋을 문제라고 생각이 들었다.
다른 코드를 봤는데 굉장히 깔끔한 코드가 있었다.
참고하도록 하자 !
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while(current != null) {
ListNode temp = current.next;
current.next = prev;
prev = current;
current = temp;
}
return prev;
}
Need to Retry -> 자료구조를 사용해보자.
public ListNode reverseList(ListNode head) {
ListNode l = null;
ListNode r = null;
ListNode m = head;
while (m != null) {
r = m.next;
m.next = l;
l = m;
m = r;
}
return l;
}
Reference Code
public ListNode reverseList(ListNode head) {
//declare Stack
//for each node
// put node in stack
//take first node from stack
//while stack is not empty
//. node .next = stack.pop
//return first Node
if(head == null){
return null;
}
Stack<ListNode> nodes = new Stack<>();
ListNode cur = head;
nodes.push(cur);
while(cur != null){
if(cur.next != null){
nodes.push(cur.next);
}
cur = cur.next;
}
ListNode returnNode = nodes.pop();
ListNode headTemp = returnNode;
while(nodes.size() != 0){
headTemp.next = nodes.pop();
headTemp = headTemp.next;
}
headTemp.next = null;
return returnNode;
}
Stack을 사용하면 자연스럽게 Reverse하게 연결을 할 수가 있다.
굉장히 좋은 접근이라는 생각이 든다.
FeedBack
Iteratively 하게 풀었다.
다른 코드를 보니 Stack을 사용했는데 너무 좋은 접근이었다.
다음엔 Stack 자료구조를 떠올려서 풀어보면 좋을 거 같다.
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”.
For numbers which are multiples of both three and five output “FizzBuzz”.
n = 15,
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
public List<String> fizzBuzz(int n) {
List<String> ans = new ArrayList<>();
for (int i = 1; i <= n; i++) {
ans.add(getString(i));
}
return ans;
}
private String getString(int i) {
String fizz = "Fizz";
String buzz = "Buzz";
String fizzBuzz = "FizzBuzz";
if (i % 3 == 0 && i % 5 == 0) {
return fizzBuzz;
} else if (i % 3 == 0) {
return fizz;
} else if (i % 5 == 0) {
return buzz;
} else {
return String.valueOf(i);
}
}
Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list,
instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list.
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
문제가 뭐지?…
굉장히 어색한 스타일의 문제였다.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Input: nums = [2,2,1]
Output: 1
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
Integer value = map.getOrDefault(nums[i], 0);
map.put(nums[i], value + 1);
}
int ans = 0;
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == 1) {
ans = nums[i];
break;
}
}
return ans;
}
문제 의도와는 다르게 막 풀었다.
사실 XOR로 푸는게 정확한 답이다.
Feed Back
Case 1
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
}
XOR은 같으면 0
다르면 1이다.
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
}
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array,
you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
public void reverseString(char[] s) {
int length = s.length;
char[] ans = new char[length];
for (int i = 0; i < length; i++) {
ans[i] = s[length - 1 - i];
}
for (int i = 0; i < length; i++) {
s[i] = ans[i];
}
}
막 풀어도 될까 했는데 풀리는구나.
그래도 좋은 코드 참고하자.