LeetCode - Algorithms - 83. Remove Duplicates from Sorted List

Problem

83. Remove Duplicates from Sorted List

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null)
            return head;
        ListNode node = head;
        while(node!=null) {
            if (node.next!=null && node.next.val==node.val) {
                ListNode obsoleteNode = node.next;
                node.next = node.next.next;
                obsoleteNode = null;
            }
            else
                node = node.next;
        }
        return head;
    }
}

Submission Detail

  • 165 / 165 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted List.
  • Memory Usage: 38.4 MB, less than 10.24% of Java online submissions for Remove Duplicates from Sorted List.

LeetCode - Algorithms - 876. Middle of the Linked List

Problem

876. Middle of the Linked List

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while(node!=null) {
            list.add(node);
            node = node.next;
        }
        int n = list.size();
        return list.get(n/2);
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36.3 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode node = head;
        while(node!=null) {
            n++;
            node = node.next;
        }
        node = head;
        n /= 2;
        while(n>0) {
            node = node.next;
            n--;
        }
        return node;
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36.5 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

Two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        return slowPointer;
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36 MB, less than 9.03% of Java online submissions for Middle of the Linked List.

LeetCode - Algorithms - 203. Remove Linked List Elements

Problem

203. Remove Linked List Elements

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null)
            return head;
        ListNode previousNode = head;
        if (head != null) {
            ListNode node = head.next;
            while (node != null) {
                if (node.val == val) {
                    ListNode obsoleteNode = node;
                    previousNode.next = node.next;
                    obsoleteNode = null;
                }
                else
                    previousNode = node;
                node = node.next;
            }
        }
        if (head.val == val) {
            ListNode obsoleteNode = head;
            head = head.next;
            obsoleteNode = null;
        }
        return head;
    }
}

Submission Detail

  • 65 / 65 test cases passed.
  • Runtime: 1 ms, faster than 82.56% of Java online submissions for Remove Linked List Elements.
  • Memory Usage: 40 MB, less than 10.13% of Java online submissions for Remove Linked List Elements.

English-language idioms

English idioms, proverbs, and expressions are an important part of everyday English. Learning to use common idioms and expressions will make your English sound more native, so it’s a good idea to master some of these expressions.

The most common English idioms

A blessing in disguise

as part of a sentence

Meaning

a good thing that seemed bad at first

A dime a dozen

as part of a sentence

Meaning

(US) Anything that is common, inexpensive, and easy to get or available anywhere.

Beat around the bush

as part of a sentence

Meaning

  • To treat a topic but omit its main points, often intentionally or to delay or avoid talking about something difficult or unpleasant.
  • Avoid saying what you mean, usually because it is uncomfortable

Better late than never

by itself

Meaning

Better to arrive late than not to come at all

Bite the bullet

as part of a sentence

Meaning

  • To endure a painful or unpleasant situation that is unavoidable.

Break a leg

by itself

Meaning

  • A saying from the theatre that means “good luck”.
  • a typical English idiom used in theatre to wish a performer “good luck”.

Call it a day

as part of a sentence

Meaning

  • To declare the end of a task.
  • Stop working on something

Cut somebody some slack

as part of a sentence

Meaning

Don’t be so critical

Cutting corners

as part of a sentence

Meaning

Doing something poorly in order to save time or money

Easy does it

by itself

Meaning

Slow down

Get out of hand

as part of a sentence

Meaning

Get out of control

Get something out of your systems

as part of a sentence

Meaning

Do the thing you’ve been wanting to do so you can move on

Get your act together

by itself

Meaning

Work better or leave

Give someone the benefit of the doubt

as part of a sentence

Meaning

Trust what someone says

Go back to the drawing board

as part of a sentence

Meaning

Start over

Hang in there

by itself

Meaning

Don’t give up

Hit the sack/sheets/hay

as part of a sentence

Meaning

  • To go to bed; to go to sleep.

It’s not rocket science

by itself

Meaning

It’s not complicated

Let someone off the hook

as part of a sentence

Meaning

To not hold someone responsible for something

Make a long story short

as part of a sentence

Meaning

Tell something briefly

Miss the boat

as part of a sentence

Meaning

It’s too late

No pain, no gain

by itself

Meaning

You have to work for what you want

