2020-04-23

LeetCode - Algorithms - 912. Sort an Array

Problem

Given an array of integers nums, sort the array in ascending order.

Java

Insertion sort

class Solution {
    public int[] sortArray(int[] nums) {
        int temp;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }
        return nums;
    }
}

Submission Detail

10 / 10 test cases passed.
Runtime: 1323 ms, faster than 5.01% of Java online submissions for Sort an Array.
Memory Usage: 47.2 MB, less than 6.12% of Java online submissions for Sort an Array.

Mergesort

bottom-up mergesort

This method requires even less code than the standard recursive implementation.

class Solution {
    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int[] aux = new int[N];
        for (int len = 1; len < N; len *= 2) {
            for (int lo = 0; lo < N - len; lo += len + len) {
                int mid = lo + len - 1;
                int hi = Math.min(lo + len + len - 1, N - 1);
                merge(nums, aux, lo, mid, hi);
            }
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 7 ms, faster than 34.85% of Java online submissions for Sort an Array.
Memory Usage: 46.7 MB, less than 12.67% of Java online submissions for Sort an Array.

Top-down mergesort

recursive method

class Solution {
    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int[] aux = new int[N];
        sort(nums, aux, 0, N - 1);
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 6 ms, faster than 57.85% of Java online submissions for Sort an Array.
Memory Usage: 46.3 MB, less than 14.62% of Java online submissions for Sort an Array.

Shellsort

Example of simple idea leading to substantial performance gains.

class Solution {
    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int h = 1;
        for (; h < N / 3; h = 3 * h + 1) ;
        int temp;
        for (; h >= 1; h /= 3) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (nums[j] < nums[j - h]) {
                        temp = nums[j];
                        nums[j] = nums[j - h];
                        nums[j - h] = temp;
                    }
                }
            }
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 1865 ms, faster than 5.04% of Java online submissions for Sort an Array.
Memory Usage: 46.2 MB, less than 18.92% of Java online submissions for Sort an Array.

Quicksort

1

class Solution {
    public int[] sortArray(int[] nums) {
        qsort(0,nums.length-1, nums);
        return nums;        
    }
    
    /**
     * Quicksort
     * Programming Pearls
     * @author John Bentley
     * @param l
     * @param u
     * @param inArr
     */
    private void qsort(int l, int u, int[] inArr) {
        if (l>=u) return;
        int m=l;
        for(int i=l+1;i<=u; i++)
            if (inArr[i]<inArr[l])
                swap(inArr, ++m, i);
        swap(inArr, l, m);
        qsort(l,m-1,inArr);
        qsort(m+1,u,inArr);
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }    
}

Submission Detail

10 / 10 test cases passed.
Runtime: 4 ms, faster than 91.33% of Java online submissions for Sort an Array.
Memory Usage: 46.8 MB, less than 6.12% of Java online submissions for Sort an Array.

quicksort with 3-way partitioning

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo + 1;
        while (i <= gt) {
            if (a[i] < v) exch(a, lt++, i++);
            else if (a[i] > v) exch(a, i, gt--);
            else i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        sort(nums, 0, N - 1);
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 4 ms, faster than 89.87% of Java online submissions for Sort an Array.
Memory Usage: 46.9 MB, less than 12.99% of Java online submissions for Sort an Array.

selection sort

class Solution {
    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int temp;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (nums[j] < nums[min])
                    min = j;
            }
            temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 1169 ms, faster than 5.10% of Java online submissions for Sort an Array.
Memory Usage: 46.3 MB, less than 86.77% of Java online submissions for Sort an Array.

heap sort

iterative

Heapsort breaks into two phases: heap construction, where we reorganize the original array into a heap, and the sortdown, where we pull the items out of the heap in decreasing order to build the sorted result.

Q. Why not use a[0] in the heap representation?

A. Doing so simplifies the arithmetic a bit. It is not difficult to implement the heap methods based on a 0-based heap where the children of a[0] are a[1] and a[2], the children of a[1] are a[3] and a[4], the children of a[2] are a[5] and a[6], and so forth, but most programmers prefer the simpler arithmetic that we use. Also, using a[0] as a sentinel value (in the parent of a[1]) is useful in some heap applications.

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sink(int[] pq, int k, int n) {
        while (2 * k <= (n - 1)) {
            int j = 2 * k;
            if (j < (n - 1) && pq[j] < pq[j + 1]) j++;
            if (!(pq[k] < pq[j])) break;
            exch(pq, k, j);
            k = j;
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int k = (n - 1) / 2; k >= 0; k--)
            sink(nums, k, n);
        for (int k = n - 1; k > 0; k--) {
            exch(nums, 0, k);
            sink(nums, 0, k);
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 6 ms, faster than 53.50% of Java online submissions for Sort an Array.
Memory Usage: 46.6 MB, less than 48.27% of Java online submissions for Sort an Array.

recursion

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sink(int[] pq, int k, int n) {
        int largest = k;
        int l = 2 * k + 1;
        int r = 2 * k + 2;
        if (l < n && pq[l] > pq[largest])
            largest = l;
        if (r < n && pq[r] > pq[largest])
            largest = r;
        if (largest != k) {
            exch(pq, k, largest);
            sink(pq, largest, n);
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int k = n / 2 - 1; k >= 0; k--)
            sink(nums, k, n);
        for (int k = n - 1; k > 0; k--) {
            exch(nums, 0, k);
            sink(nums, 0, k);
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 7 ms, faster than 30.29% of Java online submissions for Sort an Array.
Memory Usage: 46.7 MB, less than 32.93% of Java online submissions for Sort an Array.

jdk PriorityQueue

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] sortArray(int[] nums) {
        Queue<Integer> q = new PriorityQueue<Integer>();
        for (int num : nums) {
            q.add(num);
        }
        int i = 0;
        while (q.size() > 0)
            nums[i++] = q.poll();
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 18 ms, faster than 16.69% of Java online submissions for Sort an Array.
Memory Usage: 47.7 MB, less than 11.36% of Java online submissions for Sort an Array.

2020-04-21

LeetCode - Algorithms - 547. Friend Circles

Problem

547. Friend Circles

Java

union–find

class Solution {
    public int findCircleNum(int[][] M) {
        int N = M.length;
        UF uf = new UF(N);
        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                if (M[i][j]==1)
                    uf.union(i,j);
            }
        }
        return uf.count();        
    }
}

/**
 * Weighted quick-union by rank with path compression by halving.
 * @author Robert Sedgewick
 * @author Kevin Wayne
 * Algorithms, 4th edition textbook code and libraries
 * https://github.com/kevin-wayne/algs4
 */
class UF {
    private int[] parent;
    private byte[] rank;
    private int count;

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }
}

Submission Detail

113 / 113 test cases passed.
Runtime: 1 ms, faster than 72.63% of Java online submissions for Friend Circles.
Memory Usage: 40.3 MB, less than 68.00% of Java online submissions for Friend Circles.

Depth-first search

class Solution {
    public int findCircleNum(int[][] M) {
        int N = M.length;
        List<Edge> edges = new ArrayList<Edge>();
        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                if (M[i][j]==1) {
                    edges.add( new Edge(i,j) );
                    edges.add( new Edge(j,i) );
                }
            }
        }
        Graph graph = new Graph(edges, N);
        boolean[] visited = new boolean[N];
        for(int i=0; i<N; i++)
            visited[i] = false;
        int c = 0;
        for(int i=0; i<N; i++) {
            if (!visited[i]) {
                dfs(graph, i, visited);
                c++;
            }
        }

        return c;        
    }
    
    private void dfs(Graph graph, int v, boolean[] visited) {
        visited[v] = true;
        for (int u : graph.adjList.get(v)) {
            if (!visited[u])
                dfs(graph, u, visited);
        }
    }
}

class Edge {
	int source, dest;

	public Edge(int source, int dest) {
		this.source = source;
		this.dest = dest;
	}
}

class Graph {
	List<List<Integer>> adjList = null;

	Graph(List<Edge> edges, int N) {
		adjList = new ArrayList<>(N);

		for (int i = 0; i < N; i++) {
			adjList.add(i, new ArrayList<>());
		}

		for (Edge edge : edges) {
			adjList.get(edge.source).add(edge.dest);
		}
	}
}

Submission Detail

113 / 113 test cases passed.
Runtime: 4 ms, faster than 25.38% of Java online submissions for Friend Circles.
Memory Usage: 40.1 MB, less than 72.00% of Java online submissions for Friend Circles.

Resources

2020-04-18

LeetCode - Algorithms - 867. Transpose Matrix

Problem

867. Transpose Matrix

Given a matrix A, return the transpose of A.

\( \begin{bmatrix}
1 &2 &3 \\
4 &5 &6 \\
7 &8 &9
\end{bmatrix} \Rightarrow \begin{bmatrix}
1 &4 &7 \\
2 &5 &8 \\
3 &6 &9
\end{bmatrix} \)

Java

class Solution {
    public int[][] transpose(int[][] A) {
        int h = A.length;
        int w = A[0].length;
        int[][] B = new int[w][h];
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++)
                B[j][i]=A[i][j];
        }
        return B;
    }
}

