by Ella Wheeler Wilcox

What can be said in New Year rhymes,
That’s not been said a thousand times?

The new years come, the old years go,
We know we dream, we dream we know.

We rise up laughing with the light,
We lie down weeping with the night.

We hug the world until it stings,
We curse it then and sigh for wings.

We live, we love, we woo, we wed,
We wreathe our brides, we sheet our dead.

We laugh, we weep, we hope, we fear,
And that’s the burden of the year.

• The Year
• Ella Wheeler Wilcox

Whenever possible, steal code.
Keep it simple, stupid.
– Programming Pearls, Jon Bentley.

Problem

200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Java

BFS

1

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

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int numIslands(char[][] grid) {
        int h = grid.length;
        if (h == 0)
            return 0;
        int w = grid[0].length;
        int r = 0;

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

        Queue<Integer[]> queue = new LinkedList<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    queue.add(new Integer[]{i,j});
                    BFS(queue, grid, visited);
                    r++;
                }
            }
        }

    	return r;
    }

    public void BFS(Queue<Integer[]> queue, char[][] islandGrid, boolean[][] visited) {

        int H = islandGrid.length;
        int L = islandGrid[0].length;

        while (queue.isEmpty() == false) {

            Integer[] x = queue.remove();
            int row = x[0];
            int col = x[1];

            if(row<0 || col<0 || row>=H || col>=L || visited[row][col] || islandGrid[row][col]!='1')
                continue;

            visited[row][col]=true;
            queue.add(new Integer[]{row, (col-1)});
            queue.add(new Integer[]{row, (col+1)});
            queue.add(new Integer[]{(row-1), col});
            queue.add(new Integer[]{(row+1), col});
        }
    }
}

Submission Detail

• 47 / 47 test cases passed.
• Runtime: 10 ms, faster than 5.88% of Java online submissions for Number of Islands.
• Memory Usage: 41.6 MB, less than 55.82% of Java online submissions for Number of Islands.

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
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

class Solution {
    final static int d[][] = {
			{0,1},
			{1,0},
			{0,-1},
			{-1,0}
	};
    