On the ball

as part of a sentence

Meaning

Doing a good job

Pull someone’s leg

as part of a sentence

Meaning

  • To tease or joke by telling a lie.
  • The phrase, from Scotland, originally meant to make a fool of someone, often by cheating them.
  • To joke with someone

Pull yourself together

by itself

Meaning

Calm down

So far so good

by itself

Meaning

Things are going well so far

Speak of the devil

by itself

Meaning

  • the short form of the English-language idiom “Speak of the devil and he doth appear” (or its alternative form “speak of the devil and he shall appear”).
  • The form “talk of the devil” is also in use in England. It is used when an object of discussion unexpectedly becomes present during the conversation.

That’s the last straw

by itself

Meaning

  • My patience has run out
  • The last straw is an idiom referring to the Straw that broke the camel’s back.

The best of both worlds

as part of a sentence

Meaning

An ideal situation

Time flies when you’re having fun

by itself

Meaning

You don’t notice how long something lasts when it’s fun

To get bent out of shape

as part of a sentence

Meaning

To get upset

To make matters worse

as part of a sentence

Meaning

Make a problem worse

Under the weather

as part of a sentence

Meaning

  • Feeling sick or poorly.
  • From under the weather bow (“affected by bad weather; seasick”); weather bow is a nautical term referring to the side of a ship exposed to bad weather.

We’ll cross that bridge when we come to it

by itself

Meaning

Let’s not talk about that problem right now

Wrap your head around something

as part of a sentence

Meaning

Understand something complicated

You can say that again

by itself

Meaning

  • That is very true; an expression of wholehearted agreement.
  • (idiomatic, in response to another person) That is very true.

Your guess is as good as mine

by itself

Meaning

I have no idea

LeetCode - Algorithms - 414. Third Maximum Number

Problem

414. Third Maximum Number

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int thirdMax(int[] nums) {
        final int N = nums.length;
        int max = nums[0];
        for (int i = 1; i < N; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        int m2 = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < max && nums[i] > m2)
                m2 = nums[i];
        }
        long m3 = Long.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < m2 && nums[i] > m3)
                m3 = nums[i];
        }
        return m3 > Long.MIN_VALUE ? new Long(m3).intValue() : max;
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 1 ms, faster than 90.82% of Java online submissions for Third Maximum Number.
  • Memory Usage: 39.2 MB, less than 7.88% of Java online submissions for Third Maximum Number.

PriorityQueue and HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

class Solution {
    public int thirdMax(int[] nums) {
        Queue<Integer> q = new PriorityQueue<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for (int i : nums) {
            if (!set.contains(i)) {
                set.add(i);
                q.add(i);
            }
            if (q.size() > 3) {
                set.remove(q.poll());
            }
        }
        if (q.size() < 3) {
            while (q.size() > 1)
                q.poll();
        }
        return q.peek();
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 5 ms, faster than 21.06% of Java online submissions for Third Maximum Number.
  • Memory Usage: 38.7 MB, less than 10.02% of Java online submissions for Third Maximum Number.

TreeSet

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

class Solution {
    public int thirdMax(int[] nums) {
        SortedSet<Integer> treeSet = new TreeSet<Integer>();
        for (int num : nums) {
            treeSet.add(num);
            if (treeSet.size() > 3)
                treeSet.remove(treeSet.first());
        }
        return treeSet.size() < 3 ? treeSet.last() : treeSet.first();
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 4 ms, faster than 39.33% of Java online submissions for Third Maximum Number.
  • Memory Usage: 38.6 MB, less than 10.02% of Java online submissions for Third Maximum Number.

javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    var max=nums[0],min=nums[0];
    for(var i=1;i<nums.length;i++) {
        if (nums[i]>max)
            max = nums[i];
        if (nums[i]<min)
            min = nums[i];
    }
    var lowguard = min-1;
    var m2 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<max && nums[i]>m2)
            m2 = nums[i];
    }
    var m3 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<m2 && nums[i]>m3)
            m3 = nums[i];
    }
    return m3!=lowguard?m3:max;
};

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 80 ms, faster than 72.32% of JavaScript online submissions for Third Maximum Number.
  • Memory Usage: 38.9 MB, less than 5.00% of JavaScript online submissions for Third Maximum Number.

