美文网首页
手撕算法系列

手撕算法系列

作者: dev_winner | 来源:发表于2020-04-25 11:30 被阅读0次

1、poj-3268-Silver Cow Party

  • 时间复杂度:O(|E|log^{|V|})
  • 空间复杂度:O(V^2)
  • 思路:建正反方向图,从源点x跑2次最短路,取每个点的往返和的最大值即可。注意处理重边。使用堆优化Dijkstra算法。其实就是降低了每次去查找当前dis数组中最小值的时间,时间复杂度由原来的 O(|V|^2) 降为O(|E|log^{|V|})
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是不重复数。
  • 时间复杂度:O(m),m为位数。
  • 空间复杂度:O(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;
    }
}

相关文章

  • 手撕算法系列

    1、poj-3268-Silver Cow Party 时间复杂度: 空间复杂度: 思路:建正反方向图,从源点x跑...

  • 手撕反向传播算法

    最近找工作需要,因此看看梯度下降法和反向传播算法,顺手来个手撕笔记。 首先来个图: 好吧,定义一下这个图其中: 表...

  • 手撕经典排序算法

    直接插入排序 第一个结点默认已序,从第二个结点开始,即i=1。每次使用一个tmp报错第i个结点,然后依次将tmp与...

  • 想吃面包别出去买了,手把手教你做手撕包,香甜软糯,奶香浓郁

    手撕已经成为了中的一种常态,很多的是食品都有手撕版本,例如手撕牛肉,手撕豆腐干,手撕鸭,手撕鸡,手撕面包当然也有的...

  • 手撕鸡

    手撕鸡、手撕面包、手撕包菜、手撕牛肉,各种手撕做法,听起来就很手工的感觉。我做的手撕鸡纯粹懒人所为。 具体做法如下...

  • 美食十五-手撕鸡

    手撕鸡是一道家常菜,很难界定它的产地归属,手撕鸡有外皮金黄的盐焗鸡手撕,有风干鸡手撕,还有特色的手撕鸡丝。 手撕鸡...

  • Android 【手撕Glide】--Glide缓存机制(面试)

    本文源码解析基于Glide 4.6.1 系列文章Android 【手撕Glide】--Glide缓存机制Andro...

  • 手撕排序算法C++

    即将进入秋招阶段,面试手撕代码是常有的事情,所以呢,早点准备,以防万一。现场手撕代码,最常见的就是排序,今天先上来...

  • 手撕算法---常见排序算法java实现

    冒泡排序 是一种比较并交换排序方式。两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。 选择排序 ...

  • 丹麦系列—金砖 手撕包

    高粉1070克 白糖140克 酵母21克 盐20克 改良剂8.5克 牛奶214克 水480克 黄油70克(老面20...

网友评论

      本文标题:手撕算法系列

      本文链接:https://www.haomeiwen.com/subject/uzbhwhtx.html