提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

几个面试经典算法题Java解答

JAVA 算法 面试
2023-03-09 21:59:58 时间

题目一：

 

  1. public class testClockwiseOutput { 
  2.     //顺时针打印一个矩阵 
  3.     
  4.     @Test 
  5.     public void test(){ 
  6.         int[][] num = new int[100][100]; 
  7.         int n = 4; 
  8.         int count =1; 
  9.         
  10.         for(int i=0;i<n;i++){ 
  11.             for(int j =0;j<n;j++){ 
  12.                 num[i][j]=count++; 
  13.             } 
  14.         } 
  15.         
  16.         output(num,0,n-1); 
  17.     } 
  18.     
  19.     public void output(int[][] num,int start,int end){ 
  20.         if(start>=end || end<=0)return; 
  21.         for(int i=start;i<=end;i++){ 
  22.             System.out.println(num[start][i]); 
  23.         } 
  24.         for(int i=start+1;i<=end;i++){ 
  25.             System.out.println(num[i][end]); 
  26.         } 
  27.         for(int i=end-1;i>=start;i--){ 
  28.             System.out.println(num[end][i]); 
  29.         } 
  30.         for(int i=end-1;i>start;i--){ 
  31.             System.out.println(num[i][start]); 
  32.         } 
  33.         output(num,start+1,end-1); 
  34.     } 
  35. } 

 

题目二：

给出一个排序好的数组和一个数，求数组中连续元素的和等于所给数的子数组

 

  1. //给出一个排序好的数组和一个数，求数组中连续元素的和等于所给数的子数组 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         int[] num = {1,2,2,3,4,5,6,7,8,9}; 
  6.         int sum = 7; 
  7.         findSum(num,sum); 
  8.     } 
  9.     
  10.     public void findSum(int[] num,int sum){ 
  11.         int left=0; 
  12.         int right=0; 
  13.         
  14.         for(int i=0;i<num.length;i++){ 
  15.             int curSum = 0; 
  16.             left = i; 
  17.             right = i; 
  18.             while(curSum<sum){ 
  19.                 curSum += num[right++]; 
  20.             }            
  21.             if(curSum==sum){ 
  22.                 for(int j=left;j<right;j++){ 
  23.                     System.out.print(num[j]+" "); 
  24.                 } 
  25.                 System.out.println(); 
  26.             } 
  27.         } 
  28.     } 

 

题目三：

 

  1. //字符数组组成的所有字符串 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         //char[] cs = {'a','b','c','d','e'};        
  6.         char[] cs = {'a','b','c'};    
  7.         int length = cs.length;        
  8.         recursionSwap(cs,0,length); 
  9.     } 
  10.     
  11.     public void swap(char[] cs,int index1,int index2){ 
  12.         char temp = cs[index1]; 
  13.         cs[index1]=cs[index2]; 
  14.         cs[index2]=temp;        
  15.     } 
  16.     
  17.     public void recursionSwap(char[] cs,int start,int length){ 
  18.         if(start>=length-1){ 
  19.             print(cs); 
  20.             return; 
  21.         } 
  22.         for(int i=start;i<length;i++){ 
  23.             swap(cs,start,i); 
  24.             recursionSwap(cs,start+1,length);    
  25.             swap(cs,start,i); 
  26.         } 
  27.     } 
  28.     
  29.     public void print(char[] cs){ 
  30.         for(int i=0;i<cs.length;i++){ 
  31.             System.out.print(cs[i]); 
  32.         } 
  33.         System.out.println(); 
  34.     } 

 

题目四：

 

  1. //数组组成的最小数 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         int[] num={1,5,9,13,442,44,6,21,211}; 
  6.         qsort(num,0,num.length-1); 
  7.         System.out.println(Arrays.toString(num)); 
  8.     } 
  9.     
  10.     public void qsort(int[] num,int left,int right){ 
  11.         if(left<right){ 
  12.             int partition = partition(num,left,right); 
  13.             qsort(num,left,partition-1); 
  14.             qsort(num,partition+1,right); 
  15.         }    
  16.     } 
  17.     
  18.     public int partition(int[] num,int left,int right){ 
  19.         int partition = num[left]; 
  20.         while(left<right){ 
  21.             while((num[right]==partition || isMBigerThanN(num,num[right],partition)) && left<right){ 
  22.                 right--; 
  23.             }            
  24.             swap(num,left,right);    
  25.             while((num[left]==partition || isMBigerThanN(num,partition,num[left])) && left<right){ 
  26.                 left++; 
  27.             } 
  28.             swap(num,left,right);        
  29.         } 
  30.         
  31.         return left; 
  32.     } 
  33.     
  34.     public void swap(int[] num,int m,int n){ 
  35.         int temp = num[m]; 
  36.         num[m]=num[n]; 
  37.         num[n]=temp; 
  38.     } 
  39.     
  40.     public boolean isMBigerThanN(int[] num,int m,int n){ 
  41.         String num1 = String.valueOf(m); 
  42.         String num2 = String.valueOf(n); 
  43.         
  44.         int temp1 = Integer.parseInt(num1+num2); 
  45.         int temp2 = Integer.parseInt(num2+num1); 
  46.         
  47.         if(temp1>temp2){ 
  48.             return true; 
  49.         } 
  50.         else{ 
  51.             return false; 
  52.         } 
  53.     } 

 

