程序员经验分享-hwhale

面试必考真题

2023-11-19

1.输入一个链表，反转链表后，输出新链表的表头。

package com.csu.marden;

public class Demo1 {
	public static void main(String[] args) {
		Node head=new Node();
		Node node1=new Node(1);
		Node node2=new Node(2);
		Node node3=new Node(3);
		head.next=node1;
		node1.next=node2;
		node2.next=node3;
		show(head);
		System.out.println("-------------------------------------------");
		show(reverse(head));
	}
	
	public static void show(Node head){
		Node temp=head.next;
		while(temp!=null){
			System.out.println(temp.value);
			temp=temp.next;
		}
	}
	
	//链表反转
	public static Node reverse(Node head){
		Node temp=head.next;
		Node newhead=new Node();
		while(temp!=null){
			//将temp节点摘下来
			head.next=temp.next;
			//将temp节点插入新表头节点后
			temp.next=newhead.next;
			newhead.next=temp;
			temp=head.next;
		}
		head.next=newhead.next;
		
		
		return head;
		
	}

}
class Node{
	int value;
	Node next;
	public Node(int value) {
		super();
		this.value = value;
	}
	public Node() {
		super();
	}
	
}

 

2.设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能:

  • set(key, value)：将记录(key, value)插入该结构
  • get(key)：返回key对应的value值

[要求]

  1. set和get方法的时间复杂度为O(1)
  2. 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
  3. 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

示例：

输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出：[1,-1]

说明：

第一次操作后：最常使用的记录为("1", 1)
第二次操作后：最常使用的记录为("2", 2)，("1", 1)变为最不常用的
第三次操作后：最常使用的记录为("3", 2)，("1", 1)还是最不常用的
第四次操作后：最常用的记录为("1", 1)，("2", 2)变为最不常用的
第五次操作后：大小超过了3，所以移除此时最不常使用的记录("2", 2)，加入记录("4", 4)，并且为最常使用的记录，然后("3", 2)变为最不常使用的记录
package com.csu.marden;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Demo1 {
	public static void main(String[] args) {
		int [][] arr={{1,1,1},{1,2,2},{1,3,2},{2,1},{1,4,4},{2,2}};
		int k=3;
		show(LRU(arr, k));
	}
	
	public static void show(int [] arr){
		for(int i=0;i<arr.length;i++){
			System.out.println(arr[i]);
		}
	}
	
	public static int[] LRU (int[][] operators, int k) {
		//使用数据结构HashMap和Queue
		HashMap<Integer,Integer> map=new HashMap<>();
		LinkedList<Integer> queue=new LinkedList<>();
		List<Integer> list=new ArrayList<>();
		for(int i=0;i<operators.length;i++){
			//判断当前执行哪个操作
			//当前执行写操作
			if(operators[i].length==3 && operators[i][0]==1){
				//判断当前缓存容量是否达到上限，即是否可以插入数据
				if(map.size()<k){
					map.put(operators[i][1], operators[i][2]);
					queue.addLast(operators[i][1]);
				}else{
					//首先删除队列头元素，再插入相应的元素节点
					int temp=queue.removeFirst();
					map.remove(temp);
					map.put(operators[i][1], operators[i][2]);
				}
			}
			//当前执行读操作
			if(operators[i].length==2 && operators[i][0]==2){
				//判断当前读取的key是否存在
				if(map.containsKey(operators[i][1])){
					
					list.add(map.get(operators[i][1]));
					//出队列，重新入队
					queue.remove((Object)operators[i][1]);
					queue.addLast(operators[i][1]);
				}else{
					list.add(-1);
				}
				
			}
		}
		int [] arr=new int [list.size()];
		for(int i=0;i<arr.length;i++){
			arr[i]=list.get(i);
		}
		return arr;
    }

}

 

3.请实现有重复数字的有序数组的二分查找。

输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

示例：

输出：5,4,[1,2,4,4,5]

输出：3

package com.csu.marden;

public class Demo3 {
	public static void main(String[] args) {
		int n=5;
		int v=4;
		int [] a={1,2,4,4,5};
		System.out.println(upper_bound_(n, v, a));
	}
	
	public static int upper_bound_ (int n, int v, int[] a) {
		if(n==0){
			return 1;
		}
		int start=0;
		int end=n-1;
		
		while(start<=end){
			int mid=(start+end)/2;
			if(a[mid]>=v){
				if(mid==start || a[mid-1]<v){
					return mid+1;
				}else{
					end=mid-1;
				}
			}else{
				start=mid+1;
			}
		}
		return n+1;
        
    }

}

二分查找的递归和非递归实现：

//非递归版本
public static int binarySearch(int [] arr,int target,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(arr[mid]==target){
				return mid;
			}else if(arr[mid]<target){
				start=mid+1;
			}else{
				end=mid-1;
			}
		}
		return -1;	
	}
	






