几个面试经典算法题Java解答
本文共 5929 字，大约阅读时间需要 19 分钟。
题目一：
- public class testClockwiseOutput {
- //顺时针打印一个矩阵
- @Test
- public void test(){
- int[][] num = new int[100][100];
- int n = 4;
- int count =1;
- for(int i=0;i<n;i++){
- for(int j =0;j<n;j++){
- num[i][j]=count++;
- }
- }
- output(num,0,n-1);
- }
- public void output(int[][] num,int start,int end){
- if(start>=end || end<=0)return;
- for(int i=start;i<=end;i++){
- System.out.println(num[start][i]);
- }
- for(int i=start+1;i<=end;i++){
- System.out.println(num[i][end]);
- }
- for(int i=end-1;i>=start;i--){
- System.out.println(num[end][i]);
- }
- for(int i=end-1;i>start;i--){
- System.out.println(num[i][start]);
- }
- output(num,start+1,end-1);
- }
- }
题目二：
给出一个排序好的数组和一个数，求数组中连续元素的和等于所给数的子数组
- //给出一个排序好的数组和一个数，求数组中连续元素的和等于所给数的子数组
- @Test
- public void test(){
- int[] num = { 1,2,2,3,4,5,6,7,8,9};
- int sum = 7;
- findSum(num,sum);
- }
- public void findSum(int[] num,int sum){
- int left=0;
- int right=0;
- for(int i=0;i<num.length;i++){
- int curSum = 0;
- left = i;
- right = i;
- while(curSum<sum){
- curSum += num[right++];
- }
- if(curSum==sum){
- for(int j=left;j<right;j++){
- System.out.print(num[j]+" ");
- }
- System.out.println();
- }
- }
- }
题目三：
- //字符数组组成的所有字符串
- @Test
- public void test(){
- //char[] cs = {'a','b','c','d','e'};
- char[] cs = { 'a','b','c'};
- int length = cs.length;
- recursionSwap(cs,0,length);
- }
- public void swap(char[] cs,int index1,int index2){
- char temp = cs[index1];
- cs[index1]=cs[index2];
- cs[index2]=temp;
- }
- public void recursionSwap(char[] cs,int start,int length){
- if(start>=length-1){
- print(cs);
- return;
- }
- for(int i=start;i<length;i++){
- swap(cs,start,i);
- recursionSwap(cs,start+1,length);
- swap(cs,start,i);
- }
- }
- public void print(char[] cs){
- for(int i=0;i<cs.length;i++){
- System.out.print(cs[i]);
- }
- System.out.println();
- }
题目四：
- //数组组成的最小数
- @Test
- public void test(){
- int[] num={ 1,5,9,13,442,44,6,21,211};
- qsort(num,0,num.length-1);
- System.out.println(Arrays.toString(num));
- }
- public void qsort(int[] num,int left,int right){
- if(left<right){
- int partition = partition(num,left,right);
- qsort(num,left,partition-1);
- qsort(num,partition+1,right);
- }
- }
- public int partition(int[] num,int left,int right){
- int partition = num[left];
- while(left<right){
- while((num[right]==partition || isMBigerThanN(num,num[right],partition)) && left<right){
- right--;
- }
- swap(num,left,right);
- while((num[left]==partition || isMBigerThanN(num,partition,num[left])) && left<right){
- left++;
- }
- swap(num,left,right);
- }
- return left;
- }
- public void swap(int[] num,int m,int n){
- int temp = num[m];
- num[m]=num[n];
- num[n]=temp;
- }
- public boolean isMBigerThanN(int[] num,int m,int n){
- String num1 = String.valueOf(m);
- String num2 = String.valueOf(n);
- int temp1 = Integer.parseInt(num1+num2);
- int temp2 = Integer.parseInt(num2+num1);
- if(temp1>temp2){
- return true;
- }
- else{
- return false;
- }
- }
题目五：
- //子数组最大和
- @Test
- public void test(){
- int[] num = { 1,-2,3,10,-4,7,2,-5};
- //int[] num = {1,-2,3,10,-4,10,2,-5};
- System.out.println(maxSum(num));
- }
- public int maxSum(int[] num){
- int curSum = 0;
- int curMaxSum = -99999999;
- int start = 0;
- int end = 0;
- for(int i=0;i<num.length;i++){
- if(curSum<=0){
- curSum = num[i];
- start = i;
- }
- else{
- curSum += num[i];
- }
- if(curSum>curMaxSum){
- curMaxSum = curSum;
- end = i;
- }
- }
- for(int i = start;i<=end;i++){
- System.out.println(num[i]);
- }
- return curMaxSum;
- }
题目六：
- public class testMinStack {
- //自定义栈，min函数得到当前最小值
- @Test
- public void test(){
- MinStack ms = new MinStack();
- ms.push(5);
- System.out.println(ms.min());
- ms.push(6);
- ms.push(2);
- ms.push(1);
- System.out.println(ms.min());
- ms.pop();
- System.out.println(ms.min());
- ms.pop();
- System.out.println(ms.min());
- }
- }
- class MinStack{
- private Stack<Integer> minStack = new Stack<Integer>();
- private Stack<Integer> stack = new Stack<Integer>();
- public int pop(){
- minStack.pop();
- return stack.pop();
- }
- public void push(int num){
- if(minStack.size()<=0){
- minStack.push(num);
- return;
- }
- Integer min = minStack.lastElement();
- if(num<min){
- minStack.push(num);
- }
- else{
- minStack.push(min);
- }
- stack.push(num);
- }
- public int min(){
- if(minStack.size()<=0){
- return -1;
- }
- return minStack.lastElement();
- }
- }
题目七：
- //找出数组中出现次数大于一半的数
- @Test
- public void test(){
- int[] num = { 1,2,2,2,2,2,2,4,2,4,6,4,2,6,8,2,7,7};
- System.out.println(moreThanHaft(num));
- }
- public int moreThanHaft(int[] num){
- int result = -1;
- int times = 0;
- for(int i=0;i<num.length;i++){
- if(times==0){
- result = num[i];
- times++;
- }
- else{
- if(num[i]==result){
- times++;
- }
- else{
- times--;
- }
- }
- }
- return result;
- }
题目八：
- //判断一个数组是否是另一个栈的出栈顺序
- @Test
- public void test(){
- int[] num = { 1,2,3,4,5};
- //int[] num1={1,2,3,5,4};
- int[] num2={ 2,1,5,3,4};
- Stack<Integer> s1 = new Stack<Integer>();
- Stack<Integer> s2 = new Stack<Integer>();
- for(int i=0;i<5;i++){
- s2.push(num2[i]);
- }
- System.out.println(testOrder(num,s1,s2));
- }
- public boolean testOrder(int[] num,Stack<Integer> s1,Stack<Integer> s2){
- int length = num.length;
- for(int i=0;i<length;i++){
- s1.push(num[i]);
- int s2Num = s2.lastElement();
- if(s2Num==s1.lastElement().intValue()){
- s1.pop();
- s2.pop();
- }
- }
- while(!s1.isEmpty()){
- if(!s1.pop().equals(s2.pop())){
- return false;
- }
- }
- return true;
- }
- 复制代码
题目九：
- //从扑克牌抽5张牌，0可以为任意数，判断是否是顺子
- @Test
- public void test(){
- int[] num = { 0,1,5,3,2};
- System.out.println(check(num));
- }
- public boolean check(int[] num){
- //0-13
- int[] pai = new int[14];
- for(int n : num){
- pai[n]+=1;
- }
- qsort(num,0,num.length-1);
- int count = pai[0];
- int start = 0;
- if(num[0]==0){
- start=num[1];
- }
- else{
- start=num[0];
- }
- for(int i = start;i<=start+5;i++){
- if(pai[i]>1)return false;
- count += pai[i];
- }
- if(count == 5)return true;
- else return false;
- }
- public void qsort(int[] num,int left,int right){
- if(left<right){
- int partition = partition(num,left,right);
- qsort(num,left,partition-1);
- qsort(num,partition+1,right);
- }
- }
- public int partition(int[] num,int left,int right){
- int partition = num[left];
- while(left<right){
- while(left<right && num[right]>=partition){
- right--;
- }
- swap(num,left,right);
- while(left<right && num[left]<=partition){
- left++;
- }
- swap(num,left,right);
- }
- return left;
- }
- public void swap(int[] num,int m,int n){
- int temp = num[m];
- num[m]=num[n];
- num[n]=temp;
- }
题目十：
来源：51CTO
转载地址：http://tjwll.baihongyu.com/
你可能感兴趣的文章
物联网路径，美国运营商怎么走？
查看>>
除Hadoop大数据技术外，还需了解的九大技术
查看>>
印度限制官员使用智能手机：真因为怕中国黑客？
查看>>
沪穗深百万地铁族担心：花生WiFi到底安全吗？
查看>>
东莞：现代会展公司成立呼叫中心 大数据分析提升办展质量
查看>>
实现“中国制造”向“中国智造”转变 大数据技术成关键
查看>>
苹果市值15个交易日蒸发450亿美元 相当于半个波音
查看>>
中小企业网络方案商该关注哪些增值空间？
查看>>
苹果Safari浏览器遭遇全球故障 搜索即崩溃
查看>>
周鸿祎谈360回归初衷
查看>>
安防爆发年 谈谈车牌识别如何实现从原理到应用的转变？
查看>>
凯立德智慧物流地图服务平台让物流行业更省心
查看>>
安防产业布局跨境电商 有哪些方法？
查看>>
“智慧城市”建设为何需要“顶层设计”
查看>>
苹果免费打电话，或引网络电话行业变革
查看>>
java 使用hibernate时创建session的辅助类
查看>>
T-Mobile CEO为视频节流辩护 声称他支持网络中立
查看>>
【沉淀】来到阿里云后，SRS大神杨成立说：“终于可以不用装大神了”
查看>>
CDN的夏天来了？
查看>>
报告称到2020年73%的企业将运行SaaS
查看>>