2045. Second short time to destination

Cities are represented by a two-way connected graph, in which there are n nodes, numbered from 1 to n (including 1 and N). The edges in the figure are represented by a two-dimensional integer array edges, where each edge [i] = [ui, vi] represents a two-way connected edge between node ui and node VI. Each group of node pairs is connected by at most one edge, and the vertex has no edge connected to itself. The time to cross either side is time # minutes.

Each node has a traffic light, which changes once every change minute, from green to red, and then from red to green, in a cycle. All signal lights change at the same time. You can enter a node at any time, but you can only leave when the node} signal is green. If the signal light is} green, you can't wait at the node and must leave.

The second smallest value is the smallest of all values that are strictly greater than the minimum value.

For example, the second smallest value in [2, 3, 4] is 3, while the second smallest value in [2, 2, 4] is 4.
Give you n, edges, time and change, and return the second short time from node 1 to node n.

be careful:

You can pass through any vertex any time, including 1 and n.
You can assume that when you leave, all the lights just turn green.

For this topic, we can think in such a way that BFS must be used, but in this way, we can only find the shortest time. In order to find the second shortest time, we can use the visited array to store whether it has been accessed. If n is accessed for the first time, set its visited to true, and when it is accessed for the second time, It must be the second shortest time. At the same time, it must be strictly different from the shortest time!

class Solution {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        // The weight of each side is the same, so we only need to find a short circuit
        // BFS is also used. The traversal layer by layer ends when n is encountered for the second time

        // First construct n nodes and integrate the edges into the points
        HashMap<Integer,List<Integer>>graph=new HashMap<>();
        int[]visited=new int[n+1];

        Node[] nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node();
        }

        // Organize all edges, and add another point to the adjacency table of each point in the edge
        for (int[] edge : edges) {
            nodes[edge[0]].neighbours.add(nodes[edge[1]]);
            nodes[edge[1]].neighbours.add(nodes[edge[0]]);
        }
        Deque<Node> queue = new LinkedList<>();

        // First queue the first node and set its access times to 1
        queue.offer(nodes[1]);
        nodes[1].visited++;

        int ans = 0;
        // The traversal level is similar to the sequence traversal of binary tree
        int level = 0;
        while (!queue.isEmpty()) {
            // Level plus one
            level++;
            // computing time
            if (ans % (2 * change) >= change) {
                ans += 2 * change - ans % (2 * change);
            }
            ans += time;
            // Layer by layer traversal
            int size = queue.size();
            while (size> 0) {
                size--;
                // Pop up the node of the current layer
                Node node = queue.poll();
                // Traverse its subordinate nodes
                for (Node next : node.neighbours) {
                    // If the subordinate node has a value equal to n, is not in the initial state, and is not equal to the current level
                    // It indicates that it has been traversed once before, so go back directly
                    if (next == nodes[n] && next.level != 0 && next.level != level) {
                        return ans;
                    }
                    // Pruning 1: the same node at the same level appears multiple times and only needs to join the team once
                    // Pruning 2: if the same node is visited twice or more (the same level is calculated once more), it can't be part of the sub short path
                    if (next.level != level && next.visited < 2) {
                        queue.offer(next);
                        next.level = level;
                        next.visited++;
                    }
                }
            }
        }
        return -1;
    }

    class Node {
        /**
         * Record the level from the starting point to the point
         */
        int level = 0;
        /**
         * Record the nodes connected to this point
         */
        List<Node> neighbours = new ArrayList<>();
        /**
         * The record has been accessed several times, and the same node is accessed multiple times at the same level
         */
        int visited = 0;
    }
}

2047. Number of valid words in the sentence

Sentences consist only of lowercase letters ('a 'to' z '), numbers ('0' to '9'), hyphens ('-'), punctuation ('!', '.' and ','), and spaces ('). Each sentence can be broken down into one or more token s according to spaces, which are separated by one or more spaces'.

If a token meets the following conditions at the same time, it is considered as a valid word:

Only lowercase letters, hyphens and / or punctuation (excluding numbers).
At most one hyphen '-'. If present, lowercase letters should exist on both sides of the hyphen ("a-b" is a valid word, but "- AB" and "ab -" are not valid words).
At most one punctuation mark. If present, punctuation should be at the end of the token.
Here are some examples of valid words: "a-b.," afad "," ba-c "," a! " And "!".

Give you a string sentence. Please find out and return the number of valid words in sentence.

First, divide the string into string array ss according to the space. Considering that it may be separated by multiple spaces, if a substring contains spaces, it proves that the substring is not a legal word and is cancelled.

We will traverse the ss array, then judge whether each string is a legal word, if so, ans+1, and finally return ANS.

The judgment method uses regular expressions. Considering strings of different lengths, if the length is 1, it can be a separate symbol or letter. When it is greater than 1, the symbol can only be at the end

class Solution {
    public int countValidWords(String sentence) {
        String[]ss=sentence.trim().split("[ ]+");
        int ans = 0;
        for (String s : ss) if (checkValidWords(s)) ans++;
        return ans;
    }
    private boolean checkValidWords(String s) {
        //Length greater than one
        if (s.length() > 1) 
            return s.matches("^[a-z]+(-[a-z]+)?[,.!]?$");
        //The length is 1, which can be a separate symbol or a separate letter
        else return s.matches("[!|,|.|[a-z]]");
    }
}