//递归版本
public static int binarySearch1(int [] arr,int target,int start,int end){
		//递归结束条件
		if(start>end){
			return -1;
		}
		int mid=(start+end)/2;
		if(arr[mid]==target){
			return mid;
		}else if(arr[mid]>target){
			return binarySearch(arr, target, start, mid-1);
		}else{
			return binarySearch(arr, target, mid+1, end);
		}
	}

 

4.分别按照二叉树先序，中序和后序打印所有的节点。

package com.csu.marden;

public class Demo4 {
	public static void main(String[] args) {
		TreeNode root=new TreeNode(1);
		TreeNode node1=new TreeNode(2);
		TreeNode node2=new TreeNode(3);
		root.left=node1;
		root.right=node2;
		threeOrders(root);
	}
	
	
	
	public static void threeOrders (TreeNode root) {
		showPre(root);
		System.out.println("---------------");
		showMid(root);
		System.out.println("---------------");
		showAft(root);
		System.out.println("---------------");
    }
	
	public static void showPre(TreeNode root){
		if(root==null){
			return;
		}else{
			System.out.println(root.value);
			showPre(root.left);
			showPre(root.right);
		}
	}
	
	public static void showMid(TreeNode root){
		if(root==null){
			return;
		}else{
			showPre(root.left);
			System.out.println(root.value);
			showPre(root.right);
		}
	}
	
	public static void showAft(TreeNode root){
		if(root==null){
			return;
		}else{
			showPre(root.left);
			showPre(root.right);
			System.out.println(root.value);
		}
	}
	

}
class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
	public TreeNode(int value) {
		super();
		this.value = value;
	}
	public TreeNode() {
		super();
	}
	
}

非递归先序遍历：

package com.csu.marden;

import java.util.Stack;

public class Demo5 {
	public static void main(String[] args) {
		TreeNode root=new TreeNode(1);
		TreeNode node1=new TreeNode(2);
		TreeNode node2=new TreeNode(3);
		root.left=node1;
		root.right=node2;
		showPreOrder(root);
	}
	
	//非递归先序遍历
	public static void showPreOrder(TreeNode root){
		Stack<TreeNode> stack=new Stack<>();
		if(root!=null){
			//将根节点入栈
			stack.push(root);
			//将栈顶元素出栈，分别将其右节点和左节点入栈
			while(stack.size()>0){
				TreeNode temp=stack.pop();
				System.out.println(temp.value);
				if(temp.right!=null){
					stack.push(temp.right);
				}
				if(temp.left!=null){
					stack.push(temp.left);
				}
			}
		}
	}
}

非递归中序遍历：

	public static void showMidOrder(TreeNode root){
		Stack<TreeNode> stack=new Stack<>();
		//将根节点入栈
		stack.push(root);
		TreeNode temp=root.left;
		//while循环包含入栈条件（左节点存在则入栈）和出栈条件（栈不为空）
		while(temp!=null || stack.size()>0){
			//入栈
			if(temp!=null){
				stack.push(temp);
				temp=temp.left;
			}else{ //出栈
				temp=stack.pop();
				System.out.println(temp.value);
				temp=temp.right;
			}
		}
	}

非递归后序遍历：

对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。

/*
	 对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，
	此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。
	所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，
	该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。
	可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问      它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
	 */
	public static void showAftOrder(TreeNode root){
		Stack<TreeNode> stack=new Stack<>();
		//使用map记录每个节点被访问的次数
		Map<TreeNode,Integer> map=new HashMap<>();
		TreeNode temp=root;
		while(temp!=null || stack.size()>0){
			if(temp!=null){
				stack.push(temp);
				map.put(temp, 1);
				temp=temp.left;
			}else{
				temp=stack.peek();
				if(map.get(temp)==2){
					System.out.println(stack.pop().value);
					temp=null;
				}else{
					map.put(temp, 2);
					temp=temp.right;
				}
			}
		}
	}

 

5.判断给定的链表中是否有环（空间复杂度O（1）的解法）

//使用快慢指针判断链表是否有环
public static  boolean hasCycle1(ListNode head) {
		if(head==null || head.next==null){
			return false;
		}
		ListNode slow=head;
		ListNode fast=head.next;
		while(slow!=fast){
            //指针为null，则说明链表无环
			if(fast==null || fast.next==null){
				return false;
			}else{
				slow=slow.next;
				fast=fast.next.next;
			}
		}
		return true;
    }

 

6.将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

package com.csu.marden;

public class Demo7 {
	public static void main(String[] args) {
		ListNode l1=new ListNode();
		ListNode node1=new ListNode(2);
		ListNode node2=new ListNode(5);
		ListNode node3=new ListNode(8);
		l1.next=node1;
		node1.next=node2;
		node2.next=node3;
		
		ListNode l2=new ListNode();
		ListNode node11=new ListNode(1);
		ListNode node22=new ListNode(4);
		ListNode node33=new ListNode(7);
		ListNode node44=new ListNode(24);
		l2.next=node11;
		node11.next=node22;
		node22.next=node33;
		node33.next=node44;
		
		show(mergeTwoLists(l1, l2));
	}
	
