Hihocoder 1135：Magic Box

Hihocoder 1135：Magic Box

2016年4月6日

15:31

描述

The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever.

 

For example, let's assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish.

 

输入

Line 1: x y z

 

Line 2: the sequence consisting of only three characters 'R', 'Y' and 'B'.

 

For 30% data, the length of the sequence is no more than 200.

 

For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20.

 

输出

The maximum number of balls in the box ever.

 

样例输入

1 2 3

RRYBRBRYBRY

0 0 0

RBYRRBY

样例输出

7

4

 

解题思路

题目意思是顺序将序列对应的气球放到box中，每次判断box中不同颜色气球的差是否正好等于x，y，z，若相等，则在box中的气球都爆炸。求在爆炸之前box中放的最大气球数目。

直接暴力方法就可以解决。使用数组a保存x，y，z（但数组是有序的，从小到大），使用数组b保存不同颜色气球的差，b[0]=['R']-['Y']，b[1]=['R']-['B']，b[2]=['Y']-['B']。

 

#include<iostream> #include<string> #include<vector> #include<cmath> #include<algorithm> using namespace std; bool compare(int a[],int b[]){     int c[3]={0};     for(int i=0;i<3;i++)c[i]=abs(b[i]);     sort(c,c+3);     for(int i=0;i<3;i++)         if(a[i]!=c[i])return false;     return true; } int main(){     int a[3]={0};     while(cin>>a[0]>>a[1]>>a[2]){         sort(a,a+3);         string s;         cin>>s;         int n=s.length();         int m=0;         int cur=0;         int b[3]={0};         for(int i=0;i<n;i++){             if(s[i]=='R'){                 b[0]++;                 b[1]++;             }             else if(s[i]=='Y'){                 b[2]++;                 b[0]--;             }             else{                 b[2]--;                 b[1]--;             }             cur++;             if(compare(a,b)){                 if(m<cur)m=cur;                 cur=0;                 for(int i=0;i<3;i++)b[i]=0;             }         }         if(m<cur)m=cur;         cout<<m<<endl;     }     return 0; }

 

 

Hihocoder 1197 : Give My Text Back

Hihocoder 1197 : Give My Text Back

2016年4月5日

16:48

#1197 : Give My Text Back

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.

 

It is known that the original text contains only English letters (a-zA-Z), spaces, commas, periods and newlines, conforming to the following format:

 

1. Each sentence contains at least one word, begins with a letter and ends with a period.

 

2. In a sentence the only capitalized letter is the first letter.

 

3. In a sentence the words are separated by a single space or a comma and a space.

 

4. The sentences are separated by a single space or a single newline.

 

It is also known the malware changes the text in the following ways:

 

1. Changing the cases of letters.

 

2. Adding spaces between words and punctuations.

 

Given the messed text, can you help Little Ho restore the original text?

 

输入

A string containing no more than 8192 English letters (a-zA-Z), spaces, commas, periods and newlines which is the messed text.

 

输出

The original text.

 

样例输入

my Name  is Little   Hi.

His   name IS Little ho  ,  We are   friends.

样例输出

My name is little hi.

His name is little ho, we are friends.

 

 

