笔试-音乐

发表于 2017-10-15 | 更新于 2020-09-15

题意

迈克喜欢在火车旅行的时候用手机听音乐，他有N首歌在手机里，在整个火车途中，他可以听P首歌，所以他想产生一个播放表产生P首歌曲，这个播放表的规则是：

每首歌都要至少被播放一次
在两首一样的歌中间，至少有M首其他的歌

迈克在想有多少种不同的播放表可以产生，那么给你N,M,P，你来算一下，输出结果取1000000007的余数。

输入:

输入N,M,P
N范围在1到100
M范围在0到N
P范围在N到100

输出 :

输出结果mod 1000000007的余数
样例输入
1 0 3
样例输出
1
提示
其他样例
1 1 3
0

2 0 3
6

50 5 100
222288991

题解

DP[i][j]表示前 i 首歌共使用了 j 首不同的歌。
考虑第i首歌，如果取前面已经用过的歌，那么可选的歌有（j-m）首歌，如果选用前面没用过的歌，那么可选的歌有（n-j+1）首歌可选。所以

dp[i][j] = dp[i-1][j] * (j-m) + dp[i-1][j-1] * (n-j+1)

，注意int会超出范围。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 105;
const int MOD = 1e9+7;
LL dp[MAX][MAX];

int main(){
    int n,m,p;
    while(cin>>n>>m>>p){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=p;i++){
            dp[i][0] = 0;
        }
        for(int j=1;j<=n;j++){
            dp[0][j] = 0;
        }
        dp[0][0] = 1;
        for(int i=1;i<=p;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = (dp[i-1][j-1]*(n-j+1))%MOD;
                if(j>m) dp[i][j] = (dp[i][j] + (dp[i-1][j]*(j-m))%MOD)%MOD;
            }
        }
//        for(int i=0;i<=p;i++){
//            for(int j=0;j<=n;j++){
//                cout<<dp[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        cout<<dp[p][n]<<endl;
    }
    return 0;
}

笔试-化简字符串

发表于 2017-10-12 | 更新于 2020-09-15

题目

滴滴笔试的题目，暂时没挂到牛客上。

题意

给出一个字符串，要求化简字符串，
如: ‘bcabcabc’ 这样的字符串会被化简为 ‘3[abc]’，
但是如果化简后的字符串比原串长度要长，则不化简。
化简可以嵌套，
比如：’abcdabcdeabcdabcdexyabcabcabcds’可以化简为’2[2[abcd]e]xy2[abc]ds’。
输出化简后的长度。

题解

枚举每个子串，求出每个子串后面连续相同的个数，然后替换成相应的简化形式。
一个字符串不一定只化简一次，所以加一层循环直到不能化简为止，取最短长度即可。

#include <bits/stdc++.h>
using namespace std;