	public static void show(ListNode head){
		ListNode temp=head.next;
		while(temp!=null){
			System.out.println(temp.value);
			temp=temp.next;
		}
	}
	
	
	//带头节点的链表
	 public static ListNode mergeTwoLists (ListNode l1, ListNode l2) {
		 ListNode newhead=new ListNode();
		 ListNode temp1=l1.next;
		 ListNode temp2=l2.next;
		 ListNode last=newhead;
		 while(temp1!=null && temp2!=null){
			 
			 if(temp1.value<=temp2.value){
				 //将temp1摘下
				 l1.next=temp1.next;
				 //将temp1插入到新节点之后
				 temp1.next=null;
				 last.next=temp1;
				 last=temp1;
				 temp1=l1.next;
			 }else{
				 //将temp2摘下
				 l2.next=temp2.next;
				 //将temp2插入到新节点之后
				 temp2.next=null;
				 last.next=temp2;
				 last=temp2;
				 temp2=l2.next;
			 }
		 }
		 if(temp1!=null && temp2==null){
			 last.next=temp1;
		 }
		 if(temp2!=null && temp1==null){
			 last.next=temp2;
		 }
		return newhead;
	    }

}

 

7.有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

package com.csu.marden;

public class Demo8 {
	public static void main(String[] args) {
		int [] arr={1,3,5,8,19,45};
		int K=3;
		System.out.println(findKth(arr, arr.length, K));
	}
	
	
	//寻找第k大的元素
	public static int findKth(int[] a, int n, int K) {
		return quickSort(a, K, 0, n-1);
        
    }
	
	public static int quickSort(int [] arr,int k,int start,int end){
		if(start>end){
			return -1;
		}
		int i=start;
		int j=end;
		int base=arr[start];
		while(i<j){
			while(i<j && arr[j]>=base){
				j--;
			}
			while(i<j && arr[i]<=base){
				i++;
			}
			if(i<j){
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		}
		//i=j
		arr[start]=arr[i];
		arr[i]=base;
		if(i==arr.length-k){
			return arr[i];
		}else if(i<arr.length-k){
			return quickSort(arr,k,i+1,end);
		}else{
			return quickSort(arr,k,start,i-1);
		}
	}

}

 

8.给定一个链表，删除链表的倒数第n个节点并返回链表的头指针

package com.csu.marden;

public class Demo9 {
	public static void main(String[] args) {
		ListNode head=new ListNode(1);
		ListNode node2=new ListNode(2);
		ListNode node3=new ListNode(3);
		ListNode node4=new ListNode(4);
		ListNode node5=new ListNode(5);
		head.next=node2;
		node2.next=node3;
		node3.next=node4;
		node4.next=node5;
		int n=2;
		show(head);
		System.out.println("---------------------------");
		show(removeNthFromEnd(head, n));
	}
	
	public static void show(ListNode head){
		ListNode temp=head;
		while(temp!=null){
			System.out.println(temp.value);
			temp=temp.next;
		}
	}
	
	//不带头节点
	public static ListNode removeNthFromEnd (ListNode head, int n) {
		if(head!=null){
			//保证n一定有效，即链表的长度大于等于n
			//如果要删除的节点在第一个位置
			if(n==getLength(head)){
				return head.next;
			}
			else{
				ListNode temp=head;
				int count=0;
				while(count!=getLength(head)-n-1){
					count++;
					temp=temp.next;
				}
				//此时temp指向待删除节点的前一个位置
				temp.next=temp.next.next;
				return head;
			}
		}
		return head;
    }
	
	public static int getLength(ListNode head){
		ListNode temp=head;
		int count=0;
		while(temp!=null){
			count++;
			temp=temp.next;
		}
		return count;
	}
	
	

}

 

9.对于一个给定的链表，返回环的入口节点，如果没有环，返回null

	//对于一个给定的链表，返回环的入口节点，如果没有环，返回null
    //方法一：使用Map集合判断
	public ListNode detectCycle(ListNode head) {
		Map<ListNode,Integer> map=new HashMap<>();
		ListNode temp=head;
		while(temp!=null){
			//map集合中已经包含当前结点，说明当前节点是环的入口
			if(map.containsKey(temp)){
				return temp;
			}else{
				map.put(temp, 1);
				temp=temp.next;
			}
		}
		return null;
    }





    
    //方法二：使用快慢指针
	 public ListNode detectCycle(ListNode head) {
		 if(head==null || head.next==null){
			 return null;
		 }
		 //定义快慢指针,从相同位置开始
		 ListNode slow=head;
		 ListNode fast=head;
		 while(true){
			 if(fast==null || fast.next==null){
				 return null;
			 }
			 fast=fast.next.next;
			 slow=slow.next;
			 if(fast==slow){
				 break;
			 }
		 }
		 //此时快指针和慢指针第一次相遇，将其中一个指针恢复到head位置，并调整步幅，直到第二次相遇的位置
		 //第二次相遇的位置即环的入口位置
		 fast=head;
		 while(fast!=slow){
			 fast=fast.next;
			 slow=slow.next;
		 }
		 return fast;   
	 }

 

10.假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

package com.csu.marden;

import java.util.ArrayList;
import java.util.List;

public class Demo11 {
	public static void main(String[] args) {
		ListNode head1=new ListNode(1);
		ListNode node2=new ListNode(2);
		ListNode node3=new ListNode(3);
		ListNode node5=new ListNode(4);
		head1.next=node2;
		node2.next=node3;
		node3.next=node5;
		
		ListNode head2=new ListNode(3);
		ListNode node4=new ListNode(4);
		head2.next=node4;
		System.out.println("链表1：");
		show(head1);
		System.out.println("链表2：");
		show(head2);
		System.out.println("求和后链表：");
		show(addInList(head1, head2));
	}
	
	
	
