⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【字符串中找出连续最长的数字串】和【数组中出现次数超过一半的数字】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

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

🔐题目详情

描述

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

输入描述：

个测试输入包含1个测试用例，一个字符串str，长度不超过255。

输出描述：

在一行内输出str中里连续最长的数字串。

示例

输入：

abcd12345ed125ss123456789

输出：

123456789

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

💡解题思路

基本思路： 构造+模拟

解题思路：
遍历字符串，遇到数字就进入一个内部循环，找到一个连续数字串，将长度与之前遍历得到的数字串长度进行对比，如果比之前的最长数字串还长，就将得到的数字串作为新的答案，直到遍历完全部字符串为止。

栗子：abcd12345ed125ss123456789

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String ss = sc.nextLine();
        char[] cs = ss.toCharArray();
        int len = 0;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < cs.length; i++) {
            int cnt = 0;
            int j = i;
            StringBuilder ret = new StringBuilder();
            while (j < cs.length && cs[j] >= '0' && cs[j] <= '9') {
                cnt++;
                ret.append(cs[j]);
                j++;
            }
            if (cnt > len) {
                len = cnt;
                ans = ret;
            }
            i = j;
        }
        System.out.println(ans);
    }
}

🌱总结

本题是一题简单模拟题，细心按照题意模拟构造即可。

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

🔐题目详情

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

数据范围： $1<=n≤50000$，数组中元素的值 $0≤val≤10000$

要求：空间复杂度：O(1)，时间复杂度 O(n)

输入描述：

保证数组输入非空，且保证有解

示例1

输入：

[1,2,3,2,2,2,5,4,2]

返回值：

2

示例2

输入：

[3,3,3,3,2,2,2]

返回值：

3

示例3

输入：

[1]

返回值：

1

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

💡解题思路

基本思路： 哈希计数

解题思路：
哈希思想：使用一个哈希表对数组元素x进行计数，每一次计数完毕后，判断该元素x的频数是否大于数组长度n的一半，如果满足这个条件，那么数组中出现次数超过一半的数字就是x。

🔑源代码

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //hash <数组元素, 出现次数>
        Map<Integer, Integer> hash = new HashMap<>();
        int ans = 0;
        int n = array.length;
        //统计数组元素的频数
        for (int x : array) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
            if (hash.get(x) > n / 2) {
                ans = x;
                break;
            }
        }
        
        return ans;
    }
}

🌱总结

本题是一道简单哈希运用题，利用哈希表计数得到每个数的数目，如果数目大于数组的长度一半了，就是满足题意的答案。
类似题：
771. 宝石与石头
2006. 差的绝对值为 K 的数对数目
1512. 好数对的数目
1365. 有多少小于当前数字的数字
LCP 44. 开幕式焰火