一些常见的算法或编程题

104 阅读 0 评论 69 点赞

我是靠谱客的博主美丽皮卡丘，最近开发中收集的这篇文章主要介绍一些常见的算法或编程题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线程死锁

package live.yanxiaohui.test.day20201202;
/**
* @Description 线程死锁
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-02 08:41<br>
* @Version 1.0<br>
*/
public class Dead {
public static void main(String[] args) {
Object o1 = new Object();
Object o2 = new Object();
new A(o1,o2,false).start();
new A(o1,o2,true).start();
}
}
class A extends Thread{
private Object o1;
private Object o2;
private boolean flag;
public A(Object o1, Object o2, boolean flag) {
this.o1 = o1;
this.o2 = o2;
this.flag = flag;
}
public void a(){
synchronized (o1){
System.out.println(Thread.currentThread().getName()+":o1");
synchronized (o2){
System.out.println(Thread.currentThread().getName()+":o2");
}
}
}
public void b(){
synchronized (o2){
System.out.println(Thread.currentThread().getName()+":o2");
synchronized (o1){
System.out.println(Thread.currentThread().getName()+":o1");
}
}
}
@Override
public void run() {
if(flag){
while(true){
a();
}
}else {
while (true){
b();
}
}
}
}

生产者与消费者（交替打印奇偶数）

