`

一著名软件公司的java笔试算法题!

阅读更多

原题如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求: "4 "不能在第三位, "3 "与 "5 "不能相连.
我看了回贴都没有很好解决,主要是没有排除重复。
解决思路:强化题目,用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路:显然是递归,初始序列122345,先从末两位(45)变化(45,54),然后末三位(345)   ...   直到最后六位.怎样解决重复问题?很简单,由于是递增序列,每生成新序列可与前一生成序列比较,如 <放弃当前序列。当然有更好效率,如预先预测。

方法一代码如下:

class   test 
{   
    //   当前固定部分 
    private   String   CurFixPart; 
    private   String   PreGenNum; 
    
public   static   void   main(String[]   args) 
{ 
  test   t=new   test(); 
  t.GenControll( "122345 "); 
} 

//   调整字符串s位置pos字符到最前 
private   String   shift(String   s,   int   pos) 
{ 
String   newStr; 
if   (s.length()> pos+1) 
    newStr=s.substring(pos,   pos+1) 
                +s.substring(0,   pos) 
                +s.substring(pos+1); 
else 
    newStr=s.substring(pos) 
                +s.substring(0,   pos); 
return   newStr; 
} 

protected   int   Validate(String   newNum) 
{ 
    String   newGenNum=CurFixPart+newNum; 
    if   (Integer.valueOf(newGenNum) <=Integer.valueOf(PreGenNum)) 
        return   0; 
    if   (newGenNum.substring(2,3).equals( "4 ")   ||   
              (newGenNum.indexOf( "35 ")!=-1)   ||   (newGenNum.indexOf( "53 ")!=-1))   
        return   0; 
            
    PreGenNum=newGenNum; 
System.out.println(newGenNum); 
return   0; 
} 
  
public   void   GenControll(String   Base) 
{ 
    PreGenNum= "0 "; 
CurFixPart= " "; 
GenNext(Base,   0); 
} 

void   GenNext(String   varPart,   int   curPos) 
{ 
if   (varPart.length()==2) 
{ 
    Validate(varPart); 
    Validate(shift(varPart,   1)); 
    return; 
  } 
//   Next   Layer 
String   newGen=shift(varPart,   curPos); 
String   SavedFixPart=CurFixPart; 
CurFixPart=CurFixPart+newGen.substring(0,1); 
GenNext(newGen.substring(1),   0); 
CurFixPart=SavedFixPart; 
//   同层递增 
if   (curPos==varPart.length()-1)     
    return; 
GenNext(varPart,   curPos+1); 
} 
} 
序列122345测试通过。 

 

方法二

其中输入的数组长度和重复的数字可以调整。但是规则是固定的。以后再考虑怎么完善成可以处理任意的字符串,规则也可以考虑用一个可配置的数组来表示。

大体的思路就是先对原始数组排序。并生成重复数字的标记数组。
在主算法的每一层循环对原始数组中的某一位数字的所有可能的位置做全枚举,同时当该位数字不是第一次出现的时候,其位置只能是上一位数字(重复数字)右侧。然后递归调用。 

用 122345 和 1222345 测试 OK

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Owen Luo
 * @version Created at 2008-11-6 下午12:51:48 用 ArrayList 和 StringBuffer 来实现较少的资源占用。
 */

public class CSDN_ArrayQuest_081106 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long   beginTime   =   System.currentTimeMillis(); 
        CSDN_ArrayQuest_081106 newProcess = new CSDN_ArrayQuest_081106();
        newProcess.preJobs();
        for (int a = 0; a < newProcess.arrayLength; a++) {
            newProcess.process(newProcess.posAL, a, 0);
        }
        long   endTime   =   System.currentTimeMillis(); 
        System.out.println(newProcess.counter);
        System.out.println( "Computation   time:   "+   (endTime-beginTime)); 
        
        

    }

    // pozAL 剩下的位置列表,从小到大,顺序排列
    // pozIndex 位置列表中遍历的起始位置
    // digitIndex 目前正在遍历处理的数字在原始排序数组中的位置

    public void process(ArrayList<Integer> pozAL, int pozIndex, int digitIndex) {

        // make a copy of pozAL
        ArrayList<Integer> tempAL = new ArrayList<Integer>(pozAL.size());
        for (int i = 0; i < pozAL.size(); i++) {
            tempAL.add(Integer.valueOf(pozAL.get(i).intValue()));
        }

        posArray[digitIndex] = tempAL.get(pozIndex).intValue();
        tempAL.remove(pozIndex);
        int nextPozIndex;
        if (digitIndex != arrayLength - 1) {
            if (flagArray[digitIndex + 1] == 1) {
                nextPozIndex = 0;
            } else {
                nextPozIndex = pozIndex; //如果是重复对象,只放右边
            }
            for (int i = nextPozIndex; i < tempAL.size(); i++) {
                process(tempAL, i, digitIndex + 1);
            }
        } else {
            genResult(posArray); //这里用一个 StringBuffer 对象,避免String类型的变量占用过多资源。
            // 条件筛出 “35”,“53”,“4”在第二位的情况
            if (result.indexOf("35") == -1 & result.indexOf("53") == -1
                    & result.indexOf("4") != 2) {
                counter++;
                System.out.println(result.toString());
            }
        }

    }

    public void preJobs() {

        // sorting original number array
        Arrays.sort(numArray);

        // initialize posArray
        posArray = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {
            posArray[i] = i;
        }

        posAL = new ArrayList<Integer>(arrayLength);
        for (int i = 0; i < arrayLength; i++) {
            posAL.add(Integer.valueOf(i));
        }

        // initialze flagArray
        flagArray = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {

            if (i == 0) {
                flagArray[i] = 1;
            } else {
                flagArray[i] = (numArray[i - 1] == numArray[i]) ? 0 : 1;
            }

        }

    }

    public void genResult(int[] pozIndex) {

        result.ensureCapacity(arrayLength);
        for (int i = 0; i < arrayLength; i++) {
            result.insert(pozIndex[i],numArray[i]);
            result.delete(pozIndex[i]+1,pozIndex[i]+2);
        }
        
    }

    int[] numArray = { 1, 2, 2, 2 ,3, 4, 5 };
    int[] posArray;
    int[] flagArray;
    int arrayLength = numArray.length;
    StringBuffer result = new StringBuffer("");
    int counter = 0;
    int counterALL = 0;
    ArrayList<Integer> posAL;

}


  

方法三

对于任意一个串利用递归进行排列时,我们是循环串中的每个字符到第一个字符进行递归。如果串中字符出现重复的话,则重复的字符只可以利用递归算法一次,即只要与前面相同的字符循环到第一个字符时不调用递归就可以避免重复,为此,我们只需要按如下方式修改算法:

import   java.util.*; 
public   class   test   { 
static   int   count=0; 
        public   static   void   main(String[]   arg)   { 
                Scanner   r=new   Scanner(System.in); 
                String   s=r.nextLine(); 
                Pailie(s, " "); 
                System.out.println( "Total: "+count); 
        } 
        static   void   Pailie(String   s,String   p)   { 
                if(s.length() <1)   { 
                System.out.println(p);//字符串长度小于1,换行 
                count++; 
                } 
                else   { 
                int   index[]=new   int[s.length()]; 
                for(int   i=0;   i <s.length();   i++)//该循环将所有字符的第一次出现的位置记录在数组index中 
                index[i]=s.indexOf(s.charAt(i)); 
                for(int   i=0;   i <s.length();   i++)   { 
                if(i==index[i])//只有当循环数与第一次记录数相等时才递归,保证相同字符中的第一个调用 
                Pailie(s.substring(1),p+s.substring(0,1));//递归,打印其它字符 
                s=s.substring(1)+s.substring(0,1);//循环移位 
                        } 
                } 
        } 
} 
这样,由于相同的字符只递归调用了一次,则避免了重复串的排列。下面是几个典型的运算结果: 
2222222(输入。当串中的所有字符相同时,应该递归调用1次) 
2222222 
Total:1 

122222(输入。当串中只有一个字符不同时,该字符应该循环所有不同位置) 
122222 
222221 
222212 
222122 
221222 
212222 
Total:6 

1223(输入。szlhj的例子) 
1223 
1232 
1322 
2231 
2213 
2312 
2321 
2123 
2132 
3122 
3221 
3212 
Total:12 

122345(输入。本题的要求,最后结果为360个,其它的我就不列出来了,大家可以自己测试) 
122345 
122354 
122453 
122435 
122534 
…… 
543221 
543212 
Total:360

 

 

分享到:
评论

相关推荐

    著名IT公司笔试题笔试题库

    在IT行业中,笔试是许多著名公司挑选优秀人才的重要环节,特别是大公司,它们通常会设置一系列严谨的测试来评估候选人的技术能力、逻辑思维和问题解决技巧。这份"著名IT公司笔试题笔试题库"正是为准备进入IT行业的...

    2016年4月方正Java软件工程师笔试题

    这个压缩包可能包含了当年方正公司Java软件工程师笔试的所有题目,包括但不限于Java语言基础、JVM原理、JavaEE相关技术、数据结构与算法等内容。考生可以通过分析这些题目来了解方正对Java工程师的技能期望,并进行...

    46家著名IT公司的笔试题

    标题 "46家著名IT公司的笔试题" 涵盖了大量的技术知识点,这些知识点是IT行业,特别是互联网领域招聘过程中的常见考核内容。这包括但不限于编程语言、算法与数据结构、操作系统、网络、数据库、软件工程、计算机基础...

    46家著名IT公司的笔试题.rar

    这个名为"46家著名IT公司的笔试题.rar"的压缩包文件显然包含了多个著名IT公司招聘过程中的笔试题目。这些题目通常涵盖了编程、算法、计算机网络、操作系统、数据结构、数据库管理、软件工程等多个IT领域的核心知识。...

    阿里软件JAVA笔试题

    阿里软件JAVA笔试题是阿里巴巴公司为招聘软件开发工程师所设计的一份笔试题目,涵盖了JAVA语言、数据结构、算法、设计模式、数据库等多方面的知识点。 本题目共有15道题目,涵盖了以下几个方面: 逻辑推理 1. 甲...

    java笔试编程题(小合集)

    第二份文档《华为Java笔试题.doc》则专门针对华为公司的Java笔试,可能包括了华为对Java技术栈的特定要求,比如JVM内存模型、Spring框架的应用、数据库操作、网络编程等。解答这类题目有助于理解企业对于Java开发者...

    各公司java笔试题

    【标题】:“各公司java笔试题”所涵盖的Java编程知识点详解 【描述】:这份资源集合了2012年和2013年北京、上海等地一些知名IT公司的Java笔试题目,其中包括用友公司和亿阳信通等企业的考题。这些题目无疑是Java...

    软件公司——华信笔试题——供大家参加笔试时参考

    【标题】:“软件公司——华信笔试题——供大家参加笔试时参考” 这是一份与软件公司华信相关的笔试题目集锦,旨在为准备参加华信或其他类似软件公司笔试的求职者提供参考资料。这类题目通常涵盖了计算机科学和技术...

    网龙最新秋招Java笔试题.docx

    网龙最新秋招Java笔试题 本文档是对网龙最新秋招Java笔试题的知识点总结。通过对试题的分析,我们可以总结出以下知识点: 1. 计算机网络基础知识: * PING 命令的实现机制:PING 命令发出的是 ICMP 请求报文,而...

    46家著名IT公司笔试题

    《46家著名IT公司笔试题》是一本集合了众多知名IT企业的面试笔试题目的电子书籍,对于准备进入IT行业的求职者来说,是一份极具价值的学习资料。这本书籍旨在帮助应聘者了解并熟悉IT公司的面试流程,提升自身的技术...

    世界著名公司面试笔试题

    在准备进入世界著名公司的工作之旅时,面试和笔试环节无疑是最关键的部分。这些环节是公司评估候选人能力、技能和潜力的重要方式。为了帮助你更好地应对这些挑战,了解并熟悉各类公司的面试笔试题库是非常有益的。...

    北京尔宜居科技有限公司Java笔试题

    "北京尔宜居科技有限公司Java笔试题" 这个标题表明这是一个与Java编程相关的考试题目集,可能是该公司在招聘Java开发人员时所使用的面试或笔试材料。这通常涵盖Java语言的基础知识、进阶特性、面向对象编程概念、多...

    北京宏景世纪软件股份有限公司Java笔试题

    【标题】:“北京宏景世纪软件股份有限公司Java笔试题”涉及的Java知识点解析 【描述】:本题目来源于北京宏景世纪软件股份有限公司的Java程序员笔试环节,这通常包括了对Java基础知识、编程能力、面向对象设计以及...

    java笔试题(收集了各大公司的笔试题)

    Java笔试题是评估应聘者技术水平和解决问题能力的重要环节,涵盖了基础语法、面向对象、数据结构、算法、JVM原理、多线程、网络协议、数据库、框架应用等多个方面。这份"java笔试题(收集了各大公司的笔试题)"资源...

    南瑞笔试题集合

    【南瑞笔试题集合】是针对应届毕业生设计的一系列笔试试题,旨在考察应聘者在IT领域的基础知识、专业技能和解决问题的能力。南瑞,作为中国电力行业的重要企业,其笔试环节通常涵盖计算机科学、软件工程、电力系统等...

    各个著名公司的笔试题(有答案)

    通过对"各个著名公司的笔试题(有答案)"的深入学习,你可以对不同公司的招聘标准有更直观的理解,同时提升自己的技术实力。 首先,编程语言是IT行业的基础,包括Java、Python、C++、C#等,可能会出现在笔试题中。...

    北京四维图新科技股份有限公司Java笔试题

    【标题】:“北京四维图新科技股份有限公司Java笔试题”涉及的Java知识点解析 【描述】:本题目来源于北京四维图新科技股份有限公司的Java笔试,通常这样的试题集会涵盖Java语言的基础、进阶以及实际应用等多个方面...

    2010最全的IT公司面试、笔试试题 java面试 笔试试题

    本资源集合了当年各大IT公司的面试和笔试试题,涵盖了Java语言的各种知识点,旨在帮助应聘者提升自己的技能水平,成功通过面试。 首先,Java面试通常会涉及到以下几个核心领域: 1. **Java基础知识**:包括Java...

    诺明软件有限公司Java笔试题

    【标题】:“诺明软件有限公司Java笔试题”通常是一份由诺明软件有限公司设计的用于评估应聘者Java编程技能的测试题目集。这样的试题旨在检验求职者的编程基础、面向对象设计、异常处理、集合框架、多线程、IO流、...

Global site tag (gtag.js) - Google Analytics