string intToStr(int num){
    string ans ="";
    while(num){
        ans += num%10+'0';
        num /= 10;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}


string getSimple(string str){
    if(str.size() < 5) return str;

    for(int i=0;i<str.size();i++){
        for(int j=i+1;j<str.size();j++){
            string sub = str.substr(i,j-i);
            int start = j , reCount = 0;
            while(str.find(sub,start)==start){
                reCount++;
                start += j-i;
            }
            if(reCount==0) continue;
            string countStr = intToStr(reCount+1);
            if(reCount*(j-i)<countStr.size()+2) continue;
            string res = str.substr(0,i);
            res+=countStr;
            res+='[';
            string next = getSimple(sub);
            res+=next;
            res+=']';
            res+= str.substr(j+reCount*(j-i),str.size()-j+reCount*(j-i));
            return res;
        }
    }
    return str;
}

int main(){
    string str;
    cin>>str;
    int mixLen = str.size();
    string preStr = str;
    string ansStr = str;
    while(true){
        string ret = getSimple(preStr);
//        cout<<ret<<endl;
        if(ret == preStr) break;
        else preStr = ret;
        if(mixLen > ret.size()){
            mixLen = ret.size();
            ansStr = ret;
        }
    }
    cout<<ansStr<<endl;
    cout<<mixLen<<endl;
    return 0;
}

C++ 常量指针和指针常量

发表于 2017-09-28 | 更新于 2020-09-15

原文链接：
http://www.cnblogs.com/beanmoon/archive/2012/09/23/2698987.html
先看一段代码：

char greeting[] = “Hello”;  
char* p = greeting; //non-const pointer,non-const data  
const char* p = greeting; //non-const pointer,const data;  
char* const p = greeting;//const pointer,non-const data;  
const char* const p = greeting; //const pointer,const data;

关于定义的阅读，一直以为这段解释很不错了已经，即以和const的相对位置来判断：
const语法虽然变化多端，但并不莫测高深。如果关键字const出现在左边，表示被指物是常量；如果出现在右边，表示指针自身是常量；如果出现在两边，表示被指物和指针两者都是常量。
如果被指物是常量，有些程序员会将关键字const写在类型之前，有些人会把它写在类型之后、*之前。两种写法的意义相同，所以下列两个定义相同：

1 2	const int* w; int const* w;

后来在百度知道上看到另一段挺有意思的解释：
其实很简单，const和*的优先级相同
且是从右相左读的，即“右左法则”
其实const只是限定某个地址存储的内容不可修改
比如:

int *p;         //读作p为指针，指向int，所以p为指向int的指针
int *const p;   //读作p为常量，是指针，指向int，所以p为指向int的常量指针， p不可修改
int const *p;   //p为指针，指向常量，为int，所以p为指向int常量的指针， *p不可修改
int ** const p; //p为常量，指向指针，指针指向int，所以p为指向int型指针的常量指针，p不可修改
int const**p;   //p为指针，指向指针，指针指向常量int，所以p为指针，指向一个指向int常量的指针， **p为int，不可修改
int * const *p; //p为指针，指向常量，该常量为指针，指向int，所以p为指针，指向一个常量指针，*p为指针，不可修改
int ** const *p;//p为指针，指向常量，常量为指向指针的指针，p为指针，指向常量型指针的指针，*p为指向指针的指针，不可修改
int * const **p;//p为指针，指向一个指针1，指针1指向一个常量，常量为指向int的指针，即p为指针，指向一个指向常量指针的指针， **p为指向一个int的指针，不可修改

笔试-射击游戏

发表于 2017-09-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/d3f26db0325444078717cc802e0056d8

题意

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(0,0),平面上有n只怪物,每个怪物有所在的坐标(x[i], y[i])。小易进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。
小易是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物同时向任意同一方向移动任意同一距离
2、让平面内的所有怪物同时对于小易(0,0)旋转任意同一角度
小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。
小易想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮小易。

如样例所示:

所有点对于坐标原点(0,0)顺时针或者逆时针旋转45°,可以让所有点都在坐标轴上,所以5个怪物都可以消灭。

输入描述:

输入包括三行。
第一行中有一个正整数n(1 ≤ n ≤ 50),表示平面内的怪物数量。
第二行包括n个整数x[i](-1,000,000 ≤ x[i] ≤ 1,000,000),表示每只怪物所在坐标的横坐标,以空格分割。
第二行包括n个整数y[i](-1,000,000 ≤ y[i] ≤ 1,000,000),表示每只怪物所在坐标的纵坐标,以空格分割。

输出描述:

输出一个整数表示小易最多能消灭多少只怪物。

输入例子1:

5
0 -1 1 1 -1
0 -1 -1 1 1

输出例子1:

5

题解

题目其实就是求两条垂直的直线上最多可以有多少个点。
两个for，两个点A，B确定一条直线，第三个for，第三个点C通过另一条直线，第四个for，对于剩下的n-3个点，如果在AB确定的直线上或者与C点构成的直线与AB垂直均可以。第四个for结束后，更新一次最大值。
最后输出最大值即可。

#include <bits/stdc++.h>
using namespace std;
double eps=1e-9;
int sgn(double x)
{
    if(x<-eps) return -1;
    if(x>eps) return 1;
    return 0;
}
double cross(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;
}
 
double dot(int x1,int y1,int x2,int y2)
{
    return x1*x2+y1*y2;
}
 
bool point_on_segment(int x1,int y1,int x2,int y2,int px,int py)
{
    return sgn(cross(x1-px,y1-py,x2-px,y2-py))==0;
}
 
bool isVertical(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
    return sgn(dot(x1-x2,y1-y2,x3-x4,y3-y4))==0;
}
 
int main()
{
    int n;
    cin>>n;
    vector<int> x(n),y(n);
    for(int i=0; i<n; i++)
        cin>>x[i];
    for(int i=0; i<n; i++)
        cin>>y[i];
    int mmax = 0;
    if(n<4) mmax = n;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            for(int p=0; p<n; p++)
            {
                if(p==i||p==j) continue;
                int ans = 3;
                for(int q=0; q<n; q++)
                {
                    if(q==i||q==j||q==p) continue;
                    if(point_on_segment(x[i],y[i],x[j],y[j],x[q],y[q])||
                       isVertical(x[i],y[i],x[j],y[j],x[p],y[p],x[q],y[q]))
                        ans++;
                }
                mmax= max(mmax,ans);
            }
        }
    }
    cout<<mmax<<endl;
    return 0;
}