	public static void show(ListNode head){
		ListNode temp=head;
		while(temp!=null){
			System.out.println(temp.value);
			temp=temp.next;
		}
	}
	
	//假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
	//给定两个这种链表，请生成代表两个整数相加值的结果链表。
	//例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
	public static ListNode addInList (ListNode head1, ListNode head2) {
		//获取第一个链表的值
		List<Integer> list1=new ArrayList<>();
		ListNode temp1=head1;
		while(temp1!=null){
			list1.add(temp1.value);
			temp1=temp1.next;
		}
		int num1=0;
		for(int i=list1.size()-1;i>=0;i--){
			num1=(int) (num1+list1.get(i)*Math.pow(10, list1.size()-i-1));
		}
		//获取第二个链表的值
		List<Integer> list2=new ArrayList<>();
		ListNode temp2=head2;
		while(temp2!=null){
			list2.add(temp2.value);
			temp2=temp2.next;
		}
		int num2=0;
		for(int i=list2.size()-1;i>=0;i--){
			num2=(int) (num2+list2.get(i)*Math.pow(10, list2.size()-i-1));
		}
		//将两个链表的值相加，并重新创建新的链表
		int result=num1+num2;
		int length=(""+result).length();
		int [] arr=new int [length];
		for(int i=arr.length-1;i>=0;i--){
			arr[i]=result%10;
			result=result/10;
		}
		ListNode newhead=new ListNode(arr[0]);
		ListNode last=newhead;
		int i=1;
		while(i<arr.length){
			ListNode temp=new ListNode(arr[i]);
			last.next=temp;
			last=last.next;
			i++;
		}
		return newhead;
    }
	
	
	
	

}

 

11.给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

package com.csu.marden;

import java.util.ArrayList;
import java.util.LinkedList;


public class Demo13 {
	public static void main(String[] args) {
		TreeNode root=new TreeNode(3);
		TreeNode node2=new TreeNode(9);
		TreeNode node3=new TreeNode(20);
		TreeNode node4=new TreeNode(15);
		TreeNode node5=new TreeNode(17);
		root.left=node2;
		root.right=node3;
		node3.left=node4;
		node3.right=node5;
		show(levelOrder1(root));
		
	}
	
	public static void show(ArrayList<ArrayList<Integer>> list){
		for(int i=0;i<list.size();i++){
			for(int j=0;j<list.get(i).size();j++){
				System.out.print(list.get(i).get(j)+"  ");
			}
			System.out.println();
		}
	}
	
	public static ArrayList<ArrayList<Integer>> levelOrder1(TreeNode root) {
		if(root==null){
			return null;
		}
		ArrayList<ArrayList<Integer>> list=new ArrayList<>();
		LinkedList<TreeNode> queue=new LinkedList<>();
		queue.addLast(root);
		while(queue.size()>0){         //队列长度动态变化
			int length=queue.size();   //length长度固定，即当前层次的节点数目
			ArrayList<Integer> templist=new ArrayList<>();
			for(int i=0;i<length;i++){
				TreeNode temp=queue.removeFirst();
				templist.add(temp.value);
				if(temp.left!=null){
					queue.addLast(temp.left);
				}
				if(temp.right!=null){
					queue.addLast(temp.right);
				}
			}
			list.add(templist);
		}
		return list;
    }
	


}

 

12.输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

package com.csu.marden;

import java.util.HashMap;
import java.util.Map;

public class Demo14 {
	public static void main(String[] args) {
		ListNode pHead1=new ListNode(1);
		ListNode pHead2=new ListNode(11);
		ListNode node1=new ListNode(2);
		ListNode node2=new ListNode(3);
		ListNode node3=new ListNode(4);
		ListNode node4=new ListNode(6);
		ListNode node5=new ListNode(7);
		ListNode node6=new ListNode(8);
		pHead1.next=node1;
		node1.next=node2;
		node2.next=node3;
		node3.next=node4;
		
		pHead2.next=node5;
		node5.next=node6;
		node6.next=node3;
		System.out.println(FindFirstCommonNode(pHead1, pHead2).value);
	}
	

	
	//输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，
	//所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
	
	
	 public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		 if(pHead1==null || pHead2==null){
			 return null;
		 }
		 Map<ListNode,Integer> map=new HashMap<>();
		 ListNode temp=pHead1;
		 while(temp!=null){
			 map.put(temp, 1);
			 temp=temp.next;
		 }
		 temp=pHead2;
		 while(temp!=null){
			 if(map.containsKey(temp)){
				 return temp;
			 }else{
				 temp=temp.next;
			 }
		 }
		return null;
	    }

}

 

