面试编程题

今天药忘吃喽~ 2022-01-23 10:53 288阅读 0赞

### 文章目录 ###

*   *  记录面试的编程题
     *   *   *  1. 二叉查找树的插入和查找
             *  2. 一个数二进制有多少个1
             *  3. 0-n二进制一共有多少个1
             *  4. 二分查找
             *  5. 快速排序
             *  6. 反转链表
             *  7. 二叉树前序遍历
             *  8. 二叉树中序遍历
             *  9. 二叉树后序遍历
             *  10. 合并排序的链表
             *  11.给一个数组和目标值，求数组中和为目标值的所有组合
             *  12.堆排序(最小K个数)
             *  13.最长公共子串
             *  14.二叉树的深度

## 记录面试的编程题 ##

#### 1. 二叉查找树的插入和查找 ####

//二叉树定义
    class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    public class FindAndInsertTree01 {
    	TreeNode root = null;
    	
    	//插入
    	public void insert(TreeNode node) {
    		if(root==null) {
    			root=node;
    		}else {
    			TreeNode current = root;
    			TreeNode parent = current;
    			while(true) {
    				parent=current;
    				if(current.val<node.val) {
    					current=current.left;
    					if(current==null) {
    						parent.left=node;
    						return;
    					}
    				}else {
    					current=current.left;
    					if(current==null) {
    						parent.right=node;
    						return;
    					}
    				}
    			}
    		}
    	}
    	
    	//查找
    	public TreeNode find(int value) {
    		TreeNode current=root;
    		while(current.val!=value) {
    			if(current.val<value) {
    				current=current.right;
    			}else if(current.val>value){
    				current=current.left;
    			}else {
    				return current;
    			}
    			if(current==null)return null;
    		}
    		return null;
    	}
    }

#### 2. 一个数二进制有多少个1 ####

public int NumberOf1(int n) {
        	int count=0;
        	if(n<0) {
        		count++;
        		n=n&0x7FFFFFFF;
        	}
        	while(n!=0) {
        		if(n%2!=0)count++;
        		n=n/2;
        	}
    		return count;
        }

#### 3. 0-n二进制一共有多少个1 ####

#### 4. 二分查找 ####

//非递归
    	public int binSearch(int arr[],int k) {
    		int low=0;
    		int high=arr.length-1;
    		while(low<high) {
    			int middle=(low+high)/2;
    			if(arr[middle]==k)return middle+1;
    			if(arr[middle]>k)high=middle-1;
    			else low=middle+1;
    		}
    		return -1;
    	}
    	
    	//递归
    	public int binSearch(int arr[],int k,int low,int high) {
    		if(low<high) {
    			int middle=(low+high)/2;
    			if(arr[middle]==k)return middle+1;
    			else if(arr[middle]>k)binSearch(arr,k,low,middle-1);
    			else binSearch(arr,k,middle+1,high);
    		}
    		return -1;
    	}

#### 5. 快速排序 ####

public int[] quickSort(int arr[],int low,int high) {
    		if(low<high) {
    			int middle=getMiddle(arr,low,high);
    			quickSort(arr,0,middle-1);
    			quickSort(arr,middle+1,high);
    		}
    		return arr;
    	}
    	
    	private int getMiddle(int[] arr, int low, int high) {
    		int temp=arr[low];
    		while(low<high) {
    			while(low<high&&arr[high]>=temp) {
    				high--;
    			}
    			arr[low]=arr[high];
    			while(low<high&&arr[low]<=temp) {
    				low++;
    			}
    			arr[high]=temp;
    		}
    		return low;
    	}

#### 6. 反转链表 ####

public ListNode ReverseList(ListNode head) {
            ListNode next=null;
            ListNode pre=null;
            while(head!=null){
                next=head.next;
                head.next=pre;
                pre=head;
                head=next;
            }
            return pre;
        }

#### 7. 二叉树前序遍历 ####

//递归
    	public List<Integer> postorder(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		postorder(root,result);
    		return result;
    	}
    	private void postorder(TreeNode root, List<Integer> result) {
    		if(root==null)return;
    		result.add(root.val);
    		postorder(root.left,result);
    		postorder(root.right,result);
    	}
    	
    	//非递归
    	public List<Integer> postorderF(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		Stack<TreeNode> s=new Stack<>();
    		Stack<TreeNode> temp=new Stack<>();
    		TreeNode cur=root;
    		while(!s.isEmpty()) {
    			cur=s.pop();
    			temp.add(cur);
    			if(cur.left!=null)s.push(cur.left);
    			if(cur.right!=null)s.push(cur.right);
    		}
            while (!temp.isEmpty()) {
                cur = temp.pop();
                result.add(cur.val);
            }
    		return result;
    	}