    public int numIslands(char[][] grid) {       
        int h = grid.length;
        if (h == 0)
            return 0;
        int w = grid[0].length;
        
        int r = 0;

        boolean[][] visited = new boolean[h][w];

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

        Queue<Point> queue = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    queue.add(new Point(i,j));
                    bfs(queue, grid, visited);
                    r++;
                }
            }
        }
        
    	return r;        
    }
    
    public void bfs(Queue<Point> queue, char[][] islandGrid, boolean[][] visited) {

        int h = islandGrid.length;
        int w = islandGrid[0].length;

        while (queue.isEmpty() == false) {
        	Point curr = queue.poll();
            int row = curr.x;
            int col =  curr.y;
            if (isValid(islandGrid, visited, h, w, row, col)) {
                visited[row][col]=true;
				for (int i = 0; i < 4; i++) {
					int x = curr.x + d[i][0];
					int y = curr.y + d[i][1];
					queue.add(new Point(x, y));
				}
            }
        }
    }
    
	private boolean isValid(char[][] grid, boolean[][] visited, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1' && !visited[row][col];
	}
    
    class Point {
		int x;
		int y;

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

Submission Detail

• 47 / 47 test cases passed.
• Runtime: 5 ms, faster than 15.24% of Java online submissions for Number of Islands.
• Memory Usage: 42.3 MB, less than 17.21% of Java online submissions for Number of Islands.

union–find

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

class Solution {
    final static int d[][] = {
			{0,1},
			{1,0},
			{0,-1},
			{-1,0}
	};
    
    public int numIslands(char[][] grid) {       
		int h = grid.length;
		if (h == 0)
			return 0;
		int w = grid[0].length;

		int N = 0;
		List<Point> ptlist = new ArrayList<Point>();
		Map<String, Integer> map = new HashMap<String, Integer>();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == '1') {
					Point pt = new Point(i,j);
					ptlist.add(pt);
					map.put(i+","+j, N++);
				}
			}
		}

		UF uf = new UF(N);
		for (int i = 0; i < N; i++) {
			Point curr = ptlist.get(i);
			int row = curr.x;
			int col = curr.y;
			for (int k = 0; k < 4; k++) {
				int x = row + d[k][0];
				int y = col + d[k][1];
				if (isValid(grid, h, w, x, y)) {
					uf.union(i, map.get(x + "," + y));
				}
			}
		}

		return uf.count();        
    }
    
    
	private boolean isValid(char[][] grid, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1';
	}
    
    class Point {
		int x;
		int y;

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

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

• 47 / 47 test cases passed.
• Runtime: 28 ms, faster than 5.05% of Java online submissions for Number of Islands.
• Memory Usage: 45.3 MB, less than 5.12% of Java online submissions for Number of Islands.

ref

• Number of Islands using BFS

The world of Jesus is the world of sunlight by comparison with that of all the sages and philosophers and the schoolmen of any country. Like the Jungfrau which stands above the glaciers in the world of snow and seems to touch heaven itself, Jesus’ teachings have that immediacy and clarity and simplicity which puts to shame all other efforts of men’s minds to know God or to inquire after God.

Whence came this dazzling light of Jesus, which put Him in a special category by Himself among all teachers of men? Whence came the “prepossessing” power of Jesus, as Emerson called it?

Quite apart from the content of Jesus’ teachings, I think the light and the power (dazzling light always has power) of Jesus came from the manner and the voice of His teaching and from His personal example. Jesus spoke as no teacher of men ever spoke. Jesus never expounded His faith, never reasoned it out. He spoke with the simplicity and certainty of clear knowledge.

Thus it is that the world of Jesus contains both that power, and something else — the absolute clarity of light, without the self-limitation of Confucius, the intellectual analysis of Buddha, or the mysticism of Chuangtse. Where others reasoned, Jesus taught, and where others taught, Jesus commanded. He spoke out of the fullness of the knowledge and love of God. Jesus communicated the feeling of the immediate knowledge and love of God, and further, immediately and without qualification, equated that love of God with obeying His commandment, which is to love one another. If all great truths are simple, we stand here in the presence of a simple truth which contains the germ of the principle for all human development, and is sufficient.

Laotse and Jesus are brothers in spirit. Jesus said, “I am meek and lowly,” and Laotse said, “Hold on to meekness and the lowly position.”

Jesus has no dogmas, no creeds, no rites, and no rituals. Jesus taught a principle, or rather two principles in one: that the kingdom of God is within you, and, almost in the same breath, that the meek and the humble shall inherit the earth. The first teaches the inner freedom of man’s spirit; the second, the worthiness of the “least of these my brethren.” In other words, the humblest man is free in spirit, and the humblest man shall win. These are the spiritual principles behind all freedom and all democracy.

This sublime person, who each day still presides over the destiny of the world, we may call divine, not in the sense that Jesus has absorbed all the divine, or has been adequate to it (to employ an expression of the schoolmen), but in the sense that Jesus is the one who has caused his fellow-men to make the greatest step toward the divine. Mankind in its totality offers an assemblage of low beings, selfish, and superior to the animal only in that its selfishness is more reflective. From the midst of this uniform mediocrity, there are pillars that rise toward the sky, and bear witness to a nobler destiny. Jesus is the highest of these pillars which show to man whence he comes, and whither he ought to tend. In him was condensed all that is good and elevated in our nature. . . .

But whatever may be the unexpected phenomena of the future, Jesus will not be surpassed. His worship will constantly renew its youth, the tale of his life will cause ceaseless tears, his sufferings will soften the best hearts; all the ages will proclaim that, among the sons of men, there is none born who is greater than Jesus.
– Renan

Who but a Frenchman with the delicacy and depth of the French could express it so well and so eloquently?

In actual fact, Christianity in China never made converts by doctrines, but it did make converts whenever a Chinese came into personal contact with a Christian personality who followed the Christian teachings; namely, those few words “Love ye one another.“

Christians breed Christians, but Christian theology does not.

事实上我们全都是些集体性人物，不管我们愿意把自己摆在什么位置，严格地说，可以看成我们所特有的东西是微乎其微的，就像我们个人是微乎其微的一样。我们全都要从前辈或同辈那里学习东西，就连最大的天才，如果单凭他所特有的内在的自我去对付一切，他也绝不会有多大成就。我们的发展要归功于广大世界千丝万缕的影响，从这些影响中，我们吸收我们能吸收的和对我们有用的那一部分。（歌德）

But, in fact, we are all collective beings, let us place ourselves as we may. For how little have we, and are we, that we can strictly call our own property? We must all receive and learn both from those who were before us, and from those who are with us. Even the greatest genius would not go far if he tried to own everything to his own internal self.

I by no means owe my works to my own wisdom alone, but to a thousand things and persons around me, who provided me with material. There were fools and sages, minds enlightened and narrow, childhood, youth, and mature age - all told me what they felt, what they thought, how they lived and worked, and what experiences they had gained; and I had nothing further to do than to put out my hand and reap what others had sown for me.

— Johann Wolfgang von Goethe, Goethe’s Works

任何个人要想突然做出惊人的发现，这是不符合事物发展的规律的。科学是一步一个脚印地向前发展，每个人都要依赖前人的工作。当你听说一个突然的，意想不到的发现 —— 仿佛晴天霹雳时，你永远可以确信，它总是由一个人对另一个人的影响所导致的，正是因为有这种相互影响才使科学的进展存在着巨大的可能性。科学并不依赖于某一个人的思想，而是依赖于千万人的集体智慧，千万人思考着同一个问题，每一个人尽他自己的一份力量，知识的大厦就是这样建造起来的。（卢瑟福）

It is not in the nature of things for any one man to make a sudden violent discovery; science goes step by step, and every man depends on the work of his predecessors. When you hear of a sudden unexpected discovery—a bolt from the blue, as it were—you can always be sure that it has grown up by the influence of one man on another, and it is this mutual influence which makes the enormous possibility of scientific advance. Scientists are not dependent on the ideas of a single man, but on the combined wisdom of thousands of men, all thinking of the same problem, and each doing his little bit to add to the great structure of knowledge which is gradually being erected.
— Ernest Rutherford

我曾经为知识领域添瓦加砖，也曾帮别人添枝加叶；这些东西的价值，比起身后留下某种纪念物的大数学家或任何其他大大小小的艺术家们创造的价值，只是程度上有所不同，性质上并无差异。(哈代)

The case for my life, then, or for that of any one else who has been a mathematician in the same sense which I have been one, is this: that I have added something to knowledge, and helped others to add more; and that these somethings have a value which differs in degree only, and not in kind, from that of the creations of the great mathematicians, or of any of the other artists, great or small, who have left some kind of memorial behind them.
– A Mathematician’s Apology, G. H. Hardy

每个人都是混账、坏蛋，只有耶稣基督除外。爱因斯坦也是个坏蛋，因为在原子弹被引爆之后，他并没有离开美国，尽管他曾极力反对使用原子弹。
最终，通过事物之间的普遍联系，一个人会以这样或那样的方式，在深浅不等的程度上与世界上发生的所有事物都扯上干系。如果一个人可以对任何一个事件施加任何影响，那么他就要为此承担责任。（亚历山德罗夫）

Everyone is a bastard, everyone is bad, with the possible exception of Jesus Christ. Einstein is bad too, because he did not leave America after the nuclear bomb was detonated over his objections.In the end, through the general interconnectedness of events, a person becomes, in some way or another, to a greater or lesser extent, party to everything that happens in the world, and if he can exert any influence whatsoever on any event, then he becomes responsible for it.
– Aleksandr Danilovich Aleksandrov

QED - an interactive textbook

Terence Tao is a starlike mathematician of our time. He is also a geek mathematician.

Repository for the QED interactive text and possible extensions
https://github.com/teorth/QED

Gamifying propositional logic: QED, an interactive textbook

It took a while for me to come up with a workable game-like graphical interface for all of this, but I finally managed to set one up, now using Javascript instead of Scratch (which would be hopelessly inadequate for this task); indeed, part of the motivation of this project was to finally learn how to program in Javascript, which turned out to be not as formidable as I had feared (certainly having experience with other C-like languages like C++, Java, or lua, as well as some prior knowledge of HTML, was very helpful).

QED version 2.0: an interactive text in first-order logic

I feel though that there could be more that could be done with this sort of framework (e.g., improved GUI, modification to other logics, developing the ability to write one’s own texts and libraries, exploring mathematical theories such as Peano arithmetic, etc.). But writing this text (particularly the first-order logic sections) has brought me close to the limit of my programming ability, as the number of bugs introduced with each new feature implemented has begun to grow at an alarming rate. I would like to repackage the code so that it can be re-used by more adept programmers for further possible applications, though I have never done something like this before and would appreciate advice on how to do so.

only when I combined two man’s solutions did it pass on Leetcode.

Problem

210. Course Schedule II

topological sort of DAG.

Java

DFS

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] tp = new int[numCourses];

    	List<Edge> edges = new ArrayList<Edge>();
    	for(int i=0; i<prerequisites.length; i++) {
    		edges.add(new Edge(prerequisites[i][0],prerequisites[i][1]));
    	}
    	Graph graph = new Graph(edges, numCourses);

    	if (!isDAG(graph, numCourses))
    			return new int[]{};

    	List<Integer> tplist = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();

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

		for (int i = 0; i < numCourses; i++)
			if (visited[i] == false)
				topologicalSortUtil(i, visited, stack, graph);
		while (stack.empty() == false)
			tplist.add( stack.pop() );

		Collections.reverse(tplist);
		for(int i=0; i<tplist.size();i++)
			tp[i] = tplist.get(i);

        return tp;       
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack, Graph graph) {
		visited[v] = true;
		Integer i;
		Iterator<Integer> it = graph.adjList.get(v).iterator();
		while (it.hasNext()) {
			i = it.next();
			if (!visited[i])
				topologicalSortUtil(i, visited, stack, graph);
		}
		stack.push(new Integer(v));
	}

    public boolean isDAG(Graph graph, int N) {
		boolean[] discovered = new boolean[N];

		int[] departure = new int[N];

		int time = 0;

		for (int i = 0; i < N; i++)
			if (discovered[i] == false)
				time = DFS(graph, i, discovered, departure, time);

		for (int u = 0; u < N; u++) {
			for (int v : graph.adjList.get(u)) {
				if (departure[u] <= departure[v])
					return false;
			}
		}

		return true;
	}

    private int DFS(Graph graph, int v, boolean[] discovered, int[] departure, int time) {
		discovered[v] = true;

		for (int u : graph.adjList.get(v)) {
			if (!discovered[u])
				time = DFS(graph, u, discovered, departure, time);
		}

		departure[v] = time++;

		return time;
	}
}

