==
тесты для ссылочного равенства (независимо от того, являются ли они одним и тем же объектом).
.equals()
тесты для равенства значений (независимо от того, являются ли они логически «равными»).
Objects.equals () проверяет наличие null
перед вызовом .equals()
, поэтому вам не нужно (доступно с JDK7, также доступным в Guava ).
String.contentEquals () сравнивает содержимое String
с содержимым любого CharSequence
(доступно с Java 1.5).
Следовательно, если вы хотите проверить, имеет ли две строки одно и то же значение, вы, вероятно, захотите использовать Objects.equals()
.
// These two have the same value
new String("test").equals("test") // --> true
// ... but they are not the same object
new String("test") == "test" // --> false
// ... neither are these
new String("test") == new String("test") // --> false
// ... but these are because literals are interned by
// the compiler and thus refer to the same object
"test" == "test" // --> true
// ... string literals are concatenated by the compiler
// and the results are interned.
"test" == "te" + "st" // --> true
// ... but you should really just call Objects.equals()
Objects.equals("test", new String("test")) // --> true
Objects.equals(null, "test") // --> false
Objects.equals(null, null) // --> true
Вы почти всегда хотите использовать Objects.equals()
. В редкой ситуации, когда вы знаете, что имеете дело с интернированными строками, вы можете использовать ==
.
Из JLS 3.10. 5. Строковые литералы :
Кроме того, строковый литерал всегда ссылается на тот же экземпляр класса
String
. Это связано с тем, что строковые литералы, или, в более общем смысле, строки, которые являются значениями константных выражений ( §15.28 ), «интернированы», чтобы обмениваться уникальными экземплярами, используя методString.intern
.. Подобные примеры также можно найти в JLS 3.10.5-1 .
После создания массива TreeNode[]
это легко:
TreeNode root = null;
for (int i=0; i<T.length; ++i) {
if (T[i] == i) { // if it's a root node
//TODO: Test for multiple root nodes here
root = nodes[i];
} else {
nodes[T[i]].addChild(nodes[i]);
}
}
Я бы добавил объект private TreeNode parent;
в класс TreeNode
, инициализировал его до null
и установил его в родительская ссылка в методе addChild
. Это удобно во время отладки, даже если вам это не нужно для первого использования этого класса. Возможно, вам понадобится это позже.
Итерации по всем узлам, для каждого узла получить значение узла и добавить текущий узел к узлу со значением.
for (int i = 0; i < N; i++) {
nodes[nodes[i].getValue()].addChild(nodes[i])
}
Я пишу ответ, однако он не показывает всех детей. Код приведен ниже,
public class App {
static class TreeNode {
private int value;
private ArrayList<TreeNode> children;
public TreeNode(int nodeValue) {
this.value = nodeValue;
this.children = new ArrayList<TreeNode>();
}
public int getValue() {
return this.value;
}
public void addChild(TreeNode child) {
this.children.add(child);
}
public ArrayList<TreeNode> getChildren() {
return this.children;
}
}
public static TreeNode buildGraph(int[] T, int K) {
final int N = T.length;
TreeNode[] nodes = new TreeNode[N];
for (int i = 0; i < N; i++) {
nodes[i] = new TreeNode(i);
}
/*
T[0] = 1
T[1] = 2
T[2] = 3
T[3] = 3
T[4] = 2
T[5] = 1
T[6] = 4
2 - 3
/ \
1 4
/ | |
0 5 6
* */
TreeNode root = nodes[K];
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean[] visited = new boolean[N];
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int index = node.getValue();
visited[index] = true;
// T[3] = 3 is a leaf with no further connection to develop
if (index == T[index]) {
continue;
}
// 2 != 3 for the root node and we havent visited node 3 earlier
if (index != T[index] && !visited[T[index]]) {
node.addChild(nodes[T[index]]);
queue.offer(nodes[T[index]]);
}
int left = 0, right = N - 1;
while (left < index && right > index) {
if (T[left] == index) {
node.addChild(nodes[left]);
queue.offer(nodes[left]);
}
if (T[right] == index) {
node.addChild(nodes[right]);
queue.offer(nodes[right]);
}
left++;
right--;
}
}
return root;
}
public static void main(String[] args) {
int[] T = new int[7];
T[0] = 1;
T[1] = 2;
T[2] = 3;
T[3] = 3;
T[4] = 2;
T[5] = 1;
T[6] = 4;
TreeNode root = buildGraph(T, 2);
System.out.println("The root = " + root.getValue());
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
ArrayList<TreeNode> children = node.getChildren();
for (int i = 0; i < children.size(); i++) {
TreeNode child = children.get(i);
queue.offer(child);
System.out.println("Parent "+ node.getValue()+ " has children = "+ child.getValue());
}
}
}
}
. В то время, когда я запускаю, я получаю вывод, например,
The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 1 has children = 0
. Любой может помочь мне исправить, как я пропущу других детей ?
Я пишу его на основе другого ответа, который кажется более простым.
public static TreeNode buildGraph1(int[] T, int K) {
final int N = T.length;
TreeNode[] nodes = new TreeNode[N];
for (int i = 0; i < N; i++) {
nodes[i] = new TreeNode(i);
}
/*
T[children] = parent if the children != K
T[0] = 1
T[1] = 2
T[2] = 3
T[3] = 3
T[4] = 2
T[5] = 1
T[6] = 4
2 - 3
/ \
1 4
/ | |
0 5 6
* */
TreeNode root = nodes[K];
int value = root.getValue();
if (T[K] != K) {
nodes[K].addChild(nodes[T[K]]);
}
for (int i = 0; i < T.length; ++i) {
if (K == i) {
continue;
}
if (T[i] != i) {
nodes[T[i]].addChild(nodes[i]);
}
}
return root;
}
Вывод представлен ниже:
The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 2 has children = 4
Parent 1 has children = 0
Parent 1 has children = 5
Parent 4 has children = 6
The root = 3 Parent 3 has children = 2 Parent 2 has children = 1 Parent 2 has children = 4 Parent 1 has children = 0 Parent 1 has children = 5 Parent 4 has children = 6
Корень равен 2, а родительский 3 имеет детей = 2, неверно, а фактически наоборот – userX 13 July 2018 в 11:05T[2] = 3
говорит, что 3 является родительским элементом 2, поэтому 2 не может быть корнем. ИT[3] = 3
показывает, что у 3 нет родителя, поэтому он является корнем. Существуют ли дополнительные правила и параметры, которые делают 2 корнем? Если да, то что, если 3 действительно было частью дерева, например.T[3] = 7; T[7] = 8; T[8] = 8; T[9] = 8; T[10] = 9;
и так далее ...? – Tomek Szpakowicz 13 July 2018 в 11:19K
указан там, где вам нужно будет начинать. Таким образом, даже если T [children] = parent, если T [K] = V, то K является родительским элементом V. Как мне изменить код сейчас – userX 13 July 2018 в 11:25