/**     * @Title: GiveMyTextBack.java   * @author olivelv    * @date Apr 4, 2016 4:11:53 PM    *   */   /**  * test:  *  my Name  is Little   Hi. ami           .i hate      hiho                     ,codr. EEENNN.    His   name IS Little ho  ,  We are   friends.  my Name  is Little   Hi.His   name IS Little ho  ,  We are   friends. my Name  is Little   Hi. His   name IS Little ho  ,  We are   friends.  His   name IS Little ho  ,We are   friends.   weoifj   ,jo. Jo, f, j l, o,o, l. result: My name is little hi. Ami. I hate hiho, codr. Eeennn. His name is little ho, we are friends. My name is little hi. His name is little ho, we are friends. My name is little hi. His name is little ho, we are friends. His name is little ho, we are friends. Weoifj, jo. 规则： 1、遇到','或者'.'如果后面还有内容，则要用"空格"间隔开 2、每个输入可能宝航多个句子  每个句子的开头单词的首字母都要大写 3、整段句的最后以'.'结尾，不应多加空格，否则会报"PE" 解题思路 首先将字符串转换为小写。使用标记量flag和first进行标识。 flag 记录前一个字符是否为空格  flag=0 表示前一个字符为空格，flag=1表示前一个为非空格 first 记录是否是句首 first=0表示句首，first=1 表示非句首 遇到','或'.'，则在其后添加"空格"。遇到字母时，若不是句首（first！=0），前一个字符为空格（flag=0），且结果字符最后一个字符不是空格，则添加一个"空格"。  *  */ public class GiveMyTextBack {     public static void main(String []args){         Scanner cin=new Scanner(System.in);         String s;         while(cin.hasNext()){             s=cin.nextLine();             s=s.toLowerCase();             int n=s.length();             int flag=0;             int first=0;             String res="";             for(int i=0;i<n;i++){                 char tmp=s.charAt(i);                 if(tmp!=' '){                     if(tmp==','){                         res+=tmp;                         res+=' ';                     }                     else if(tmp=='.'){                         res+=tmp+" ";                         first=0;                     }                     else{                         if(flag==0&&first!=0&&!res.endsWith(" "))res+=' ';                         if(first==0){                             res+=(char)(tmp-'a'+'A');                             first=1;                         }else                             res+=tmp;                         flag=1;                     }                 }else                     flag=0;             }             System.out.println(res.trim());         }     } }

 

 

338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

 

Example:

For num = 5 you should return [0,1,1,2,1,2].

 

Follow up:

 

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

Space complexity should be O(n).

Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

 

解题思路：

这个题目类似89. Gray Code，找规律

0 - 0

1 - 1

2 - 1

3 - 2

4 - 1

5 - 2

6 - 2

7 - 3

8 - 1

[2^(i-1),2^i-1]是由[0,2^(i-1)-1]数组+1得到的。例如上面的[4,7]的值是由[0,3]+1得到的。

class Solution { public:     vector<int> countBits(int num) {         vector<int>res(num+1,0);         int base=1;         int k=1;         while(k<=num){         for(int j=0;j<base&&k<=num;j++)                 res[k++]=res[j]+1;             base<<=1;         }         return res;               } };

 

 

202. Happy Number

Write an algorithm to determine if a number is "happy".

 

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

 

Example: 19 is a happy number

 

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

 

解题思路：

方法一：使用set保存中间值，每次判断中间结果是否在set中，或者判断中间结果是否为1.。

方法二：利用Happy Number的一个性质。。https://en.wikipedia.org/wiki/Happy_number

// using set costs 4ms class Solution { public:     bool isHappy(int n) {        set<int>s;        if(n==0)return false;        s.insert(n);        while(true){            int tmp=0;            while(n){                tmp+=(n%10)*(n%10);                n/=10;            }            n=tmp;            if(n==1)return true;            if(s.find(n)!=s.end())return false;            s.insert(n);        }        return false;     } };   // https://en.wikipedia.org/wiki/Happy_number // Happy_number has attribute all happy number ends in 1,all non-happy number ends in 4; // costs 0ms sometimes class Solution { public:     bool isHappy(int n) {        if(n==0)return false;        int tmp=0;        while(n!=1&&n!=4){            while(n){                tmp+=(n%10)*(n%10);                n/=10;            }            n=tmp;            tmp=0;        }        return n==1;     } };

 

 

263. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

 

解题思路：

水题、、、、、

class Solution { public:     bool isUgly(int num) {         if(num<1)return false;         // 4ms         while((num&1)==0)num>>=1;         // 8ms         //while((num%2)==0)num/=2;         while(num%3==0)num/=3;         while(num%5==0)num/=5;         return num==1;     } };