class Edge {
	int source, dest;

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

}

public 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

• 44 / 44 test cases passed.
• Runtime: 9 ms, faster than 37.80% of Java online submissions for Course Schedule II.
• Memory Usage: 39.7 MB, less than 98.78% of Java online submissions for Course Schedule II.

ref

• Topological Sorting
• Check if given digraph is a DAG or not
• Topological Sort by DFS
• Topological Sort Algorithm for DAG using DFS it is not right, bug in it!

my exercises is to find solutions which can help me to understand these puzzle algorithms.

Problem

207. Course Schedule

scheduling problem with precedence constraints.

key

• DAG: a digraph with no directed cycles.
• A digraph has a topological order if and only if it is a DAG.
• Is a given digraph a DAG ?
• Depth-first search

Java

DFS

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

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    	List<Edge> edges = new ArrayList<Edge>();
    	for(int i=0; i<prerequisites.length; i++) {
    		edges.add(new Edge(prerequisites[i][0],prerequisites[i][1]));
    	}
    	Graph graph = new Graph(edges, numCourses);
        return isDAG(graph, numCourses);        
    }

    private boolean isDAG(Graph graph, int N) {
  		boolean[] discovered = new boolean[N];

  		int[] departure = new int[N];

  		int time = 0;

  		for (int i = 0; i < N; i++)
  			if (discovered[i] == false)
  				time = DFS(graph, i, discovered, departure, time);

  		for (int u = 0; u < N; u++) {
  			for (int v : graph.adjList.get(u)) {
  				if (departure[u] <= departure[v])
  					return false;
  			}
  		}
  		return true;
	}

  private int DFS(Graph graph, int v, boolean[] discovered, int[] departure, int time) {
		discovered[v] = true;

		for (int u : graph.adjList.get(v)) {
			if (!discovered[u])
				time = DFS(graph, u, discovered, departure, time);
		}

		departure[v] = time++;

		return time;
	}
}

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

