This is the most comprehensive solution report I have ever seen in LC.
Genius solution!!! Holy High (hao li hai)!!!
This is the most comprehensive solution report I have ever seen in LC.
Genius solution!!! Holy High (hao li hai)!!!
The idea is to find the first non-nine node from the right.
Increase its val by 1 and change everything behind it to zero.
public ListNode plusOne(ListNode head) {
ListNode notNine = new ListNode(0);
notNine.next = head;
head = notNine;
for (ListNode node = head; node != null; node = node.next)
if (node.val != 9) notNine = node;
notNine.val += 1;
for (ListNode node = notNine.next; node != null; node = node.next)
node.val = 0;
return head.val > 0 ? head : head.next;
}
Also, you really don't need pos and neg...
Track the longest one is enough.
Be greedier ^_^
@SmartBoyIn3716 It cannot be O(1) time.....
Greedy，just counting how many monotonic segments (I call segment from now on) are there.
To see it, first convince yourself that if you have an array with n segments the longest wiggle subsequence cannot have length more than n.
Then convince yourself that if there are n segments, you will always be able to construct a wiggle subsequence of length n.
The code is both the process of counting segments and constructing the wiggle subsequence.
All you need is the last element in the current longest wiggle and if the last segment is increasing.
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int ans = 1, tail = nums[0];
Boolean inc = null;
for (int x: nums) {
if (x == tail) continue;
if (inc == null || inc != x > tail) {
inc = x > tail;
ans++;
}
tail = x;
}
return ans;
}
Try run a small case by pencil and paper then you will fully understand why par also need reverse. Good luck!
very busy these days. Somehow it's keep getting attack....
I will try bring it back this week....
Thank you for asking!
One last comment. I write that reply to marc8 is not because of his comment particularly.
I have seen too many people here thinks that LC's test is some golden rule.
If the program runs fast enough here, then it is ok. Don't need to think about improvements.
If the program passes the tests and AC here, then it has no bugs.
I have even seen people given O(n^4) worst case solution and claim that it is fast because it beats 90% O(n^2) here.
I just don't have the patience to these.
I'd say sorry to marc8 if he also feels bad about my comment.
But I wouldn't be sorry to any of those who do not care about the performance of their code and only care about AC and LC runtime.
You are right, I am arrogant.