2020 May 30 Problems
57 views
Skip to first unread message
Tarini Pattanaik
May 30, 2020, 11:16:50 AM5/30/20
to leetcod...@googlegroups.com
150: Evaluate Reverse polish notation
Runtime: 105 ms, faster than 5.05% of Java online submissions for Evaluate Reverse Polish Notation.
public int evalRPN(String[] tokens) {
if (tokens.length == 0)
return 0;
Stack<Integer> stack = new Stack<Integer>();
int res = Integer.valueOf(tokens[0]);
for (int i = 0; i < tokens.length; i++) {
if (!isOperator(tokens[i])) {
stack.push(Integer.valueOf(tokens[i]));
} else {
if (stack.size() >= 2) {
int num1 = stack.pop();
int num2 = stack.pop();
res = evaluate(num2, num1, tokens[i]);
stack.push(Integer.valueOf(res));
System.out.println(" num1 = " + num1 + " num2 = " + num2 + " result = " + res);
}
}
}
return res;
}
int evaluate(int operand1, int operand2, String operator) {
if ("+".equals(operator)) {
return operand1 + operand2;
} else if ("-".equals(operator)) {
return operand1 - operand2;
} else if ("*".equals(operator)) {
return operand1 * operand2;
} else if ("/".equals(operator)) {
return operand1 / operand2;
}
return 0;
}
boolean isOperator(String op) {
Set<String> set = new HashSet<String>();
set.add("+");
set.add("-");
set.add("*");
set.add("/");
return set.contains(op);
}
if (tokens.length == 0)
return 0;
Stack<Integer> stack = new Stack<Integer>();
int res = Integer.valueOf(tokens[0]);
for (int i = 0; i < tokens.length; i++) {
if (!isOperator(tokens[i])) {
stack.push(Integer.valueOf(tokens[i]));
} else {
if (stack.size() >= 2) {
int num1 = stack.pop();
int num2 = stack.pop();
res = evaluate(num2, num1, tokens[i]);
stack.push(Integer.valueOf(res));
System.out.println(" num1 = " + num1 + " num2 = " + num2 + " result = " + res);
}
}
}
return res;
}
int evaluate(int operand1, int operand2, String operator) {
if ("+".equals(operator)) {
return operand1 + operand2;
} else if ("-".equals(operator)) {
return operand1 - operand2;
} else if ("*".equals(operator)) {
return operand1 * operand2;
} else if ("/".equals(operator)) {
return operand1 / operand2;
}
return 0;
}
boolean isOperator(String op) {
Set<String> set = new HashSet<String>();
set.add("+");
set.add("-");
set.add("*");
set.add("/");
return set.contains(op);
}
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/9fcd8fd3-83dd-4b71-8a62-bfa3f79565c8%40googlegroups.com.
mohan kumar
May 30, 2020, 5:00:15 PM5/30/20
to leetcod...@googlegroups.com
| 152 | 31.3% | Medium |
Same as maxSumSubArray.. just that we need to take both min and max as there can be negatives.
public int maxProduct(int[] A) {
if (A.length == 0) {
return 0;
}
int maxherepre = A[0];
int minherepre = A[0];
int maxsofar = A[0];
int maxhere, minhere;
for (int i = 1; i < A.length; i++) {
maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
maxsofar = Math.max(maxhere, maxsofar);
maxherepre = maxhere;
minherepre = minhere;
}
return maxsofar;
}
}
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CANQx_AQ1CGanjV_N6CAzkcisXk-SHi1nc-gtCKNOo%2B9HtDv-Eg%40mail.gmail.com.
Abhishek Kaukuntla
May 31, 2020, 1:17:08 AM5/31/20
to leetcode-meetup
| 150 | Evaluate Reverse Polish Notation | 35.6% | Medium |
Runtime: 4 ms, faster than 92.73% of Java online submissions for Evaluate Reverse Polish Notation.
Memory Usage: 39.4 MB, less than 8.00% of Java online submissions for Evaluate Reverse Polish Notation.
Time complexity: O(N) where N is the length of the tokens array
Space complexity: O(N)
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
Set<String> operators = operators();
for (int i=0; i<tokens.length; i++) {
String token = tokens[i];
if (operators.contains(token)) { // it's an operator, perform the operation on the previous 2 integers
if (stack.size() >= 2) {
// Pop 2 numbers from stack and perform the operation
Integer num1 = stack.pop();
Integer num2 = stack.pop();
Integer result;
if (token.equals("+")) {
result = num2 + num1;
} else if (token.equals("-")) {
result = num2 - num1;
} else if (token.equals("/")) {
result = num2/num1;
} else {
result = num2 * num1;
}
stack.push(result);
}
} else { // it is an integer, push it on to the stack
stack.push(Integer.parseInt(token));
}
}
return stack.isEmpty() ? -1 : stack.pop();
}
private Set<String> operators() {
Set<String> operators = new HashSet<String>();
operators.add("+");
operators.add("-");
operators.add("*");
operators.add("/");
return operators;
Rudy Talukder
May 31, 2020, 2:43:35 AM5/31/20
to leetcod...@googlegroups.com
Runtime: 44 ms, faster than 79.72% of Python3 online submissions for Roman to Integer.
Memory Usage: 13.6 MB, less than 5.38% of Python3 online submissions for Roman to Integer.
O(N) of time = N
O(N) of space = 1
def romanToInt(self, s: str) -> int:
res=0
i=0
while (i<len(s)):
if (s[i]=='C'):
if ((i+1)<len(s)):
if(s[i+1]=='M'):
res+=900
i+=2
elif(s[i+1]=="D"):
res+=400
i+=2
else:
res+=100
i+=1
else:
res+=100
i+=1
elif (s[i]=='X'):
if ((i+1)<len(s)):
if(s[i+1]=='C'):
res+=90
i+=2
elif(s[i+1]=='L'):
res+=40
i+=2
else:
res+=10
i+=1
else:
res+=10
i+=1
elif (s[i]=='I'):
if ((i+1)<len(s)):
if(s[i+1]=='X'):
res+=9
i+=2
elif(s[i+1]=='V'):
res+=4
i+=2
else:
res+=1
i+=1
else:
res+=1
i+=1
elif (s[i] == 'M'):
res+=1000
i+=1
elif (s[i]=='D'):
res+=500
i+=1
elif (s[i] == 'L'):
res+=50
i+=1
elif (s[i] == 'V'):
res+=5
i+=1
return res
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAFdrHHVm8x0wPC-DvhPYq%3DmvmNCKJanK9rK83DWN8su1QtQrwQ%40mail.gmail.com.
Message has been deleted
Abhishek Kaukuntla
May 31, 2020, 11:44:34 PM5/31/20
to leetcode-meetup
| 13 | Roman to Integer | 55.2% | Easy |
Runtime: 6 ms, faster than 33.61% of Java online submissions for Roman to Integer.
Memory Usage: 39.6 MB, less than 6.09% of Java online submissions for Roman to Integer.
Time complexity: O(N) where N is the length of Roman string value
Space complexity: O(1) because the storage used is always constant regardless of the input size
*/
class Solution {
public int romanToInt(String s) {
Map<String, Integer> roman = new HashMap<String, Integer>();
roman.put("", 0);
roman.put("I", 1);
roman.put("V", 5);
roman.put("X", 10);
roman.put("L", 50);
roman.put("C", 100);
roman.put("D", 500);
roman.put("M", 1000);
String prevCh = "";
int sum = 0;
for (int i=1; i<=s.length(); i++) {
String ch = s.substring(i-1, i);
if (roman.get(ch) > roman.get(prevCh)) {
sum = (sum - roman.get(prevCh)) + (roman.get(ch) - roman.get(prevCh));
} else {
sum += roman.get(ch);
}
prevCh = ch;
}
return sum;
}
}
On Friday, May 29, 2020 at 11:08:05 PM UTC-7, Daryl Wang wrote:
deepika panda
Jun 1, 2020, 3:12:03 PM6/1/20
to leetcode-meetup
150. Evaluate Reverse Polish Notation:
Runtime: 4 ms, faster than 92.67% of Java online submissions for Evaluate Reverse Polish Notation.
Memory Usage: 39.8 MB, less than 6.00% of Java online submissions for Evaluate Reverse Polish Notation.
Solution:
class Solution {
public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0)
return 0;
Set<String> operators = new HashSet<>(Arrays.asList("+","-","*","/"));
Stack<Integer> st = new Stack<>();
for (String s : tokens){
if (operators.contains(s)) {
int op1 = st.pop();
int op2 = st.pop();
int result = 0;
switch (s) {
case "+": result = op1 + op2;
break;
case "-": result = op2 - op1;
break;
case "*": result = op2 * op1;
break;
case "/": result = op2 / op1;
break;
}
st.push(result);
} else {
st.push(Integer.parseInt(s));
}
}
return st.isEmpty() ? 0 : st.pop();
}
}
deepika panda
Jun 2, 2020, 6:12:28 PM6/2/20
to leetcode-meetup
152. Maximum Product Subarray
Runtime: 1 ms, faster than 93.54% of Java online submissions for Maximum Product Subarray.
Memory Usage: 39.9 MB, less than 8.54% of Java online submissions for Maximum Product Subarray.
Solution:
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int min = nums[0];
int max = nums[0];
int maxProduct = nums[0];
for (int i=1; i < nums.length; i++) {
int orig_max = max;
max = Math.max(nums[i], Math.max(max*nums[i], min*nums[i]));
min = Math.min(nums[i], Math.min(min*nums[i], orig_max*nums[i]));
maxProduct = Math.max(maxProduct, max);
}
return maxProduct;
}
}
deepika panda
Jun 2, 2020, 9:16:15 PM6/2/20
to leetcode-meetup
13. Roman to Integer
Runtime: 6 ms, faster than 33.99% of Java online submissions for Roman to Integer.
Memory Usage: 39.5 MB, less than 6.09% of Java online submissions for Roman to Integer.
Solution:
class Solution {
public int romanToInt(String s) {
if (s == null || s.length() == 0)
return -1;
Map<String, Integer> map = new HashMap<>();
map.put("I", 1);
map.put("IV", 4);
map.put("V", 5);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
int result = 0;
char[] chars = s.toCharArray();
for (int i=0; i < chars.length; i++) {
char ch1 = chars[i];
char ch2 = '\0';
if (i+1 < chars.length)
ch2 = chars[i+1];
if (ch1 == 'I' && (ch2 == 'V' || ch2 == 'X')) {
result += map.get(new String(new char[] {ch1, ch2}));
i++;
} else if (ch1 == 'X' && (ch2 == 'L' || ch2 == 'C')) {
result += map.get(new String(new char[] {ch1, ch2}));
i++;
} else if (ch1 == 'C' && (ch2 == 'D' || ch2 == 'M')) {
result += map.get(new String(new char[] {ch1, ch2}));
i++;
} else
result += map.get(new String(new char[] {ch1}));
}
return result;
}
}
R K
Jun 3, 2020, 10:14:22 AM6/3/20
to leetcod...@googlegroups.com
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Roman to Integer.
Memory Usage: 5.9 MB, less than 100.00% of C++ online submissions for Roman to Integer.
class Solution {
public:
int romanToInt(string s) {
int i = 0;
int x = 0;
int c = 0;
int sum = 0;
for(char n:s){
switch(n){
case 'I':
i++;
break;
case 'V':
if(i!=0){
sum += 5-i;
i=0;
}
else{
sum += 5;
}
break;
case 'X':
if(i!=0){
sum += 10-i;
i=0;
}
else{
x++;
}
break;
case 'L':
if(x!=0){
sum += 50-x*10;
x=0;
}
else{
sum += 50;
}
break;
case 'C':
if(x!=0){
sum += 100-x*10;
x=0;
}
else{
c++;
}
break;
case 'D':
if(c!=0){
sum += 500-c*100;
c=0;
}
else{
sum += 500;
}
break;
case 'M':
if(c!=0){
sum += 1000-c*100;
c=0;
}
else{
sum += 1000;
}
break;
default:
break;
}
}
sum += i + x*10 + c*100;
return sum;
}
};
public:
int romanToInt(string s) {
int i = 0;
int x = 0;
int c = 0;
int sum = 0;
for(char n:s){
switch(n){
case 'I':
i++;
break;
case 'V':
if(i!=0){
sum += 5-i;
i=0;
}
else{
sum += 5;
}
break;
case 'X':
if(i!=0){
sum += 10-i;
i=0;
}
else{
x++;
}
break;
case 'L':
if(x!=0){
sum += 50-x*10;
x=0;
}
else{
sum += 50;
}
break;
case 'C':
if(x!=0){
sum += 100-x*10;
x=0;
}
else{
c++;
}
break;
case 'D':
if(c!=0){
sum += 500-c*100;
c=0;
}
else{
sum += 500;
}
break;
case 'M':
if(c!=0){
sum += 1000-c*100;
c=0;
}
else{
sum += 1000;
}
break;
default:
break;
}
}
sum += i + x*10 + c*100;
return sum;
}
};
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/7094a21c-b76c-49dd-b439-756c89a5f35d%40googlegroups.com.
Best Regards
Recep Kuyuk
Daryl Wang
Jun 6, 2020, 12:53:39 PM6/6/20
to leetcode-meetup
| 13 | Roman to Integer | 55.2% | Easy |
The basic case is straightforward; iterate over each character and add its value to the result. The tricky part is in dealing with the exception cases for 4* and 9*. It's possible to hold onto I/X/C and not add them until you see if the next character is one of the 5*/10* characters, but I find the easiest way to deal with this case is to subtract twice the amount. This way you can add each character's value to the result immediately, and not have to worry about special handling for the last character. The only state needed is what the previous character was. Subtracting twice takes care of the fact that one of the I/X/C shouldn't have counted and was there to indicate the general subtraction rule.
O(n) time
O(1) space
class Solution:
def romanToInt(self, s: str) -> int:
result = 0
prev = ""
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
for char in s:
result += values[char]
if (char == "V" or char == "X") and prev == "I":
result -= 2
elif (char == "L" or char == "C") and prev == "X":
result -=20
elif (char == "D" or char == "M") and prev == "C":
result -= 200
prev = char
return result
On Friday, May 29, 2020 at 11:08:05 PM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 6, 2020, 1:00:41 PM6/6/20
to leetcode-meetup
| 152 | Maximum Product Subarray | 31.3% | Medium |
This is similar to the maximum sum subarray problem. The basic idea for that problem is to keep a best sum so far, and iterate through the array. Each number we either add it to the sum so far, or we start over with the number as the new sum so far. At the end we can return the largest running sum we saw while iterating through the array.
The multiplication problem has the same general idea. The catch is dealing with negative numbers; we have to catch the case of two negative numbers multiplying together into a positive. Therefore we keep two running products while iterating through the array; one for the most negative product and one for the most positive product. The rest of the problem is the same as the maximum sum solution.
int maxProduct(int* nums, int numsSize) {
int bestProduct;
int prevPosProduct, prevNegProduct;
bestProduct = nums[0];
prevPosProduct = nums[0];
prevNegProduct = nums[0];
for (int i = 1; i < numsSize; i++) {
int currentValue = nums[i];
int continuedProduct, continuedNegProduct;
if (currentValue > 0) {
continuedProduct = currentValue * prevPosProduct;
continuedNegProduct = currentValue * prevNegProduct;
} else {
continuedProduct = currentValue * prevNegProduct;
continuedNegProduct = currentValue * prevPosProduct;
}
if (continuedProduct > currentValue) {
prevPosProduct = continuedProduct;
} else {
prevPosProduct = currentValue;
}
if (continuedNegProduct < currentValue) {
prevNegProduct = continuedNegProduct;
} else {
prevNegProduct = currentValue;
}
if (prevPosProduct > bestProduct) {
bestProduct = prevPosProduct;
}
}
return bestProduct;
}
On Friday, May 29, 2020 at 11:08:05 PM UTC-7, Daryl Wang wrote:
Daryl Wang
Jun 6, 2020, 1:11:25 PM6/6/20
to leetcode-meetup
| 150 | Evaluate Reverse Polish Notation | 35.6% | Medium |
The reverse Polish version of the calculator problem is a lot simpler to deal with. The fundamental idea is to again create a stack of arguments, but the ordering makes things simpler. Iterate through the expression, adding the numbers to the top of the stack. When any operator is seen, you can just pop off the top two elements of the stack for the operator arguments and do that math operation. Then add that value to the top of the stack, and continue parsing.
At the end the stack will have one element, which is the final answer.
One gotcha here is how division is defined; in the negative case the answer should go to 0. -5 / 2 should return -2 instead of -3; you may need to implement this rounding yourself if the built integer division use floor division instead.
O(n) time
O(n) time
O(n) space
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
def truncdiv(a, b):
# Division function that truncates to 0 instead of rounding to a more negative number when dealing with negative results.
return int(a / b)
args = []
ops = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': truncdiv}
for token in tokens:
if token in ops:
arg2 = args.pop()
arg1 = args.pop()
value = ops[token](arg1, arg2)
args.append(value)
else:
args.append(int(token))
return args[0]
On Friday, May 29, 2020 at 11:08:05 PM UTC-7, Daryl Wang wrote:
Reply all
Reply to author
Forward
0 new messages