阿里笔试题(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)


相关推荐

发表回复

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

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