Added 2 solutions & modified 2 solutions

varunu28 · varunu28 · commit cadc92310696 · 2020-02-22T15:48:19.000-08:00
diff --git a/Easy/Sort Integers by The Number of 1 Bits.java b/Easy/Sort Integers by The Number of 1 Bits.java
@@ -0,0 +1,22 @@
+class Solution {
+  public int[] sortByBits(int[] arr) {
+    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
+      public int compare(Integer o1, Integer o2) {
+        int c = Integer.bitCount(o1) - Integer.bitCount(o2);
+        if (c != 0) {
+          return c;
+        }
+        return o1 - o2;
+      }
+    });
+    for (int num : arr) {
+      pq.add(num);
+    }
+    int[] ans = new int[arr.length];
+    int idx = 0;
+    while (!pq.isEmpty()) {
+      ans[idx++] = pq.poll();
+    }
+    return ans;
+  }
+}
diff --git a/Medium/Apply Discount Every n Orders.java b/Medium/Apply Discount Every n Orders.java
@@ -0,0 +1,37 @@
+class Cashier {
+  int n;
+  int discount;
+  int currCount;
+  Map<Integer, Integer> priceMap;
+  public Cashier(int n, int discount, int[] products, int[] prices) {
+    this.n = n;
+    this.currCount = 0;
+    this.discount = discount;
+    priceMap = new HashMap<>();
+    for (int i = 0; i < products.length; i++) {
+      priceMap.put(products[i], prices[i]);
+    }
+  }
+
+  public double getBill(int[] product, int[] amount) {
+    currCount++;
+    double totalBill = 0;
+    for (int i = 0; i < product.length; i++) {
+      totalBill += amount[i] * priceMap.get(product[i]);
+    }
+    if (currCount % n == 0) {
+      totalBill -= getDiscount(totalBill);
+    }
+    return totalBill;
+  }
+  
+  private double getDiscount(double totalBill) {
+    return (totalBill * discount) / 100;
+  }
+}
+
+/**
+ * Your Cashier object will be instantiated and called as such:
+ * Cashier obj = new Cashier(n, discount, products, prices);
+ * double param_1 = obj.getBill(product,amount);
+ */
diff --git a/Medium/Remove K Digits.java b/Medium/Remove K Digits.java
@@ -1,35 +1,25 @@
 class Solution {
-    public String removeKdigits(String num, int k) {
-        Stack<Integer> stack = new Stack<>();
-        int idx = 0;
-        int n = num.length();
-        while (idx < n) {
-            while (k > 0 && !stack.isEmpty()) {
-                if (stack.peek() <= Character.getNumericValue(num.charAt(idx))) {
-                    break;
-                }
-                stack.pop();
-                k--;
-            }
-            
-            stack.push(Character.getNumericValue(num.charAt(idx++)));
-        }
-        
-        while (k-- > 0) {
-            stack.pop();
-        }
-        
-        StringBuilder sb = new StringBuilder();
-        while (!stack.isEmpty()) {
-            sb.append(stack.pop());
-        }
-        
-        String ans = sb.reverse().toString();
-        idx = -1;
-        while (idx + 1 < ans.length() && ans.charAt(idx + 1) == '0') {
-            idx++;
-        }
-        
-        return ans.substring(idx + 1).length() == 0 ? "0" : ans.substring(idx + 1);
+  public String removeKdigits(String num, int k) {
+    LinkedList<Character> stack = new LinkedList<>();
+    for (char c : num.toCharArray()) {
+      while (!stack.isEmpty() && k > 0 && stack.peekLast() > c) {
+        stack.removeLast();
+        k--;
+      } 
+      stack.addLast(c);
     }
+    while (k-- > 0) {
+      stack.removeLast();
+    }
+    StringBuilder sb = new StringBuilder();
+    boolean currZero = true;
+    for (char c : stack) {
+      if (currZero && c == '0') {
+        continue;
+      }
+      currZero = false;
+      sb.append(c);
+    }
+    return sb.length() == 0 ? "0" : sb.toString();
+  }
 }
diff --git a/Medium/Sort Colors.java b/Medium/Sort Colors.java
@@ -1,23 +1,25 @@
 class Solution {
-    public void sortColors(int[] nums) {
-        int idx1 = 0;
-        int idx2 = nums.length - 1;
-        int idx = 0;
-        
-        while (idx <= idx2) {
-            if (nums[idx] == 0) {
-                nums[idx] = nums[idx1];
-                nums[idx1] = 0;
-                idx1++;
-            }
-            if (nums[idx] == 2) {
-                nums[idx] = nums[idx2];
-                nums[idx2] = 2;
-                idx2--;
-                idx--;
-            }
-            
-            idx++;
-        }
+  public void sortColors(int[] nums) {
+    int zeroIdx = 0;
+    int curr = 0;
+    int n = nums.length - 1;
+    int twoIdx = n;
+    while (curr <= twoIdx) {
+      if (nums[curr] == 0) {
+        swap(nums, curr++, zeroIdx++);
+      }
+      else if (nums[curr] == 2) {
+        swap(nums, curr, twoIdx--);
+      }
+      else {
+        curr++;
+      }
     }
+  }
+  
+  private void swap(int[] nums, int idx1, int idx2) {
+    int temp = nums[idx1];
+    nums[idx1] = nums[idx2];
+    nums[idx2] = temp;
+  }
 }
