Added 2 solutions & refactored 4 solutions

varunu28 · varunu28 · commit bbcb43a76879 · 2019-05-19T11:07:46.000-07:00
diff --git a/Easy/Implement strStr.java b/Easy/Implement strStr.java
@@ -1,5 +1,16 @@
 class Solution {
     public int strStr(String haystack, String needle) {
-        return haystack.indexOf(needle);
+        int start = 0;
+        int end = haystack.length() - needle.length() + 1;
+        
+        while (start < end) {
+            if (haystack.substring(start, start + needle.length()).equals(needle)) {
+                return start;
+            }
+            
+            start++;
+        }
+        
+        return -1;
     }
 }
diff --git a/Easy/Last Stone Weight.java b/Easy/Last Stone Weight.java
@@ -0,0 +1,27 @@
+class Solution {
+    public int lastStoneWeight(int[] stones) {
+        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
+            @Override
+            public int compare(Integer o1, Integer o2) {
+                return o2.compareTo(o1);
+            }
+        });
+
+        for (int stone : stones) {
+            pq.add(stone);
+        }
+
+        while (pq.size() > 1) {
+            int stone1 = pq.poll();
+            int stone2 = pq.poll();
+
+            int resSize = Math.max(stone1, stone2) - Math.min(stone1, stone2);
+
+            if (resSize > 0) {
+                pq.add(resSize);
+            }
+        }
+
+        return pq.size() == 1 ? pq.poll() : 0;
+    }
+}
diff --git a/Easy/Remove All Adjacent Duplicates In String.java b/Easy/Remove All Adjacent Duplicates In String.java
@@ -0,0 +1,17 @@
+class Solution {
+    public String removeDuplicates(String S) {
+        StringBuilder sb = new StringBuilder();
+        char[] chars = S.toCharArray();
+
+        for (char c : chars) {
+            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
+                sb.deleteCharAt(sb.length() - 1);
+            }
+            else {
+                sb.append(c);
+            }
+        }
+
+        return sb.toString();
+    }
+}
diff --git a/Medium/Integer To Roman.java b/Medium/Integer To Roman.java
@@ -1,27 +1,17 @@
 class Solution {
     public String intToRoman(int num) {
-        List<Integer> keys = Arrays.asList(1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000);
-        List<String> values = Arrays.asList("I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M");
-        Map<Integer, String> map = new HashMap<>();
-        for (int i=0; i<keys.size(); i++) {
-            map.put(keys.get(i), values.get(i));
-        }
-        
+        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
+        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
+    
         StringBuilder sb = new StringBuilder();
-
-        for (int i=keys.size()-1; i>=0; i--) {
-            if (num / keys.get(i) > 0) {
-                int n = num / keys.get(i);
-                num %= keys.get(i);
-
-                sb.append(String.join("", Collections.nCopies(n, map.get(keys.get(i)))));
-            }
-
-            if (num == 0) {
-                break;
+        
+        for (int i = 0; i < values.length; i++) {
+            while (num >= values[i]) {
+                num -= values[i];
+                sb.append(strs[i]);
             }
         }
-
+        
         return sb.toString();
     }
 }
diff --git a/Medium/Longest Substring Without Repeating Characters.java b/Medium/Longest Substring Without Repeating Characters.java
@@ -1,19 +1,21 @@
 class Solution {
     public int lengthOfLongestSubstring(String s) {
-        int maxL = 0;
-        Set<Character> arr = new HashSet<>();
-        int j = 0;
-        int i = 0;
-        while (i<s.length()) {
-            if (!arr.contains(s.charAt(i))) {
-                arr.add(s.charAt(i++));
-                maxL = Math.max(maxL, arr.size());
+        int maxLen = 0;
+        int n = s.length();
+        int start = 0;
+        int end = 0;
+        Set<Character> set = new HashSet<>();
+        
+        while (end < n) {
+            if (!set.contains(s.charAt(end))) {
+                set.add(s.charAt(end++));
+                maxLen = Math.max(maxLen, set.size());
             }
             else {
-                arr.remove(s.charAt(j++));
+                set.remove(s.charAt(start++));
             }
         }
         
-        return maxL;
+        return maxLen;
     }
 }
diff --git a/Medium/String to Integer(atoi).java b/Medium/String to Integer(atoi).java
@@ -3,51 +3,32 @@ public int myAtoi(String str) {
         if (str.length() == 0) {
             return 0;
         }
-
-        StringBuilder sb = new StringBuilder();
+        
         int idx = 0;
         int n = str.length();
-
-        // Removing initial white spaces
+        int sign = 1;
         while (idx < n && str.charAt(idx) == ' ') {
             idx++;
         }
-
-        int sign = 1;
-        // Updating sign value if there is a '+' or '-' present
-        if (idx < n) {
-            if (str.charAt(idx) == '-') {
-                sign = -1;
-                idx++;
-            }
-            else if (str.charAt(idx) == '+') {
-                idx++;
-            }
+        
+        if (idx < n && (str.charAt(idx) == '-' || str.charAt(idx) == '+')) {
+            sign = str.charAt(idx) == '-' ? -1 : 1;
+            idx++;
         }
-
-        // Integer limits
-        int positiveLimit = Integer.MAX_VALUE;
-        int negativeLimit = Integer.MIN_VALUE;
-
-        // Adding values to StringBuilder until a digit is found
-        // Keeping a check for bounds
+        
+        long num = 0;
         while (idx < n && Character.isDigit(str.charAt(idx))) {
-            sb.append(str.charAt(idx));
-            if (sign == 1 && Long.parseLong(sb.toString()) > positiveLimit) {
-                return Integer.MAX_VALUE;
+            num = num * 10 + Character.getNumericValue(str.charAt(idx++));
+            
+            if ((sign == 1 && num > Integer.MAX_VALUE) || (-num < Integer.MIN_VALUE)) {
+                return getOverflowValue(sign);
             }
-
-            if (sign == -1 && Long.parseLong(sb.toString()) * sign < negativeLimit) {
-                return Integer.MIN_VALUE;
-            }
-
-            idx++;
         }
-
-        if (sb.length() == 0) {
-            return 0;
-        }
-
-        return (int) (Long.parseLong(sb.toString()) * sign);
+        
+        return sign * (int) num;
+    }
+    
+    private int getOverflowValue(int sign) {
+        return sign == -1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
     }
 }