题目五：

 

  1. //子数组***和 
  2.     @Test 
  3.     public void test(){ 
  4.         int[] num = {1,-2,3,10,-4,7,2,-5}; 
  5.         //int[] num = {1,-2,3,10,-4,10,2,-5}; 
  6.         System.out.println(maxSum(num)); 
  7.     } 
  8.     
  9.     public int maxSum(int[] num){ 
  10.         int curSum = 0; 
  11.         int curMaxSum = -99999999; 
  12.         int start = 0; 
  13.         int end = 0; 
  14.         
  15.         for(int i=0;i<num.length;i++){ 
  16.             if(curSum<=0){ 
  17.                 curSum = num[i]; 
  18.                 start = i; 
  19.             } 
  20.             else{ 
  21.                 curSum += num[i]; 
  22.             } 
  23.             if(curSum>curMaxSum){ 
  24.                 curMaxSum = curSum;        
  25.                 end = i; 
  26.             } 
  27.         }    
  28.         for(int i = start;i<=end;i++){ 
  29.             System.out.println(num[i]); 
  30.         } 
  31.         return curMaxSum; 
  32.     } 

 

题目六：

 

  1. public class testMinStack { 
  2.     //自定义栈，min函数得到当前最小值 
  3.     
  4.     @Test 
  5.     public void test(){ 
  6.         MinStack ms = new MinStack(); 
  7.         ms.push(5); 
  8.         System.out.println(ms.min()); 
  9.         ms.push(6); 
  10.         ms.push(2); 
  11.         ms.push(1); 
  12.         System.out.println(ms.min()); 
  13.         ms.pop(); 
  14.         System.out.println(ms.min()); 
  15.         ms.pop(); 
  16.         System.out.println(ms.min()); 
  17.         
  18.     } 
  19. } 
  20.  
  21. class MinStack{ 
  22.     private Stack<Integer> minStack = new Stack<Integer>();    
  23.     private Stack<Integer> stack = new Stack<Integer>(); 
  24.     
  25.     public int pop(){ 
  26.         minStack.pop();        
  27.         return stack.pop(); 
  28.     } 
  29.     
  30.     public void push(int num){ 
  31.         if(minStack.size()<=0){ 
  32.             minStack.push(num); 
  33.             return; 
  34.         } 
  35.         Integer min = minStack.lastElement(); 
  36.         if(num<min){ 
  37.             minStack.push(num); 
  38.         } 
  39.         else{ 
  40.             minStack.push(min); 
  41.         } 
  42.         stack.push(num); 
  43.     } 
  44.     
  45.     public int min(){ 
  46.         if(minStack.size()<=0){ 
  47.             return -1; 
  48.         } 
  49.         return minStack.lastElement(); 
  50.     } 
  51. } 

 

题目七：

 

  1. //找出数组中出现次数大于一半的数 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         int[] num = {1,2,2,2,2,2,2,4,2,4,6,4,2,6,8,2,7,7}; 
  6.         System.out.println(moreThanHaft(num)); 
  7.     } 
  8.     
  9.     public int moreThanHaft(int[] num){        
  10.         int result = -1; 
  11.         int times = 0; 
  12.         for(int i=0;i<num.length;i++){ 
  13.             if(times==0){ 
  14.                 result = num[i]; 
  15.                 times++; 
  16.             } 
  17.             else{ 
  18.                 if(num[i]==result){ 
  19.                     times++; 
  20.                 } 
  21.                 else{ 
  22.                     times--; 
  23.                 } 
  24.             } 
  25.         } 
  26.         
  27.         return result; 
  28.     } 

 