#### 8. 二叉树中序遍历 ####

//递归
    	public List<Integer> inorder(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		inorder(root,result);
    		return result;
    	}
    	private void inorder(TreeNode root, List<Integer> result) {
    		if(root==null)return;
    		inorder(root.left,result);
    		result.add(root.val);
    		inorder(root.right,result);
    	}
    	
    	//非递归
    	public List<Integer> inorderF(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		Stack<TreeNode> s=new Stack<>();
    		s.push(root);
    		TreeNode cur=root;
    		while(cur != null ||!s.isEmpty()) {
    			while(cur!=null) {
    				s.push(cur.left);//添加根节点
    				cur=cur.left;//添加左子节点
    			}
    			cur=s.pop();// 当前栈顶已经是最底层的左节点了，取出栈顶元素，访问该节点
    			result.add(cur.val);
    			cur=cur.right;// 添加右节点
    		}
    		return result;
    	}

#### 9. 二叉树后序遍历 ####

//递归
    	public List<Integer> postorder(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		postorder(root,result);
    		return result;
    	}
    	private void postorder(TreeNode root, List<Integer> result) {
    		if(root==null)return;
    		postorder(root.left,result);
    		postorder(root.right,result);
    		result.add(root.val);
    	}
    	
    	//非递归
    	public List<Integer> postorderF(TreeNode root) {
    		List<Integer> result=new ArrayList<>();
    		Stack<TreeNode> s=new Stack<>();
    		Stack<TreeNode> temp=new Stack<>();
    		TreeNode cur=root;
    		while(!s.isEmpty()) {
    			cur=s.pop();
    			temp.add(cur);
    			if(cur.left!=null)s.push(cur.left);
    			if(cur.right!=null)s.push(cur.right);
    		}
            while (!temp.isEmpty()) {
                cur = temp.pop();
                result.add(cur.val);
            }
    		return result;
    	}

> 二叉树的遍历 [https://segmentfault.com/a/1190000016674584\#articleHeader10][https_segmentfault.com_a_1190000016674584_articleHeader10]

#### 10. 合并排序的链表 ####

public ListNode Merge(ListNode list1,ListNode list2) {
    		ListNode node=null;
    		ListNode head=node;
    		if(list1==null)return list2;
    		if(list2==null)return list1;
    		while(list1!=null&&list2!=null) {
    			if(list1.val<=list2.val) {
    				if(head==null) {
    					head=node=list1;
    				}else {
    					node.next=list1;
    					node=node.next;
    				}
    				list1=list1.next;
    			}else {
    				if(head==null) {
    					head=node=list2;
    				}else {
    					node.next=list2;
    					node=node.next;
    				}
    				list2=list2.next;
    			}
    		}
    		if(list1==null) {
    			node.next=list2;
    		}else if(list2==null){
    			node.next=list1;
    		}
    		return head;
    	}

#### 11.给一个数组和目标值，求数组中和为目标值的所有组合 ####

public int[] twoSum(int[] nums, int target) {
            Map<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<nums.length;i++){
            	map.put(nums[i], i);
            }
            
            for(int i=0;i<nums.length;i++){
            	int value=target-nums[i];
            	if(map.containsKey(value)&&map.get(value)!=i){
            		return new int[]{i,map.get(value)};
            	}
            }
    		return null;
        }

#### 12.堆排序(最小K个数) ####

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        	ArrayList<Integer> list=new ArrayList<>();
        if(input.length<k||k==0)return list;	
         sort(input);
        	for(int i=0;i<k;i++) {
        		list.add(input[i]);
        	}
    		return list;
        }
    	public static void sort(int arr[]) {
    		int N=arr.length-1;
    		for(int i=N/2;i>=0;i--) {
    			sink(arr,i,N);
    		}
    		while(N>0) {
    			swap(arr,0,N--);
    			sink(arr,0,N);
    		}
    	}
    	
    	private static void sink(int[] arr, int i, int N) {
    		while(2*i+1<=N) {
    			int k=i*2+1;//左子树
    			if(k<N&&arr[k]<arr[k+1]) {
    				k++;//找到左右子树中较大的一个
    			}
    			if(arr[i]>arr[k])break;
    			swap(arr,i,k);
    			i=k;
    		}
    	}
    
    	private static void swap(int[] arr, int i, int k) {
    		int temp=arr[i];
    		arr[i]=arr[k];
    		arr[k]=temp;
    	}

#### 13.最长公共子串 ####

#### 14.二叉树的深度 ####

[https_segmentfault.com_a_1190000016674584_articleHeader10]: https://segmentfault.com/a/1190000016674584#articleHeader10