323 .idea/workspace.xml
View file
81 src/differentWaysToAddParens/Solution.java
View file
@@ -0,0 +1,81 @@
package differentWaysToAddParens;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

//Given a string of numbers and operators,
// return all possible results from computing all the different possible ways to group numbers and operators.
// The valid operators are +, - and *.
//
//
// Example 1
// Input: "2-1-1".
//
// ((2-1)-1) = 0
// (2-(1-1)) = 2
// Output: [0, 2]
//
//
// Example 2
// Input: "2*3-4*5"
//
// (2*(3-(4*5))) = -34
// ((2*3)-(4*5)) = -14
// ((2*(3-4))*5) = -10
// (2*((3-4)*5)) = -10
// (((2*3)-4)*5) = 10
// Output: [-34, -14, -10, -10, 10]
public class Solution {
public static void main(String[] args) {
String input = "2*3+4*5";
for (int result : new Solution().diffWaysToCompute(input)) {
System.out.println(result);
}
}

// the idea is to split the problem to left/right half at each operator
// and shrink it by combining all results from left part and right part
// when the input is a valid number, we terminate
// this way you don't need to worry about the -
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ret = new LinkedList<>();
// note we don't really need to build the expressions
// just create all possible combinations and compute the shit in different orders
for (int i = 0; i < input.length(); i++) {
switch (input.charAt(i)) {
case '+':
case '-':
case '*':
List<Integer> lefts = diffWaysToCompute(input.substring(0, i));
List<Integer> rights = diffWaysToCompute(input.substring(i + 1));
for (int left : lefts) {
for (int right : rights) {
ret.add(calculate(left, right, input.charAt(i)));
}
}
break;
default:
break;
}
}
if (ret.size() == 0) {
ret.add(Integer.parseInt(input));
}
return ret;
}

int calculate(int left, int right, char op) {
switch (op) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
default:
return 0;
}
}
}
36 src/search2DMatrixII/Solution.java
View file
@@ -0,0 +1,36 @@
package search2DMatrixII;

//Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
//
// Integers in each row are sorted in ascending from left to right.
// Integers in each column are sorted in ascending from top to bottom.
// For example,
//
// Consider the following matrix:
//
// [
// [1, 4, 7, 11, 15],
// [2, 5, 8, 12, 19],
// [3, 6, 9, 16, 22],
// [10, 13, 14, 17, 24],
// [18, 21, 23, 26, 30]
// ]
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {

int height = matrix.length;
int width = matrix[0].length;
int x = 0, y = width - 1;
while(matrix[x][y] != target) {
if(matrix[x][y] < target) {
x++;
} else {
y--;
}
if(x >= height || y < 0) {
return false;
}
}
return true;
}
}
63 src/slidingWindowMax/Solution.java
View file
@@ -0,0 +1,63 @@
package slidingWindowMax;

import java.util.LinkedList;
import java.util.Queue;

//Given an array nums, there is a sliding window of size k which is moving from the very
// left of the array to the very right. You can only see the k numbers in the window.
// Each time the sliding window moves right by one position.
//
// For example,
// Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
//
// Window position Max
// --------------- -----
// [1 3 -1] -3 5 3 6 7 3
// 1 [3 -1 -3] 5 3 6 7 3
// 1 3 [-1 -3 5] 3 6 7 5
// 1 3 -1 [-3 5 3] 6 7 5
// 1 3 -1 -3 [5 3 6] 7 6
// 1 3 -1 -3 5 [3 6 7] 7
// Therefore, return the max sliding window as [3,3,5,5,6,7].
//
// Note:
// You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
public class Solution {
public static void main(String[] args) {
int[] nums = {1, 3, 1, 2, 0, 5};
int k = 3;
for (int i : new Solution().maxSlidingWindow(nums, k)) {
System.out.println(i);
}
}
// the idea is to use a linked list to keep track of INDICES
// the list should not be longer than k,
// we check that by looking at the index we're considering - index of head of the queue
// the list should only contain possible largest number of window of size k
// we ensure this by removing tail of the list if num[tail] is smaller than num[i]
// because tail < i, and since num[i] > num[tail],
// if there's a window that requires a max containing i,
// the max index can't be i because windows containing num[tail] must also contain num[i]
public int[] maxSlidingWindow(int[] nums, int k) {
if (k == 0 || nums.length == 0) {
return new int[0];
}
int[] rst = new int[nums.length - k + 1];
LinkedList<Integer> q = new LinkedList<>();
int curIndex = 0;
for (int i = 0; i < nums.length; i++) {
while(!q.isEmpty() && q.peek() < i - k + 1) {
q.removeFirst();
}
while(!q.isEmpty() && nums[q.getLast()] < nums[i]) {
q.removeLast();
}
q.add(i);
if ((i + 1) >= k) {
rst[curIndex] = nums[q.peek()];
curIndex++;
}
}
return rst;
}
}