您的位置: 首页  >  IT文章  >  各大IT公司算法跟数据结构面试题整理Java实现

各大IT公司算法跟数据结构面试题整理Java实现

分类: IT文章 • 2022-05-22 16:51:04
各大IT公司算法和数据结构面试题整理Java实现
1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
      10
    /      \
  6      14
 /   \     /   \
4  8 12  16
转换成双向链表
4=6=8=10=12=14=16。


首先我们定义的二元查找树 节点的数据结构如下：
 struct BSTreeNode
 {
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node

 };

解答：

/**
 * @author WuKung
 * @****URL http://blog.****.net/wu_kung/
 * @createdDate 2014-4-6 下午2:58:32
 * 树的节点类
 */
class TreeNode{
	
	int key;
	TreeNode left;
	TreeNode right;
	
	public TreeNode(int key,TreeNode left,TreeNode right){
		this.key=key;
		this.left=left;
		this.right=right;
	}
}

public class BinarySearchTreeTest{
	static TreeNode root=null;
	public static void main(String[] args){
		BinarySearchTreeTest bst = new BinarySearchTreeTest();
		bst.createdBST();
		System.out.println("输出创建好的二叉查找树");
		bst.inorderTraversal(root);
		
		System.out.println();
		System.out.println("根节点的关键字"+root.key);
		System.out.println("输出转换得到的双链表");
		bst.convertToDoubleList(root);//传入二叉排序树的根节点
		TreeNode node = bst.doubleListHead;
		while(node!=null){
			System.out.print(node.key+",");
			node=node.right;
		}
	}
	
	//构建一颗二叉查找树
	public void createdBST(){
		addTreeNode(10);
		addTreeNode(6);
		addTreeNode(4);
		addTreeNode(8);
		addTreeNode(14);
		addTreeNode(12);
		addTreeNode(16);
	}
	
	
	
	//向二叉排序树中插入（添加）节点
	public void addTreeNode(int key){
		
		if(root==null){
			root=new TreeNode(key, null, null);
		}else{
			TreeNode node=root,parent=null; 
			while(node!=null){
				 parent = node;
				if(key==node.key){
					System.out.println("该节点已存在");
					return;
				}else if(key<node.key){
					node=node.left;
				}else{
					node=node.right;
				}
			}
			
			//找到插入（添加）的地方后，新建一个节点对象
			if(key<parent.key){
				parent.left = new TreeNode(key, null, null);
			}else if(key>parent.key){
				parent.right = new TreeNode(key, null, null);
			}
		}
	
	}
	
	//中序遍历，打印出遍历后的结果
	public void inorderTraversal(TreeNode root){
		if(root==null){
			return;
		}
		inorderTraversal(root.left);
		System.out.print(root.key+",");
		inorderTraversal(root.right);
	}
	
	/**
	 * 将二叉查找树转换成一个双向的链表
	 * 1.将双链表的头指针和尾指针都指向二叉排序树的第一个元素4
	 * 2.通过调用移动尾指针指向下一个6
	 * 3.循环第二步直到尾指针指到二叉排序树的最后一个元素16
	 * @param root 传入一颗二叉排序树的根节点
	 */
	TreeNode doubleListHead=null;//双链表头节点
	TreeNode doubleListTail=null;//双链表尾节点
	public void convertToDoubleList(TreeNode node){
		if(node==null){
			return;
		}
		convertToDoubleList(node.left);
		if(doubleListTail==null){
			doubleListHead = node;
		}else{
			doubleListTail.right = node ;
		}
		node.left = doubleListTail;
		doubleListTail=node;
		convertToDoubleList(node.right);
	}
	
}

输出结果：各大IT公司算法跟数据结构面试题整理Java实现


2.金额转换,阿拉伯数字的金额转换成中国传统形式如:(￥1011)——>(一千零一十一元整)输出:

/**
 * 将数字表示的钱转换成中文表示
 * @author WuKung
 * @****URL http://blog.****.net/wu_kung/
 * @createdDate 2014-4-6 下午5:07:12
 */
public class MoneySwap {
	
	char[] char1={'零','一','二','三','四','五','六','七','八','九'};
	char[] char2={'元','拾','百','千','万','拾','百','千','亿'};
	public static void main(String[] args){
		MoneySwap ms = new MoneySwap();
		String str=ms.swap(10008445);
		System.out.println(str);
	}
	
	public String swap(int money){
		StringBuffer sb = new StringBuffer();
		
		int unit=0;
		while(money!=0){
			sb.insert(0, (char)char2[unit++]); 
			int temp = money%10;
			sb.insert(0, (char)char1[temp]);
			money/=10;
		}
		//加上去零的正则表达式
		String str=sb.toString().replaceAll("零[拾百千]", "零").replaceAll("零+万", "万")
					.replaceAll("零+元", "元").replaceAll("零+", "零");
		return str;
	}
	
}

输出结果：

各大IT公司算法跟数据结构面试题整理Java实现


3.设计包含 min 函数的栈。
定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。


