阿里笔试题(2017在线编程题)– 数串分组 –Java实现

阿里笔试题(2017在线编程题)– 数串分组 –Java实现看到有人写了阿里的面试题,心里痒痒,好久没搞过这些了,写着实现一下题目2017年3月阿里在线编程题(实习内推)给定一串数字判断是否存在这三个元素,它们将数字串分为四个子串,其中每个子串的数字之和均相同(该3个元素不纳入计算)要求时间复杂度和空间复杂度均不能超过O(n)实现简单的用Java实现了一下,大家凑乎看,有问题请多多指出–一个半路出家的Java程序员代

大家好,又见面了,我是你们的朋友全栈君。

看到有人写了阿里的面试题,心里痒痒,好久 没搞过这些了,写着实现一下

题目

2017年3月阿里在线编程题(实习内推)

给定一串数字
判断是否存在这三个元素,它们将数字串分为四个子串,其中每个子串的数字之和均相同(该3个元素不纳入计算)
要求时间复杂度和空间复杂度均不能超过O(n)

实现

简单的用Java实现了一下,大家凑乎看,有问题请多多指出--一个半路出家的Java程序员

代码

package com.test;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
 * 
 * @author Selecter Wane
 * @see 给定一串数字判断是否存在这三个元素,它们将数字串分为四个子串,其中每个子串的数字之和
 *         均相同(该3个元素不纳入计算),要求时间复杂度和空间复杂度均不能超过O(n)
 *
 */
public class NumberSplit {
    
    /**
     * 
     * @author Selecter Wane
     * @see        方法一:
     * @see     解题:如果存在四等分,那么有且只有一种情况;
     *             每部分和值不超过总值的1/4
     * @see        空间复杂度:        O(N)
     *             时间复杂度:        O(N)
     */
    class Func1 {
        Integer total;                        //每部分的和
        String numberStr;                    //原始字符串
        Integer[] array;                    //和值数组
        Map<Integer, Integer> sumMap = new HashMap<Integer, Integer>();        //对应和值的索引
        Integer[] splitIndex = {0, 0, 0};    //三个元素
        Boolean checkStr = true;            //判断是否全部为数字字符
        
        Func1(String numberStr) {
            this.init(numberStr);
        }
        /**
         * 初始化
         * @param numberStr 目标字符串
         */
        Func1 init (String numberStr) {
            this.numberStr = numberStr;
            array = new Integer[numberStr.length()];
            int sum = 0;
            for (int index = 0; index < numberStr.length(); index ++) {
                if (this.numberStr.charAt(index) < 48 || this.numberStr.charAt(index) > 57) {
                    checkStr = false;
                    return this;
                }
                sum += numberStr.charAt(index) - 48;
                array[index] = sum;
                sumMap.put(sum, index);
            }
            return this;
        }
        
        /**
         * 执行判断处理
         */
        Boolean excute() {
            boolean flag = false;
            //每部分总和不超过总和的1/4
            total = array[this.numberStr.length() - 1] / 4;
            //遍历第一个元素
            for (int index = 0; index < this.numberStr.length(); index ++) {
                //第一个元素不可能为第一位
                if (index == 0) {
                    continue ;
                }
                if (array[index - 1] > total) {
                    break ;
                }
                int _total = array[index - 1];
                //找第二个元素
                int _secondSum = array[index] + _total;
                if (sumMap.get(_secondSum) != null) {
                    int _secondIndex = sumMap.get(_secondSum) + 1;
                    int _threeSum = array[_secondIndex] + _total;
                    //找第三个元素
                    if (sumMap.get(_threeSum) != null) {
                        int _threeIndex = sumMap.get(_threeSum) + 1;
                        int _fourSum = array[_threeIndex] + _total;
                        //确认最后一部分和值
                        if (_fourSum == array[this.numberStr.length() - 1]) {
                            splitIndex[0] = index;
                            splitIndex[1] = _secondIndex;
                            splitIndex[2] = _threeIndex;
                            total = _total;
                            flag = true;
                        }
                    }
                }
                
            }
            return flag;
        }
        
        /**
         * 输出结果详情
         */
        void print() {
            if (!this.checkStr) {
                System.out.println("输入字符串中含有非数字字符\n");
                return ;
            }
            if (!this.excute()) {
                System.out.println("不存在这样的三个元素\n");
                return ;
            }
            System.out.println("原始字符串为:\t" + this.numberStr + "\n"
                    + "三个元素的索引为:\t" + this.splitIndex[0] + "," + this.splitIndex[1] + "," + this.splitIndex[2] + "\n"
                    + "三个元素为:\t" + this.numberStr.charAt(this.splitIndex[0]) + "," + this.numberStr.charAt(this.splitIndex[1]) + "," + this.numberStr.charAt(this.splitIndex[2]) + "\n"
                    + "四部分为:" + "\n"
                    + "\t" + this.numberStr.substring(0, this.splitIndex[0]) + "\n"
                    + "\t" + this.numberStr.substring(this.splitIndex[0] + 1, this.splitIndex[1]) + "\n"
                    + "\t" + this.numberStr.substring(this.splitIndex[1] + 1, this.splitIndex[2]) + "\n"
                    + "\t" + this.numberStr.substring(this.splitIndex[2] + 1) + "\n"
                    + "每部分和值为:\t" + this.total + "\n");
        }
        
    }
    
