小景哥哥

1005. 继续(3n+1)猜想 (25)

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
输入格式：每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。
输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。
输入样例：
6
3 5 6 7 8 11
输出样例：
7 6

1007. 素数对猜想 (20)
让我们定义 dn 为：dn = pn+1 – pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。
输入格式：每个测试输入包含1个测试用例，给出正整数N。
输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。
输入样例：
20
输出样例：
4

28.数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length <= 0)
            return 0;
        if(array.length == 1)
            return array[0];
        Arrays.sort(array);
        int length = array.length;
        if(length % 2 == 0 && array[length / 2 - 1] == array[length / 2]){
            return array[length / 2];
        }else if(length % 2 == 1 && array[length / 2] == array[length / 2 + 1])
            return array[length / 2];
        else 
            return 0;
    }
}

//方法二，基于快速排序算法思想

42.和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
 

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        if(array.length < 1)
            return list;
        int ahead = array.length - 1;
        int behind = 0;
        
        while(ahead > behind){
            long curSum = array[ahead] + array[behind];
            if(curSum == sum){
                list.add(array[ahead]);
                list.add(array[behind]);
                break;
            }else if(curSum > sum)
                ahead--;
            else behind++;
        }
        Collections.sort(list);
        return list;
    }
}

33.丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的
 

import java.util.ArrayList;
public class Solution {

    public int GetUglyNumber_Solution(int n){
        if(n<=0)return 0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        list.add(1);
        int i2=0,i3=0,i5=0;
        while(list.size()<n)//循环的条件
        {
            int m2=list.get(i2)*2;
            int m3=list.get(i3)*3;
            int m5=list.get(i5)*5;
            int min=Math.min(m2,Math.min(m3,m5));
            list.add(min);
            if(min==m2)i2++;
            if(min==m3)i3++;
            if(min==m5)i5++;
        }
        return list.get(list.size()-1);
    }
}

1053.住房空置率 (20)-PAT乙级真题java实现

在不打扰居民的前提下，统计住房空置率的一种方法是根据每户用电量的连续变化规律进行判断。判断方法如下： 
在观察期内，若存在超过一半的日子用电量低于某给定的阈值e，则该住房为“可能空置”； 
若观察期超过某给定阈值D天，且满足上一个条件，则该住房为“空置”。 
现给定某居民区的住户用电量数据，请你统计“可能空置”的比率和“空置”比率，即以上两种状态的住房占居民区住房总套数的百分比。 
输入格式： 
输入第一行给出正整数N（<=1000），为居民区住房总套数；正实数e，即低电量阈值；正整数D，即观察期阈值。随后N行，每行按以下格式给出一套住房的用电量数据： 
K E1 E2 … EK 
其中K为观察的天数，Ei为第i天的用电量。 
输出格式： 
在一行中输出“可能空置”的比率和“空置”比率的百分比值，其间以一个空格分隔，保留小数点后1位。 
输入样例： 
5 0.5 10 
6 0.3 0.4 0.5 0.2 0.8 0.6 
10 0.0 0.1 0.2 0.3 0.0 0.8 0.6 0.7 0.0 0.5 
5 0.4 0.3 0.5 0.1 0.7 
11 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 
11 2 2 2 1 1 0.1 1 0.1 0.1 0.1 0.1 
输出样例： 
40.0% 20.0% 
（样例解释：第2、3户为“可能空置”，第4户为“空置”，其他户不是空置。）

63.数据流中的中位数

题目描述

1049. 数列的片段和(20) 
给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列{0.1, 0.2, 0.3, 0.4}，我们有(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这10个片段。 
给定正整数数列，求出全部片段包含的所有的数之和。如本例中10个片段总和是0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。 
输入格式： 
输入第一行给出一个不超过105的正整数N，表示数列中数的个数，第二行给出N个不超过1.0的正数，是数列中的数，其间以空格分隔。 
输出格式： 
在一行中输出该序列所有片段包含的数之和，精确到小数点后2位。 
输入样例： 
4 
0.1 0.2 0.3 0.4 
输出样例： 
5.00

1016. 部分A+B (15) 
正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6。 
现给定A、DA、B、DB，请编写程序计算PA + PB。 
输入格式： 
输入在一行中依次给出A、DA、B、DB，中间以空格分隔，其中0 < A, B < 10^10。 
输出格式： 
在一行中输出PA + PB的值。 
输入样例1： 
3862767 6 13530293 3 
输出样例1： 
399 
输入样例2： 
3862767 1 13530293 8 
输出样例2： 
0

1057.数零壹(20)–PAT乙级真题java实现

给定一串长度不超过10^5的字符串，本题要求你将其中所有英文字母的序号（字母a-z对应序号1-26，不分大小写）相加，得到整数N，然后再分析一下N的二进制表示中有多少0、多少1。例如给定字符串“PAT (Basic)”，其字母序号之和为：16+1+20+2+1+19+9+3=71，而71的二进制是1000111，即有3个0、4个1。

输入格式：

输入在一行中给出长度不超过105、以回车结束的字符串。

输出格式：

在一行中先后输出0的个数和1的个数，其间以空格分隔。

输入样例：

PAT (Basic)

输出样例：

3 4