13.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

package com.csu.marden;

import sun.util.calendar.JulianCalendar;

public class Demo15 {
	public static void main(String[] args) {
		System.out.println(JumpFloor(5));
	}
	
	public static int JumpFloor(int target) {
		//动态规划,dp[i]表示调到第i个台阶有多少种方法
		int [] dp=new int [target+1];
		//初始化
		dp[1]=1;
		dp[0]=1;
		for(int i=2;i<dp.length;i++){
			dp[i]=dp[i-1]+dp[i-2];
		}
		return dp[target];
    }

}

 

14.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

package com.csu.marden;

import java.util.Stack;

public class Demo16 {
	public static void main(String[] args) {
		
	}
	//用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
	static Stack<Integer> stack1 = new Stack<Integer>();
    static Stack<Integer> stack2 = new Stack<Integer>();
    
    public static void push(int node) {
        stack1.push(node);
    }
    
    public static int pop() {
    	//先将stack1中的所有元素出栈，并以此入栈stack2
    	while(stack1.size()>0){
    		stack2.push(stack1.pop());
    	}
    	int temp=stack2.pop();
    	while(stack2.size()>0){
    		stack1.push(stack2.pop());
    	}
		return temp;
    }

}

 

15.实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

package com.csu.marden;

public class Demo17 {
	public static void main(String[] args) {
		System.out.println(sqrt(1034));
	}
	
	//采用二分法计算
	public static int sqrt (int x) {
		if(x==0 || x==1){
			return x;
		}
		int start=0;
		int end=x;
		while(start<=end){
			int mid=(start+end)/2;
			if(mid*mid==x){
				return mid;
			}
			else if(mid*mid<x){
				if((mid+1)*(mid+1)>x){
					return mid;
				}else{
					start=mid+1;
				}
			}else{
				end=mid-1;
			}
		}
		return 0;

    }

}

 

16.给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列.
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

package com.csu.marden;

import java.util.Stack;

public class Demo18 {
	public static void main(String[] args) {
		System.out.println(isValid("["));
	}

	/*
	 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
		括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
	 */
	
	//通过栈，判断括号是否匹配
	public static boolean isValid (String s) {
		Stack<Character> stack1=new Stack<>();
		Stack<Character> stack2=new Stack<>();
		
		//首先判断括号序列的长度是否为偶数
		if(s.length()%2==0){
			//1.将所有符号压入stack1
			for(int i=0;i<s.length();i++){
				stack1.push(s.charAt(i));
			}
			//2.将stack1中的元素出栈
			while(!stack1.isEmpty()){
				if(stack1.peek()=='}' || stack1.peek()==']' || stack1.peek()==')'){
					stack2.push(stack1.pop());
				}
				else if(stack1.peek()=='{'){
					if(stack2.isEmpty()){
						return false;
					}else{
						if(stack2.peek()=='}'){
							stack2.pop();
							stack1.pop();
						}else{
							stack2.push(stack1.pop());
						}
					}
					
				}
				else if(stack1.peek()=='['){
					if(stack2.isEmpty()){
						return false;
					}else{
						if(stack2.peek()==']'){
							stack2.pop();
							stack1.pop();
						}else{
							stack2.push(stack1.pop());
						}
					}
					
				}
				else if(stack1.peek()=='('){
					if(stack2.isEmpty()){
						return false;
					}else{
						if(stack2.peek()==')'){
							stack2.pop();
							stack1.pop();
						}else{
							stack2.push(stack1.pop());
						}
					}
					
				}
			}
			if(stack2.isEmpty()){
				return true;
			}else{
				return false;
			}
		}else{
			return false;
		}
		
    }
}

 

17.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

	public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		TreeNode root=new TreeNode(pre[0]);
		if(pre.length==1){
			root.left=null;
			root.right=null;
			return root;
		}
		//得到中序中根的位置
		int temp=pre[0];
		int index;
		for(index=0;index<in.length;index++){
			if(in[index]==temp){
				break;
			}
		}
		//创建左子树
		if(index>0){
			int [] new_pre=new int [index];
			int [] new_in=new int [index];
			for(int i=0;i<new_pre.length;i++){
				new_pre[i]=pre[i+1];
			}
			for(int i=0;i<new_in.length;i++){
				new_in[i]=in[i];
			}
			root.left=reConstructBinaryTree(new_pre, new_in);
			
		}else{
			root.left=null;
		}
		//创建右子树
		if(index<in.length-1){
			int [] new_pre=new int [pre.length-index-1];
			int [] new_in=new int [pre.length-index-1];
			for(int i=0;i<new_pre.length;i++){
				new_pre[i]=pre[1+index+i];
			}
			for(int i=0;i<new_in.length;i++){
				new_in[i]=in[index+1+i];
			}
			root.right=reConstructBinaryTree(new_pre, new_in);
		}else{
			root.right=null;
		}
		return root; 
    }

 