题目八：

  1. //判断一个数组是否是另一个栈的出栈顺序 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         int[] num = {1,2,3,4,5}; 
  6.         //int[] num1={1,2,3,5,4}; 
  7.         int[] num2={2,1,5,3,4}; 
  8.         Stack<Integer> s1 = new Stack<Integer>(); 
  9.         Stack<Integer> s2 = new Stack<Integer>(); 
  10.         for(int i=0;i<5;i++){ 
  11.             s2.push(num2[i]); 
  12.         } 
  13.         
  14.         System.out.println(testOrder(num,s1,s2)); 
  15.     } 
  16.     
  17.     public boolean testOrder(int[] num,Stack<Integer> s1,Stack<Integer> s2){ 
  18.         int length = num.length;        
  19.         for(int i=0;i<length;i++){ 
  20.             s1.push(num[i]); 
  21.             int s2Num = s2.lastElement(); 
  22.             if(s2Num==s1.lastElement().intValue()){ 
  23.                 s1.pop(); 
  24.                 s2.pop(); 
  25.             } 
  26.         } 
  27.         while(!s1.isEmpty()){ 
  28.             if(!s1.pop().equals(s2.pop())){ 
  29.                 return false; 
  30.             } 
  31.         } 
  32.         return true; 
  33.     } 
  34.  
  35. 复制代码

题目九：

 

  1. //从扑克牌抽5张牌，0可以为任意数，判断是否是顺子 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         int[] num = {0,1,5,3,2}; 
  6.         System.out.println(check(num)); 
  7.     } 
  8.     
  9.     public boolean check(int[] num){ 
  10.         //0-13 
  11.         int[] pai = new int[14]; 
  12.         for(int n : num){ 
  13.             pai[n]+=1; 
  14.         } 
  15.         qsort(num,0,num.length-1); 
  16.         int count = pai[0]; 
  17.         int start = 0; 
  18.         if(num[0]==0){ 
  19.             start=num[1]; 
  20.         } 
  21.         else{ 
  22.             start=num[0]; 
  23.         } 
  24.         for(int i = start;i<=start+5;i++){ 
  25.             if(pai[i]>1)return false; 
  26.             count += pai[i]; 
  27.         } 
  28.         if(count == 5)return true; 
  29.         else return false; 
  30.         
  31.     } 
  32.     
  33.     public void qsort(int[] num,int left,int right){ 
  34.         if(left<right){ 
  35.             int partition = partition(num,left,right); 
  36.             qsort(num,left,partition-1); 
  37.             qsort(num,partition+1,right); 
  38.         } 
  39.     } 
  40.     
  41.     public int partition(int[] num,int left,int right){ 
  42.         int partition = num[left]; 
  43.         while(left<right){ 
  44.             while(left<right && num[right]>=partition){ 
  45.                 right--; 
  46.             } 
  47.             swap(num,left,right); 
  48.             while(left<right && num[left]<=partition){ 
  49.                 left++; 
  50.             } 
  51.             swap(num,left,right); 
  52.         } 
  53.         
  54.         return left;        
  55.     } 
  56.     
  57.     public void swap(int[] num,int m,int n){ 
  58.         int temp = num[m]; 
  59.         num[m]=num[n]; 
  60.         num[n]=temp; 
  61.     } 

 

题目十：

  1. //输出第k个丑数(因子只有2，3，5) 
  2.     
  3.     @Test 
  4.     public void test(){ 
  5.         findUglyNum(8); 
  6.     } 
  7.     
  8.     public void findUglyNum(int index){ 
  9.         int[] num = new int[index]; 
  10.         int next = 1; 
  11.         num[0]=1; 
  12.         int index2=0; 
  13.         int index3=0; 
  14.         int index5=0;    
  15.  
  16.         while(next<index){ 
  17.             int num2 = num[index2]*2; 
  18.             int num3 = num[index3]*3; 
  19.             int num5 = num[index5]*5; 
  20.             
  21.             num[next] = getSuitable(num2,num3,num5); 
  22.             
  23.             while(num[index2]*2<=num[next]){ 
  24.                 index2++; 
  25.             } 
  26.             while(num[index3]*3<=num[next]){ 
  27.                 index3++; 
  28.             } 
  29.             while(num[index5]*5<=num[next]){ 
  30.                 index5++; 
  31.             }                
  32.             next++; 
  33.             
  34.         } 
  35.         System.out.println(num[index-1]); 
  36.     } 
  37.     
  38.     public int getSuitable(int num2,int num3,int num5){ 
  39.         int s = num2; 
  40.         if(num3<s){ 
  41.             s = num3; 
  42.         } 
  43.         if(num5<s){ 
  44.             s = num5; 
  45.         } 
  46.         return s; 
  47.     } 
复制代码

 

复制代码

 

相关文章