From 6522012065712fb0ece31bff9ff10b38a83b10e1 Mon Sep 17 00:00:00 2001 From: Michael Hunteman Date: Thu, 22 Sep 2022 10:14:04 -0500 Subject: Initial commit --- Anagram.java | 27 ++++++++++++++++ CloneGraph.java | 39 +++++++++++++++++++++++ CourseSchedule.java | 60 +++++++++++++++++++++++++++++++++++ ListCycle.java | 32 +++++++++++++++++++ LongestPalindrome.java | 55 ++++++++++++++++++++++++++++++++ LongestSubstringWithoutRepeat.java | 27 ++++++++++++++++ MaxSubArray.java | 19 ++++++++++++ MergeLists.java | 62 +++++++++++++++++++++++++++++++++++++ MinRotatedArray.java | 27 ++++++++++++++++ Palindrome.java | 30 ++++++++++++++++++ Parentheses.java | 26 ++++++++++++++++ ProductExceptSelf.java | 31 +++++++++++++++++++ RemoveNthNode.java | 37 ++++++++++++++++++++++ ReverseList.java | 31 +++++++++++++++++++ Stock.java | 25 +++++++++++++++ SumTwoIntegers.java | 30 ++++++++++++++++++ TwoSum.java | 20 ++++++++++++ node/GraphNode.class | Bin 0 -> 624 bytes node/GraphNode.java | 21 +++++++++++++ node/ListNode.class | Bin 0 -> 396 bytes node/ListNode.java | 9 ++++++ 21 files changed, 608 insertions(+) create mode 100644 Anagram.java create mode 100644 CloneGraph.java create mode 100644 CourseSchedule.java create mode 100644 ListCycle.java create mode 100644 LongestPalindrome.java create mode 100644 LongestSubstringWithoutRepeat.java create mode 100644 MaxSubArray.java create mode 100644 MergeLists.java create mode 100644 MinRotatedArray.java create mode 100644 Palindrome.java create mode 100644 Parentheses.java create mode 100644 ProductExceptSelf.java create mode 100644 RemoveNthNode.java create mode 100644 ReverseList.java create mode 100644 Stock.java create mode 100644 SumTwoIntegers.java create mode 100644 TwoSum.java create mode 100644 node/GraphNode.class create mode 100644 node/GraphNode.java create mode 100644 node/ListNode.class create mode 100644 node/ListNode.java 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 stack = new Stack(); + ArrayList visited = new ArrayList(); + 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 map = new HashMap(); + 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(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 stack = new Stack(); + ArrayList visited = new ArrayList(); + 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 occur = new ArrayList(); + 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 alpha = new ArrayList(); + 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 map = new HashMap(); + map.put(')','('); + map.put(']','['); + map.put('}','{'); + Stack stack = new Stack(); + 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 map = new HashMap(); + 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 Binary files /dev/null and b/node/GraphNode.class 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 neighbors; + public GraphNode() { + val = 0; + neighbors = new ArrayList(); + } + public GraphNode(int val) { + this.val = val; + neighbors = new ArrayList(); + } + public GraphNode(int val, ArrayList neighbors) { + this.val = val; + this.neighbors = neighbors; + } +} diff --git a/node/ListNode.class b/node/ListNode.class new file mode 100644 index 0000000..a0f839b Binary files /dev/null and b/node/ListNode.class 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; } +} -- cgit v1.2.3