The best-known quantum algorithms

Shor’s algorithm

Shor’s algorithm is a polynomial-time quantum computer algorithm for integer factorization. It was invented in 1994 by the American mathematician Peter Shor.

Shor’s algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve.

Shor’s algorithm was the first non-trivial quantum algorithm showing a potential of ‘exponential’ speed-up over classical algorithms, It captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration. Therefore, to implement Shor’s algorithm is comparable to the ‘Hello, World’ of classical computing. (Mark Ritter, senior manager of physical sciences at IBM)

Peter Shor

Shor: I’ve been writing poetry occasionally since high school, but I never considered making a career of it.

If computers that you build are quantum,
Then spies of all factions will want ‘em.
Our codes will all fail,
And they’ll read our email,
Till we’ve crypto that’s quantum, and daunt ‘em.
(by Jennifer and Peter Shor)

You can see why I chose a career as a scientist rather than as a poet.(Shor’s joke)

There are several aspects of quantum mechanics that make quantum computers more powerful than digital computers. One of these is the superposition principle, which says that a quantum system can be in more than one state at the same time. Another one of these is interference; a third is the exponentially large size of the state space of a quantum mechanical system.

There are some problems that quantum computers seem to be exponentially faster than classical computers at, like factoring. There are other problems that quantum computers don’t speed up at all, like sorting. So asking “which is better, a classical computer or a quantum computer” is like asking “which is a better transportation device, a boat or a car.” It really depends on what you want to do with it.

Grover’s algorithm

Grover’s algorithm is a quantum algorithm for searching an unstructured database or an unordered list. It was devised by Lov Grover in 1996.

Grover’s algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search.

Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover’s algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when N is large.

Grover’s algorithm demonstrate the power of quantum parallelism, in specific, making queries in parallel.

LeetCode - Algorithms - 896. Monotonic Array

Problem

896. Monotonic Array

Java

One Pass

© Approach 3: One Pass (Simple Variant)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isMonotonic(int[] A) {
        boolean increasing = true;
        boolean decreasing = true;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) decreasing = false;
            if (A[i] < A[i + 1]) increasing = false;
        }
        return increasing || decreasing;
    }
}

Submission Detail

  • 366 / 366 test cases passed.
  • Runtime: 1 ms, faster than 100.00% of Java online submissions for Monotonic Array.
  • Memory Usage: 47.8 MB, less than 18.59% of Java online submissions for Monotonic Array.

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isMonotonic(int[] A) {
        final int N = A.length;
        if (N<=2)
            return true;
        int[] d = new int[N-1];
        for(int i=1, j=0; i<N; i++,j++) {
            d[j] = A[i]-A[i-1];
        }
        int min=d[0],max=d[0];
        for(int i=1; i<N-1; i++) {
            if (d[i]<min) min = d[i];
            if (d[i]>max) max = d[i];
        }
        return (min<=0 && max<=0) || (min>=0 && max>=0);
    }
}

Submission Detail

  • 366 / 366 test cases passed.
  • Runtime: 2 ms, faster than 31.40% of Java online submissions for Monotonic Array.
  • Memory Usage: 46.9 MB, less than 18.59% of Java online submissions for Monotonic Array.

LeetCode - Algorithms - 1232. Check If It Is a Straight Line

Problem

1232. Check If It Is a Straight Line

similar question

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private boolean isColine(int x1, int y1, int x2, int y2, int x3, int y3) {
        int a = (y3 - y2) * (x3 - x1);
        int b = (y3 - y1) * (x3 - x2);
        return a == b;
    }

    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        boolean b;
        for (int i = 0; i < N - 2; i++) {
            b = isColine(coordinates[i][0], coordinates[i][1], coordinates[i + 1][0], coordinates[i + 1][1], coordinates[i + 2][0], coordinates[i + 2][1]);
            if (b == false)
                return false;
        }
        return true;
    }
}

Submission Detail

  • 79 / 79 test cases passed.
  • Runtime: 1 ms, faster than 22.67% of Java online submissions for Check If It Is a Straight Line.
  • Memory Usage: 41 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Computational geometry method

© Copyright 2002-2020, Robert Sedgewick and Kevin Wayne.

