笔试/面试题杂说

以你之姓@ 2022-05-11 13:18 304阅读 0赞

##### *        开始各种笔试了，从明天起会高频不定期的更新各种题，java的，flag在这里立起来！一起加油！* #####

# 1、分解质因数 #

import java.util.Scanner;
    
    /* * 分解质因数 */
    public class Prime_Factorization { 
    	public static void main(String[] args) { 
    		Scanner in = new Scanner(System.in);
    		int n = in.nextInt();
    		prime_factorization(n);
    		in.close();
    	}
    	
    	public static void prime_factorization(int n) { 
    		if (n < 2) { 
    			throw new RuntimeException("参数错误");
    		}
    		for(int i = 2;i * i < n;i++) { 
    			while(n % i == 0) { 
    				System.out.print(i + " ");
    				n /= i;
    			}
    		}
    		if(n != 1) { 
    			System.out.println(" " + n);
    		}
    	}
    }

# 2、输出1~n之间的所有素数 #

import java.util.Scanner;
    
    /* * 输出1~n之间的所有素数 */
    public class Print_Prime { 
    	public static void main(String[] args) { 
    		Scanner in = new Scanner(System.in);
    		int n = in.nextInt();
    		print_prime(n);
    		in.close();
    	}
    	
    	public static void print_prime(int n) { 
    		if(n < 2) { 
    			return;
    		}
    		System.out.print(2 + " ");
    		//直接看奇数
    		for(int i = 3; i < n;i += 2) { 
    			int j;
    			for(j = 2;j < Math.sqrt(i);j++) { 
    				if(i % j == 0) { 
    					break;
    				}
    			}
    			if(j == (int)Math.sqrt(i) + 1) { 
    				System.out.print(i + " ");
    			}
    		}
    	}
    }

# 3、快速排序 #

/* * 快速排序 */
    public class QuickSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 11,55,3,4,7,99,5};
    		new QuickSort().quickSort(arr,0,arr.length - 1);
    		for(int i = 0;i < arr.length;i++) { 
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	public void quickSort(int[] arr,int L,int R) { 
    		int i = L;
    		int j = R;
    		int pivot = arr[(L + R) >> 1];
    		while(i <= j) { 
    			while(arr[i] < pivot) { 
    				i++;
    			}
    			while(arr[j] > pivot) { 
    				j--;
    			}
    			if(i <= j) { 
    				int temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    				i++;
    				j--;
    			}
    		}
    		if(j > L) { 
    			quickSort(arr, L, j);
    		}
    		if (i < R) { 
    			quickSort(arr, i, R);
    		}
    	}
    }

# 4、插入排序 #

/* * 插入排序 */
    public class InsertSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 11,55,3,4,7,99,5};
    		new InsertSort().insertSort(arr);
    		for(int i = 0;i < arr.length;i++) { 
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	public void insertSort(int[] arr) { 
    		for(int i = 1;i < arr.length;i++) { 
    			int value = arr[i];
    			int j;
    			for(j = i - 1;j >= 0;j--) { 
    				if (value < arr[j]) { 
    					arr[j + 1] = arr[j];
    				}else if(value >= arr[j]) { 
    					break;
    				}
    			}
    			arr[j + 1] = value;
    		}
    		//第二种写法，其实一样
    // for(int i = 1;i < arr.length;i++) { 
    // int value = arr[i];
    // int j = i - 1;
    // while(j >= 0 && arr[j] > value) { 
    // arr[j + 1] = arr[j];
    // j--;
    // }
    // arr[++j] = value;
    // }
    	}
    }

# 5、选择排序 #

/* * 选择排序 */
    public class SelectSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 11,55,3,4,7,99,5};
    		new SelectSort().selectSort(arr);
    		for (int i = 0; i < arr.length; i++) { 
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	public void selectSort(int[] arr) { 
    		for(int i = 0;i < arr.length - 1;i++) { 
    			int minIndex = i;
    			for(int j = i + 1;j < arr.length;j++) { 
    				if (arr[minIndex] > arr[j]) { 
    					minIndex = j;
    				}
    			}
    			int temp = arr[i];
    			arr[i] = arr[minIndex];
    			arr[minIndex] = temp;
    		}
    	}
    }

# 6、冒泡排序 #