笔试-合唱

发表于 2017-09-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/fddf64d5757e41ec93f3ef0c0a10b891

题意

小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。
对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。
现在要对把这n个音调分配给小Q或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。
如样例所示: 小Q选择演唱{5, 6}难度为1, 牛博士选择演唱{1, 2, 1}难度为2,难度之和为3,这一个是最小难度和的方案了。
输入描述:
输入包括两行,第一行一个正整数n(1 ≤ n ≤ 2000) 第二行n个整数v[i](1 ≤ v[i] ≤ 10^6), 表示每个音调。

输出描述:

输出一个整数,表示小Q和牛博士演唱最小的难度和是多少。

输入例子1:

5
1 5 6 2 1

输出例子1:

3

题解

设DP[i][j]（j>i）为两个人最近唱的音调分别为第i个和第j个。
状态转移：
如果i==j-1,也就是换人演唱的时候，DP[i][j]也就是DP[j-1][j]的值应该为DP[k][j-1]+abs(v[k][j]),k为这个人上次演唱的音调位置。
如果i<j-1,也就是最近演唱的人继续演唱当前字符，DP[i][j]的值应该为DP[i][j-1]+abs(v[j]-v[j-1])。
最后结果应该DP[i][n],1<=i<n中的最小值。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    vector< vector<int> > dp(n+1,vector<int>(n+1));
 
    for(int i=1;i<=n;i++){
        if(i>2) dp[i-1][i] = dp[i-2][i-1] + abs(v[i-1]-v[i-2]);
    }
 
//    for(int i=0;i<=n;i++){
//        for(int j=0;j<=n;j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
 
    for(int j=1;j<=n;j++){
        for(int i=1;i<j-1;i++){
            dp[i][j]=dp[i][j-1]+abs(v[j]-v[j-1]);
            dp[j-1][j]=min(dp[j-1][j],dp[i][j-1]+abs(v[i]-v[j]));
        }
    }
    int ans = INT_MAX;
    for(int i=1;i<n;i++){
        ans=min(ans,dp[i][n]);
    }
    cout<<ans<<endl;
    return 0;
}

笔试-最长公共子括号序列

发表于 2017-09-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/504ad6420b314e5bb614e1684ad46d4d

题意

一个合法的括号匹配序列被定义为:

空串””是合法的括号序列
如果”X”和”Y”是合法的序列,那么”XY”也是一个合法的括号序列
如果”X”是一个合法的序列,那么”(X)”也是一个合法的括号序列
每个合法的括号序列都可以由上面的规则生成
例如””, “()”, “()()()”, “(()())”, “(((()))”都是合法的。
从一个字符串S中移除零个或者多个字符得到的序列称为S的子序列。
例如”abcde”的子序列有”abe”,””,”abcde”等。
定义LCS(S,T)为字符串S和字符串T最长公共子序列的长度,即一个最长的序列W既是S的子序列也是T的子序列的长度。
小易给出一个合法的括号匹配序列s,小易希望你能找出具有以下特征的括号序列t:
1、t跟s不同,但是长度相同
2、t也是一个合法的括号匹配序列
3、LCS(s, t)是满足上述两个条件的t中最大的
因为这样的t可能存在多个,小易需要你计算出满足条件的t有多少个。

如样例所示: s = “(())()”,跟字符串s长度相同的合法括号匹配序列有:
“()(())”, “((()))”, “()()()”, “(()())”,其中LCS( “(())()”, “()(())” )为4,其他三个都为5,所以输出3.

输入描述:

输入包括字符串s(4 ≤ |s| ≤ 50,|s|表示字符串长度),保证s是一个合法的括号匹配序列。

输出描述:

输出一个正整数,满足条件的t的个数。

输入

(())()

输出

3

题解

长度相同的不同的匹配括号序列的LCS最长肯定为N-1,枚举每个左括号，将该左括号移动到其他位置，使得序列仍然匹配，统计即可，注意会有重复，扔到set中去重。

#include<bits/stdc++.h>
using namespace std;
  
bool valid(string str){
    stack<int> pos;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){
            pos.push(i);
        }else if(pos.empty()){
            return false;
        }else{
            pos.pop();
        }
    }
    return pos.empty();
}
set<string> ans;
  
int main()
{
    string str;
    cin>>str;
    int maxLen = 0;
    for(int i=0;i<str.size();i++){
        string afterErase(str);
        afterErase.erase(i,1);
        for(int j=0;j<afterErase.size();j++){
            if(j==i) continue;
            string afterInsert(afterErase);
            afterInsert.insert(j,1,str[i]);
            if(valid(afterInsert)&&afterInsert!=str){
                ans.insert(afterInsert);
            }
        }
    }
    cout<<ans.size()<<endl;
    return 0;
}

笔试-游历魔法王国

发表于 2017-09-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/f58859adc39f4edc9cd8e40ba4160339

题意

魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。
小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。

输入描述:
输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 50)和L(1 ≤ L ≤ 100),表示城市个数和小易能行动的次数。
第二行包括n-1个整数parent[i](0 ≤ parent[i] ≤ i), 对于每个合法的i(0 ≤ i ≤ n - 2),在(i+1)号城市和parent[i]间有一条道路连接。

输出描述:

输出一个整数,表示小易最多能游历的城市数量。

输入例子1:

5 2
0 1 2 3

输出例子1:

3

题解

求出树上每个节点的最长链长度，记录最长的长度maxLen。
如果L<=maxLen,那么显然结果应该为L+1；
如果L>maxLen,那么表示存在需要走回头路的情况，我们肯定不希望走到最后在返回去消耗余下的步数，而是可以在最长链的中途的子链上消耗掉这些剩余的步数，假设剩余res=L-maxLen,那么可以增加的城市应该是res/2+1。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n,l;
    cin>>n>>l;
    vector<int> parent(n);
    for(int i=1;i<n;i++){
        cin>>parent[i];
    }
    int maxLen = 0;
    vector<int> dp(n);
    for(int i=1;i<n;i++){
        dp[i]=dp[parent[i]]+1;
        maxLen = max(maxLen,dp[i]);
    }
    if(l<=maxLen){
        cout<<l+1<<endl;
    }else{
        cout<<min(n,maxLen+(l-maxLen)/2+1)<<endl;;
    }
    return 0;
}

leetcode 678. Valid Parenthesis String

发表于 2017-09-19 | 更新于 2020-09-15

题目

https://leetcode.com/problems/valid-parenthesis-string/description/

题意

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
An empty string is also valid.

