Hexo
0%

Posted on Edited on In

Minimize Malware Spread

In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.

Some nodes initial are initially infected by malware. Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.

We will remove one node from the initial list. Return the node that if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

Note that if a node was removed from the initial list of infected nodes, it may still be infected later as a result of the malware spread.

Read more »

Posted on Edited on In

值，类型和操作符

值

值表示为二进制位存储在计算机易失内存中，每种值对应一种类型，

Read more »

Posted on Edited on In

Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

1
2
Input: row = [0, 2, 1, 3]
Output: 1

Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

1
2
Input: row = [3, 2, 0, 1]
Output: 0

Explanation: All couples are already seated side by side.
Note:

  • len(row) is even and in the range of [4, 60].
  • row is guaranteed to be a permutation of 0…len(row)-1.

题意分析

给定一个row数组，代表每个座位做的人，0和1是情侣，2和3是情侣，我们最终的目标就是将情侣都安排到一起。这里采用贪心策略，首先判断是否相邻的两个已经是情侣关系，如果是继续扫描下一组，如果不是，就将第二个换成第一个的情侣，而我们怎么找到第一个人的情侣的位置呢，好让第二个做正确的交换，这里pos数组就登场啦。pos数组刚好是row数组的逆，所谓逆，就是将索引和值对调，也就是pos数组的索引是row数组的值，因为大家都是数字，且不重复，这一点可以很容易的达到，只需要遍历row数组即可。这里采用贪心的策略是因为我们的每次交换至少可以完成一对情侣，最好的情况可以使得两对情侣都坐在一起，所以算法正确性毋庸置疑。

代码实现

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
class Solution {
   public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];
        int res = 0;
        for(int i = 0; i < n; i++) {
            pos[row[i]] = i;
        }

        for(int i = 0; i < n; i += 2) {
            int j = row[i] % 2 == 0 ? row[i] + 1 : row[i] - 1;
            if(row[i + 1] != j) {
                swap(row, pos, i + 1, pos[j]);
                res++;
            }
        }
        return res;
    }

    private void swap(int[] row, int[] pos, int i, int j) {
        int temp = row[i];
        row[j] = row[i];
        pos[row[j]] = i;
        row[i] =temp;
        pos[row[i]] = j;
    }
}

Posted on Edited on In

K-Similar Strings

Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.

Read more »

Posted on Edited on In

DOCTYPE

我们在编写html的时候往往第一行就是DOCTYPE的声明，那么这个DOCTYPE是什么呢？DOCTYPE=Document Type。也就是文档类型，众所周知，html作为一种在web时代使用的超文本标记语言，最基本的功能就是作为文档传达信息。

而html（1993）经过20几年的发展，其中发展出了众多标准，DOCTYPE的作用之一就是指明文档类型，如html的最新版本html5的DOCTYPE就是!DOCTYPE html。此外，在浏览器端，DOCTYPE还指明了其渲染文档的模式，明确说来就是是否采用怪异模式(quirks mode)渲染，与之对应的是标准模式(standard mode)，声明一个合法的DOCTYPE可以使得浏览器以标准模式渲染，至于渲染模式存在的原因还要归结于历史因素，简言之就是为了解决兼容性的问题。

DOCTYPE起初的目的是用作文档验证，我们在声明中指定一个DTD(Document Type Defination)的链接，该DTD用于解析和验证文档的合法性，而html5没有指定DTD，所以html5的DOCTYPE可以如此简洁。

附HTML4的DOCTYPE，<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "https://www.w3.org/TR/html4/strict.dtd">

Read more »

Posted on Edited on In

Similar String Groups

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, “tars” and “rats” are similar (swapping at positions 0 and 2), and “rats” and “arts” are similar, but “star” is not similar to “tars”, “rats”, or “arts”.

Together, these form two connected groups by similarity: {“tars”, “rats”, “arts”} and {“star”}. Notice that “tars” and “arts” are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

1
2
3
4
Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Note:

  • A.length <= 2000
  • A[i].length <= 1000
  • A.length * A[i].length <= 20000
  • All words in A consist of lowercase letters only.
  • All words in A have the same length and are anagrams of each other.
  • The judging time limit has been increased for this question.

题意分析

给定一个字符串数组，将相似的字符串分在一个group，问这样的group有多少。这里我们采用union-find策略，理由union-find数据结构的特点，只需要将相似字符串union，最后看这个uf的size就可以了。设字符串长度为M，字符串数组长度为N，则最坏时间复杂度为MN^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
class Solution {
    public int numSimilarGroups(String[] A) {
        UF uf = new UF(A.length);
        for(int i = 0; i < A.length - 1; i++) {
            for(int j = i + 1; j < A.length; j++) {
                if(similar(A[i], A[j])) uf.union(i, j);
            }
        }
        return uf.count();
    }

    private boolean similar(String s1, String s2) {
        int count = 0;
        // 如果有两个字符不同则相似
        for(int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i)!= s2.charAt(i) && ++count > 2) return false;
        }
        return true;
    }

    private class UF {
        private int[] parents;
        private int[] size;
        private int count;

        public UF(int n) {
            parents = new int[n];
            size = new int[n];
            
            for(int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
            count = n;
        }

        public int count() {return count;}

        public boolean connected(int p, int q) {return find(p) == find(q);}

        public int find(int id) {
            while(id != parents[id])
                id = parents[id];
            return id;
        }

        public void union(int i, int j) {
            int iid = find(i);
            int jid = find(j);
            if(iid == jid) return;

            if(size[iid] > size[jid]) {
                size[iid] += size[jid];
                parents[jid] = iid;
            } else {
                size[jid] += size[iid];
                parents[iid] = jid;
            }
            count--;
        }
    }
}

Posted on Edited on In

Redundant Connection II

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Read more »

Posted on Edited on In

Keys and rooms

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

1
2
3
4
5
6
7
Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.
1
2
3
4
5
Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

  • 1 <= rooms.length <= 1000
  • 0 <= rooms[i].length <= 1000
  • The number of keys in all rooms combined is at most 3000.

题意分析

该题是检查可达性问题的形式相对简单的一道题。在有向图中，从0出发，检查是否可以到达任意结点。我们维护的唯一的数据结构是set，我们每到达一个结点，都将其添加到set中，然后dfs相邻结点，完成一次完整的从0开始的dfs遍历后，若set的大小和rooms的大小一致，则说明可达所有结点，否则，返回false。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    Set<Integer> s = new HashSet<>();
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        dfs(rooms, 0);
        return s.size() == rooms.size();
    }

    private void dfs(List<List<Integer>> rooms, int i) {
        s.add(i);
        List<Integer> keys = rooms.get(i);
        for(int key : keys) {
            if(!s.contains(key))
                dfs(rooms, key);
        }

    }
}

Posted on Edited on In

EventualSafeNode

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Read more »

Posted on Edited on In

IsBipartite

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Read more »