package live.yanxiaohui.test.day20201202;
/**
* @Description todo
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-02 09:15<br>
* @Version 1.0<br>
*/
public class Demo {
public static void main(String[] args) {
Data d = new Data();
new T1(d).start();
new T2(d).start();
}
}
class T1 extends Thread {
private Data data;
public T1(Data data) {
this.data = data;
}
@Override
public void run() {
while (true) {
synchronized (data) {
try {
Thread.sleep(1000);
if (data.count % 2 == 0) {
data.wait();
}
System.out.println(Thread.currentThread().getName() + ":" + data.count);
data.count++;
data.notify();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
class T2 extends Thread {
private Data data;
public T2(Data data) {
this.data = data;
}
@Override
public void run() {
while (true) {
synchronized (data) {
try {
Thread.sleep(1000);
if (data.count % 2 != 0) {
data.wait();
}
System.out.println(Thread.currentThread().getName() + ":" + data.count);
data.count++;
data.notify();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
class Data {
public int count;
}

两个有序数组合并为一个有序数组

package live.yanxiaohui.test.day20201202;
import java.util.Arrays;
/**
* @Description 两个有序数组排序
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-02 08:49<br>
* @Version 1.0<br>
*/
public class ArraySort {
public static void main(String[] args) {
int[] a = {0, 1, 1, 3, 6};
int[] b = {1, 2, 4, 5, 6, 7,8,10};
//int[] c = sort1(a, b);
int[] c = sort2(a, b);
for (int i : c) {
System.out.println(i);
}
}
/**
* o(a.length+b.length)
*
* @param a
* @param b
* @return
*/
public static int[] sort1(int[] a, int[] b) {
int[] c = new int[a.length + b.length];
int i = 0, j = 0, index = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
c[index++] = a[i++];
} else {
c[index++] = b[j++];
}
}
// a数组先遍历完
if(i==a.length){
for(;j<b.length;j++){
c[index++]=b[j];
}
}
// b数组先遍历完
if(j==b.length){
for(;i<a.length;i++){
c[index++]=a[i];
}
}
return c;
}
/**
* o(a.length+b.length+ c.length^2)
*/
public static int[] sort2(int[] a, int[] b) {
int[] c = new int[a.length + b.length];
int index=0;
for(int i:a){
c[index++]=i;
}
for(int i:b){
c[index++]=i;
}
Arrays.sort(c);
return c;
}
}

两个数组找交集

package live.yanxiaohui.test.day20201202;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @Description todo
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-02 09:20<br>
* @Version 1.0<br>
*/
public class Same {
public static void main(String[] args) {
int[] a = {0, 1, 1, 3, 6};
int[] b = {1, 2, 4, 5, 6, 7, 8, 10};
System.out.println(same(a, b));
}
private static List<Integer> same(int[] a, int[] b) {
List<Integer> c = new ArrayList<>(Math.max(a.length, b.length));
Map<Integer, Object> map = new HashMap<>((int) (Math.ceil(a.length) / 0.75) + 1);
for (int i : a) {
map.put(i,null);
}
for (int i:b){
if(map.containsKey(i)){
c.add(i);
}
}
return c;
}
}

单向链表检测环

package live.yanxiaohui.test.day20201202;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
/**
* @Description 快慢引用检测环
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-02 09:20<br>
* @Version 1.0<br>
*/
public class Same {
public static void main(String[] args) {
int len = 10;
List<Node> list = new ArrayList<>(len);
// 设置环 9->8->7...->0
IntStream.range(0, len).forEach(i -> {
Node n = new Node(i + "");
if (list.size() > 0) {
n.next = list.get(i - 1);
}
list.add(n);
});
// 设置环 6->5->4->3->2->1->0->6->5....
Node node = list.get(0);
node.next = list.get(6);
System.out.println(loop(list.get(list.size() - 1)));
}
/**
*
* @param node 链表头
* @return
*/
private static boolean loop(Node node) {
Node a = node, b = node;
while (a != null && b != null) {
if((a = a.next)==null){
return false;
}
if(b.next == null){
return false;
}
if ((b = b.next.next)==null) {
return false;
}
if (a.equals(b)) {
return true;
}
}
return false;
}
}
class Node {
public Node next;
private String name;
public Node(String name) {
this.name = name;
}
@Override
public boolean equals(Object obj) {
// todo 不严谨，可优化
return name.equals(((Node) obj).getName());
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}

反转单向链表

/**
* @Description 反转单向列表
* 示例：4->3->2->1->0
变为 0->1->2->3->4
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author： yanxh<br>
* @Date 2020-12-08 10:59<br>
* @Version 1.0<br>
*/
public class Demo {
public static void main(String[] args) {
// 创建单向列表
Node first = new Node(0);
for (int i = 1; i <=4; i++) {
Node node = new Node(i);
node.next = first;
first = node;
}
// 反转
System.out.println("==================================");
Node swap = swap(first);
System.out.println(swap);
}
public static Node swap(Node node) {
Node t = null;
while (node != null) {
Node next = node.next;
node.next = t;
t = node;
node = next;
}
return t;
}
}
class Node {
Node next;
Integer index;
public Node(Integer index) {
this.index = index;
}
}

两个栈实现一个队列

package live.yanxiaohui;
import java.util.Stack;
import java.util.stream.IntStream;
/**
* @Description 两个栈实现一个队列
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author yanxh<br>
* @Date 2020/12/11 9:24<br>
* @Version 1.0<br>
*/
public class Queue<E> {
private Stack<E> s1 = new Stack<>();
private Stack<E> s2 = new Stack<>();
public void offer(E val) {
//入队
s1.push(val);
}
public E poll() {
//出队
while (!s1.isEmpty()){
s2.push(s1.pop());
}
if(s2.isEmpty()){
return null;
}
E result = s2.pop();
while(!s2.isEmpty()){
s1.push(s2.pop());
}
return result;
}
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>();
IntStream.range(0, 10).forEach(i -> queue.offer(i));
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
queue.offer(100);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}

两个队列实现一个栈

package live.yanxiaohui;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.IntStream;
/**
* @Description 两个队列实现一个栈 先进后出
* @CSDN https://blog.csdn.net/yxh13521338301
* @Author yanxh<br>
* @Date 2020/12/11 9:24<br>
* @Version 1.0<br>
*/
public class Stack<E> {
Queue<E> q1 = new LinkedBlockingQueue<>();
Queue<E> q2 = new LinkedBlockingQueue<>();
public void push(E e){
q1.offer(e);
}
public E pop(){
E result = null;
while(!q1.isEmpty()){
E poll = q1.poll();
if(q1.isEmpty()){
result = poll;
}else {
q2.offer(poll);
}
}
if(q2.isEmpty()){
return null;
}
while(!q2.isEmpty()){
q1.offer(q2.poll());
}
return result;
}
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
IntStream.range(0,10).forEach(i->s.push(i));
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
s.push(100);
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
}