剑指算法

题目二：单例设计模式

1.题目描述：设计一个类，只能生成一个实例化对象。

​ （1）分析：例如:windows中任务管理器，jvm回收器，运行过程中只有一个实例，创建对象会使用该类的构造方法，那么可以将其设置为private,由该类提供一个对象，由该类的静态方法提供出来，保证对象一直是该类提供的。

​ （2）提供2个，饿汉式和懒汉式（线程不安全，需要改为线程安全）

一：懒汉式： 优点是线程安全，但是对象一直存在于内存中，浪费空间。

public class Singleton{private Singleton singletonInstance=new SingletonInstance();priate Singleton(){}public static Singleton getInstance(){return singletonInstance;}}}

二：饿汉式：优点是对象在需要的时候才创建，不浪费资源，缺点是多线程中不安全，需要改进。

线程不安全：

public class Singleton{ //此处不实例化对象。private Singleton singletonInstance;priate Singleton(){}public static Singleton getInstance(){if(SingletonInstance==null){//此处在多线程进行时，如果线程1进入这里阻塞，那么线程二进行上面的判断的时候，发现对象是没有创建的，则还会进入这个分支语句。则会//创建2个对象。不能保证单例的特点了。singleton=new Singleton();}return singletonInstane;}}}

线程安全

public class Singleton{ private static Singleton singletonInstance;private Singleton() {}public static Singleton getSingletongHolder() {//第一层访问控制，能节约线程的等待时间。如果对象已经创立了则无需等待。if (singletonInstance == null) {//同步代码 synchronized (Singleton.class) {//第二层控制，保证对象不存在时才创建。if (singletonInstance == null) {singletonInstance = new Singleton();}}}return singletonInstance;} }

题目三：二维数组中查找目标值

1.题目描述:一个二维数组，每一行大小顺序按从左到右排列；每一列按从上到下排列。给定一个target，确定是否在其中。

​ 数组例子：

1234

5	8	9	10
6	11	12	13
7	14	15	16

2：思路一：（1）利用双指针迫近寻找， 找到一个边角，如右上角，如果target比他大，则行数+1，（因为右上角的值是该行最大的值）如果target比他小，则列数-1（该数值是该列中最小的数据，比他小只能是前几列中），终止条件：row>array.length-1 || col<0;

//方法一：利用双指针：利用该数组的排列顺序，使得指针慢慢迫近。时间复杂度：O（mn）条件：public static boolean searchKey(int[][] array,int target){int row=0;int col=array[0].length-1;if(array==null||array.length==0){return false;}// 循环条件 row<array.length-1 && col>0；while (row<array.length-1 && col>0){//等于目标值，则输出行和列，返回true 结束方法。if(array[row][col]==target){System.out.println(row+" "+col);return true;}//不等于目标值时的2种处理if(target<array[row][col]){col--;}else{row++;}}System.out.println("没有找到");return false;}

测试:

@Test public void mt(){int[][] array={{1,2,3,4},{3,5,6,7},{8,9,13,14},{15,16,17,18}};ArraySearch.searchKey(array,13);}

结果：

2 2

总结

以上是生活随笔为你收集整理的剑指算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。