/* * 冒泡排序 */
    public class BubbleSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 11,55,3,4,7,99,5};
    		new BubbleSort().bubbleSort(arr);
    		for (int i = 0; i < arr.length; i++) { 
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	public void bubbleSort(int[] arr) { 
    		for(int i = 0;i < arr.length - 1;i++) { 
    			for(int j = 0;j < arr.length - i - 1;j++) { 
    				if (arr[j] > arr[j + 1]) { 
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    	}
    }

# 7、二分查找（递归与非递归） #

/* * 二分查找（递归与非递归） */
    public class BinarySearch{ 
    	public static void main(String[] args) { 
    		//注意二分查找针对的是有序数列
    		int[] arr = { 3,4,5,7,11,55,99};
    		int n1 = new BinarySearch().binarySearch1(arr,55);
    		int n2 = new BinarySearch().binarySearch2(arr,0,arr.length,99);
    		System.out.println(n1);
    		System.out.println(n2);
    	}
    
    	/* * 非递归 */
    	public int binarySearch1(int[] arr,int k) { 
    		int i = 0;
    		int j = arr.length - 1;
    		//注意这里一定要是<=
    		while(i <= j) { 
    			int mid = (i + j) >> 1;
    			if (arr[mid] == k) { 
    				return mid;
    			}else if (arr[mid] < k) { 
    				i = mid + 1;
    			}else { 
    				j = mid - 1;
    			}
    		}
    		return -1;
    	}
    	
    	/* * 递归 */
    	public int binarySearch2(int[] arr,int left,int right,int k) { 
    		//注意终止条件
    		if (left > right) { 
    			return -1;
    		}
    		int mid = (left + right) >> 1;
    		if(arr[mid] == k) { 
    			return mid;
    		}else if(arr[mid] < k) { 
    			return binarySearch2(arr, mid + 1, right, k);
    		}else { 
    			return binarySearch2(arr, left, mid - 1, k);
    		}
    	}
    }

# 8、堆排序 #

public class HeapSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 11,55,3,4,7,99,5};
    		heapSort(arr);
    	}
    
    	public static void heapSort(int[] arr) { 
    		//建立初始堆
    		//(arr.length-1)/2最后一个非叶子节点
    		for(int i = (arr.length - 1) / 2;i >= 0;i--) { 
    			heapOne(arr,arr.length,i);
    		}
    		
    		int n = arr.length;
    		while(n > 0) { 
    			System.out.print(arr[0] + " ");
    			arr[0] = arr[n - 1];
    			n--;
    			heapOne(arr, n, 0);
    		}
    	}
    	
    	//n：堆中的有效数据 k：待筛选节点，让k节点落到底层
    	public static void heapOne(int[] arr,int n,int k) { 
    		int k1 = 2 * k + 1;//左孩子
    		int k2 = 2 * k + 2;//右孩子
    		if(k1 >= n && k2 >= n) { //已经是叶子节点
    			return;
    		}
    		int a1 = Integer.MAX_VALUE;
    		int a2 = Integer.MAX_VALUE;
    		if(k1 < n) { 
    			a1 = arr[k1];//左孩子值
    		}
    		if(k2 < n) { 
    			a2 = arr[k2];//右孩子值
    		}
    		
    		//已经符合堆的要求
    		if (arr[k] <= a1 && arr[k] <= a2) { 
    			return;
    		}
    		
    		//找到左右孩子中最小的，和它交换
    		if (a1 < a2) { 
    			int temp = arr[k];
    			arr[k] = arr[k1];
    			arr[k1] = temp;
    			heapOne(arr, n, k1);//继续筛选子树
    		}else { 
    			int temp = arr[k];
    			arr[k] = arr[k2];
    			arr[k2] = temp;
    			heapOne(arr, n, k2);//继续筛选子树
    		}
    	}
    }

# 9、反转单链表 #

/* * 反转单链表 */
    class Node{ 
    	int value;
    	Node next;
    	public Node(int data) { 
    		this.value = data;
    	}
    }
    
    public class ReverseSignleList { 
    	
    	public static void main(String[] args) { 
    		Node node = new Node(5);
    		node.next = new Node(4);
    		node.next.next = new Node(3);
    		node.next.next.next = new Node(2);
    		node.next.next.next.next = new Node(1);
    		Node head = reverse(node);
    		while(head != null) { 
    			System.out.print(head.value + " ");
    			head = head.next;
    		}
    	}
    	
    	public static Node reverse(Node head) { 
    		Node cur = null;
    		Node next = null;
    		while(head != null) { 
    			next = head.next;
    			head.next = cur;
    			cur = head;
    			head = next;
    		}
    		return cur;
    	}
    }