• 42 / 42 test cases passed.
• Runtime: 5 ms, faster than 69.31% of Java online submissions for Course Schedule.
• Memory Usage: 44.6 MB, less than 94.62% of Java online submissions for Course Schedule.

ref

• Check if given digraph is a DAG or not
• Representing graphs
• 4.2 Directed Graphs

just run code of others.

Problem

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Java

Iterative Algorithm

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

class Solution {
    public List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> combinations = new ArrayList<List<Integer>>();

		int[] combination = new int[k];
		for (int i = 0; i < k; i++) {
			combination[i] = i;
		}

		while (combination[k - 1] < n) {
			List<Integer> comblist = new ArrayList<Integer>();
			for(int i=0; i<combination.length; i++) {
				comblist.add(combination[i]+1);
			}
			combinations.add(comblist);
			int t = k - 1;
			while (t != 0 && combination[t] == n - k + t) {
				t--;
			}
			combination[t]++;
			for (int i = t + 1; i < k; i++) {
				combination[i] = combination[i - 1] + 1;
			}
		}

		return combinations;        
    }
}

Submission Detail

• 27 / 27 test cases passed.
• Runtime: 3 ms, faster than 88.15% of Java online submissions for Combinations.
• Memory Usage: 39.7 MB, less than 80.43% of Java online submissions for Combinations.

