在十分紧张的情况下幸运完成了P2，于是结合考试中做的一些笔记与大家略微分享我的思路

由于大家编写MIPS代码时主要以翻译为主，且选择工具链不一（指各种语言），所以本文将只展示思路，以伪代码形式呈现，并将我遇到的MIPS难点单独列出

和《算法设计与分析》考试是笔试一个道理www

T1：P2_L2_merorder_2023

Main Idea

由于两个序列均为已经排好序的不下降数组，所以在编写程序时只需要遍历两个数组一遍，将较小者逐一合入新数组即可

Pseudo Code

输入：两个长度分别为m，n的不下降数组a[] b[]

输出：一个长度为(m+n)的数组ans[]，为所求合并后的数组
$$
\begin{aligned}
&i\leftarrow 0;\
&j\leftarrow 0;\
&while\ (i<n\ &&\ j<m)\ do\
&\quad while\ (A[i]<=B[j])\ do\
&\qquad print\ (A[i++]);\
&\quad end\
&\quad while\ (A[i]>B[j])\ do\
&\qquad print\ (B[j++]);\
&\quad end\
&end\
&while\ (i<n)\ do\
&\quad print(A[i++]);\
&end\
&while\ (j<m)\ do\
&\quad print(B[j++]);\
&end\
\end{aligned}
$$
复杂度分析：i和j需要遍历完两个数组一遍，所以复杂度为O(n+m)

注意点：

  1. 这种写法由于是while套while，会导致lable上增加难度，建议提前在代码中为不同的while注释不同的名字，方便程序写作，如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(){
    //while1
        while()/*do something*/;
        //while2
        while()/*do something*/;
    	//while3
    }
    while()/*do something*/;
    //while4
    while()/*do something*/;
    //while5

  2. 在实际写作中，因为不考虑效率要求，也可以将内层循环中的while改为if，设置标签时会更简单一些

  3. 本题数据范围较小，所以也可以使用类似计数排序的方法，期望复杂度和遍历两个数组一致

  4. 说出来给大家乐呵一下，在下.space忘乘4了，de了好一会儿🙏

T2：P2_L1_asteroids_2023

题目编号 1122-1162

本题的代码已经给出来啦~而且方法很巧妙，对着翻译就好！

甚至可以不看题面

没有想到可以补充的地方，过~

T3：LeetCode: 390. 消除游戏

为大家找到了代码的提交入口（误）

除用标程的递归外（标程的参数可以减少至一个），本题也可以使用位运算完成

Main Idea

将这n个数标记为0…n-1

若当前为奇数轮，则删除操作为从0开始，隔一个删除一个，可以等效为“删除所有二进制末尾为0的数字“，答案当前位的二进制赋1

若当前为偶数轮，则删除操作为从最后一个数开始，隔一个删除一个，可以等效为”删除所有二进制下末尾数与最大数末位数相同的数字“，答案当前位的二进制赋最大数末位数的反

换种说法，就是：
$$
(ans)_2[i]=\left{
\begin{aligned}
&1&i\equiv 0(mod\ 2)\
&(n)_2[i]&i\equiv 1(mod\ 2)\
\end{aligned}
\right.
$$
注意，在上式中：

  1. i代表的是二进制第i位，奇数轮的i为偶数，偶数轮的i为奇数

  2. 编号从0开始，所以
    $$
    (n)_2[i]==\sim (n-1)_2[i]
    $$

我们的编号是从0开始的，最后别忘了将答案加一

Pseudo Code1

$$
\begin{aligned}
&ans\leftarrow 0;\
&for\ i\ from\ 0\ to\ \log(n)-1\ do\
&\quad if\ (i&1)\ then\
&\qquad ans\leftarrow ans\ |\ (2^i\ &\ n);\
&\quad else\
&\qquad ans\leftarrow ans\ |\ 2^i;\
&\quad endif\
&end\
&ans\leftarrow ans+1;\
&print(ans);
\end{aligned}
$$

复杂度分析：i从0循环到logn-1，整体复杂度为O(log)

Pseudo Code2

或者我们换一种实现方法，将for循环拆开
$$
\begin{aligned}
&mod\leftarrow 2^{[\log(n)]};\
&ans\leftarrow (n\ |\ 1431655765);\
&ans\leftarrow ans\mod mod;\
&ans\leftarrow ans+1;\
&print(ans);\
\end{aligned}
$$
其中：

  • mod为n二进制下最高位1对应的数

  • $$
    1431655765=2^0+2^2+…2^{2k}
    $$

复杂度分析：O(1)

(家人们谁懂啊 把nlog的朴素方法优化到O(1)，真的是一件很酷的事~)