shailrshah
/ WordSearch.java
Created
November 6, 2017 04:17
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public boolean exist(char[][] board, String word) { | |
| for(int i = 0; i < board.length; i++) | |
| for(int j = 0; j < board[0].length; j++) | |
| if(existHelper(board, word, 0, i, j)) | |
| return true; | |
| return false; | |
| } | |
| private boolean existHelper(char[][] board, String word, int pos, int i, int j) { |
shailrshah
/ IsAlmostPalindrome.java
Last active
November 6, 2017 02:28
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public boolean validPalindrome(String s) { | |
| int i = 0, j = s.length()-1; | |
| while(i < j) | |
| if(s.charAt(i) == s.charAt(j)) { i++; j--; } | |
| else return isPalindrome(s, i, j-1) || isPalindrome(s, i+1, j); | |
| return true; | |
| } | |
| private boolean isPalindrome(String s, int i, int j) { | |
| while(i < j) |
shailrshah
/ IsOneEditDistance.java
Created
November 6, 2017 01:18
Given two strings S and T, determine if they are both one edit distance apart.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public boolean isOneEditDistance(String s, String t) { | |
| String s1 = s.length() < t.length() ? s : t; | |
| String s2 = s.length() < t.length() ? t : s; // s2 is the longer string (if unequal) | |
| int n1 = s1.length(); | |
| int n2 = s2.length(); | |
| int diffLength = Math.abs(n1 - n2); | |
| if(diffLength > 1 || s.equals(t)) // strings can't be exactly the same | |
| return false; | |
| boolean tryReplace = (diffLength == 0); |
shailrshah
/ CompressString.java
Last active
November 6, 2017 00:20
Return a string's Run length encoding if that's shorter than the string length.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| private static String compressString(String s) { | |
| int n = s.length(); | |
| StringBuilder sb = new StringBuilder(); | |
| for(int i = 0; i < n; i++) { | |
| char ch = s.charAt(i); | |
| int count = 1; | |
| while((i+1) < n && ch == s.charAt(i+1)) { | |
| count++; |
shailrshah
/ IsPalindromePermute.java
Created
November 5, 2017 23:23
Given a string, check if it is a permutation of a palindrome
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| private static boolean isPalindromePermute(String s) { | |
| int checker = 0; | |
| for(char ch : s.toCharArray()) { | |
| int n = getIntVal(ch); | |
| if(n >= 0 && n < 26) | |
| checker ^= (1<<n); | |
| } | |
| return getNumberOfSetBits(checker) < 2; |
shailrshah
/ UniquePathsGrid.java
Last active
November 13, 2017 23:11
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* m = 5, n = 4 | |
| 1 1 1 1 | |
| 1 2 3 4 | |
| 1 3 6 10 | |
| 1 4 10 20 | |
| 1 5 15 35 | |
| */ | |
| public int uniquePaths(int m, int n) { | |
| int[][] paths = new int[m][n]; |
shailrshah
/ ConnectRight.java
Created
November 5, 2017 19:54
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public void connect(TreeLinkNode root) { | |
| if(root == null) | |
| return; | |
| if(root.left!=null) { | |
| root.left.next = root.right; | |
| if(root.next != null) | |
| root.right.next = root.next.left; | |
| } |
shailrshah
/ RemoveDuplicates.java
Created
November 5, 2017 19:05
Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public int removeDuplicates(int[] nums) { | |
| int n = nums.length; | |
| if(n < 2) | |
| return n; | |
| int toInsert = 1; | |
| for(int i = 1; i < n; i++) | |
| if(nums[i] != nums[i-1]) |
shailrshah
/ MergeKLinkedLists.java
Created
November 5, 2017 17:02
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public ListNode mergeKLists(ListNode[] lists) { | |
| if(lists == null || lists.length == 0) return null; | |
| PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (node1, node2)->node1.val-node2.val); | |
| // Initialize a linked list that will be returned at the end. | |
| ListNode head = new ListNode(0); | |
| ListNode help = head; | |
| // Add the heads of each linked list in the lists[] array to queue. They'll be in sorted order. |
shailrshah
/ DutchFlag.java
Last active
November 5, 2017 18:40
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* Red = 0, White = 1, Blue = 2 | RWRBBRWWR | |
| i = j = 0, k = 8 | |
| j = R => i = j = 1 | |
| j = W => j = 2 | |
| j = R => RRWBBRWWR, i = 2, j = 3 | |
| j = B => RRWRBRWWB, i = 2, j = 3, k = 7 | |
| j = R => RRRWBRWWB, i = 3, j = 4, k = 7 | |
| j = B =>RRRWWRWBB, i = 3, j = 4, k = 6 | |
| j = W => j = 5 | |
| j = R => RRRRWWWBB, i = 3, j = 6, k = 6 |