Submission Detail

36 / 36 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Transpose Matrix.
Memory Usage: 40.6 MB, less than 91.67% of Java online submissions for Transpose Matrix.

2020-04-15

A Response to "Bell's Conjecture"

\(\huge e^{i\pi}+1=0 \)

by Charlie Marion and William Dunham

Before we let you get away,
Your choices set in stone,
Consider what we have to say:
E.T.! O, please! Call home!

Stop the presses! Hold that thought!
And listen to our voices.
Ruffled, even overwrought,
We’ll supplement your choices.

Old Archie, Isaac, C. F. Gauss–
Though each deserves a floor
In mathematics’ honored house,
Make room for just one more.

Without the Bard of Basel, Bell,
You’ve clearly dropped the ball.
Our votes are cast for Euler, L.
Whose OPERA says it all:

Six dozen volumes — what a feat!
Profound and deep throughout
Does Leonhard rank with the elite?
Of this there is no doubt.

Consider how he summed, in turn
The quite elusive mix
Of one slash n all squared — you’ll learn
he got π² slash six.

\( \zeta(2)=\sum_{n=1}^{\infty}\frac{1}{n^2} = \lim_{n \to \infty} (\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}) = \frac{\pi^2}{6} \)

We’re shocked we did not see his name
With those you justly sainted.
No Euler in your Hall of Fame?
Your judgment’s surely Taine-ted.

