每日一练——Day3

骑猪看日落 2023-09-27 17:08 129阅读 0赞

> **前言：**
> 
> 小亭子正在努力的学习编程，接下来将开启编程题的练习~~
> 
> 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~
> 
> 同时如果本文对你有帮助的话，**烦请点赞关注支持一波, 感激不尽~~**

## 第一题 ##

### 题目描述： ###

> ### [题目链接][Link 1] ###
> 
> ### 描述 ###
> 
> 读入一个字符串str，输出字符串str中的连续最长的数字串
> 
> #### 输入描述： ####
> 
> 个测试输入包含1个测试用例，一个字符串str，长度不超过255。
> 
> #### 输出描述： ####
> 
> 在一行内输出str中里连续最长的数字串。
> 
> ### 示例1 ###
> 
> 输入：
> 
>     abcd12345ed125ss123456789
> 
> 复制输出：
> 
>     123456789

### 解题分析： ###

> 思路：
> 
> 遍历字符串，用一个空的字符串（我们设置为cur）记录连续的数字串，如果遇到不是数字字符，则表示一个连续的数字串结束了，则将数字串跟之前的数字串比较，如果更长，则更新更长的数字串替换之前那个字符串。
> 
> 注意：
> 
> 1. 有一种特殊的情况： 123abc123456
> 
> 这种情况最长的那个数字串遍历到最后也没遇到非数字的字符，所以需要单独处理。
> 
> 2. 每次遍历结束一个数字串，都需要将cur置为空

### 代码实现： ###

import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String str = in.nextLine();
            String ret = "";//这个用来存储每次最长的数字串
            String cur = ""; //用来存每一个数字串
            int i = 0;
            for(; i < str.length();i++){
                char ch = str.charAt(i);  //返回i下标处的值
                if(ch >= '0' && ch <= '9'){
                    cur += ch;
                }else{
                    if (ret.length() < cur.length()){
                        ret = cur;
                           }
                           cur = ""; // 把cur置空
                }
            }
            //处理123abc123456这种情况
            if(i == str.length() && ret.length() < cur.length()){
                ret = cur;
            }
            System.out.print(ret);
            }
        }

## 第二题 ##

### 题目描述： ###

> [题目链接][Link 2]
> 
> ### 描述 ###
> 
> 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
> 
> 例如输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
> 
> 数据范围： 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

### 解题分析： ###

> 补充:
> 
> *1、众数*是一组数据中出现次数最多的那个数。
> 
> 2、中位数是把一组数据排序（习惯上按从小到大顺序排序）后，居于“中间位置”的数。
> 
> 思路一：用排序
> 
> 1、排序
> 
> 2、遍历数组找到中间的数字X  
> 3、再次遍历数组,看下X出现了多少次  
> 4、看下X的个数是否大于数字长度的一半
> 
> 思路二：用众数
> 
> ![27a875a0cf3344b08c8d18a915861e6c.png][]
> 
> 1、如果两个数不相等，就消去这两个数，极端情况下，每次消去一个众数和一个非众数，那么，如果存在众数，最后留下的数肯定是众数
> 
> 2、再次遍历数组，判断这个数是否超过长度的一半

### 代码实现： ###

思路一 : 排序+中位数

import java.util.*;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            //判断参数
            if ( array == null || array.length == 0) {
                return 0;
            }
            //排序
            Arrays.sort(array);
            //求中位数
            int len = array.length;
            int midNum = array[len / 2]; // 中位数
            //遍历数组,统计中位数出现的次数
            int count = 0 ;
            for (int i = 0 ; i < len ; i++) {
                if (array[i] == midNum) {
                    count ++ ;
                }
            }
            //判断是否超过数组长度的一半
            if (count > len / 2 ) {
                return midNum;
            }
            //找到的众数没有超过数组长度的一半,返回0
            return 0;
        }
    }

思路二 : 众数

public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            if (array == null || array.length == 0 ) { //
                return 0;
            }
            // int result = array[0];
            // int times = 1 ;// 记录次数
            //i从数组第二个元素开始，遍历数组进行判断
            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;
        }
    }

[Link 1]: https://www.nowcoder.com/practice/bd891093881d4ddf9e56e7cc8416562d?tpId=85&&tqId=29%20864&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[Link 2]: https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPa%20ge=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[27a875a0cf3344b08c8d18a915861e6c.png]: https://img-blog.csdnimg.cn/27a875a0cf3344b08c8d18a915861e6c.png