18.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

package com.csu.marden;

import java.util.HashSet;
import java.util.Set;



public class Demo3 {
	public static void main(String[] args) {
		int [] arr={2,3,4,5};
		System.out.println(maxLength(arr));
	}
	


    //暴力枚举
	public static  int maxLength (int[] arr) {
		int maxLength=0;
		for(int i=0;i<arr.length;i++){
			for(int j=i+1;j<arr.length;j++){
				if(judge(arr, i, j)){
					maxLength=Math.max(maxLength, j-i+1);
				}
			}
		}
		return maxLength;
    }
	
	//判断是否为无重复子串
	public static boolean judge(int [] arr,int start,int end){
		Set<Integer> set	=new HashSet<>();
		for(int i=start;i<=end;i++){
			if(set.contains(arr[i])){
				return false;
			}else{
				set.add(arr[i]);
			}
		}
		return true;
		}

}

package com.csu.marden;

import java.util.HashSet;
import java.util.Set;

public class Demo4 {
	public static void main(String[] args) {
		String str="pwwkew";
		System.out.println(maxLength(str));
		
	}
	
    //使用滑动窗口技术
    //判断重复使用数据结构set或者map
	public static  int maxLength (String str) {
		if(str==null || str.length()==0){
			return 0;
		}
		Set<Character> set=new HashSet<>();
		int start=0;
		int end=0;
		int maxLength=0;
		int length=str.length();
		while(start<length){
			while(end<length && !set.contains(str.charAt(end))){
				set.add(str.charAt(end));
				end++;
			}
			maxLength=Math.max(maxLength, end-start);
			if(end==length){
				break;
			}else{
				set.remove(str.charAt(start));
				start++;
			}
		}
		return maxLength;
	}

}

 

19.给定一个二叉树和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于sum 的路径

 public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

 

20.给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

该二叉树之字形层序遍历的结果是

[

[3],

[20,9],

[15,7]

]

package com.csu.marden;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

public class Demo5 {
	public static void main(String[] args) {
		TreeNode root=new TreeNode(3);
		TreeNode node1=new TreeNode(9);
		TreeNode node2=new TreeNode(20);
		TreeNode node3=new TreeNode(15);
		TreeNode node4=new TreeNode(7);
		root.left=node1;
		root.right=node2;
		node1.left=node3;
		node1.right=node4;
		show(zigzagLevelOrder(root) );
	}
	
	
	public static void show(ArrayList<ArrayList<Integer>> list){
		for(int i=0;i<list.size();i++){
			for(int j=0;j<list.get(i).size();j++){
				System.out.print(list.get(i).get(j)+"  ");
			}
			System.out.println();
		}
	}
	
	
	
	public static ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
		if(root==null){
			return null;
		}
		ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
		LinkedList<TreeNode> queue=new LinkedList<>();
		queue.addLast(root);  //将根节点入队
		boolean flag=false;     //判断是否反转(交替反转)
		while(!queue.isEmpty()){
			int length=queue.size();
			ArrayList<Integer> list=new ArrayList<>();
			for(int i=0;i<length;i++){
				TreeNode temp=queue.pop();
				list.add(temp.value);
				if(temp.left!=null){
					queue.add(temp.left);
				}
				if(temp.right!=null){
					queue.add(temp.right);
				}
			}
			if(flag==false){
				result.add(list);
				flag=!flag;
			}else{
				Collections.reverse(list);
				result.add(list);
				flag=!flag;
			}
		}
		return result;
    }

}

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

面试算法刷题

