---
cid: 112
title: 周赛157
slug: 112
date: 2019/10/06 12:19:00
updated: 2019/10/13 08:50:59
status: publish
author: harumonia
categories:
  - 源流清泉
  - leetcodeの解题日志
tags:
  - 算法
  - LeetCode
  - 周赛
noThumbInfoStyle: default
outdatedNotice: no
reprint: standard
thumbChoice: default
thumbStyle: default
hidden: false
---

## 结果

![res](https://harumona-blog.oss-cn-beijing.aliyuncs.com/old_articles/1437205549.png?Expires=1602302340&)

只做了三题。。。
前两题使用哈希表解，不过第一题应该有更简单的数学解法，不过当时时间紧迫，就没有多去考虑。
第三题是深搜。。。好久没写深搜了，卡了好久，不过还好最后做出来了= =

## 玩筹码

> 数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
>
> 你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
>
> 将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
> 将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
> 最开始的时候，同一位置上也可能放着两个或者更多的筹码。
>
> 返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

```c++
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        map<int,int> ma;
        for(int i=0;i<chips.size();i++){
            ma[chips[i]]++;
        }

        int qi = 0,ou = 0,qi_max = 0,ou_max = 0;
        for(const auto& m:ma){
            if(m.first % 2 == 0){
                if(m.second > ou_max) ou_max = m.second;
                ou += m.second;
            }
            else{
                if(m.second > qi_max) qi_max = m.second;
                qi += m.second;
            }
        }

        if(ma.size() > 2){
            if(qi-qi_max > ou-ou_max)
                return ou;
            else
                return qi;
        }
        else{
            return min(qi,ou);
        }
    }
};
```

## 最长定差子序列

> 给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。

```c++
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        map<int,int> ma;
        int max_len = 1;
        for(auto ar:arr){
            if(ma[ar-difference] != 0){
                ma[ar] = ma[ar-difference]+1;
                if(max_len < ma[ar]) max_len = ma[ar];
            }
            else if(ma[ar] != 0){
                continue;
            }
            else{
                ma[ar]++;
            }
        }
        return max_len;
    }
};
```

## 黄金矿工

> 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m \* n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
>
> 为了使收益最大化，矿工需要按以下规则来开采黄金：
>
> 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
> 矿工每次可以从当前位置向上下左右四个方向走。
> 每个单元格只能被开采（进入）一次。
> 不得开采（进入）黄金数目为 0 的单元格。
> 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

```c++
class Solution {
public:
    int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}},m,n;
    vector<vector<bool>> visited;
    int res_fin;

    int getMaximumGold(vector<vector<int>>& grid) {
        m=grid.size();
        if(m==0){
            return 0;
        }
        n=grid[0].size();
        visited=vector<vector<bool>>(m,vector<bool>(n,false));

        res_fin = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){

                if(grid[i][j] == 0) continue;
                recursion(grid,i,j,grid[i][j]);
            }
        }
        return res_fin;
    }

    void recursion(vector<vector<int>>& grid,int startx,int starty,int res){
        visited[startx][starty]=true;

        if(res_fin < res) res_fin = res;

        for(int i=0;i<4;i++){
            int newx=startx+d[i][0];
            int newy=starty+d[i][1];
            if(judge(newx,newy) && grid[newx][newy]!=0 && !visited[newx][newy]){
                recursion(grid,newx,newy,res+grid[newx][newy]);
            }
        }

        visited[startx][starty]=false;

        return;
    }

    bool judge(int x,int y){
        return x>=0 && y>=0 && x<m && y<n;
    }
};
```

## 统计元音字母序列的数目

没时间做的第四题啊 残念

> 给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
>
> 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
> 每个元音 'a' 后面都只能跟着 'e'
> 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
> 每个元音 'i' 后面 不能 再跟着另一个 'i'
> 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
> 每个元音 'u' 后面只能跟着 'a'
> 由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

```c++
int countVowelPermutation(int n) {
    long a = 1, e = 1, i = 1, o = 1, u = 1;
    long res = 0, mod = 1e9+7;
    for(int j = 1;  j < n; j++) {
        long a1, e1, i1, o1, u1;
        a1 = (e + i + u) % mod;
        e1 = (a + i) % mod;
        i1 = (e + o) % mod;
        o1 = i;
        u1 = (i + o) % mod;
        a = a1, e = e1, i = i1, o = o1, u = u1;
    }
    res = (a + e + i + o + u) % mod;
    return res;
}
```

### 吐槽

- 这道题可以说非常的鬼畜，不知道官方出于什么想法把它安排在第四条归类为困难。。。

- 为什么对 10^9+7 取模？再查了一些资料后，得出结论
    1. 1000000007 是一个质数（素数），对质数取余能最大程度避免冲突～
    2. int32 位的最大值为 2147483647，所以对于 int32 位来说 1000000007 足够大
    3.int64 位的最大值为 2^63-1，对于 1000000007 来说它的平方不会在 int64 中溢出
      所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对 1000000007 取模，再保存在 int64 里面不会溢出
- 这一题还有进阶的快速幂解法，没有听说过，研究研究。

## 后记

于是周赛打掉了我好不容易攒出来的一页绿%>\_<%

![p1](https://harumona-blog.oss-cn-beijing.aliyuncs.com/old_articles/2855058512.png?Expires=1602302380&)