|
2045. 到达目的地的第二短时间
城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi]?表示一条节点?ui 和节点?vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time?分钟。
每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都?同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点?信号灯是绿色时 才能离开。如果信号灯是??绿色 ，你 不能 在节点等待，必须离开。
第二小的值 是?严格大于 最小值的所有值中最小的值。
例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。
给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。
注意：
你可以 任意次 穿过任意顶点，包括 1 和 n 。
你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。
对于这个题目，我们可以用这样一种方式思考，肯定是使用BFS了，但是这样我们只能找到用时最短的时间，为了找到用时第二短的时间，我们可以使用visited数组来储存是否访问过，如果第一次访问到n，就将其visited设置为真，第二次访问到时，必然是用时第二短的时间，同时还要考虑，必须和最短时间严格不等！
class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
// 每条边的权重是一样的，所以，我们只需要找到次短路就可以了
// 一样使用BFS，一层一层的遍历，第二次遇到 n 才结束
// 先构造 n 个节点,将边整合到点中
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();
}
// 整理所有边，边中每个点的邻接表内都加入另一个点
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<>();
// 先把第 1 个节点入队，并设置其访问次数为 1
queue.offer(nodes[1]);
nodes[1].visited++;
int ans = 0;
// 遍历的层级，与二叉树的层序遍历类似
int level = 0;
while (!queue.isEmpty()) {
// 层级加一
level++;
// 计算时间
if (ans % (2 * change) >= change) {
ans += 2 * change - ans % (2 * change);
}
ans += time;
// 一层一层的遍历
int size = queue.size();
while (size> 0) {
size--;
// 弹出当前层的节点
Node node = queue.poll();
// 遍历其下级的节点
for (Node next : node.neighbours) {
// 如果下级节点有等于 n 的，并且不是初始状态，并且不等于当前层级
// 说明之前已经遍历过一次了，那就直接返回吧
if (next == nodes[n] && next.level != 0 && next.level != level) {
return ans;
}
// 剪枝1：同一个层级同一个节点出现多次，只需要入队一次
// 剪枝2：同一个节点被访问了两次及以上（同一层级多次算一次），它肯定不可能是次短路径的一部分
if (next.level != level && next.visited < 2) {
queue.offer(next);
next.level = level;
next.visited++;
}
}
}
}
return -1;
}
class Node {
/**
* 记录从起点到该点的层级
*/
int level = 0;
/**
* 记录该点相连的节点
*/
List<Node> neighbours = new ArrayList<>();
/**
* 记录被访问过几次，同一个节点在同一层级被访问多次算一次
*/
int visited = 0;
}
}
2047. 句子中的有效单词数
句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。
如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：
仅由小写字母、连字符和/或标点（不含数字）。
至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
至多一个 标点符号。如果存在，标点符号应当位于 token 的 末尾 。
这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。
给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。
先根据空格分割字符串为字符串数组ss，考虑到可能用多个空格分隔，如果某个子串中含有空格，即证明这个子串不是合法单词，取消。
我们会遍历ss数组，然后判断每个字符串是不是合法单词，如果是则ans+1，最后返回ans。
判断方式使用正则表达式，考虑到不同长度的字符串，如果长度为1，可以为单独的符号或字母，大于1时，符号只能在末尾
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) {
//长度大于一
if (s.length() > 1)
return s.matches("^[a-z]+(-[a-z]+)?[,.!]?$");
//长度为1，可以为单独的符号，或者单独的字母
else return s.matches("[!|,|.|[a-z]]");
}
}
|