keys

  • Shoelace formula, also known as Gauss’s area formula
  • vertices must listed in clockwise(or counterclockwise, increasing order of polar angle) order
  • CCW: Given three points a, b, and c, is a→b→c a counterclockwise turn? Determinant (or cross product) gives 2x signed area of planar triangle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Comparator;
import java.util.Arrays;

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        Point2D[] a = new Point2D[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Point2D(coordinates[i][0], coordinates[i][1]);
        }
        Arrays.sort(a);
        Arrays.sort(a, 1, N, a[0].polarOrder());
        int A = a[N - 1].x() * a[0].y() - a[0].x() * a[N - 1].y();
        for (int i = 0; i < N - 1; i++) {
            A += a[i].x() * a[i + 1].y() - a[i + 1].x() * a[i].y();
        }
        return A == 0;
    }
}

final class Point2D implements Comparable<Point2D> {
    private final int x;
    private final int y;

    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() {
        return x;
    }

    public int y() {
        return y;
    }

    public static int ccw(Point2D a, Point2D b, Point2D c) {
        int area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        if (area2 < 0) return -1;
        else if (area2 > 0) return +1;
        else return 0;
    }

    public int compareTo(Point2D that) {
        if (this.y < that.y) return -1;
        if (this.y > that.y) return +1;
        if (this.x < that.x) return -1;
        if (this.x > that.x) return +1;
        return 0;
    }

    public Comparator<Point2D> polarOrder() {
        return new PolarOrder();
    }

    private class PolarOrder implements Comparator<Point2D> {
        public int compare(Point2D q1, Point2D q2) {
            int dx1 = q1.x - x;
            int dy1 = q1.y - y;
            int dx2 = q2.x - x;
            int dy2 = q2.y - y;

            if (dy1 >= 0 && dy2 < 0) return -1;
            else if (dy2 >= 0 && dy1 < 0) return +1;
            else if (dy1 == 0 && dy2 == 0) {
                if (dx1 >= 0 && dx2 < 0) return -1;
                else if (dx2 >= 0 && dx1 < 0) return +1;
                else return 0;
            } else return -ccw(Point2D.this, q1, q2);
        }
    }
}

Submission Detail

  • 79 / 79 test cases passed.
  • Runtime: 6 ms, faster than 9.07% of Java online submissions for Check If It Is a Straight Line.
  • Memory Usage: 38.8 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

LeetCode - Algorithms - 832. Flipping an Image

Problem

832. Flipping an Image

similar question : 48. Rotate Image

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        final int N = A.length;
        final int M = A[0].length;
        int tmp;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M/2; j++) {
                tmp = A[i][j];
                A[i][j] = A[i][N-1-j];
                A[i][N-1-j] = tmp;
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                A[i][j] = A[i][j]==0?1:0;
            }
        }
        return A;
    }
}

Submission Detail

  • 82 / 82 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Flipping an Image.
  • Memory Usage: 39.1 MB, less than 16.27% of Java online submissions for Flipping an Image.

LeetCode - Algorithms - 905. Sort Array By Parity

It’s easy indeed.

Problem

905. Sort Array By Parity

Java

Two Pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int[] B = new int[N];
        int left=0, right=N-1;
        for(int i=0; i<N; i++) {
            if ((A[i]&1)==0) {
                B[left++]=A[i];
            }
            else {
                B[right--]=A[i];
            }
        }
        return B;
    }
}

Submission Detail

  • 285 / 285 test cases passed.
  • Runtime: 1 ms, faster than 99.47% of Java online submissions for Sort Array By Parity.
  • Memory Usage: 40.1 MB, less than 30.13% of Java online submissions for Sort Array By Parity.

In-Place

© Solution - Approach 3: In-Place

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int left = 0, right = N - 1;
        int temp;
        while (left < right) {
            if ((A[left] & 1)==1 && (A[right] & 1)==0) {
                temp = A[left];
                A[left] = A[right];
                A[right] = temp;
            }
            if ((A[left] & 1) == 0) left++;
            if ((A[right] & 1) == 1) right--;
        }
        return A;
    }
}

Submission Detail

  • 285 / 285 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Array By Parity.
  • Memory Usage: 39.6 MB, less than 30.13% of Java online submissions for Sort Array By Parity.