@Victorcxq @zwqleetcoder: I have added some explanation in the post, hope it helps.
alexander
@alexander
Your selfdiscipline defines you.
Posts made by alexander

RE: [Java/C++] Clean Code  BFS

[Java/C++] Clean Code  BFS
shortestpath
:The delay of the network is the time for the signal to reach the furthest node, so this is ashortestpath
problem, and we need to calculateshortestpath
for all nodes;initialization
: We can initialize thewait time
for all nodes toinfinity
, except the sourceK
, itswait time
is0
. Then start fromK
, we update thebest wait time
for all its neighbornb
asdelay[K] + w(K, nb)
, note that these are temporary best result for these neighbors, theirbestwaittime
can be further optimized byRELAXATION
from other incoming edges later.RELAXATION
: by definition is  for nodev
, if there is an edge(u, v)
fromu
tov
, its distancetosourcedist(v)
is longer thandist(u) + w(u, v)
, wherew(u,v)
is the length(or weight) of edge(u,v)
, thendist(v)
can be optimized asdist(u) + w(u, v)
.level order BFS
: what we are doing here is, firstRELAX
all the neighbors ofK
, thenRELAX
all the neighbors of its neighbors thatare updated with a better waittime
, then keep going ... until all node can no longer beRELAX
ed.next level
 note that the candidates for next level can be duplicated, because nodes in the current level could share neighbors. That's why we want to use anset
to keep track of all the neighbors everRELAX
ed in this level. So, don't put neighbor in the queue for next round if it is already visited.
NOTE
:
negative weight cycle
 Cycles can be avoided as long as its weight will be not less than without the cycle. But this method cannot handlenegative weight cycle
.Java  adjacency matrix
class Solution { public int networkDelayTime(int[][] times, int N, int K) { int[] delay = new int[N + 1]; Arrays.fill(delay, Integer.MAX_VALUE); Integer[][] edge = new Integer[101][101]; for (int[] e : times) edge[e[0]][e[1]] = e[2]; Queue<Integer> q = new LinkedList<>(); q.offer(K); delay[K] = 0; while (!q.isEmpty()) { Set<Integer> set = new HashSet<>(); for (int n = q.size(); n > 0; n) { int u = q.poll(); for (int v = 1; v <= 100; v++) { if (edge[u][v] != null && delay[u] + edge[u][v] < delay[v]) { if (!set.contains(v)) { set.add(v); q.offer(v); } delay[v] = delay[u] + edge[u][v]; } } } } int maxdelay = 0; for (int i = 1; i <= N; i++) maxdelay = Math.max(maxdelay, delay[i]); return maxdelay == Integer.MAX_VALUE ? 1 : maxdelay; } }
C++
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<int> waits(N + 1, INT_MAX); map<int, map<int, int>> adj; for (auto e : times) adj[e[0]][e[1]] = e[2]; queue<int> q; q.push(K); waits[K] = 0; while (!q.empty()) { set<int> set; for (int n = q.size(); n > 0; n) { int u = q.front(); q.pop(); for (pair<int, int> nb : adj[u]) { int v = nb.first; if (waits[u] + adj[u][v] < waits[v]) { if (!set.count(v)) { set.insert(v); q.push(v); } waits[v] = waits[u] + adj[u][v]; } } } } int maxwait = 0; for (int i = 1; i <= N; i++) maxwait = max(maxwait, waits[i]); return maxwait == INT_MAX ? 1 : maxwait; } };

[Java/C++] Clean Code
Java
class Solution { public char nextGreatestLetter(char[] letters, char target) { int dist = 26; for (char c : letters) { dist = Math.min(dist, (c + 25  target) % 26 + 1); } return (char) ('a' + ((target + dist  'a') % 26)); } }
C++
class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int dist = 26; for (char c : letters) { dist = min(dist, (c + 25  target) % 26 + 1); } return 'a' + (target + dist  'a') % 26; } };

[C++] Clean Code
class Solution { public: int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) { long x1 = A, y1 = B, x2 = C, y2 = D, x3 = E, y3 = F, x4 = G, y4 = H; long overlap_x = max(0L, min(x2, x4)  max(x1, x3)); long overlap_y = max(0L, min(y2, y4)  max(y1, y3)); return (x2  x1) * (y2  y1) + (x4  x3) * (y4  y3)  overlap_x * overlap_y; } };

RE: [Java/C++] Clean Code with Explanation
@jianchao.li.fighter Thank you for posting! Good point! :)

[Java/C++] Clean Code with Explanation

