ARTS-WEEK 6 | Eric Jin

Algorithm

Description

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

solution

思路一：给数组做一个备份，然后排序数组。遍历数组，如果原数组和排序的新数组元素不等，这个位置就是需要排序的点，记录下来。

public int findUnsortedSubarray(int[] nums) {
    if (nums == null || nums.length <= 0)
        return 0;
    int len = nums.length;
    int start = len;
    int end = 0;
    //备份
    int[] cnums = nums.clone();
    Arrays.sort(cnums);
    for (int i = 0; i < len; i++) {
        //不同则比较最小最大
        if (nums[i] != cnums[i]){
            start = Math.min(i,start);
            end = Math.max(i,end);
        }
    }
    return (end - start) >= 0 ? end - start + 1 : 0;
}

思路二：用栈，遍历数组，如果后一个数比前一个大，就把元素当前的下标放入栈中，一旦遇到后一个比前一个小的，就把栈最上面的索引取出来。跟当前元素对比，直到栈最上面的索引元素比遍历元素大。从栈中取出的元素就是需要排序的正确位置。相反，最大的从后面遍历元素。

public int findUnsortedSubarray_stack(int[] nums) {
    if (nums == null || nums.length <= 0)
        return 0;
    LinkedList<Integer> stack = new LinkedList<>();
    int len = nums.length;
    int start = len,end = 0;
    for (int i = 0; i < len; i++) {
        //栈不为空，且栈顶的索引元素大于当前元素
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
            start = Math.min(start,stack.pop());
        stack.push(i);
    }
    stack.clear();
    for (int i = len - 1; i >=0 ; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
            end = Math.max(end,stack.pop());
        stack.push(i);
    }
    return (end - start) > 0 ? end - start + 1 : 0;
}

思路三：找到非递增或递减中的最小最大值然后与数组元素比较，一旦比最小比遍历元素小，就放在此处

public int findUnsortedSubarray(int[] nums) {
    if (nums == null || nums.length <= 0)
        return 0;
    int len = nums.length;
    int min = Integer.MAX_VALUE,max = Integer.MIN_VALUE;
    //当后一个小于前一个时，比较得出最小的元素，是为之后界定最小边界
    for (int i = 1; i < len; i++) {
        if (nums[i - 1] > nums[i])
            min = Math.min(min,nums[i]);
    }
    //当前一个元素大于后一个元素，比较得出最大元素，是为之后界定最大边界
    for (int i = len - 2; i >= 0; i--) {
        if (nums[i] > nums[i+1])
            max = Math.max(max,nums[i]);
    }
    int l,r;
    for (l = 0; l < len; l++)
        if (min < nums[l])
            break;
    for (r  = len - 1; r >= 0 ; r--)
        if (max > nums[r])
            break;
    return (r - l) > 0 ? (r - l + 1) : 0;

}

Review

看源码的时候看到HTTP状态码301(permanent) 和 302(temporary) 有不同区别的对待，一时忘记这两者重定向的内含。找到了这篇文章 302 Redirect vs. 301 Redirect: Which is Better?，这篇文章说了301 和 302 的优劣。

文章说了，这两种重定向对于用户来说，其实是一样的，但是他们的区别是搜索引擎所关注的。

301 的重定向是指永久的指向了新的地址，302 的重定向是暂时的指向。搜索引擎需要通过这个状态码去弄清楚是保存旧页面地址呢，还是直接用新页面替换旧页面地址。

不过文中说Google 意识到很多人错误的使用了302，其实他们想要的是永久的重定向。所以Google 会弄清楚你究竟想要用的是301还是302。

但是其他搜索引擎可能做不到，如果301被用作了302，那么搜索引擎会继续索引旧地址，把新地址忽视，作为了一个重复的地址。这种时候就会影响到搜索排序。

Google spokespeople have said that they will treat a 302 as a 301 if they think the webmaster has made an error, but why take a chance, and what about other search engines?

Tip

昨天看到《Effective Java》，看到单例模式。这个在大家的印象中有各种懒汉模式，饿汉模式，然后又分线程安全与不安全。

但是看了书才知道还有一个枚举的单例模式，还是最推荐最简单有效的。

正常只是私有化构造方法，公开一个静态方法获取单例对象。

