[Leetcode] Reverse Nodes in k-Group

25. Reverse Nodes in k-Group QuestionEditorial Solution My Submissions

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

 

I didn’t make it myself.

Looked at this most upvoted solution: https://discuss.leetcode.com/topic/7126/short-but-recursive-java-code-with-comments

Walking through this code step by step helps, recursion is really really powerful, the machine helps you do exactly what you want!

public ListNode reverseKGroup(ListNode head, int k) {

ListNode curr = head;
int count = 0;
while(curr != null && count != k){//find the k+1 node
curr = curr.next;
count++;
}

if(count == k){//if k+1 is found
curr = reverseKGroup(curr, k);//reverse list that has k+1 as head

while(count > 0){
ListNode temp = head.next;
head.next = curr;
curr = head;
head = temp;
count--;
}
head = curr;
}
return head;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well

}

Advertisements

Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

I’m amazed at the recursive solution, so concise:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val >= l2.val){
l2.next = mergeTwoLists(l1, l2.next);
return l2;
} else {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
}

Expression Add Operators

https://leetcode.com/problems/expression-add-operators/

Looked at this awesome post: https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear

Recursion, recursion, recursion. It’s the beauty of computer science. It’s so powerful and could be applied to solve so many problems!

public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
dfs(res, sb, num, 0, target, 0, 0);
return res;

}

private void dfs(List<String> res, StringBuilder sb, String num, int pos, int target, long prev, long multi) {
if(pos == num.length()){
if(target == prev) res.add(sb.toString());
return;
}
for(int i = pos; i < num.length(); i++){
if(num.charAt(pos) == '0' && i != pos) break;
long curr = Long.parseLong(num.substring(pos, i+1));
int len = sb.length();
if(pos == 0){
dfs(res, sb.append(curr), num, i+1, target, curr, curr);
sb.setLength(len);
} else {
dfs(res, sb.append("+").append(curr), num, i+1, target, prev+curr, curr);
sb.setLength(len);

dfs(res, sb.append("-").append(curr), num, i+1, target, prev-curr, -curr);
sb.setLength(len);

dfs(res, sb.append("*").append(curr), num, i+1, target, prev - multi + multi*curr, multi*curr);
sb.setLength(len);
}
}
}

Data Stream as Disjoint Intervals

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

  • I’m thinking to maintain the numbers as a sorted array, but it doesn’t give me quick insertion into the correct place
  • Then I was thinking to use the previous problem Insert Interval to help with this one, but that’s purely cheating and I’m not if that can work either.
  • The moment, I clicked the Tag, it shows Binary Search Tree, I’m impressed!
    • It’s this thought process that values! Don’t click to show Tags too early, think about it, which data structure would you come up to use?
  • Now, my thoughts:
    • try to use the idea from https://fishercoder.com/2016/07/16/count-of-smaller-numbers-after-self/
    • to build a BST, while inserting a new node, check to see if merge is needed, check both the node’s parent and child, let each node’s value be the lower boundary of the interval and define another field which is the array of interval in this node class
    • after trial and error, rewriting it multiple times: discussion with badyu2000@ here: https://discuss.leetcode.com/topic/47084/java-fast-log-n-solution-186ms-without-using-the-treemap-but-a-customized-bst/12
    • I’ve got my 100% original code to pass 8/9 test cases, I’m really excited about it, my thought process could be visited in that thread, but I’m still puzzled why the last case didn’t pass, from my eyes check, I don’t see any difference between my output and the expected output.

Scramble String

https://leetcode.com/problems/scramble-string/

As Charles_p@’s solution: https://discuss.leetcode.com/topic/1195/any-better-solution/3, it’s the most concise and straightforward:

public boolean isScramble(String s1, String s2) {
if(s1 == null || s2 == null || s1.length() != s2.length()) return false;
if(s1.equals(s2)) return true;
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
if(!Arrays.equals(c1, c2)) return false;
for(int i = 1; i < s1.length(); i++){
if(isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) return true;
if(isScramble(s1.substring(0, i), s2.substring(s2.length()-i)) && isScramble(s1.substring(i), s2.substring(0, s2.length()-i))) return true;
}
return false;
}

 

I tried my own way, generated all possible scrambled strings for s1 and put them into a set, however, it got TLE, I am curious to see how it could be optimized: https://discuss.leetcode.com/topic/52081/one-possible-follow-up-or-mutation-did-anyone-try-to-generate-all-possible-scrambled-strings-for-s1