ref

• Generate Combinations in Java
• Combinations

just verify code of other peer.

Problem

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Java

BASIC ALGORITHM 1: REMOVE

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

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	permutation_remove(nums,nums.length,list);
    	return list;        
    }

	  private void permutation_remove(int[] a, int n, List<List<Integer>> list) {
  		if (n == 1) {
  			List<Integer> x = new ArrayList<Integer>();
  			for(int i=0;i<a.length;i++)
  				x.add(new Integer(a[i]));
  			list.add(x);
  			return;
  		}
  		for (int i = 0; i < n; i++) {
  			swap(a, i, n - 1);
  			permutation_remove(a, n - 1, list);
  			swap(a, i, n - 1);
  		}
	 }

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

Submission Detail

• 25 / 25 test cases passed.
• Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
• Memory Usage: 38 MB, less than 82.98% of Java online submissions for Permutations.

HEAP’S ALGORITHM

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

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	permutation_heaps(nums,nums.length,list);
    	return list;        
    }

	private void permutation_heaps(int[] a, int n, List<List<Integer>> list) {
		if (n == 1) {
			List<Integer> x = new ArrayList<Integer>();
			for(int i=0;i<a.length;i++)
				x.add(new Integer(a[i]));
			list.add(x);
			return;
		}
		for (int i = 0; i < (n - 1); i++) {
			permutation_heaps(a, n - 1, list);
			if (n % 2 == 0)
				swap(a, n - 1, i);
			else
				swap(a, n - 1, 0);
		}
		permutation_heaps(a, n - 1, list);
	}

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

Submission Detail

• 25 / 25 test cases passed.
• Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
• Memory Usage: 36.3 MB, less than 98.58% of Java online submissions for Permutations.

ref

• GENERATING PERMUTATIONS
• Backtracking

Problem

49. Group Anagrams

Given an array of strings, group anagrams together.

JavaScript

solution by Joan Indiana Lyness

Algorithms 101: Group Anagrams in JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    var m = {};
    for(var i=0;i<strs.length;i++) {
        var s = strs[i];
        var c = s.split("").sort();
        m[c]?m[c].push(s):m[c]=[s];
    }
    var r = [];
    var keys = Object.keys(m);
    for(var k=0; k<keys.length; k++) {
        r.push( m[keys[k]] );
    }
    return r;
};

Submission Detail

• 101 / 101 test cases passed.
• Runtime: 144 ms, faster than 32.01% of JavaScript online submissions for Group Anagrams.
• Memory Usage: 45.6 MB, less than 34.78% of JavaScript online submissions for Group Anagrams.

Java

translation from solution of Joan Indiana Lyness

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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> list = new ArrayList<List<String>>();
		Map<String, List<String>> map = new HashMap<String, List<String>>();
		String s;
		char[] c;
		String key;
		for (int i = 0; i < strs.length; i++) {
			s = strs[i];
			c = s.toCharArray();
			Arrays.sort(c);
			key = new String(c);
			if (map.containsKey(key)) {
				map.get(key).add(s);
			} else {
				List<String> glist = new ArrayList<String>();
				glist.add(s);
				map.put(key, glist);
			}
		}

		list.addAll(map.values());
		return list;      
    }
}

Submission Detail

• 101 / 101 test cases passed.
• Runtime: 9 ms, faster than 83.05% of Java online submissions for Group Anagrams.
• Memory Usage: 40.8 MB, less than 96.49% of Java online submissions for Group Anagrams.

ref

• Sorting characters alphabetically in a String