1、poj-3268-Silver Cow Party
- 时间复杂度:
- 空间复杂度:
- 思路:建正反方向图,从源点x跑2次最短路,取每个点的往返和的最大值即可。注意处理重边。使用堆优化
Dijkstra
算法。其实就是降低了每次去查找当前dis数组中最小值的时间,时间复杂度由原来的降为
。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[][] cost1, cost2;
static int n, m, x, ans;
static List<Node>[] graph1, graph2; // 邻接表
static int[] dis1, dis2;
static boolean[] vis;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
n = in.nextInt();
m = in.nextInt();
x = in.nextInt(); // x作为源点
x--; // 记得减去1
cost1 = new int[n][n];
cost2 = new int[n][n];
dis1 = new int[n];
dis2 = new int[n];
vis = new boolean[n];
// 记录正向边
graph1 = new ArrayList[n];
// 记录反向边
graph2 = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph1[i] = new ArrayList<Node>();
graph2[i] = new ArrayList<Node>();
dis1[i] = dis2[i] = (int) 1e7;
for (int j = 0; j < n; j++)
cost1[i][j] = cost2[i][j] = 100005; // 初始化最大值,防止重边,有重边则取最小
}
for (int i = 0, a, b, c; i < m; i++) {
a = in.nextInt();
b = in.nextInt();
a--; // 节点编号减去1
b--;
c = in.nextInt();
// 记录边权值,为了防止重边
// 记录正向边
cost1[a][b] = Math.min(cost1[a][b], c);
// 记录反向边
cost2[b][a] = Math.min(cost2[b][a], c);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cost1[i][j] < 100005) // 有实际距离才建边
graph1[i].add(new Node(j, cost1[i][j]));
if (cost2[i][j] < 100005)
graph2[i].add(new Node(j, cost2[i][j]));
}
}
Dijkstra(x, dis1, graph1);
Arrays.fill(vis, false); // 重置标志
Dijkstra(x, dis2, graph2);
ans = 0;
// 两次跑最短路,取和最大即可
for (int i = 0; i < n; i++)
ans = Math.max(dis1[i] + dis2[i], ans);
System.out.println(ans);
}
}
private static void Dijkstra(int S, int[] dis, List<Node>[] graph) {
// 构建一个最小堆
Queue<NodeSort> queue = new PriorityQueue<NodeSort>();
// 先把源点添加进去,且设置源点到其本身的距离为0
dis[S] = 0;
queue.add(new NodeSort(0, S));
NodeSort head;
Node cur;
while (!queue.isEmpty()) {
head = queue.remove();
if (vis[head.cur]) // 过滤掉已归纳到最短距离集合的点
continue;
vis[head.cur] = true; // 归纳该点到最短路径的集合
// 扫描其相邻的边
for (int i = 0, u = head.cur, v, z, len = graph[u].size(); i < len; i++) { // 松弛
cur = graph[u].get(i);
v = cur.to;
z = cur.cap;
if (!vis[v] && dis[u] + z < dis[v]) { // 更新当前点到相邻点的最短距离
dis[v] = dis[u] + z;
queue.add(new NodeSort(dis[v], v));
}
}
}
}
}
//边类型
class Node {
int to, cap;
public Node(int to, int cap) {
this.to = to;
this.cap = cap;
}
}
// 自定义数据结构比较器,重写比较类型
class NodeSort implements Comparable<NodeSort> {
// 源点到当前点cur的最短距离为 t
int t, cur;
public NodeSort(int t, int cur) {
this.t = t;
this.cur = cur;
}
@Override
public int compareTo(NodeSort o) {
return this.t - o.t;
}
}
2、找一个大于n的最小不重复数
- 给定任意一个正整数,求比这个数大且最小的“不重复数”。“不重复数”的含义是相邻两位数字不相同,例如
1101
是重复数,而1201
是不重复数。 - 时间复杂度:
,m为位数。
- 空间复杂度:
- 思路:先把原数加1,处理进位,然后从高位往低位找第一对相邻重复数,将低一位上的数字加1,处理进位:若当前位是10,则此位变0,继续处理进位,否则判断当前位上的数字是否与高位相同,若相同,则将此位加1,继续进位处理,否则将这位以后的子串都变成
01
串。其本质就是贪心,把最高的相邻重复数字换掉,之后刷成01串即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str;
// 给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。
int[] num;
int len, bg;
boolean flag;
while (in.hasNext()) {
str = in.next();
len = str.length();
num = new int[len + 100];
for (int i = 0; i < len; i++) // 倒序存储
num[len - 1 - i] = str.charAt(i) - '0';
// 1、将原数加1后处理进位
num[0]++;
for (bg = 0; num[bg] == 10; bg++) {
num[bg] = 0;
num[bg + 1]++;
}
if (bg == len)
len++;
// 2、从高位往低位找第一对相邻重复数
flag = true;
for (int i = len - 1; i > 0; i--)
if (num[i - 1] == num[i]) {
flag = false;
bg = i - 1; // 标记第一个重复数的低一位
break;
}
if (!flag) { // 有相邻重复数:如:8989899 -> 8989900 -> 8990000 -> 9000000 -> 9010101
// 3、先将低位加1
num[bg]++;
while (true) {
// 处理进位
while (num[bg] == 10) {
// 当当前位置为0,高位加1
num[bg] = 0;
num[++bg]++;
}
if (bg == len) // 注意判断是否需要增加长度
len++;
if (num[bg] == num[bg + 1])
num[bg]++;
else
break;
}
if (bg > 0) {
num[--bg] = 0; // 将低一位都变成010101...
while (--bg > -1)
num[bg] = 1 - num[bg + 1];
}
}
for (int i = len - 1; i >= 0; i--)
System.out.print(num[i]);
System.out.println();
}
in.close();
}
}
3、链表奇偶位倒置,12345678->21436587
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ListNode head = new ListNode(0), cur = head;
for (int i = 1; i < 10; i++) {
cur.next = new ListNode(i);
cur = cur.next;
}
ListNode nowCur = new Solution().oddEvenList(head.next);
while (nowCur != null) {
System.out.print(nowCur.val + " ");
nowCur = nowCur.next;
}
System.out.println();
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode first = head, second = first == null ? null : first.next, tmp;
// 虚拟一个头节点,便于操作
ListNode dummyHead = new ListNode(-1), pre = dummyHead;
// 两两同时移动
while (first != null && second != null) {
// 先保存一下第3个链表节点
tmp = second.next;
// 将当前第1个节点先指向第3个节点
first.next = tmp;
// 将第2个节点指向第一个节点
second.next = first;
// 将 first 上一个节点 pre 指向 第2个节点
pre.next = second;
// 每次保存下一个 first 的上一个节点 pre
pre = first;
// 归位指针,指向下一次将要遍历的节点
first = tmp;
second = first == null ? null : first.next;
}
return dummyHead.next;
}
}
网友评论