aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Anagram.java27
-rw-r--r--CloneGraph.java39
-rw-r--r--CourseSchedule.java60
-rw-r--r--ListCycle.java32
-rw-r--r--LongestPalindrome.java55
-rw-r--r--LongestSubstringWithoutRepeat.java27
-rw-r--r--MaxSubArray.java19
-rw-r--r--MergeLists.java62
-rw-r--r--MinRotatedArray.java27
-rw-r--r--Palindrome.java30
-rw-r--r--Parentheses.java26
-rw-r--r--ProductExceptSelf.java31
-rw-r--r--RemoveNthNode.java37
-rw-r--r--ReverseList.java31
-rw-r--r--Stock.java25
-rw-r--r--SumTwoIntegers.java30
-rw-r--r--TwoSum.java20
-rw-r--r--node/GraphNode.classbin0 -> 624 bytes
-rw-r--r--node/GraphNode.java21
-rw-r--r--node/ListNode.classbin0 -> 396 bytes
-rw-r--r--node/ListNode.java9
21 files changed, 608 insertions, 0 deletions
diff --git a/Anagram.java b/Anagram.java
new file mode 100644
index 0000000..d7f8280
--- /dev/null
+++ b/Anagram.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class Anagram {
+ public static boolean isAnagram(String s, String t) {
+ char[] arrS = s.toCharArray();
+ char[] arrT = t.toCharArray();
+ int[] occur = new int[26];
+ for (char c : arrS) {
+ occur[c - 'a']++;
+ }
+ for (char c : arrT) {
+ occur[c - 'a']--;
+ }
+ for (int i : occur) {
+ if (i != 0)
+ return false;
+ }
+ return true;
+ }
+
+ public static void main(String[] args) {
+ String s = "anagram";
+ String t = "nagaram";
+ System.out.println(isAnagram(s, t));
+ }
+}
diff --git a/CloneGraph.java b/CloneGraph.java
new file mode 100644
index 0000000..ada085c
--- /dev/null
+++ b/CloneGraph.java
@@ -0,0 +1,39 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class CloneGraph {
+ public static GraphNode cloneGraph(GraphNode node) {
+ Stack<GraphNode> stack = new Stack<GraphNode>();
+ ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
+ stack.push(node);
+ GraphNode clone = new GraphNode(node.val, node.neighbors);
+ while (!stack.empty()) {
+ node = stack.pop();
+ if (visited.contains(node))
+ continue;
+ GraphNode curr = new GraphNode(node.val, node.neighbors);
+ visited.add(node);
+ System.out.println("Node: " + node.val);
+ System.out.print("Neighbors: ");
+ for (GraphNode neighbor : node.neighbors) {
+ stack.push(neighbor);
+ System.out.print(neighbor.val + " ");
+ }
+ System.out.println();
+ }
+ return clone;
+ }
+
+ public static void main(String[] args) {
+ GraphNode head = new GraphNode(1);
+ GraphNode first = new GraphNode(2);
+ GraphNode second = new GraphNode(3);
+ GraphNode third = new GraphNode(4, new ArrayList<>(Arrays.asList(first, second)));
+ second.neighbors = new ArrayList<>(Arrays.asList(head, third));
+ first.neighbors = new ArrayList<>(Arrays.asList(head, second));
+ head.neighbors = new ArrayList<>(Arrays.asList(first, second));
+
+ GraphNode curr = cloneGraph(head);
+ }
+}
diff --git a/CourseSchedule.java b/CourseSchedule.java
new file mode 100644
index 0000000..5b5ed02
--- /dev/null
+++ b/CourseSchedule.java
@@ -0,0 +1,60 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class CourseSchedule {
+ public static boolean canFinish(int[][] prerequisites) {
+ GraphNode node = createGraph(prerequisites);
+ return !detectCycle(node);
+ }
+
+ public static GraphNode createGraph(int[][] prerequisites) {
+ HashMap<Integer, GraphNode> map = new HashMap<Integer, GraphNode>();
+ for (int[] prerequisite : prerequisites) {
+ if (map.containsKey(prerequisite[0])) {
+ if (map.containsKey(prerequisite[1])) {
+ map.get(prerequisite[0]).neighbors.add(map.get(prerequisite[1]));
+ } else {
+ GraphNode node = new GraphNode(prerequisite[1]);
+ map.put(node.val, node);
+ map.get(prerequisite[0]).neighbors.add(node);
+ }
+ continue;
+ }
+ GraphNode pre = new GraphNode(prerequisite[1]);
+ GraphNode node = new GraphNode(prerequisite[0],
+ new ArrayList<GraphNode>(Arrays.asList(pre)));
+ map.put(pre.val, pre);
+ map.put(node.val, node);
+ }
+ // TODO: return first GraphNode in map
+ return map.get(1);
+ }
+
+ public static boolean detectCycle(GraphNode node) {
+ Stack<GraphNode> stack = new Stack<GraphNode>();
+ ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
+ stack.push(node);
+ while (!stack.empty()) {
+ node = stack.pop();
+ if (visited.contains(node)) {
+ System.out.println("Cycle " + node.val);
+ return true;
+ }
+ visited.add(node);
+ System.out.println("Node: " + node.val);
+ System.out.print("Neighbors: ");
+ for (GraphNode neighbor : node.neighbors) {
+ stack.push(neighbor);
+ System.out.print(neighbor.val + " ");
+ }
+ System.out.println();
+ }
+ return false;
+ }
+
+ public static void main(String[] args) {
+ int[][] prerequisites = {{1, 4}, {1, 2}, {2, 3}, {3, 6}, {6, 2}, {4, 5}};
+ System.out.println(canFinish(prerequisites));
+ }
+}
diff --git a/ListCycle.java b/ListCycle.java
new file mode 100644
index 0000000..a48f38a
--- /dev/null
+++ b/ListCycle.java
@@ -0,0 +1,32 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class ListCycle {
+ public static boolean hasCycle(ListNode head) {
+ if (head == null)
+ return false;
+ else if (head.next == null)
+ return false;
+
+ ListNode slow = head;
+ ListNode fast = head.next;
+ while (slow != null && fast.next != null) {
+ if (slow == fast)
+ return true;
+ slow = slow.next;
+ fast = fast.next.next;
+ }
+ return false;
+ }
+
+ public static void main(String[] args) {
+ ListNode first = new ListNode(2, null);
+ ListNode third = new ListNode(4, first);
+ ListNode second = new ListNode(0, third);
+ first.next = second;
+ ListNode head = new ListNode(3, first);
+
+ System.out.println(hasCycle(head));
+ }
+}
diff --git a/LongestPalindrome.java b/LongestPalindrome.java
new file mode 100644
index 0000000..447bb27
--- /dev/null
+++ b/LongestPalindrome.java
@@ -0,0 +1,55 @@
+import java.lang.*;
+import java.util.*;
+
+class LongestPalindrome {
+ public static String longestPalindrome(String s) {
+ // TODO: check if s length is 0 or 1
+ // TODO: find simpler solution
+
+ s = s.toLowerCase();
+ char[] arr = s.toCharArray();
+ String ans = null;
+
+ int i = 0;
+ int j = 0;
+ int max = 0;
+ // Odd case: "aba"
+ for (int a = 1; a < arr.length - 1; a++) {
+ i = a - 1;
+ j = a + 1;
+ while (i >= 0 && j < arr.length) {
+ if (arr[i] == arr[j]) {
+ if (j - i > max) {
+ max = j - i;
+ ans = s.substring(i, j + 1);
+ }
+ i--;
+ j++;
+ } else {
+ break;
+ }
+ }
+ }
+ // Even case: "abba"
+ for (i = 0, j = i + 1; i < arr.length - 1; i++) {
+ while (i >= 0 && j < arr.length) {
+ if (arr[i] == arr[j]) {
+ if (j - i > max) {
+ max = j - i;
+ ans = s.substring(i, j + 1);
+ }
+ i--;
+ j++;
+ } else {
+ break;
+ }
+ }
+ }
+ return ans;
+ }
+
+ public static void main(String[] args) {
+ String s = "kl;fadsjf;dalscbbciuporeqwrpo";
+ System.out.println(longestPalindrome(s));
+ }
+}
diff --git a/LongestSubstringWithoutRepeat.java b/LongestSubstringWithoutRepeat.java
new file mode 100644
index 0000000..d01ecf3
--- /dev/null
+++ b/LongestSubstringWithoutRepeat.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class LongestSubstringWithoutRepeat {
+ public static int lengthOfLongestSubstring(String s) {
+ char[] arr = s.toCharArray();
+ int max = 0;
+ ArrayList<Character> occur = new ArrayList<Character>();
+ for (char c : arr) {
+ if (!occur.contains(c)) {
+ occur.add(c);
+ } else {
+ occur.clear();
+ occur.add(c);
+ }
+ if (max < occur.size()) {
+ max = occur.size();
+ }
+ }
+ return max;
+ }
+
+ public static void main(String[] args) {
+ String s = "pwwkew";
+ System.out.println(lengthOfLongestSubstring(s));
+ }
+}
diff --git a/MaxSubArray.java b/MaxSubArray.java
new file mode 100644
index 0000000..89698c2
--- /dev/null
+++ b/MaxSubArray.java
@@ -0,0 +1,19 @@
+import java.lang.*;
+import java.util.*;
+
+class MaxSubArray {
+ public static int maxSubArray(int[] nums) {
+ int currSum = 0;
+ int maxSum = 0;
+ for (int i : nums) {
+ currSum = Math.max(currSum + i, 0);
+ maxSum = Math.max(maxSum, currSum);
+ }
+ return maxSum;
+ }
+
+ public static void main(String[] args) {
+ int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
+ System.out.println(maxSubArray(nums));
+ }
+}
diff --git a/MergeLists.java b/MergeLists.java
new file mode 100644
index 0000000..e939511
--- /dev/null
+++ b/MergeLists.java
@@ -0,0 +1,62 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class MergeLists {
+ public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
+ if (list1 == null && list2 == null)
+ return new ListNode();
+ else if (list1 == null)
+ return list2;
+ else if (list2 == null)
+ return list1;
+
+ ListNode curr1 = list1;
+ ListNode curr2 = list2;
+
+ ListNode head;
+ if (curr1.val < curr2.val) {
+ head = curr1;
+ curr1 = curr1.next;
+ } else {
+ head = curr2;
+ curr2 = curr2.next;
+ }
+
+ ListNode node = head;
+ while (curr1 != null && curr2 != null) {
+ if (curr1.val < curr2.val) {
+ node.next = curr1;
+ curr1 = curr1.next;
+ } else {
+ node.next = curr2;
+ curr2 = curr2.next;
+ }
+ node = node.next;
+ }
+
+ if (curr1 == null) {
+ node.next = curr2;
+ } else {
+ node.next = curr1;
+ }
+
+ return head;
+ }
+
+ public static void main(String[] args) {
+ ListNode second1 = new ListNode(4, null);
+ ListNode first1 = new ListNode(2, second1);
+ ListNode list1 = new ListNode(1, first1);
+
+ ListNode second2 = new ListNode(4, null);
+ ListNode first2 = new ListNode(3, second2);
+ ListNode list2 = new ListNode(1, first2);
+
+ ListNode curr = mergeTwoLists(list1, list2);
+ while (curr != null) {
+ System.out.println(curr.val);
+ curr = curr.next;
+ }
+ }
+}
diff --git a/MinRotatedArray.java b/MinRotatedArray.java
new file mode 100644
index 0000000..b93b2b4
--- /dev/null
+++ b/MinRotatedArray.java
@@ -0,0 +1,27 @@
+import java.lang.*;
+import java.util.*;
+
+class MinRotatedArray {
+ public static int findMin(int[] nums) {
+ int s = 0;
+ int e = nums.length - 1;
+ int min = Integer.MAX_VALUE;
+ while (s < e) {
+ int mid = (s + e) / 2;
+ if (nums[mid - 1] > nums[mid]) {
+ return nums[mid];
+ }
+ if (nums[s] < nums[mid] && nums[e] < nums[mid])
+ s = mid + 1;
+ else {
+ e = mid - 1;
+ }
+ }
+ return min;
+ }
+
+ public static void main(String[] args) {
+ int[] nums = {3, 4, 5, 1, 2};
+ System.out.println(findMin(nums));
+ }
+}
diff --git a/Palindrome.java b/Palindrome.java
new file mode 100644
index 0000000..2c1ca47
--- /dev/null
+++ b/Palindrome.java
@@ -0,0 +1,30 @@
+import java.lang.*;
+import java.util.*;
+
+class Palindrome {
+ public static boolean isPalindrome(String s) {
+ s = s.toLowerCase();
+ char[] nonAlpha = s.toCharArray();
+ ArrayList<Character> alpha = new ArrayList<Character>();
+ for (char c : nonAlpha) {
+ if (Character.isLetter(c))
+ alpha.add(c);
+ }
+
+ int i = 0;
+ int j = alpha.size() - 1;
+ while (i < j) {
+ if (alpha.get(i) != alpha.get(j))
+ return false;
+ i++;
+ j--;
+ }
+
+ return true;
+ }
+
+ public static void main(String[] args) {
+ String s = "A man, a plan, a canal: Panama";
+ System.out.println(isPalindrome(s));
+ }
+}
diff --git a/Parentheses.java b/Parentheses.java
new file mode 100644
index 0000000..b1a1b82
--- /dev/null
+++ b/Parentheses.java
@@ -0,0 +1,26 @@
+import java.lang.*;
+import java.util.*;
+
+class Parentheses {
+ public static boolean isValid(String s) {
+ HashMap<Character, Character> map = new HashMap<Character, Character>();
+ map.put(')','(');
+ map.put(']','[');
+ map.put('}','{');
+ Stack<Character> stack = new Stack<Character>();
+ char[] arr = s.toCharArray();
+ stack.push(arr[0]);
+ for (int i = 1; i < arr.length; i++) {
+ if (arr[i] == '(' || arr[i] == '[' || arr[i] == '{')
+ stack.push(arr[i]);
+ else if (map.get(arr[i]) == stack.peek())
+ stack.pop();
+ }
+ return stack.isEmpty();
+ }
+
+ public static void main(String[] args) {
+ String s = ")(";
+ System.out.println(isValid(s));
+ }
+}
diff --git a/ProductExceptSelf.java b/ProductExceptSelf.java
new file mode 100644
index 0000000..3b56f11
--- /dev/null
+++ b/ProductExceptSelf.java
@@ -0,0 +1,31 @@
+import java.lang.*;
+import java.util.*;
+
+class ProductExceptSelf {
+ public static int[] product(int[] nums) {
+ int[] left = new int[nums.length];
+ int[] right = new int[nums.length];
+ left[0] = 1;
+ right[nums.length - 1] = 1;
+
+ int s = 1;
+ int e = nums.length - 2;
+ while (s <= nums.length && e >= 0) {
+ left[s] = left[s - 1] * nums[s - 1];
+ right[e] = right[e + 1] * nums[e + 1];
+ s++;
+ e--;
+ }
+
+ int[] res = new int[nums.length];
+ for (int i = 0; i < nums.length; i++)
+ res[i] = left[i] * right[i];
+
+ return res;
+ }
+
+ public static void main(String[] args) {
+ int[] nums = {-1, 1, 0, -3, 3};
+ System.out.println(Arrays.toString(product(nums)));
+ }
+}
diff --git a/RemoveNthNode.java b/RemoveNthNode.java
new file mode 100644
index 0000000..bdcde30
--- /dev/null
+++ b/RemoveNthNode.java
@@ -0,0 +1,37 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class RemoveNthNode {
+ public static ListNode removeNthFromEnd(ListNode head, int n) {
+ if (head.next == null && n == 1)
+ return head.next;
+
+ ListNode prev = head;
+ ListNode end = head;
+ while (n > 0 && end.next != null) {
+ end = end.next;
+ n--;
+ }
+ while (end.next != null) {
+ prev = prev.next;
+ end = end.next;
+ }
+ prev.next = prev.next.next;
+ return head;
+ }
+
+ public static void main(String[] args) {
+ ListNode fourth = new ListNode(5, null);
+ ListNode third = new ListNode(4, fourth);
+ ListNode second = new ListNode(3, third);
+ ListNode first = new ListNode(2, second);
+ ListNode head = new ListNode(1, first);
+
+ ListNode curr = removeNthFromEnd(head, 1);
+ while (curr != null) {
+ System.out.println(curr.val);
+ curr = curr.next;
+ }
+ }
+}
diff --git a/ReverseList.java b/ReverseList.java
new file mode 100644
index 0000000..96e09a2
--- /dev/null
+++ b/ReverseList.java
@@ -0,0 +1,31 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class ReverseList {
+ public static ListNode reverseList(ListNode head) {
+ ListNode prev = null;
+ ListNode node = head;
+ while (node != null) {
+ ListNode tmp = node.next;
+ node.next = prev;
+ prev = node;
+ node = tmp;
+ }
+ return prev;
+ }
+
+ public static void main(String[] args) {
+ ListNode fourth = new ListNode(5, null);
+ ListNode third = new ListNode(4, fourth);
+ ListNode second = new ListNode(3, third);
+ ListNode first = new ListNode(2, second);
+ ListNode head = new ListNode(1, first);
+
+ ListNode curr = reverseList(head);
+ while (curr != null) {
+ System.out.println(curr.val);
+ curr = curr.next;
+ }
+ }
+}
diff --git a/Stock.java b/Stock.java
new file mode 100644
index 0000000..7a7915b
--- /dev/null
+++ b/Stock.java
@@ -0,0 +1,25 @@
+import java.lang.*;
+import java.util.*;
+
+class Stock {
+ public static int maxProfit(int[] prices) {
+ int s = 0;
+ int e = prices.length - 1;
+ int low = Integer.MAX_VALUE;
+ int high = 0;
+ while (s < e) {
+ if (prices[s] < low)
+ low = prices[s];
+ if (prices[e] > high)
+ high = prices[e];
+ s++;
+ e--;
+ }
+ return high - low > 0 ? high - low : 0;
+ }
+
+ public static void main(String[] args) {
+ int[] prices = {7, 1, 5, 3, 6, 4};
+ System.out.println(maxProfit(prices));
+ }
+}
diff --git a/SumTwoIntegers.java b/SumTwoIntegers.java
new file mode 100644
index 0000000..acb2590
--- /dev/null
+++ b/SumTwoIntegers.java
@@ -0,0 +1,30 @@
+import java.lang.*;
+import java.util.*;
+
+class SumTwoIntegers {
+ public static int getSum(int a, int b) {
+ int bitmask = 0b1;
+ int carry = 0b0;
+ int sum = 0;
+
+ while (bitmask != 0) {
+ int i = a & bitmask;
+ int j = b & bitmask;
+
+ sum |= (i ^ j) ^ carry;
+ carry = (i & j) | ((i | j) & carry);
+
+ bitmask <<= 1;
+ carry <<= 1;
+ }
+ return sum;
+ }
+
+ public static void main(String[] args) {
+ int a = 12;
+ int b = 32;
+ int ans = getSum(a, b);
+ System.out.println(ans);
+ System.out.println(Integer.toBinaryString(ans));
+ }
+}
diff --git a/TwoSum.java b/TwoSum.java
new file mode 100644
index 0000000..b285c60
--- /dev/null
+++ b/TwoSum.java
@@ -0,0 +1,20 @@
+import java.lang.*;
+import java.util.*;
+
+class TwoSum {
+ public static int[] twoSum(int[] nums, int target) {
+ HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
+ for (int i = 0; i < nums.length; i++) {
+ if (map.containsKey(target - nums[i]))
+ return new int[] {map.get(target - nums[i]), i};
+ map.put(nums[i], i);
+ }
+ return new int[] {-1, -1};
+ }
+
+ public static void main(String[] args) {
+ int[] nums = {2, 7, 11, 15};
+ int target = 9;
+ System.out.println(Arrays.toString(twoSum(nums, target)));
+ }
+}
diff --git a/node/GraphNode.class b/node/GraphNode.class
new file mode 100644
index 0000000..ae63fe4
--- /dev/null
+++ b/node/GraphNode.class
Binary files differ
diff --git a/node/GraphNode.java b/node/GraphNode.java
new file mode 100644
index 0000000..db15ebb
--- /dev/null
+++ b/node/GraphNode.java
@@ -0,0 +1,21 @@
+package node;
+
+import java.lang.*;
+import java.util.*;
+
+public class GraphNode {
+ public int val;
+ public ArrayList<GraphNode> neighbors;
+ public GraphNode() {
+ val = 0;
+ neighbors = new ArrayList<GraphNode>();
+ }
+ public GraphNode(int val) {
+ this.val = val;
+ neighbors = new ArrayList<GraphNode>();
+ }
+ public GraphNode(int val, ArrayList<GraphNode> neighbors) {
+ this.val = val;
+ this.neighbors = neighbors;
+ }
+}
diff --git a/node/ListNode.class b/node/ListNode.class
new file mode 100644
index 0000000..a0f839b
--- /dev/null
+++ b/node/ListNode.class
Binary files differ
diff --git a/node/ListNode.java b/node/ListNode.java
new file mode 100644
index 0000000..6b345ec
--- /dev/null
+++ b/node/ListNode.java
@@ -0,0 +1,9 @@
+package node;
+
+public class ListNode {
+ public int val;
+ public ListNode next;
+ public ListNode() {}
+ public ListNode(int val) { this.val = val;}
+ public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-18 18:22:22 +0000