写一个最和规矩的单例模式：

public class Singleton implements Serializable {
    private static Singleton singleton;
    private String id;

    private Singleton(){id = "test";}

    public static Singleton getInstance(){
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null){
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }

    public String getId() {
        return id;
    }

    private Object readResolve() throws ObjectStreamException {
        return singleton;
    }
}

加了锁保证多线程下只实例一个。加了double check。
在序列化反序列化的时候重写readResolve() 方法，这样能保证序列化反序列化依旧为一个实例。

但是即使这样，如果利用反射进行处理，依旧可以获取到多个实例

public class SingletonTest {
	static String file = "C:\\Users\\lanse\\Desktop\\SINGLETON.txt";
    public static void main(String[] args) throws Exception{
        Singleton s = Singleton.getInstance();
        Singleton s2 = Singleton.getInstance();
        System.out.println("静态方法获取实例是否一致：" + (s == s2));

        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
        oos.writeObject(s);
        oos.flush();
        System.out.println("write finish");

        ObjectInputStream ois = new ObjectInputStream(new FileInputStream(file));
        Singleton reS = (Singleton) ois.readObject();
        System.out.println("序列化后的实例一致么：" + (reS == s));

//        测试反射：：：
        Constructor<Singleton> cons = Singleton.class.getDeclaredConstructor();
        cons.setAccessible(true);
        Singleton consInstance = cons.newInstance();
        System.out.println("反射生成的实例是否一致：" + (consInstance == s));
    }
}

output

静态方法获取实例是否一致：true
write finish
序列化后的实例一致么：true
反射生成的实例是否一致：false

枚举实现单例

public enum SingleEnum {
    INSTANCE 
}

这种方式实现的单例，序列化反序列化，线程安全，甚至反射的攻击都被杜绝了。来看源码：

这是反射newInstance()方法的源码

public T newInstance(Object ... initargs)
    ...
    if ((clazz.getModifiers() & Modifier.ENUM) != 0)
        throw new IllegalArgumentException("Cannot reflectively create enum objects");
    ConstructorAccessor ca = constructorAccessor;   // read volatile
    ...
}

无法对枚举类型进行反射构造！！！

学习Linux 的时候，你会感觉其实起步的命令行是最麻烦的，也是最难记的。命令还有那么多的参数，虽然你可以用man command 或者 command --help 来查找帮助手册，但是，帮助手册真的很不友好，对新手来说，没有什么比实例更能说明问题的了。就像学代码一样，直接把 helloworld展示出来，要比说一堆什么参数是什么意思要好的多。

比如我经常忘记tar命令它具体的参数用法，如果我man tar 那一堆的命令我完全看懵逼。

Cheat—— 给Linux初学者和管理员一个终极命令行"备忘单"

这个，忘记具体使用的时候直接 cheat tar

$ cheat tar
# To extract an uncompressed archive:
tar -xvf /path/to/foo.tar

# To create an uncompressed archive:
tar -cvf /path/to/foo.tar /path/to/foo/

# To extract a .gz archive:
tar -xzvf /path/to/foo.tgz

# To create a .gz archive:
tar -czvf /path/to/foo.tgz /path/to/foo/

# To list the content of an .gz archive:
tar -ztvf /path/to/foo.tgz

# To extract a .bz2 archive:
tar -xjvf /path/to/foo.tgz

# To create a .bz2 archive:
tar -cjvf /path/to/foo.tgz /path/to/foo/

# To extract a .tar in specified Directory:
tar -xvf /path/to/foo.tar -C /path/to/destination/

# To list the content of an .bz2 archive:
tar -jtvf /path/to/foo.tgz

# To create a .gz archive and exclude all jpg,gif,... from the tgz
tar czvf /path/to/foo.tgz --exclude=\*.{jpg,gif,png,wmv,flv,tar.gz,zip} /path/to/foo/

# To use parallel (multi-threaded) implementation of compression algorithms:
tar -z ... -> tar -Ipigz ...
tar -j ... -> tar -Ipbzip2 ...
tar -J ... -> tar -Ipixz ...

有示例，友好。

文中有cheat的详细介绍和安装指南。

Algorithm

Description

solution

Review

Tip

枚举实现单例

Share