【阿里国际笔试】编程1&3

1.小红拿到了一个01串，她有以下两种操作:
1.选择一个字符取反，代价为x。
2.选择两个相邻的字符同时取反，代价为y。
小红想知道，自己将字符串变成全0”的最小代价是多少?
字符取反，指的是1变成0’"0变成1
样例
3 5
11101
result: 11

代码实现
注意:
没说y是优选, 然后注意溢出.将cost和count设为Long.

3.小红拿到了一棵树。所谓树，即n个节点、n -1条边的无向连通图。
小红定义一张图的权值为: 所有节点到1号节点的最短路长度之和。
小红想知道，假设i号节点和1号节点连一条边，生成的基环树的权值为多少?你需要回答1到n的答案。 (1时可以视为不添加任何边)基环树定义:n个节点、n条边的图。基环树保证有且仅有一个环。
本题中，所有的边均为无向边，且长度为1。

输入描述
第一行输入一个正整数n，代表节点的数量。接下来的n-1行，每行输入两个正整数u和v，代表点u和点v有一条无向边连接。1

代码
实现了样例,
实际上的操作思路是 start,cur
要判断是否有新边, 是则加入新边, 重新计算lengths. 最后要恢复结构.

import java.util.Scanner;

/**
 * 

 * 测试leetcode
 * 
 *
 * @author Mr.Shi
 * @since 2023-09-18 19:35
 **/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class test {

    private ArrayList> graph;

    public test(int numNodes) {
        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public int[] calculateLengths(int startNode) {
        int numNodes = graph.size();
        int[] lengths = new int[numNodes];
        Arrays.fill(lengths, -1); // 初始化长度为-1，表示不可达

        Queue queue = new LinkedList<>();
        queue.add(startNode);
        lengths[startNode] = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : graph.get(node)) {
                if (lengths[neighbor] == -1) {
                    lengths[neighbor] = lengths[node] + 1;
                    queue.add(neighbor);
                }
            }
        }

        return lengths;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        test calLen = new test(n);
        int a = 0,b = 0;
        while(sc.hasNextInt()) {
            a = sc.nextInt()-1;b = sc.nextInt()-1;
            calLen.addEdge(a,b);
        }

        int startNode = 0;
        int[] lengths = calLen.calculateLengths(startNode);

        System.out.println("Lengths from node " + startNode + ":");
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + ": " + cal(lengths,calLen,startNode,i));
        }
    }

    public static int cal(int[] lengths, test obj,int start,int cur){
        int sum=0;
        for (int i = 0; i < lengths.length; i++) {
            sum +=lengths[i];//原
        }
        if (start == cur) {
            return sum;
        }
        //重新计算0-i的长度
        if (obj.graph.get(start).contains(cur)) {//如果有这条边
            return sum;
        }else {
            //obj.addEdge(start,cur);
            //计算start->cur的新长度lengths[cur],并更新
            //int[] lengths1 = obj.calculateLengths(start);
            return  sum - (lengths[cur]-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
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