If we sort all the numbers into
buckets
indexed by these numbers, this is essentially asking you to repetitively take an bucket while giving up the 2 buckets next to it. (the range of these numbers is [1, 10000]) 
The optimal final result can be derived by keep updating 2 variables
skip_i
,take_i
, which stands for:
skip_i
: the best result for subproblem of first(i+1)
buckets from0
toi
, while you skip thei
th bucket.
take_i
: the best result for subproblem of first(i+1)
buckets from0
toi
, while you take thei
th bucket. 
DP formula:
take[i] = skip[i1] + values[i];
skip[i] = Math.max(skip[i1], take[i1]);
take[i]
can only be derived from: if you skipped the[i1]
th bucket, and you take bucket[i].
skip[i]
through, can be derived from eithertake[i1]
orskip[i1]
, whatever the bigger;
/** * for numbers from [1  10000], each has a total sum sums[i]; if you earn sums[i], you cannot earn sums[i1] and sums[i+1] * kind of like house robbing. you cannot rob 2 connected houses. * */
Java
class Solution { public int deleteAndEarn(int[] nums) { int n = 10001; int[] values = new int[n]; for (int num : nums) values[num] += num; int take = 0, skip = 0; for (int i = 0; i < n; i++) { int takei = skip + values[i]; int skipi = Math.max(skip, take); take = takei; skip = skipi; } return Math.max(take, skip); } }
C++
class Solution { public: int deleteAndEarn(vector<int>& nums) { int n = 10001; vector<int> values(n, 0); for (int num : nums) values[num] += num; int take = 0, skip = 0; for (int i = 0; i < n; i++) { int takei = skip + values[i]; int skipi = max(skip, take); take = takei; skip = skipi; } return max(take, skip); } };


[Java/C++] Clean Code
 for each day from
end
tostart
, record thenext
day of temperaturet
for allt
in[30, 100]
 for each day from n1 to 0; for all temperature higher than temp[i], find the earliest
Java
class Solution { public int[] dailyTemperatures(int[] temps) { int n = temps.length; int[] waits = new int[n]; int[] next = new int[101]; // next day with with certain temperature. for (int i = n  1; i >= 0; i) { int earliest = Integer.MAX_VALUE; for (int t = temps[i] + 1; t <= 100; t++) { if (next[t] != 0) earliest = Math.min(earliest, next[t]); } if (earliest != Integer.MAX_VALUE) waits[i] = earliest  i; next[temps[i]] = i; } return waits; } }
C++
class Solution { public: vector<int> dailyTemperatures(vector<int>& temps) { int n = temps.size(); vector<int> waits(n, 0); vector<int> next(101, INT_MAX); // next day with with certain temperature. for (int i = n  1; i >= 0; i) { int earliest = INT_MAX; for (int t = temps[i] + 1; t <= 100; t++) { earliest = min(earliest, next[t]); } if (earliest != INT_MAX) waits[i] = earliest  i; next[temps[i]] = i; } return waits; } };
 for each day from

RE: [C++] [Java] Clean Code  5 lines (2 Solution)
@KkevinLi I think the definition of matrix exclude that case.

[Java/C++] Clean Code with Explanation
 This is a good use case for
UnionFind
, compare to Sentence Similarity I, here the similarity between words aretransitive
, so all the connected(similar
) words should be group into anunion
represented by theirultimate parent
(or family holder, you name it).  The connections can be represented by an parent map
Map<String, String> m
, which record thedirect parentship
we learned in each pair, but not theultimateparent
. To build it, go through the inputpairs
, for eachpair<w1, w2>
, use the recursivefind()
method to find theultimateparent
for both word parent1
,parent2
, if they are different, assignparent1
as parent ofparent2
(or the other way around), so that the to families aremerged
.  The classic
find(x)
method will find theultimateparent
ofx
. I modified it a little bit, make it do a little of extra initialization work assign x itself as its parent when it is not initialize
 so that we don't have to explicitly initialize the map at the beginning.
Java
class Solution { public boolean areSentencesSimilarTwo(String[] a, String[] b, String[][] pairs) { if (a.length != b.length) return false; Map<String, String> m = new HashMap<>(); for (String[] p : pairs) { String parent1 = find(m, p[0]), parent2 = find(m, p[1]); if (!parent1.equals(parent2)) m.put(parent1, parent2); } for (int i = 0; i < a.length; i++) if (!a[i].equals(b[i]) && !find(m, a[i]).equals(find(m, b[i]))) return false; return true; } private String find(Map<String, String> m, String s) { if (!m.containsKey(s)) m.put(s, s); return s.equals(m.get(s)) ? s : find(m, m.get(s)); } }
C++
class Solution { public: bool areSentencesSimilarTwo(vector<string>& a, vector<string>& b, vector<pair<string, string>> pairs) { if (a.size() != b.size()) return false; map<string, string> m; for (pair<string, string> p : pairs) { string parent1 = find(m, p.first), parent2 = find(m, p.second); if (parent1 != parent2) m[parent1] = parent2; } for (int i = 0; i < a.size(); i++) if (a[i] != b[i] && find(m, a[i]) != find(m, b[i])) return false; return true; } private: string find(map<string, string>& m, string s) { return !m.count(s) ? m[s] = s : (m[s] == s ? s : find(m, m[s])); } };
 This is a good use case for

RE: [Java/C++] Clean Code
@gautamcse27 when the code get here, the first 2 if has failed, means,
a[i]
is a negative star, ands.back()
is an positive star.
if positive star strictly less than the negative stara[i]
, the negative star will destroy the positive star on stack top and potentially more on the stack, therefore usei
to neutralizei++
at the end of the loop, so that i stay on the current negative star for the next round.