niki
BAN USERFirst solution is using stack:
public ListNode reverseWithStack(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ListNode reversed = null;
ListNode result = null;
while (!stack.isEmpty()) {
ListNode current = new ListNode(stack.pop());
if (reversed == null) {
reversed = current;
result = reversed;
} else {
reversed.next = current;
reversed = reversed.next;
}
}
return result;
}
The second solution doesn't use stack:
public ListNode reverseWithoutStack(ListNode listNode) {
ListNode result = null;
while (listNode != null) {
ListNode curr = new ListNode(listNode.val);
if (result == null) {
result = curr;
} else {
curr.next = result;
result = curr;
}
listNode = listNode.next;
}
return result;
}
My solution will not let you to have duplicates:
private HashMap<Integer, Integer> cache = new HashMap<>();
public boolean isTripletExist(int sum, List<Integer> a) {
int n = a.size();
Collections.sort(a);
if (a.isEmpty()) {
return false;
}
putIntoCache(a.get(0));
for (int i = 0; i < n; i++) {
int a1 = a.get(i);
for (int j = i + 1; j < n; j++) {
int a2 = a.get(j);
int s = sum - (a1 + a2);
if (cache.containsKey(s)) {
if (s == a1 || s == a2) {
if (cache.get(s) > 1) {
return true;
}
} else {
return true;
}
}
putIntoCache(a2);
}
}
return false;
}
private void putIntoCache(int key) {
int newVal = (cache.containsKey(key) ? cache.get(key) + 1 : 1);
cache.put(key, newVal);
}
public int maxNumber(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
return rec(s);
}
private int rec(String s) {
int n = s.length();
if (n == 1) {
return s.charAt(0) - '0';
}
int current = s.charAt(n - 1) - '0';
int prev = rec(s.substring(0, n - 1));
int sum = current + prev;
int product = current * prev;
return Math.max(sum, product);
}
My solution in Java:
- niki July 22, 2017