    @Test
    public void testFunc1_1() {
        new Func1("99999999999").print();
    }
    
    @Test
    public void testFunc1_2() {
        new Func1("999999").print();
    }
    
    @Test
    public void testFunc1_3() {
        new Func1("111111152564397").print();
    }
    
    @Test
    public void testFunc1_4() {
        new Func1("3435363").print();
    }
    
    @Test
    public void testFunc1_5() {
        new Func1("3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333"
                + "9"
                + "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333"
                + "6"
                + "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333"
                + "5"
                + "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
                + "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
                + "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111").print();
    }
    
}


结果

原始字符串为:	99999999999
三个元素的索引为:	2,5,8
三个元素为:	9,9,9
四部分为:
	99
	99
	99
	99
每部分和值为:	18

不存在这样的三个元素

原始字符串为:	111111152564397
三个元素的索引为:	7,10,13
三个元素为:	5,6,9
四部分为:
	1111111
	25
	43
	7
每部分和值为:	7

原始字符串为:	3435363
三个元素的索引为:	1,3,5
三个元素为:	4,5,6
四部分为:
	3
	3
	3
	3
每部分和值为:	3

原始字符串为:	333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333393333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333633333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333335111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
三个元素的索引为:	166,333,500
三个元素为:	9,6,5
四部分为:
	3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
	3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
	3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
	111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
每部分和值为:	498

使用Junit简单测试了一下,第一篇文章,大家多多指教

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/144790.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 使用cef3开发的浏览器不支持flash问题的解决

    使用cef3开发的浏览器不支持flash问题的解决开发浏览器时遇到了flash的问题,网上搜了下,解决的方法基本是加npapi、ppapi,一开始奔着ppapi去的,没有解决,后来用的npapi,在项目的output下新建plugins文件夹,将NPSWF32_22_0_0_209.dll拷入到文件夹下。问题解决。

  • 解决$.ajax()请求异常~ jQuery提示parsererror错误解决办法

    解决$.ajax()请求异常~ jQuery提示parsererror错误解决办法在前端通过ajax请求后台之后返回的时候,出现了下面的异常:error:function(req,textStatus,errorThrown){}req:textStatus:”parsererror”;errorThrown:undefined.而自己的ajax请求如下:type:’POST’,contentType:’application/j…

  • 子网划分介绍以及如何划分子网(例题详解)

    子网划分介绍以及如何划分子网(例题详解)子网划分这项技术用来把一个单一的IP网络地址划分成多个更小的子网(subnet)。这种技术可使一个较大的分类IP地址能够被进一步划分为几个子网。这样就可以让使用一个大的分类地址(classfuladdress)的企业能给该企业中处于不同地理位置的分公司分配不同的子网,对外整个企业是一个网络地址,而在内部,不同分公司则有不同的子网地址,因而不需要为每个站点都分别申请一个网络地址。子网划分通常是把IP地址中主机标识部分划出一定的位数用作本网的各个子网,剩余的主机标识作为相应子网的主机标识部分。

  • Restful api 防止重复提交

    Restful api 防止重复提交

  • python flask教程_python框架有哪些

    python flask教程_python框架有哪些大家好,这算是我使用CSDN以来第一次正二八经的想自己写一篇博客。如果有写的不好的地方还请大家见谅!使用pipenv的方便之处就是可以单独的为每一个python 项目建立对应的虚拟环境,而且该过程简单方便。下面我会用简短的步骤来描述这个过程:1. 首先使用pip进行安装pipenv。 用管理员身份打开命令行(cmd),然后输入pipinstallpipenv 回车,结果如下图所…

  • python中怎样换行输出_python换行继续输入

    python中怎样换行输出_python换行继续输入python输出换行的方法:1、用转义符号【\n】,代码为【str3=”..\n”】;2、直接用print输出一个空行,代码为【print(str1);print(“”);print(str2)】。本教程操作环境:windows7系统、python3.9版,DELLG3电脑。python输出换行的方法:方法1:用转义符号。str3=”我不见,万古英雄曾拔剑,铁笛高吹龙夜吟\n”st…

    2022年10月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号