# 10、反转双向链表 #

/* * 反转双向链表 */
    class DoubleNode{ 
    	int value;
    	DoubleNode pre;
    	DoubleNode next;
    	public DoubleNode(int data) { 
    		this.value = data;
    	}
    }
    
    public class ReverseDoubleList { 
    	public static void main(String[] args) { 
    		DoubleNode node = new DoubleNode(5);
    		node.next = new DoubleNode(4);
    		node.pre = null;
    		node.next.next = new DoubleNode(3);
    		node.next.pre = node;
    		node.next.next.next = new DoubleNode(2);
    		node.next.next.pre = node.next;
    		node.next.next.next.next = new DoubleNode(1);
    		node.next.next.next.pre = node.next.next;
    		node.next.next.next.next.next = null;
    		DoubleNode head = reverse(node);
    		DoubleNode tail = null;
    		while(head != null) { 
    			System.out.print(head.value + " ");
    			tail = head;
    			head = head.next;
    		}
    		System.out.println();
    		while(tail != null) { 
    			System.out.print(tail.value + " ");
    			tail = tail.pre;
    		}
    	}
    	
    	public static DoubleNode reverse(DoubleNode head) { 
    		DoubleNode pre = null;
    		DoubleNode next = null;
    		while(head != null) { 
    			next = head.next;
    			head.next = pre;
    			head.pre = next;
    			pre = head;
    			head = next;
    		}
    		return pre;
    	}
    	
    }

# 11、用一个栈实现另一个栈的排序 #

/* * 用一个栈实现另一个栈的排序 */
    import java.util.Stack;
    
    public class SortStackByStack { 
    	Stack<Integer> stackData = null;
    	Stack<Integer> stackHelp = null;
    	
    	public SortStackByStack() { 
    		stackData = new Stack<>();
    		stackHelp = new Stack<>();
    		stackData.push(3);
    		stackData.push(4);
    		stackData.push(5);
    		stackData.push(2);
    		stackData.push(6);
    		stackData.push(7);
    	}
    	
    	public static void main(String[] args) { 
    		SortStackByStack s = new SortStackByStack();
    		s.sortStackByStack();
    		while(!s.stackData.isEmpty()) { 
    			System.out.print(s.stackData.pop() + " ");
    		}
    	}
    	
    	public void sortStackByStack() { 
    		while(!stackData.isEmpty()) { 
    			int cur = stackData.pop();
    			if (stackHelp.isEmpty() || cur >= stackHelp.peek()) { 
    				stackHelp.push(cur);
    			}else { 
    				while(!stackHelp.isEmpty() && stackHelp.peek() > cur) { 
    					stackData.push(stackHelp.pop());
    				}
    				stackHelp.push(cur);
    			}
    		}
    		while(!stackHelp.isEmpty()) { 
    			stackData.push(stackHelp.pop());
    		}
    	}
    }

# 12、设计一个具有getMin()功能的栈（两种方式） #