It’s time to honor one you missed,
To do your duty well.
Add worthy Euler to your list,
And save him by the Bell.

Reprinted from the Mathematics Magazine, Vol.70, December, 1997, p.326
The Genius of Euler: Reflections on His Life and Work
Charlie Marion is a high school teacher
Euler is also celebrated by the Lutheran Church on their Calendar of Saints on May 24.

2020-04-12

Tower of Hanoi

Problem

We are given a tower of n disks, initially stacked in decreasing size on one of three pegs: The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.

Solution

The minimal number of moves required to solve a Tower of Hanoi puzzle is \( 2^n-1 \), where n is the number of disks. This is precisely the nth Mersenne number.

recurrence relation

\( T_0=0, T_1=1 \)
\( T_n=2T_{n-1}+1 \)

if we let \( u_n=T_n+1 \), we have
\( u_0=1 \)
\( u_n=2u_{n-1} \), for n>0
\( u_n=2^n \)
hence \( T_n=2^n-1 \)

Java

recurrence

public class HanoiTower {

    public static void move(int n, char source, char target, char auxiliary) {
        if (n==1)
            System.out.println("move " + source + " to " + target);
        else {
            // Move n - 1 disks from source to auxiliary, so they are out of the way
            move(n-1,source,auxiliary,target);
            // Move the nth disk from source to target
            System.out.println("move " + source + " to " + target);
            // Move the n - 1 disks that we left on auxiliary onto target
            move(n-1,auxiliary,target,source);
        }
    }

    public static void main(String[] args) {
        move(3, 'A', 'C', 'B');
    }
}

resources

2020-04-11

Why should you listen to Vivaldi's "Four Seasons"? - Betsy Schwarm - TED-Ed

Light, bright, and cheerful. It’s some of the most familiar of all early 18th century music. It’s been featured in uncounted films and television commercials, but what is it and why does it sound that way?

