【Java笔试强训】Day3（OR59 字符串中找出连续最长的数字串、JZ39 数组中出现次数超过一半的数字）

OR59 字符串中找出连续最长的数字串

链接：OR59 字符串中找出连续最长的数字串

题目：

读入一个字符串str，输出字符串str中的连续最长的数字串

题目分析：

代码实现：

package Day3;

import java.util.Scanner;

public class Day3_1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String ret = "";
        String cur = "";
        int i = 0;
        for (; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch >= '0' && ch <= '9') {
                cur = cur + ch + "";
            }else {
                if (ret.length() < cur.length()) {
                    ret = cur;
                }
                cur = "";
            }
        }
        //处理123abc123456这种情况
        if(i == str.length() && ret.length()< cur.length()) {
            ret = cur;
        }
        System.out.printf(ret);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

链接：JZ39 数组中出现次数超过一半的数字

题目：

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

题目分析：

注意！！：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)，不符合题目要求，并非最优，所以我们不使用

我们使用另一种方法：
首先，出现次数超过数组长度一半的那个数字我们称为众数
我们可以这样做：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，由于众数的个数超过了一半即比非众数多，那么如果存在众数，最后留下的数肯定是众数。

代码实现：

package Day3;

public class Day3_2 {
    public int MoreThanHalfNum_Solution (int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int result = array[0];//我们要的众数
        int times = 1; // 次数
        for(int i=1;i<array.length;++i){
            if(times != 0){
                if(array[i] == result) {
                    ++times; // 相同则加1

                }else{
                    --times; // 不同则减1

                }
            }
            else {
                // 更新result的值为当前元素，并置次数为1

                result = array[i];
                times = 1;
            }
        }
        // 判断result是否符合条件，即出现次数大于数组长度的一半

        times = 0;
        for(int i=0;i<array.length;++i){
            if(array[i] == result) ++times;
        }

        return (times > array.length/2) ? result : 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36