Contest 168

通过：4/4 排名：61 / 1552 1:08:39 1WA

No.5291 统计位数为偶数的数字

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

示例 1：

输入： nums = [12,345,2,6,7896]
输出： 2
解释：
12 是 2 位数字（位数为偶数）
345 是 3 位数字（位数为奇数）
2 是 1 位数字（位数为奇数）
6 是 1 位数字 位数为奇数）
7896 是 4 位数字（位数为偶数）
因此只有 12 和 7896 是位数为偶数的数字

示例 2：

输入： nums = [555,901,482,1771]
输出： 1
解释：
只有 1771 是位数为偶数的数字。

提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 10^5

嗯，水题。（但是大佬一行代码。。）
时间复杂度：$O(n)$

1
2
3
4
5
6
7

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            if len(str(num))%2 == 0:
                ans+=1
        return ans

Contest No.15 Biweekly

通过：4/4 排名：43 / 797 0:46:11 1WA

No.5126 有序数组中出现次数超过25%的元素

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

我很认真地按照题目意思去做的。。。后来翻看别人的答案恍然大悟，其实就是求众数，可以用collections.Counter() 加上 most_common就可以了

时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        a = len(arr)//4
        ln = 9999999999
        n = 0
        for num in arr:
            if ln == num:
                n+=1
            else:
                ln = num
                n = 1
            if n>a:
                return ln

1
2
3
4

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        c = collections.Counter(arr)
        return c.most_common(1)[0][0]

Contest 167

通过：4/4 排名：107 / 1534 1:43:12 5WA

No.5283 二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

输入：head = [0]
输出：0

示例 3：

输入：head = [1]
输出：1

示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5：

输入：head = [0,0]
输出：0

提示：

• 链表不为空。
• 链表的结点总数不超过 30。
• 每个结点的值不是 0 就是 1。

嗯，水题。
时间复杂度：$O(n)$

1
2
3
4
5
6
7

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        ans = 0
        while head!=None:
            ans = ans*2+head.val
            head = head.next
        return ans

C用了很久了，但是也没有说很系统平铺的整体看过，一直是用什么会什么，不用什么就过去了。既然C已经被我当做是一门已经掌握的语言，所以就重新扫一遍C里面不那么面熟的东西或者理解有偏差的东西，当做是个记录以备复习使用，也可以对C打个结了。

auto && register && static

怎么也没想到会把这三个放在一起，一个是C++中常用的声明类型的关键字，一个没见过的，和一个还算常用的，这里主要理解的偏差还是在 auto 上。

在C++中，auto作为一种自动判断变量类型的定义存在，比如当我使用 auto c = 10; 去定义 c 这个变量的时候，是和 int c = 10; 的作用是一样的，这样可以节省很多去考虑这个变量具体是什么类型以及大量的敲字母的时间，还可以避免一些打字错误，比如 vector<map<int,string>>::iterator a = 这种东西可以直接 auto a = 还是挺爽的。顺便这里提一嘴，C++中的 auto 后面必须赋值，否则编译器不知道到底要初始化成什么类型的。

很早之前就想去日本转一转，前一段时间终于算是忙中偷闲出去玩了一圈，回来之后也来整理整理出去游玩的过程，也给小伙伴们一个参考。我也是第一次出国玩，所以有没有说明好的地方也希望小伙伴们能提出来~~

准备工作

这次出行去了京都、宇治、奈良、大阪，去的城市不是很多，这次单独介绍一下出行的准备工作，方便想去的小伙伴单独查阅，下一篇会介绍去的景点，再给大家推荐一下好景点和好吃的！

最近在使用进行MATLAB进行一些计算的时候因为计算时间实在是太长了（五天。所以开始考虑进行算法优化，就在这时无意间看到了系统的CPU占用率，what？25%哈哈哈哈哈或或或或或或或或，matlab个ZZ。于是想起了parfor这回事，算法用的是动态规划算法，但是在每个递推过程中也要计算$2000 \times 2000$个循环，正好可以用并行计算，perfect，条件允许，直接开始！

要啥简介，直接开干

来看一个简单的不能再简单的例子，我们用for将一个数组乘以2

1
2
3
4
5

n = 1000;
a = rand(n,1);
for i=1:n
    a(i) = a(i) * 2;
end

试着跑一下，没什么问题（这要有啥问题可以不活了），看一下运行时间

1

Elapsed time is 0.000034 seconds.

一个n x 1大小的随机数组，然后把其中每个数乘以二，下面就是改成parfor并行计算的

忘记前一段时间某个时候提到某个事情了，想起来纠错这回事，大概回忆了一下是一个挺有意思的过程，索性重新搜索了一下复习了一遍，把大概原理在这里写一写，权当记录

从小时候说起

小时候妈妈教导我……咳咳，打开方式不太对。

小的时候我的娱乐活动比较少，空闲时间基本上都是在看书中度过的，其中有一本书我记得很清楚，叫做《数学游戏》，里面是各种数学题，很多有趣很多有意思的题目，直到现在仍然对其中的题目印象非常深刻，还有再读一遍的冲动。

好，进入正题，这本书中有这样一个题目：

国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中一桶被下了毒。为了确定哪桶是毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。问：至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？

以我小学生的智力水平，书中的题目大部分都是这个难度，我也都是直接放弃看答案了，这里我们还是稍微给自己一点时间稍微思考一下：

Contest 131

通过：4/4 排名：44/917 1:10:59 2WA

这次竞赛整体感觉难度一般，基本看到题目后直接就有思路，看了看其他人的做法，基本上思路一样。但是依旧~错的多、逻辑复杂、做题的时候感觉考虑清楚了但是做的时候细节还是有没考虑到的地方。速度嘛，不要求了，目前的目的还是能做出来吧。

No.5016 删除最外层的括号

1WA

一开始使用迭代器进行 string 的遍历，然后在测试的时候，有时候测试结果是正确的，有时候是 out of range，最后也没有发现是什么原因，就先去做剩下三个题了，回来之后改成循环数字下标就好了，可能是最后一个位置超出了 string 的长度，以后还是多用下标比较合适，除非循环内要做的工作比较简单。

Contest 132

通过：3/4 排名：99/1047 0:59:44 1WA

最后一道题规定时间内没有做出来，超时7分钟做出来的，无错误提交（似乎）。

这次竞赛感觉看完题都比较虚，但是其实做题之后的效果比预想的好，虽然最后一道题规定时间内没有做出来，但是感觉可以接受，也是很久没有出过 hard 的题目了，这次的 hard 题目实现的相当的。。。。复杂且乱，但是能做出来就是好事。

No.5024 除数博弈

1WA

看到这个题，感觉可能是动态规划后，第一个想法：动态规划都是简单的题了啊！

是的，这道题还花了整整20分钟才做出来，感觉其中十分钟浪费在了不可置信上和另外一些事情上。。。这次做竞赛太不专心了，批评一下自己，竞赛还是要好好做的。

实现思路上没啥可说的，就是动态规划的思路，从小到大依次遍历所有约数对应的N-x的值，所有约数全部为 true 的时候，这时无论先手做如何操作，对方都是必胜的情况，所以这时的 N 为 false ，其余所有情况均为 true ，只需要在每一步操作时将 N 的值变为对应的 false 的 N-x 的值即可。