This is the opening of “Spring” from “The Four Seasons,” by Italian composer Antonio Vivaldi. “The Four Seasons” are famous in part because they are a delight to the ear. However, even more notable is the fact that they have stories to tell. At the time of their publication in Amsterdam in 1725, they were accompanied by poems describing exactly what feature of that season Vivaldi intended to capture in musical terms. In providing specific plot content for instrumental music, Vivaldi was generations ahead of his time.

If one were to read the poems simultaneously to hearing the music, one would find the poetic scenes synchronizing nicely with the musical imagery. We are told that the birds welcome spring with happy song, and here they are doing exactly that. Soon, however, a thunderstorm breaks out. Not only is there musical thunder and lightning, there are also more birds, wet, frightened, and unhappy.

In “Summer,” the turtle dove sings her name “tortorella” in Italian, before a hail storm flattens the fields. “Autumn” brings eager hunters dashing out in pursuit of their prey.

The “Winter” concerto begins with teeth chattering in the cold before one takes refuge by a crackling fire. Then it’s back out into the storm where there’ll be slips and falls on the ice. In these first weeks of winter, the old year is coming to a close, and so does Vivaldi’s musical exploration of the seasons.

Not until the early 19th century would such expressive instrumental program music, as it was known, become popular. By then, larger, more varied ensembles were the rule with woodwinds, brass, and percussion to help tell the tale. But Vivaldi pulled it off with just one violin, strings, and a harpsichord. Unlike his contemporary Bach, Vivaldi wasn’t much interested in complicated fugues. He preferred to offer readily accessible entertainment to his listeners with melodies that pop back up later in a piece to remind us of where we’ve been. So the first movement of the “Spring” concerto begins with a theme for spring and ends with it, too, slightly varied from when it was last heard.

It was an inspired way to attract listeners, and Vivaldi, considered one of the most electrifying violinists of the early 18th century, understood the value of attracting audiences. Such concerts might feature himself as the star violinist. Others presented the young musicians of the Pietà, a Venetian girls’ school where Vivaldi was Director of Music. Most of the students were orphans. Music training was intended not only as social skills suitable for young ladies but also as potential careers for those who might fail to make good marriages.

Even in the composer’s own time, Vivaldi’s music served as diversion for all, not just for the wealthy aristocrats. 300 years later, it’s an approach that still works, and Vivaldi’s music still sounds like trotting horses on the move.

2020-04-10

The Four Seasons - Sonnet text - Antonio Vivaldi

The Four Seasons is Vivaldi‘s best-known work, and is among the most popular pieces in the classical music repertoire.

Antonio Vivaldi composed a collection of “sound-pictures” that magically brought seasonal sights and sounds to the ear.

Spring

Allegro

Springtime is upon us.
The birds celebrate her return with festive song,
and murmuring streams are
softly caressed by the breezes.
Thunderstorms, those heralds of Spring, roar,
casting their dark mantle over heaven,
Then they die away to silence,
and the birds take up their charming songs once more.

Largo e pianissimo sempre

On the flower-strewn meadow, with leafy branches
rustling overhead, the goat-herd sleeps,
his faithful dog beside him.

Allegro pastorale

Led by the festive sound of rustic bagpipes,
nymphs and shepherds lightly dance
beneath the brilliant canopy of spring.

Summer

Allegro non molto

Under a hard season, fired up by the sun
Languishes man, languishes the flock and burns the pine
We hear the cuckoo’s voice;
then sweet songs of the turtledove and finch are heard.
Soft breezes stir the air, but threatening
the North Wind sweeps them suddenly aside.
The shepherd trembles,
fearing violent storms and his fate.

Adagio e piano – Presto e forte

The fear of lightning and fierce thunder
Robs his tired limbs of rest
As gnats and flies buzz furiously around.

Presto

Alas, his fears were justified
The Heavens thunder and roar and with hail
Cut the head off the wheat and damages the grain.

Autumn

Allegro

Celebrates the peasant, with songs and dances,
The pleasure of a bountiful harvest.
And fired up by Bacchus’ liquor,
many end their revelry in sleep.

Adagio molto

Everyone is made to forget their cares and to sing and dance
By the air which is tempered with pleasure
And (by) the season that invites so many, many
Out of their sweetest slumber to fine enjoyment

Allegro