面试必考真题 的相关文章

  • React 引入ant-design开发指南

    使用create react app搭建react开发环 创建react脚手架 create react app react antd demo 进入react antd demo cd react antd demo 运行react an

  • MYSQL中索引与主键的区别

    MYSQL中索引与主键的区别 索引 索引好比是一本书的目录 可以快速的通过页码找到你需要的那一页 惟一地标识一行 主键 做为数据库表唯一行标识 作为一个可以被外键有效引用的对象 索引是一种特殊的文件 InnoDB数据表上的索引是表空间的一个

  • Unity中的重载和重写

    Unity中的重载和重写 一 重载 二 重写 三 重载和重写的区别 一 重载 重载 两个必须一个可以 参数名必须相同 参数列表必须不同 返回值类型可以不同 代码示例 using System Collections using System

  • Linux 磁盘命令工具 比df更好用

    对于分析磁盘使用情况 有两个非常好用的命令 du 和 df 简单来说 这两个命令的作用是这样的 du 命令 它是英文单词 disk usage 的简写 主要用于查看文件与目录占用多少磁盘空间 df 命令 它是英文单词 disk free 的

  • python爬取证券之星网站

    周末无聊 找点乐子 coding utf 8 import requests from bs4 import BeautifulSoup import random import time 抓取所需内容 user agent Mozilla

  • 安卓逆向学习-Crack01 学习记录

    Crack01 学习记录 要感谢京峰教育 资料下载 https download csdn net download m0 47210241 85053839 利用jadx gui打开 分析代码 package com zhy editVi

  • nodejs封装api

    安装了nodeJs 执行 安装淘宝镜像 npm install g cnpm registry https registry npm taobao org 安装 yarn 我使用这个 淘宝镜像总是莫名其妙各种bug npm install

  • aix安装 php,CNESA

    aix安装samba服务器可以使用两种方式安装 一种是使用rpm包进行安装 一种是使用源码编译安装 一 使用samba的rpm包进行安装 1 下载samba的rpm包 下载地址为http www bullfreeware com searc

  • C++笔记--线程间共享数据

    当线程在访问共享数据的时候 必须制定一些规矩 用来限定线程可访问的数据位 还有 一个线程更新了共享数据 需要对其他线程进行通知 从易用性的角度 同一进程中的多个线程进行数据共享 错误的共享数据使用是产生并发bug的一个主要原因 当涉及到共享

  • 为什么训练集用fit_transform()而测试集用transform()及sklearn.feature_extraction.text.CountVectorizer API详解

    真正讲明白的 https blog csdn net yyhhlancelot article details 85097656 API https scikit learn org stable modules generated skl

  • mysql+mybatis 批量插入与批量更新

    首先批量更新需要增加 数据库的链接必须加上但是数据库连接必须加上 allowMultiQueries true 属性 不然会报错 You have an error in your SQL syntax check the manual t

  • 各种源码下载地址(目前只有ffmpeg和nginx,libcurl,RapidJSON 文档)

    各种源码下载地址 目前只有ffmpeg和nginx libcurl RapidJSON 文档 ffmpeg源码下载地址 http ffmpeg org download html releases nginx源码下载地址 http hg n

  • H5监听移动端物理/浏览器返回键

    JavaScript没有监听物理返回键的API 所以只能使用 popstate 事件监听 工具类如下 export function handleBrowserGoBack back console log back pushHistory

  • 论文阅读——基于深度学习智能垃圾分类

    B Fu S Li J Wei Q Li Q Wang and J Tu A Novel Intelligent Garbage Classification System Based on Deep Learning and an Emb

  • su命令切换用户输入密码后，提示：鉴定故障

    在终端通过su命令切换用户输入密码后 提示 鉴定故障 这是因为在安装linux系统时未设置root用户密码造成的 需要重新设置密码后再切换用户 具体操作命令如下 设置root用户密码 sudo passwd root 切换用户 su

  • 三步搞定ABAP DOI操作EXCEL

    ABAP可以使用OLE与DOI两种方式实现操作EXCEL 使用OLE时 每个单元格的值和样式都需要写代码实现 特别是对于不规则的格式 代码量巨大 而DOI是从服务器已经上传的EXCEL模板中下载模板然后打开修改实现数据保存 当然 也可以直接

  • springboot中的kafka的KafkaTemplate的配置类

    package com lf report utils import org apache kafka clients producer ProducerConfig import org apache kafka common seria

  • opencv 智能答卷识别系统(一)

    目标 这里是2 智能答卷之别系统二 识别答卷答案 识别准号证号码 识别姓名 识别试卷类别 试卷是有标记的 如试卷上方的黑框 排序结构 使用c 的标准排序算法 struct Ruley bool operator const Rect a1

  • 华为OD机试真题-座位调整-2023年OD统一考试（B卷）

    题目描述 疫情期间课堂的座位进行了特殊的调整 不能出现两个同学紧挨着 必须隔至少一个空位 给你一个整数数组 desk表示当前座位的占座情况 由若干 0 和 1 组成 其中 0 表示没有占位 1 表示占位 在不改变原有座位秩序情况下 还能安排