判断系列是否是合法的括号序列，其中’*’可以替代’)’或者‘(’或者空。

题解

暴力求解

对每个’‘都替换为三种情况递归判断，但是会超时。时间复杂度O（N3^N）。


class Solution {
private:
    char place[3] = {'(',')','*'};
private:
    bool valid(string str) {
        int cnt = 0;
        for(int i=0;i<str.size();i++){
            if(str[i]=='(') cnt++;
            else if(str[i]==')') cnt--;
        }
        return cnt==0;
    }
    bool dfs(string s,int index){
        if(index==s.size()){
            return valid(s);
        }else if(s[index]=='*'){
            for(int k=0;k<3;k++){
                s[index] = place[k];
                if(dfs(s,index+1))
                    return true;
            }
        }else{
            return dfs(s,index+1);
        }
    }
public:
    bool checkValidString(string s) {
        return dfs(s,0);
    }
};

设dp[i][j] 为true，当且仅当s[i], s[i+1], …, s[j]是合适的。
状态转换方程为：如果存在i+1<=k<=j使得s[i][k]为true且s[k+1][j]为true。

class Solution {
private:
    vector< vector<int> > dp;
public:
    bool checkValidString(string s) {
        if(s.size()==0) return true;
        dp.resize(s.size(),vector<int>(s.size()));

        for(int i=0;i<s.size();i++)
            if(s[i]=='*') dp[i][i] = true;

        for(int size = 1;size<s.size();size++){
            for(int i=0;i+size<s.size();i++){
                if(s[i]=='('||s[i]=='*'){
                    for(int k=i+1;k<=i+size;k++){
                        if((s[k]==')'||s[k]=='*')&&
                        (k==i+1||dp[i+1][k-1])&&
                        (k==i+size||dp[k+1][i+size]))
                            dp[i][i+size] = true;
                    }
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

时间复杂度O(N^3)，空间复杂度O(N^2)。

贪心

依次扫描，维护两个值，cmin代表，最少的可能不匹配的左括号，cmax代表最多的可能不匹配的左括号数量。
显然，如果当前字符为‘(’,cmin，cmax都加1；
如果当前字符为‘)’，cmin，cmax都减1，但是cmin至少应该为0；如果cmax小于0，标识右括号数量大于左括号，不匹配。
如果当前字符为‘*’，如果替换为‘(’,cmax加1，如果替换为’)’，cmin减1，同样至少为0。
最后判断cmin是否为0.

class Solution {
public:
    bool checkValidString(string s) {
        int cmin = 0,cmax = 0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                cmin++;
                cmax++;
            }
            else if(s[i]==')'){
                cmin = max(cmin-1,0);
                cmax--;
            }else{
                cmax++; //*=left
                cmin=max(cmin-1,0); //*=right
            }
            if(cmax<0) return false;
        }
        return cmin==0;
    }
};

时间复杂度O(N)，空间复杂度O(1).

leetcode 680. Valid Palindrome II

发表于 2017-09-19 | 更新于 2020-09-15

题目

https://leetcode.com/problems/valid-palindrome-ii/description/

题意

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

给出一一个非空的字符串，判断是否能够删除0个或者一个字符使得字符串变为回文。

题解

暴力。判断原串是否回文，如果不是，遍历每个字符，判断删掉该字符能否构成回文。时间复杂度O(N^2) ,超时。
因为最多只能删掉一个字符，所以，先从两端开始判断，如果相等向中间逼近，如果不等，则跳过一个字符（左边或者右边），判断余下的串是否回文。

class Solution
{
public:
    bool validPalindrome(string s)
    {
        int i=0,j=s.size()-1;
        while(i<=j&&s[i]==s[j])
        {
            i++;
            j--;
        }
        if(i>j) return true; //no delete

        int ni = i,nj = j-1;
        while(ni<=nj&&s[ni]==s[nj])
        {
            ni++;
            nj--;
        }
        if(ni>nj) return true; //delete j
        ni = i+1,nj = j;
        while(ni<=nj&&s[ni]==s[nj])
        {
            ni++;
            nj--;
        }
        if(ni>nj) return true; //delete i
        return false;
    }
};

剑指offer - 从上往下打印二叉树

发表于 2017-08-23 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701

题意

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

题解

二叉树的层次遍历。

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        if(root==NULL) return ans;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty()){	
            TreeNode * node = que.front();
            ans.push_back(node->val);
            que.pop();
            if(node->left)
                que.push(node->left);
            if(node->right)
                que.push(node->right);
        }
        return ans;
    }
};