The hunters emerge at the new dawn,
And with horns and dogs and guns depart upon their hunting
The beast flees and they follow its trail;
Terrified and tired of the great noise
Of guns and dogs, the beast, wounded, threatens
Languidly to flee, but harried, dies.

Winter

Allegro non molto

To tremble from cold in the icy snow,
In the harsh breath of a horrid wind;
To run, stamping one’s feet every moment,
Our teeth chattering in the extreme cold

Largo

Before the fire to pass peaceful,
Contented days while the rain outside pours down.

Allegro

We tread the icy path slowly and cautiously,
for fear of tripping and falling.
Then turn abruptly, slip, crash on the ground and,
rising, hasten on across the ice lest it cracks up.
We feel the chill north winds course through the home
despite the locked and bolted doors…
this is winter, which nonetheless
brings its own delights.

2020-04-09

数学题 - 1

A course of pure mathematics, G.H.Hardy

P34

chapterⅠ Real Variables

If a,b,c are positive,and \( a+b+c=1 \),then
\( (\frac{1}{a}-1)(\frac{1}{b}-1)(\frac{1}{c}-1) \geq 8. \) (Math. Trip. 1932)

if a>0 and b>0 then \( \frac{a+b}{2} \geq \sqrt{ab} \)

\( a>0, b>0, c>0, a+b+c=1 \)

\( (\frac{1}{a}-1)(\frac{1}{b}-1)(\frac{1}{c}-1) \)

\(=\frac{b+c}{a} \times \frac{a+c}{b} \times \frac{a+b}{c} \)

\( \geq 2 \times \frac{\sqrt{bc}}{a} \times 2 \times \frac{\sqrt{ac}}{b} \times 2 \times \frac{\sqrt{ab}}{c} = 8 \)

求极限

p207, No.5

\( \lim_{x \to \infty} \sqrt{x}(\sqrt{x+a}-\sqrt{x}) \)

p207, No.8

\( \lim_{x \to \infty} x^3(\sqrt{x^2+\sqrt{x^4+1}}-x \sqrt{2}) \)

求原函数

p281, No.53

\( \int \frac{x-1}{(x+1) \sqrt{x(x^2+x+1)}}dx \)

p263, No.6

\( \int \frac{1}{x \sqrt{3x^2+2x+1}}dx \)

有理数跟自然数等势

\( NXN \sim N \)

笛卡儿坐标系第一象限内的整数格点是直观地能一笔画联起来的，我是用y=-x的平行线簇，从原点出发，呈锯齿状把所有整数格子点串起来，这就表明NXN的元素是可以线性化的，即能存储到一个数组里

具体的双射关系是：

\( f(\langle a, b \rangle)=\frac{(a+b)(a+b+1)}{2}+b \)

反函数 \( g(a)=\langle \frac{1}{2N(N+3)}-a, a-\frac{1}{2N(N+1)} \rangle \) ，其中 \( N=floor(\frac{\sqrt{8a+1}-1}{2}) \)

是把横纵坐标联立后解一个一元二次方程得的这个结果

2020-04-07

LeetCode - Algorithms - 815. Bus Routes

Hard problem. Accepted after four submissions. Done by myself.

Problem

815. Bus Routes

Java

class Solution {
    public boolean routesIntersect(int[] route1, int[] route2) {
        boolean r = false;
        Set<Integer> tmpSet = new HashSet<Integer>();
        for(int i=0; i<route1.length; i++)
            tmpSet.add(route1[i]);
        for(int i=0; i<route2.length; i++) {
            if (tmpSet.contains(route2[i])) {
                r = true;
                break;
            }
        }
        return r;
    }

