LeetCode157周周赛

赛题链接：https://leetcode-cn.com/contest/weekly-contest-157

赛题一：玩筹码

数轴上放置一些筹码，这些筹码的位置记录存放在数组chips中。chips[i]表示在第chips[i]这个位置有一个筹码。值得注意的是，可能有多个chips[i]值相同，表示在数组同一位置上有多个筹码。

现在对数轴上的任意筹码做以下两个动作无限次（任意次数，可以0次）：

1.将筹码向左或向右移动一个位置，记代价为1。

2.将筹码向左或向右移动两个位置，记代价为0。

返回将所有筹码移动到同一位置需要的最小代价

思考如下：

• [1] 任意指定一个“标杆”位置，所有筹码向标杆集中转移，则由上述规则知道，与“标杆”位置相隔位置数为偶数的筹码代价为0。相隔位置数为奇数的筹码都可以花费0代价集中到“标杆”位置的左一位/右一位。
• [2] 则实际上，标杆位置设置在哪与最终结果无关，寻找最小代价其实就是判断奇数位置上还是偶数位置上的筹码个数更少。

class Solution {
	vector<int>::iterator it;
	int evensum=0,oddsum=0;
public:
    int minCostToMoveChips(vector<int>& chips) {
    	for(it=chips.begin();it<chips.end();it++){
            if(*it%2==0)
                evensum++;
            else
                oddsum++;
        }
		return min(evensum,oddsum); 
    }
};
           

赛题二：最长定差子序列

给定一个数组arr，保持顺序不变。给定一个整数difference，现在让你找出arr中相邻元素之差等于difference的子序列，并返回其中最长的子序列的长度。

思考如下：

思路一暴力法

• 用两个迭代器，第一个迭代器遍历数组，用来选定各个子序列的首元素；第二个迭代器基于第一个迭代器选定首元素的情况下”寻找“对应的子序列。

  结果：不出意料的TLE了

思路二 分割子序列

• 基于上述超时，可以考虑在找到子序列的同时，将子序列从原序列中分割出来存进一个新数组，比较并返回新数组的最大长度。

  结果：方法有漏洞。

举例：5，1，7，5，3，1 difference=-2

最大长度应该为4

解释：7，5，3，1

思路二中在对第一个5分割子序列时将5，3，1分割出序列，即分割成了三个序列:5,3,1与1与7,5

（可以进一步优化）

思路三：动态规划

class Solution {
	int leng=0; 
	map<int,int> dp;
	public:
	int longestSubsequence(vector<int>& arr, int difference) {
		int d=difference;
    	for(int i=0;i<arr.size();i++){
			dp[arr[i]]=dp[arr[i]-d]+1;
			leng=max(leng,dp[arr[i]]);
			}
		return leng;
    }
};
           

赛题三：黄金矿工

很明显的dfs，这里日常参考王同学的代码：

class Solution {
public:
    int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
    void dfs(vector<vector<int>>& grid, int x, int y, int tmp, int& value, vector<vector<bool>>& visit){  // tmp 不能加引用
        if(grid[x][y]==0) return ;
        value = max(value,tmp += grid[x][y]);
        visit[x][y] = true;
        
        for(int i=0;i<4;i++){
            int tmpx = x+dx[i],tmpy = y+dy[i];
            if(tmpx<0||tmpx>=grid.size()||tmpy<0||tmpy>=grid[0].size()) continue; // 注意等号
            if(grid[tmpx][tmpy]==0||visit[tmpx][tmpy]) continue;
            dfs(grid,tmpx,tmpy,tmp,value,visit);
        }
        visit[x][y] = false;
    }
    int getMaximumGold(vector<vector<int>>& grid) {
        int m=grid.size(), n=grid[0].size(), result = 0;
        // bool visit[m][n]={0};
        vector<vector<bool>> visit(m,vector<bool>(n,false)); // init
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=0){
                    dfs(grid,i,j,0,result,visit);
                }
            }
        }
        return result;
    }
};

           

赛题四：统计元音字母序列的数目

略

总结：发现自己最基本的算法还是不扎实。

例如dfs，dp都只是有思路，缺少训练。