/* * 用两种方式设计一个具有getMin功能的栈 */
    import java.util.Stack;
    
    public class StackWithGetMin { 
    	public static void main(String[] args) { 
    		MyStack1 stack1 = new MyStack1();
    		stack1.push(5);
    		stack1.push(6);
    		stack1.push(2);
    		stack1.push(3);
    		stack1.push(7);
    		stack1.push(1);
    		System.out.println("当前最小值：" + stack1.getMin());
    		System.out.println("弹出：" + stack1.pop());
    		System.out.println("当前最小值" + stack1.getMin());
    		
    		MyStack1 stack2 = new MyStack1();
    		stack2.push(5);
    		stack2.push(6);
    		stack2.push(2);
    		stack2.push(3);
    		stack2.push(7);
    		stack2.push(1);
    		System.out.println("当前最小值：" + stack2.getMin());
    		System.out.println("弹出：" + stack2.pop());
    		System.out.println("当前最小值" + stack2.getMin());
    	}
    }
    
    class MyStack1{ 
    	Stack<Integer> stackData = null;
    	Stack<Integer> stackMin = null;
    	public MyStack1() { 
    		stackData = new Stack<>();
    		stackMin = new Stack<>();
    	}
    	public void push(int data) { 
    		if (stackMin.isEmpty()) { 
    			stackMin.push(data);
    		}else if (data < stackMin.peek()) { 
    			stackMin.push(data);
    		}
    		stackData.push(data);
    	}
    	public int pop() { 
    		if (stackData.isEmpty()) { 
    			throw new RuntimeException("栈为空");
    		}
    		int value = stackData.pop();
    		if (value == stackMin.peek()) { 
    			stackMin.pop();
    		}
    		return value;
    	}
    	public int getMin() { 
    		return stackMin.peek();
    	}
    }
    
    class MyStack2{ 
    	Stack<Integer> stackData = null;
    	Stack<Integer> stackMin = null;
    	public MyStack2() { 
    		stackData = new Stack<>();
    		stackMin = new Stack<>();
    	}
    	public void push(int data) { 
    		if (stackMin.isEmpty()) { 
    			stackMin.push(data);
    		}else if (data < stackMin.peek()) { 
    			stackMin.push(data);
    		}else if(data > stackMin.peek()) { 
    			stackMin.push(stackMin.peek());
    		}
    		stackData.push(data);
    	}
    	public int pop() { 
    		if (stackData.isEmpty()) { 
    			throw new RuntimeException();
    		}
    		stackMin.pop();
    		return stackData.pop();
    	}
    	public int getMin() { 
    		return stackMin.peek();
    	}
    }

# 13、单例设计模式 #

/* * 单例设计模式：保证一个类仅有一个实例，并提供一个访问他的全局访问点 * （1）单例类只能有一个实例 * 这是最基本的，真正做到整个系统中唯一并不容易，通常还要考虑反射破坏，序列化/反序列化，对象垃圾回收等问题 * （2）单例类必须自己创建自己的唯一实例 * 通常给实例构造函数protected或private权限 * （3）单例类必须给所有其他对象提供这一实例 * 通常定义静态方法getInstance()返回 * * 优点： * 1、提供了唯一实例的受控访问，避免对资源的多重占用 * 2、在内存里只有一个实例，减少了内存的开销，尤其是频繁的创建和销毁实例 * 3、缩小名空间，避免全局变量污染空间，但比类操作更灵活 * 缺点： * 1、由于单例模式没有抽象层，因此单例类的扩展有很大的困难 * 2、单例类的职责过重，在一定程度上违背了“单一职责原则” */
    //饿汉式（简单可用）
    //优点：没有加锁，执行效率会提高
    //缺点：没有Lazy初始化，可能有时候不需要使用，浪费内存
    class SignleTon{ 
    	private static SignleTon instance = null;
    	private SignleTon() { }
    	public static SignleTon getInstance() { 
    		if (instance == null) { 
    			instance = new SignleTon();
    		}
    		return instance;
    	}
    }
    
    
    public class Signleton { 
    	private static Signleton instance = new Signleton();
    	
    	private Signleton() { }
    	
    	public static Signleton getInstance() { 
    		return instance;
    	}
    }
    
    //懒汉式（线程不安全）
    class Signleton1{ 
    	private static Signleton1 instance = null;
    	
    	private Signleton1() { }
    	
    	public static Signleton1 getInstance() { 
    		if (instance == null) { 
    			instance = new Signleton1();
    		}
    		return instance;
    	}
    }
    
    //同步方法的懒汉式（效率低）
    class Signleton2{ 
    	private static Signleton2 instance = null;
    	
    	private Signleton2() { }
    	
    	public static synchronized Signleton2 getInstance() { 
    		if (instance == null) { 
    			instance = new Signleton2();
    		}
    		return instance;
    	}
    }
    
    //双重校验锁（可用，但还是会有问题，如指令重排序）
    class Signleton3{ 
    	private static Signleton3 instance = null;
    	
    	private Signleton3() { }
    	
    	public static Signleton3 getInstance() { 
    		if (instance == null) { 
    			synchronized (Signleton3.class) { 
    				if (instance == null) { 
    					instance = new Signleton3();
    				}
    			}
    		}
    		return instance;
    	}
    }
    
    //静态内部类
    class Signleton4{ 
    	private static class SignletonHolder{ 
    		private static final Signleton4 INSTANCE = new Signleton4();
    	}
    	
    	private Signleton4() { }
    	
    	public static final Signleton4 getInstance() { 
    		return SignletonHolder.INSTANCE;
    	}
    }