    public boolean inArray(int[] a, int x) {
        boolean b = false;
        for(int i=0; i<a.length; i++) {
            if (x==a[i]) {
                b = true;
                break;
            }
        }
        return b;
    }
    
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S==T) return 0;
        int minDist = Integer.MAX_VALUE;

        int h = routes.length;

        List<Integer> list_S = new ArrayList<Integer>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                if (routes[i][j]==S) {
                    list_S.add(i);
                }
            }
        }

        Map<Integer, List<Integer>> reachableRouteMap = new HashMap<Integer, List<Integer>>();
        for(int i=0; i<h; i++) {
            List<Integer> list = new ArrayList<Integer>();
            for(int j=0; j<h; j++) {
                if (j!=i && routesIntersect(routes[i],routes[j])) {
                    list.add(j);
                }
            }
            reachableRouteMap.put(i,list);
        }

        boolean[] visited = new boolean[h];
        for (int i = 0; i < h; i++) {
            visited[i] = false;
        }

        Queue<Node> q = new LinkedList<>();
        for(Integer i : list_S) {
            Node s = new Node(i, 1);
            q.add(s);
        }

        while (!q.isEmpty()) {
            Node curr = q.poll();
            visited[curr.route] = true;
            if (inArray(routes[curr.route], T)) {
                return curr.dist;
            }
            List<Integer> list = reachableRouteMap.get(curr.route);
            for(Integer idx : list) {
                if (visited[idx]==false) {
                    Node node = new Node(idx, curr.dist+1);
                    q.add(node);
                }
            }
        }

        if (minDist == Integer.MAX_VALUE)
            minDist = -1;
        return minDist;        
    }
    
    class Node {
        int route;
        int dist;

        public Node(int route, int dist) {
            this.route = route;
            this.dist = dist;
        }
    }    
}

Submission Detail

45 / 45 test cases passed.
Runtime: 1156 ms, faster than 5.02% of Java online submissions for Bus Routes.
Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Bus Routes.

2020-04-05

5 tips to improve your critical thinking - Samantha Agoos - TED-Ed

Every day, a sea of decisions stretches before us. Some are small and unimportant, but others have a larger impact on our lives. For example, which politician should I vote for? Should I try the latest diet craze? Or will email make me a millionaire? We’re bombarded with so many decisions that it’s impossible to make a perfect choice every time. But there are many ways to improve our chances, and one particularly effective technique is critical thinking. This is a way of approaching a question that allows us to carefully deconstruct a situation, reveal its hidden issues, such as bias and manipulation, and make the best decision. If the critical part sounds negative that’s because in a way it is. Rather than choosing an answer because it feels right, a person who uses critical thinking subjects all available options to scrutiny and skepticism. Using the tools at their disposal, they’ll eliminate everything but the most useful and reliable information. There are many different ways of approaching critical thinking, but here’s one five-step process that may help you solve any number of problems.

One: formulate your question. In other words, know what you’re looking for. This isn’t always as straightforward as it sounds. For example, if you’re deciding whether to try out the newest diet craze, your reasons for doing so may be obscured by other factors, like claims that you’ll see results in just two weeks. But if you approach the situation with a clear view of what you’re actually trying to accomplish by dieting, whether that’s weight loss, better nutrition, or having more energy, that’ll equip you to sift through this information critically, find what you’re looking for, and decide whether the new fad really suits your needs.

Two: gather your information. There’s lots of it out there, so having a clear idea of your question will help you determine what’s relevant. If you’re trying to decide on a diet to improve your nutrition, you may ask an expert for their advice, or seek other people’s testimonies. Information gathering helps you weigh different options, moving you closer to a decision that meets your goal.

Three: apply the information, something you do by asking critical questions. Facing a decision, ask yourself, “What concepts are at work?” “What assumptions exist?” “Is my interpretation of the information logically sound?” For example, in an email that promises you millions, you should consider, “What is shaping my approach to this situation?” “Do I assume the sender is telling the truth?” “Based on the evidence, is it logical to assume I’ll win any money?”

Four: consider the implications. Imagine it’s election time, and you’ve selected a political candidate based on their promise to make it cheaper for drivers to fill up on gas. At first glance, that seems great. But what about the long-term environmental effects? If gasoline use is less restricted by cost, this could also cause a huge surge in air pollution, an unintended consequence that’s important to think about.

Five: explore other points of view. Ask yourself why so many people are drawn to the policies of the opposing political candidate. Even if you disagree with everything that candidate says, exploring the full spectrum of viewpoints might explain why some policies that don’t seem valid to you appeal to others. This will allow you to explore alternatives, evaluate your own choices, and ultimately help you make more informed decisions.

This five-step process is just one tool, and it certainly won’t eradicate difficult decisions from our lives. But it can help us increase the number of positive choices we make. Critical thinking can give us the tools to sift through a sea of information and find what we’re looking for. And if enough of us use it, it has the power to make the world a more reasonable place.