思路分析:
a.要想一个在栈中找出栈的最小值,且时间复杂度为1,我们可能回想到每次向栈插入push()一个值都对其进行排序操作,将最小值放在栈顶,但是我们很快会发现这种方式破坏了栈的结构,不再满足栈的先进先出的特点了(FIFO),此法不行
b.通过一个成员函数来保存最新值,但当最小元素弹出栈pop()时,我们无法得到次小元素,所以此法也不行。
c.大家可能立马想到用数组了。通过数组来保存对栈进行插入或删除后栈中的最小值,但这有一个弊端,我们不知道要给数组申请大多的地址空间,因为我们事先无法确定会插入多少个数到栈中,此法不优
d.我们可以使用一个辅助栈来存放最小值
操作:

option dataStack栈 minStack栈
push(3) 3 3
push(5) 3,5 3,3
push(2) 3,5,2 3,3,2
push(6) 3,5,2,6 3,3,2,2
pop() 3,5,2 3,3,2
pop() 3,5 3,3
minStack就是我们的辅助栈，dataStack就是主要的数据栈
现在我知道要得到栈中的最小值,就是辅助栈的栈顶元素故调用minStack.peek()。

Java代码如下：

package com.WuKung.blog;
import java.util.Stack;

/**
 * @author WuKung
 * @****URL http://blog.****.net/wu_kung/
 * @createdDate 2014-4-7 下午11:18:47
 */
public class StackWithMin<E extends Comparable<E>> extends Stack<E>{

	Stack<E> data;
	Stack<E> min;
	
	public StackWithMin(Stack<E> data,Stack<E> min){
		this.data = data;
		this.min = min;
	}

	@Override
	public E push(E item) {
		// TODO Auto-generated method stub
	
		if(data.size()==0||item.compareTo(min.peek())<0){
			min.push(item);
		}else{
			min.push(min.peek());
		}
		data.push(item);
		return super.push(item);
	}

	@Override
	public synchronized E pop() {
		// TODO Auto-generated method stub
		if(!min.isEmpty()&&!data.isEmpty()){
			min.pop();
			data.pop();
		}
		return super.pop();
	}
	
	public E min(){
		return min.peek();
	}
}
测试类：
package com.WuKung.blog;
import java.util.Stack;

/**
 * @author WuKung
 * @****URL http://blog.****.net/wu_kung/
 * @createdDate 2014-4-8 上午12:17:18
 */
public class StackT {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Stack<Integer> data = new Stack<Integer>();
		Stack<Integer> min = new Stack<Integer>();
		StackWithMin<Integer> test = new StackWithMin<Integer>(data, min);
		test.push(new Integer(3));	
		test.push(new Integer(5));	
		test.push(new Integer(2));	
		test.push(new Integer(6));	
		test.pop();
		test.pop();
		System.out.println(test.min());
	}
}

测试结果：

各大IT公司算法跟数据结构面试题整理Java实现

4.输入一个正整数n，求出全部连续正整数相加后等于n的所有序列。
例如:
15=1+2+3+4+5；
15=4+5+6；
15=7+8。


思路:a.首先15/2=7.5,所以15不可能被两个大于7.5的数相加得到,所以我们只要控制循环变量的start的值不大于8即可。
b.由于所求的结果系列不止一个,如15就有三个序列,并且每个序列都有一个起始和结束值。故可用一个start变量表示其实值,end变量表示结束值;
15的三个序列的｛start=1......end=5｝{start=4....end=6}{start=7,end=8}
c.为了方便表示:start简称s,end简称b,求的和为sum初始值为0,
进行如下操作:
当sum<=15时减去s,即s后移一位,或者加上b,即s后移一位
｛1, 2, 3, 4, 5, 6, 7, 8｝
算法分析:先找出第一个序列:
｛1,2,3,4,5｝此时sum=15,s=1,b=5;s后移一位,s=2
   {2,3,4,5} 此时sum=14,小于15;b后移一位,b=6;
   {2,3,4,5,6}此时sum=20,大于15;s后移一位,s=3;
     {3,4,5,6}此时sum=18,大于15;s后移一位,s=4;
       {4,5,6}此时sum=15,等于15;s后移一位,s=5;
        ｛5,6｝此时sum=11,小于15;b后移一位,b=7;
         {5,6,7}类推下去...
             {7,8}此时sum=15,小于15,s后移一位,s=8;由于s=8不小于15/2+1;
循环结束。

Java代码：

import java.util.Scanner;

/**
 * @author WuKung
 * @****URL http://blog.****.net/wu_kung/
 * @createdDate 2014-4-8 下午1:28:49
 */
public class GetSum {
	static int count=0;
	public static void show(int n,int s,int b){
		count++;
		System.out.println("输出第"+count+"系列");
		String str=" ";
		for(int i=s;i<=b;i++){
			str+=i+"+";
		}
		
		StringBuffer sb = new StringBuffer(str);
		sb.deleteCharAt(sb.length()-1);
		sb.append("="+n);
		System.out.println(sb.toString().trim());
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		System.out.println("输入一个整数");
		int n=sc.nextInt();
		fn(n);
	}
	
	public static void fn(int n){
		int s=1;int b=0;int sum=0;
		while(s<n/2+1){
			if(sum==n){
				show(n,s,b);
				sum-=s++;
			}else if(sum>n){
				sum-=s++;
			}else{
				sum+=++b;
			}
			
		}
	}
}

持续更新中。。。


1楼u014403128昨天 17:16
赞一个
Re: a018041762昨天 17:18
回复u014403128n谢谢

相关推荐