随机推荐

  • C#获取当前路径 -- 7种方法

    目录 一 代码 二 路径区别 三 参考文献 一 代码 推荐使用第3种 internal static class Program static void Main 获取模块的完整路径 string path1 System Diagnost

  • C++：入门学习C++，它在C的基础上做了哪些修改？

    文章目录 命名空间 缺省参数 函数重载 引用 引用作为函数返回值 引用的收益 引用和指针的区别 引用和指针的对比 内联函数 内联函数的特性 内联函数和宏的关系 指针空值问题 命名空间 首先看这样的代码 include

  • vue canvas typescript 绘制时间标尺

    项目中有个需求 将对象一天内对应的不同的状态在时间轴上显示出来 调研的方案有5种 1 时间轴用div画 时间轴上遮罩的状态改变则改变时间轴div本身的颜色 2 时间轴用div画 时间轴上的遮罩用div画 状态改变则改变遮罩div的颜色 时间

  • 详解原码、反码、补码——深入理解补码

    学过计算机原理的人都知道原码 反码 补码 但是有多少人知道为什么会有这三种码呢 这三种码又是用来干嘛的呢 众所周知 在计算机的世界只有01 那么显然所有的数都得转成二进制 这样计算机才能够理解 如何将一个十进制的数转成二进制就不说了 说下原

  • linux文件代理高速下载,告别龟速下载!

    原始下载链接 wget https github com SwinTransformer storage releases download v1 0 0 swin tiny patch4 window7 224 pth 高速下载 wget

  • windows注册表参数(%1,%2,%v)

    windows注册表是不区分大小写的 参数 含义 1 文件路径 2 系统默认的打印机 3 文件扇区 4 端口 D 文件路径 L 文件长路径 V 文件路径 W 当前文件的父目录的路径 参考 https blog csdn net meng s

  • 唯一化算法

    源代码git地址 对于无序列表的唯一化算法 从前往后依次处理节点p 在p的前驱中查找 通过find函数 值相同者 则调用remove函数将相同者删除 template

  • 1093: 数1的个数

    存限制 128 MB 题目描述 给定一个十进制正整数n 1 n 10000 写下从1到n的所有整数 然后数一下其中出现的数字 1 的个数 例如当n 2时 写下1 2 这样只出现了1个 1 当n 12时 写下1 2 3 4 5 6 7 8 9

  • Qt stylesheet border-color属性，QFontMetrics Class

    一 border color border color 属性设置四条边框的颜色 此属性可设置 1 到 4 种颜色 border color 属性是一个简写属性 可设置一个元素的所有边框中可见部分的颜色 或者为 4 个边分别设置不同的颜色 请

  • 程序员常用命令集，只收集名字 ^^

    export PATH home hanmeimei local bin PATH which ls file helloworld objdump help objdump h s d exit o ldd helloworld ulim

  • ROS里程计：navigation/Tutorials/RobotSetup/Odom

    ROS里程计 navigation Tutorials RobotSetup Odom 通过ROS发布里程表信息 1 通过ROS发布里程表信息 2 nav msgs Odometry消息 3 使用tf发布Odometry转换 4 编写代码

  • IDEA中web项目c3p0-config.xml文件的配置及存放目录

    IDEA中web项目c3p0 config xml文件的配置及存放目录 今天在IDEA上折腾了很长一段时间 始终连接不上数据库 日志总是说找不到mysql 这是我的测试代码 Test public void fun2 throws SQLE

  • windows下java swt实现操作redis的客户端工具

    原文 windows下java swt实现操作redis的客户端工具 源代码下载地址 http www zuidaima com share 1902705862708224 htm redisclient 1 0 正式发布 适用于多个 R

  • ip广播系统服务器软件,【网络广播服务器软件IP网络广播软件数字广播软件】 - 太平洋安防网...

    参数说明 品牌 万凯wankai 详细描述 具备 版权局颁发的计算机软件 标准TCP IP网络协议 安装于连接以太网的计算机 IP广播的网络终端具有 立的ID号与IP地址 可以单 接收服务器的个性化定时播放节目 定时播放的操作 可以通过电脑

  • Hibernate之inverse和cascade详解

    继Hibernate学习笔记整理之后 发现inverse和cascade这两个属性在配置过程中比较含糊 仔细比较一下是有些地方比较像 所以很容易搞糊涂 借助此文来阐述下inverse和cascade的区别 什么是inverse 默认值为fa

  • centos8安装postgresql步骤

    1 安装源 1 sudo yum y install epel release 2 postgresql官网发布的postgresql对应的安装源 sudo yum install y https download postgresql o

  • There are multiple modules with names that only differ in casing.

    问题 在 npm run dev 后 控制台出现警告 没有出现链接 但是在浏览器上直接输入地址http localhost 8080 又可显示界面 There are multiple modules with names that onl

  • 华为机试HJ55 挑7

    HJ55 挑7 Python 题目 解题思路 代码 结果 题目 解题思路 1 多组输入 需要循环 2 循环查找到输入数值即可 字符串查找用in 能否整除 求余后判断是否 0 3 最后打印找到的数字的列表长度 代码 def func n in

  • 逐行对比LLaMA2和LLaMA模型源代码

    几个小时前 2023年7月18日 Meta发布了允许商用的开源模型LLaMA2 笔者逐行对比了LLaMA2模型源代码 和LLaMA相比 几乎没有改动 细节如下 是否改动 LLaMA2 LLaMA 模型整体构架 无 Transformer T

  • 面试必考真题

    1 输入一个链表 反转链表后 输出新链表的表头 package com csu marden public class Demo1 public static void main String args Node head new Node

热门标签