single number I/II, remove Nth node from end of list

fishercoder1534 · fishercoder1534 · commit 010064e1af7d · 2016-08-05T08:41:29.000-07:00
diff --git a/EASY/src/easy/RemoveNthNodeFromEndOfList.java b/EASY/src/easy/RemoveNthNodeFromEndOfList.java
@@ -0,0 +1,49 @@
+package easy;
+
+import utils.CommonUtils;
+import classes.ListNode;
+
+/**19. Remove Nth Node From End of List  QuestionEditorial Solution  My Submissions
+Total Accepted: 122330
+Total Submissions: 400291
+Difficulty: Easy
+Given a linked list, remove the nth node from the end of list and return its head.
+
+For example,
+
+   Given linked list: 1->2->3->4->5, and n = 2.
+
+   After removing the second node from the end, the linked list becomes 1->2->3->5.
+Note:
+Given n will always be valid.
+Try to do this in one pass.*/
+public class RemoveNthNodeFromEndOfList {
+    public ListNode removeNthFromEnd(ListNode head, int n) {
+        ListNode temp = head;
+        int len = 0;
+        while(temp != null){
+            temp = temp.next;
+            len++;
+        }
+        if(n == len) return head.next;
+        
+        temp = head;
+        int cut = len-n;
+        while(cut-- > 1){
+            temp = temp.next;
+        }
+        if(temp.next != null){
+            temp.next = temp.next.next;
+            return head;
+        }
+        return null;
+    }
+    
+    public static void main(String...strings){
+        ListNode head = new ListNode(1);
+        head.next = new ListNode(2);
+        RemoveNthNodeFromEndOfList test = new RemoveNthNodeFromEndOfList();
+        ListNode res = test.removeNthFromEnd(head, 2);
+        CommonUtils.printList(res);
+    }
+}
diff --git a/MEDIUM/src/medium/SingleNumberII.java b/MEDIUM/src/medium/SingleNumberII.java
@@ -0,0 +1,37 @@
+package medium;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**137. Single Number II  QuestionEditorial Solution  My Submissions
+Total Accepted: 91512
+Total Submissions: 236469
+Difficulty: Medium
+Given an array of integers, every element appears three times except for one. Find that single one.
+
+Note:
+Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
+
+Hide Tags Bit Manipulation
+Show Similar Problems
+*/
+public class SingleNumberII {
+
+    public int singleNumber(int[] nums) {
+        Map<Integer, Integer> map = new HashMap();
+        for(int i : nums){
+            map.put(i, map.getOrDefault(i, 0) + 1);
+        }
+        for(int key : map.keySet()){
+            if(map.get(key) != 3) return key;
+        }
+        return 0;
+    }
+    
+    public static void main(String...strings){
+        int[] nums = new int[]{2,2,3,2};
+        SingleNumberII test = new SingleNumberII();
+        System.out.println(test.singleNumber(nums));
+    }
+
+}
diff --git a/MEDIUM/src/medium/SingleNumberIII.java b/MEDIUM/src/medium/SingleNumberIII.java
@@ -0,0 +1,36 @@
+package medium;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**260. Single Number III  QuestionEditorial Solution  My Submissions
+Total Accepted: 42536
+Total Submissions: 92175
+Difficulty: Medium
+Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
+
+For example:
+
+Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
+
+Note:
+The order of the result is not important. So in the above example, [5, 3] is also correct.
+Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
+*/
+public class SingleNumberIII {
+    //Approach 1: normal hashmap
+    public int[] singleNumber(int[] nums) {
+        Map<Integer, Integer> map = new HashMap();
+        for(int i : nums){
+            map.put(i, map.getOrDefault(i, 0)+1);
+        }
+        
+        int[] res = new int[2];
+        int index = 0;
+        for(int key : map.keySet()){
+            if(map.get(key) == 1) res[index++] = key;
+            if(index == 2) break;
+        }
+        return res;
+    }
+}
