命运逻辑门,活动入口:STEINS;GATE 電脳言語のオルダーソンループ

这次比上次那个《程序员死绝了》简单多了,只给出剧情相关的四个题解

由于咱は日本語本当上手实在不懂日文(全靠浏览器实时翻译成中/英文读题,黑盒测试),只能说一下大概的题意

第一题 正則表現のエントリーポイント

题意

输入两个字符串,在两个字符串间添加分号 ‘;’ 后输出

题解

过于简单,无题解

第二题 性能解析のタイプセーフ

题意

大意是游戏中的角色升级:

第一行输入: N 和 K 代表 N 个角色,以及进行一次游戏能够获得 K 点经验(小数)

之后每行给出每一个角色所需的经验点数

计算需要打多少场游戏

题解

累加角色经验值得到 sum,计算 res 使得 res * k > sum

简单,无代码

第三题 例外処理のタブーサーチ

题意

第一行输入:给出 N、M 和 L,分别代表第一个表格的行数、两个表格的列数、第二个表格的行数

往后的 N 行是第一个表格的元素,再往后的 L 行是第二个表格的元素

根据第二个表格的数据计算出第三个表格,规则为:在第二个表格中,对于每一行数据的每个元素,用下一行的同列元素减去本行元素,得到第三个表格对行对应列的元素

拿第三个表格的数据与第一个表格对比,输出第三个表格中的行在第一个表格中的行数

题解

C# 代码

数据量不大,用了 Linq 和 List<> 的 SequenceEqual(),替换成其他方法效率会高一点

得到差后立即搜索第一个表格,也可以减少时间/空间消耗

using System;
using System.Linq;
using System.Collections.Generic;

namespace Paiza {
    class Program {
        static void Main() {
            List<List<int>> l1 = new List<List<int>>(), l2 = new List<List<int>>(), l3 = new List<List<int>>();

            string[] input = Console.ReadLine().Split();
            int n = Convert.ToInt32(input[0]), m = Convert.ToInt32(input[1]), l = Convert.ToInt32(input[2]);

            for (int i = 0; i < n; i++)
                l1.Add(Console.ReadLine().Split().Select(x => int.Parse(x)).ToList());

            for (int i = 0; i < l; i++)
                l2.Add(Console.ReadLine().Split().Select(x => int.Parse(x)).ToList());

            for (int i = 0; i < l - 1; i++) {
                List<int> subs = new List<int>();
                for (int j = 0; j < m; j++) {
                    subs.Add(l2[i + 1][j] - l2[i][j]);
                }
                l3.Add(subs);
            }

            for (int i = 0; i < l - 1; i++)
                for (int j = 0; j < n; j++)
                    if (l1[j].SequenceEqual(l3[i])) 
                        Console.WriteLine(j + 1);

        }
    }
}

第四题 進化戦略のプロシージャ

Continue reading “Paiza 命运石之门活动 题解”

仅记录,使用顺序合并,不包括分治和小顶堆(优先队列)

时间224ms,空间 28.8 MB(看脸)

思路简述

  1. 新建链表节点 res 作为答案链表的根节点
  2. 顺序遍历数组,使用 p 指针遍历数组中的每个链表
    • p 指针遍历链表时,向 res 中添加链表元素
  3. 使用前后指针 q1 和 q2 确定添加位置
    • q1 在前 q2 在后,当 q1.val 大于或等于 p.val 时,说明找到了 p 的位置(q1 和 q2 之间),此时将 q2 的下一个节点的 val 设置为 p.val、next 指向 q1 即可入链
    • 入链时需要 new 新的链表元素,直接使用 p 指针会导致重复链/断链

C# 题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        int n = lists.Length;
        if(n == 0) return null;
        ListNode resRoot = new ListNode(val: -10001); //链的根
        for(int i = 0; i < n; i++) { //遍历链数组
            ListNode p = lists[i], q1, q2;
            while(p != null) { //遍历每个链
                q1 = resRoot.next; //前指针
                q2 = resRoot; //后指针
                while(q1 != null) { //寻找位置
                    if(q1.val == p.val || q1.val > p.val) break;
                    q1 = q1.next;
                    q2 = q2.next;
                }
                q2.next = new ListNode(val: p.val, next: q1); // ... -> q2 -> new ListNode(this.val = p.val) -> q1 -> ...
                p = p.next;
            }
        }
        return resRoot.next; //返回根的下一个元素
    }
}