记一次简单的服务器修复


修复

  • 起因

今天戳开自己博客突然发现只显示出了Ngnix的默认错误界面, 而我挂在同一服务器上的seafile和gitea都没有问题, 就意识到大概是PHP挂了.

  • 定位问题

上服务器用ps aux | grep php一看, 果然是PHP没启动起来, 尝试重新启动发现并没有效果.
于是systemctl status php-fpm看看发生了什么, 第一行大概提示的是找不到mbstring.

20191206095800367_28116.png

一开始感觉只要把这个文件补上大概就可以了, 于是pacman -F mbstring看看.........没有
我有点不信邪...然后pacman -Fx ".*mbstring.*", 为啥mbstring.h的头文件都有但是没有mbstring.so啊不科学

网上查了查发现, Arch的PHP在打包的时候会加上--enable-mbstring参数将mbstring嵌入到PHP的可执行文件里面去, php -m也验证了这一点...
那你还提示个球啊摔..............

最后发现是, 我之前在php.ini里面加了句extension=mbstring, 然后PHP就会尝试去加载这个外部模块...emmmmmm

以及...其实...他就是只是报个错而已...对于正常启动没有任何影响

  • 重新定位问题

修改了php.ini以后, php-fpm.service还是启动不起来, 现在的报错变成了这样

20191206100425652_4564.png

怎么会没有权限呢? 我去看了一眼/run/php-fpm/php-fpm.sock的权限, root/group都是root, 然后看了看php-fpm.service的内容也没有指定用户和组, 那就应该是以root权限启动的啊

然后我顺手看了一眼php-fpm.conf.d/www.conf... 咦...有个pacnew文件, 是更新了啥吗? 然后我就懂了...

20191206100720401_5274.png)

所以 问题大概是PHP-FPM更新以后改进了权限运行策略...emmmmmm

于是 把这部分照着pacnew修改一下之后就好了= =

总结

滚动更新一大缺点就是...上游更新可能导致服务莫名其妙就被更挂了...

当然, 我的第一反应也是肯定更新了啥把php更挂了, 然后看了看官方的News啥也没提, 重新安装了几遍包也没啥用

........................嗯 好吧

顺带一提我的PHP-FPM版本是7.4.0-2

LeetCode刷题Wrapper


起因

LeetCode上的题目放到本地调试很麻烦, 需要在本地新建一个Main方法来运行, 多TestCase的测试也需要写很多重复代码, 所以想写一个简单Wrapper将很多重复的工作放在里面来执行.

目标

使用Wrapper之后, 只需要将Solution类放入再实现getTestCase()即可.
这里的Solution类可以直接不作任何修改的复制粘贴到LeetCode中, 不需要任何额外的代码即可直接运行这个类.

public class Problem7 extends AbstractSolution{
    /**
     * Given a 32-bit signed integer, reverse digits of an integer.
     * <p>
     * Example 1:
     * Input: 123
     * Output: 321
     * <p>
     * Example 2:
     * Input: -123
     * Output: -321
     * <p>
     * Example 3:
     * Input: 120
     * Output: 21
     * <p>
     * Note:
     * Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
     */
    class Solution{
        @Resource
        public int reverse(int x){
            // 统一调整到负数来处理
            boolean isPositive = x >= 0;
            x = isPositive ? -x : x;

            int result = 0;
            while(x < 0 && result >= Integer.MIN_VALUE / 10){
                int n = x % 10;
                if(result == 0){
                    result = result + n;
                }else{
                    if(result == Integer.MIN_VALUE / 10 && x < -8){
                        break;
                    }
                    result = result * 10 + n;
                }
                x /= 10;
            }
            result = x < 0 ? 0 : result;

            return isPositive ? -result : result;
        }
    }

    @Override
    protected Map<?, ?> getTestCase(){
        return ImmutableMap.builder()
                .put(123, 321)
                .put(-123, -321)
                .put(120, 21)
                .put(1534236469, 0)
                .put(-2147483412, -2143847412)
                .put(1463847412, 2147483641)
                .put(1234, 111)
                .build();
    }
}

由于使用Guava, 所以可能还需要引入它的依赖到工程中.
另外, Solution类的入口方法需要放上@Resource注解, 否则Wrapper无法找到运行的入口方法.
运行的结果如下所示:

TestCase 0: Passed
TestCase 1: Passed
TestCase 2: Passed
TestCase 3: Passed
TestCase 4: Passed
TestCase 5: Passed
TestCase 6: Wrong
    Input: 1234
    Output: 4321
    Expected: 111
Some TestCase Failed!

解析

首先展示一下AbstractSolution的内容:

public abstract class AbstractSolution{
    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.getName().endsWith("$Solution")){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            for(Method m : methods){
                if(m.isAnnotationPresent(Resource.class)){
                    targetMethod = m;
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for(Object input : testCase.keySet()){
            Object result = targetMethod.invoke(targetInstance, input);
            Object expectedResult = testCase.get(input);
            boolean passed = result.toString().equals(expectedResult.toString());
            allPassed = passed && allPassed;

            if(passed){
                System.out.printf("TestCase %d: Passed\n", index++);
            }else{
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, input, result, expectedResult);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

我们在Problem7类中运行的main()方法放在了AbstractSolution里, 首先我们需要获得实际子类的实例, 即Problem7类的实例.
AbstractSolution类里, 我们是没办法知道到底具体是哪一个子类调用的main()方法的, 如果想要知道有两种方法:

  1. 运行的命令行参数里, 会带上实际执行的子类.
    例如在这个例子中, 命令行参数是java algorithm.leetcode.Problem7. 这样从命令行参数就可以知道实际调用main()的类是Problem7了.
  2. 在加载子类之前, 父类一定会被加载. 因此, 我们遍历当前一遍所有加载的类, 看当前类的哪一个子类被加载了, 就可以知道实际调用的类.

在这里, 我使用的是第二种方法, 通过ReflectionUtils.getLoadedSubClass(AbstractSolution.class)来获取, 具体实现如下:

    @SuppressWarnings("unchecked")
    public static <T> Class<? extends T> getLoadedSubClass(Class<T> superClass){
        // Read Loaded Classes
        Collection<Class<?>> classes = getLoadedClass(Thread.currentThread().getContextClassLoader());

        // Find the SubClass of CurrentClass
        for(Class c : classes){
            if(c.getSuperclass() != null && superClass.equals(c.getSuperclass())){
                return c;
            }
        }
        throw new IllegalStateException("No Valid SubClass.");
    }

    /**
     * 获取指定类加载器已加载的类
     */
    @SuppressWarnings("unchecked")
    public static Collection<Class<?>> getLoadedClass(ClassLoader cl){
        try{
            Field f = ClassLoader.class.getDeclaredField("classes");
            f.setAccessible(true);
            return (Collection<Class<?>>)f.get(cl);
        }catch(NoSuchFieldException | IllegalAccessException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Unexpected Error.");
    }

ClassLoader本身是没有提供方法让你获得当前已加载的类, 但是存在一个private的classes属性包含所有已加载的类, 因此可以通过读取该属性来获得指定类加载已加载的类.

在获得Problem7的实例solutionWrapper后, 我们再从Problem7类中找到其内部类$Solution并实例化它.
需要注意的是, 这里不能直接用newInstance(), 因为内部类没有public的构造器, 只有包含外部类引用的private构造器, 所以需要首先获得这个构造器, 然后使用构造器实例化内部类.

在获得内部类targetClass以后, 再遍历所有的方法找到标记有注解的方法作为入口方法targetMethod.
这里用@Resouce注解的原因只是...我觉得用JDK自带注解就够了...

最后, 检查一下testCase的类型和targetMethod的参数类型是否匹配, 就可以调用targetMethod来实际执行Solution类里的实际方法了.
这里考虑到存在primitive类型和其包装类混用的情况, 所以首先将其都unwrap, 如果都为primitive类型那么一定是可以转型成功的(当然可能损失精度).
如果没有primitive类型, 那么使用isAssignableFrom()方法来判断; 如果一个primitive一个正常对象, 那么必然转型失败.

    /**
     * 检查是否可从target转型到source
     * 考虑两个primitive类型一定可以互转(可能损失精度)
     */
    public static boolean isAssignableFrom(Class<?> source, Class<?> target){
        source = Primitives.unwrap(source);
        target = Primitives.unwrap(target);

        // All Object
        if(source.isPrimitive() && target.isPrimitive()){
            return true;
        }else if(!source.isPrimitive() && !target.isPrimitive()){
            return source.isAssignableFrom(target);
        }else{
            return false;
        }
    }

总的来说, 大体上的思路就是这样了, 我觉得还是很有意思的.

总结

这么一番操作下来, 感觉对框架内部实现的很多东西了解得更深了呢233
之前简单的看过Spring-Core的内部实现, 也是大量类似的检查代码, 以及一吨设计模式→_→
实话说, 感觉设计得有点太过复杂了...不过有可能是我看的源码版本比较老吧233(Spring 3.1.1)

懒果然是人类进步的阶梯(并不

Update 2019-05-10:
我把AbstractSolution又改了改, 在方法上做标注还是有一些略麻烦...
我把它改成了标注在内部类上, 然后用lookup属性来指定待执行的方法, 或者选取第一个找到的Public方法

public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.isAnnotationPresent(Resource.class)){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for(Method m : methods){
                if(!annotation.lookup().isEmpty()){
                    // specify by lookup
                    if(m.getName().equals(annotation.lookup())){
                        targetMethod = m;
                    }
                }else{
                    // first public method
                    if(Modifier.isPublic(m.getModifiers())){
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

Update 2019-09-04:

以前做的居然不支持多参数输入, 醉了醉了...
验证参数类型其实挺麻烦的, 感觉在我这个场景下也不是特别重要就删掉了...只检查参数数目是否一致
然后输出的检测考虑到可能会有比较复杂的类型输出出来干脆就用gson全部转换到字符串然后比较字符串好了...

public abstract class AbstractSolution{
    private final static Gson gson = new GsonBuilder().create();

    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for (Class<?> c : classes) {
            if (c.isAnnotationPresent(Resource.class)) {
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if (targetClass != null && targetClass.getDeclaredConstructors().length > 0) {
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if (targetClass != null) {
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for (Method m : methods) {
                if (!annotation.lookup().isEmpty()) {
                    // specify by lookup
                    if (m.getName().equals(annotation.lookup())) {
                        targetMethod = m;
                    }
                } else {
                    // first public method
                    if (Modifier.isPublic(m.getModifiers())) {
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if (targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0) {
            runCases(targetInstance, targetMethod, testCase);
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for (Object input : testCase.keySet()) {
            // read params
            Object[] params;
            if (targetMethod.getParameterCount() > 1) {
                params = new Object[Array.getLength(input)];
                for (int i = 0; i < params.length; i++) {
                    params[i] = Array.get(input, i);
                }
            } else {
                params = new Object[]{input};
            }

            // check parameter length
            if (params.length != targetMethod.getParameterCount()) {
                throw new IllegalArgumentException("Incompatible Parameters.");
            }

            // actual invoke
            Object result = targetMethod.invoke(targetInstance, params);
            Object expectedResult = testCase.get(input);

            // compare string
            String inputStr = gson.toJson(input);
            String resultStr = gson.toJson(result);
            String expectedStr = gson.toJson(expectedResult);
            boolean passed = resultStr.equals(expectedStr);
            allPassed = passed && allPassed;

            if (passed) {
                System.out.printf("TestCase %d: Passed\n", index++);
            } else {
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, inputStr, resultStr, expectedStr);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

关于键盘的一些碎碎念


像我可能是对键盘不太挑的类型, 一直薄膜键盘用下来感觉也挺不错的.

其实也用过同学的机械, 无论是国产轴还是原厂轴, 亦或是青轴, 茶轴, 黑轴, 红轴都试过, 但始终觉得都不是我的菜.

依稀记得买的第一个键盘是Fuhlen L400, 39块钱买了不吃亏不上当, 其实我用起来一直感觉还是不错的, 直到最近发现shift键经常按下去谈不起来emmm

后来买了笔记本, 型号是Gigabyte U2442D, 这是一款每次拿出来总有人要问是什么牌子的笔记本2333

当然这时候我一般会装一个x: 这是全球第二大主板厂商(x

言归正传, 我觉得这款笔记本的键盘的使用体验还是相当不错的, 和同期mbp2013款的键盘使用体验不相上下.
也是就此, 我觉得自己其实喜欢上这种短键程的剪刀脚键盘, 特别是悬浮式巧克力键帽.
我可以很自然地把手掌放在桌子上, 然后手指在键盘上翻飞, 非常舒适. 但是像那种一般的高键帽键盘就...必须得悬空打字了, 实话说我觉得很不习惯

新款mbp的蝴蝶键盘就真的是...有一种强烈的按锅仔片的感觉

于是, 后来台式机买新键盘的时候, 我就买了Rapoo E9100P, 虽然作为一个薄膜键盘来说确实有些贵了, 但是不得不说使用体验还是很棒的, 比如说我现在就是在用这块键盘敲字www
其他的薄膜键盘的推荐可能是thinkpad那款了吧...不过高昂的价格让我望而却步Orz

最后就是最近, 因为之前说Fuhlen L400挂了嘛, 考虑到Rapoo E9100P给我带来的良好体验, 于是入手了一块Rapoo V500.
本来一开始打算再买一块Rapoo E9100P这个系列的, 但是还是感觉有些贵= =
而且考虑到毕业了, 估计也不会再要, 不如干脆买一个超入门机械好了→_→ 顺便也可以习惯一下悬空打字的感觉吧emmm

未来工作的话主力键盘, 如果能够习惯机械的感觉的话, 可能会考虑换一块Varmilo吧...
应该会买87键版的, 然后海韵蓝? 主要是太好看了啊啊啊啊啊啊啊啊(我就是颜狗)
应该会买无线版本吧...嗯

20190505002313983_14909.png
20190505002418824_5345.png


Update 2019-05-24:
用了一段时间以后发现Rapoo V500简直坑爆了, 手感什么的就不说了, 我倒要求不是那么高
但主要是有些组合键按不下去啊啊啊啊啊
一开始看到常用键无冲就没想那么多, 直到最近用sublime的时候发现命令面板Ctrl+Alt+P老是按不出来, 于是...测试了一下
QQ截图20190524083653.png
好吧...就是这垃圾键盘按不出来, 而且不只是Ctrl+Alt+P还有0/U/K/Enter也是...
emmmmmmmmmmmmmmmmmmm...........我那个40块的Fuhlen L400都不会这样啊摔
果然机械键盘一定要注意全键无冲么Orz


关于技术学习的一些思考


我觉得任何技术都可以从这么几个角度去考虑:

技术选型

  • 这个框架它解决了什么旧的问题? 又带来了什么新的问题?
  • 它与其他同类技术相比有什么特点? 其侧重点在什么地方?
  • 基于以上问题, 该框架适用于什么场合?

软件工程的一个基本原则就是没有银弹, 任何技术都有其适用的场合, 在学习一个技术之前先想清楚为什么要学它.

比如说, 微服务的两大主要优点是 分布式部署 和 代码解耦, 但问题是如果你的项目量级根本没有大到需要分布式部署, 而且业务的复杂程度也没有大到耦合度很高, 那么到底是为什么需要它呢? 不要忘记了, 一项技术会有优点的同时那么必然也会有缺点以及其带来的问题.

优点没有享受到, 反倒是被缺点坑到吐血, 那就是本末倒置了.

当然你说是做技术储备, 从长远考虑, 那当我没说.

技术学习

一般来说, 技术文档可以分为三类: Tutorial, User Guide和Reference

  • 首先应该看的是Tutorial, 一般是step-by-step的教你做一个基本的demo出来.
  • 然后应该看的是User Guide, 一般是介绍整体功能结构以及常见场景的解决方案.
  • 最后是Reference, 基本上就是事无巨细的罗列所有功能了.

一般来说, Tutorial用来快速上手, 深入学习需要User Guide看一遍, Reference那就纯粹是查漏补缺了, 需要的时候翻一翻就行.

我个人的学习路线基本上是:

  • 首先通过step-by-step的Tutorial快速构建出一个demo, 了解其基本写法
  • 然后根据User Guide, 在demo上进行魔改以完成我所想的功能
  • 如果遇到一些奇葩问题, 可以去stackoverflow上看看有没有解答
  • 如果没有, 可能就需要去怼源码了→_→

学习Tutorial的时候可能很重要的一点是, 不仅仅是照着做, 更要想清楚为什么要这么做, 每一行都有什么用, 我能不能不这么写, 有没有别的写法.

技术总结

纸上得来终觉浅,绝知此事要躬行

在使用技术的过程中, 更要去思考和总结, 还是上面提到的几个问题:

  • 横向比较: 它与其他同类框架相比有什么特点?
  • 纵向比较: 这个框架它解决了什么问题? 又带来了什么问题?
  • 最后: 基于以上问题, 该框架适用于什么场合?

这是软件工程层面的, 从纯技术层面上, 在使用过程中会逐渐对其机制逐渐了解, 那么能不能从机制反推出框架内部的实现原理?

  • 如果实现一个功能类似的框架, 会怎么设计?
  • 框架现有的一些坑, 如果重新设计的话, 会怎么去设计?

带着以上问题再去学习源码, 必然是事半功倍, 你会了解到:

  • 框架的设计和你的设计有什么不同, 侧重点分别在什么地方?
  • 为什么框架会有这些坑? 也许是没想到, 那么你可以提交PR, 也许只是一种折衷和妥协, 那么为什么要这么妥协?
  • 如果你发现你的理念和现有框架的理念完全不同, 在某一方面又有突出优势, 那么说不定你就可以开个新的框架了呢233

技术本身不是重点, 重点是技术背后的思想和设计理念.

就好比挖沙子, 到底用铁铲挖还是挖掘机挖其实取决于你到底要挖多少沙子(不同场景). 挖基坑可以用挖土机, 那挖古墓还用挖土机? 而且会用铁铲挖了再去学怎么用挖掘机挖很难吗? 毕竟造挖掘机的人也是从用铲子挖开始的.
更重要的是, 怎么从挖掘机联想到推土机, 甚至是如何去自动化整个造房子的过程.


最大正方形


问题

0,1矩阵中最大的全1正方形

例如:

int[][] a = {
    {0, 1, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 1, 0, 1, 1},
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 0},
    {0, 1, 1, 1, 0},
};

答案应该是: 2

解答

朴素的思路

思路上是把一个二维搜索问题变成了一个一维搜索问题
即将二维数组转化为柱状图, 在柱状图上找正方形, 例如上述例子转为柱状图后:

0, 1, 1, 1, 0, 
0, 2, 0, 2, 0, 
0, 3, 1, 3, 0, 
1, 4, 2, 4, 1, 
2, 5, 0, 5, 2, 
3, 6, 1, 6, 3, 
0, 7, 2, 7, 0, 
0, 8, 3, 8, 0, 

具体的找法比较绕口, 不如直接看代码:

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;

    int rows = array.length, cols = array[0].length;
    for(int i = 1; i < rows; i++){
        for(int j = 0; j < cols; j++){
            if(array[i][j] > 0){
                array[i][j] = array[i - 1][j] + 1;
            }
        }
    }

    int maxVal = 0;
    for(int[] row : array){
        for(int i = 0; i < cols - maxVal; i++){
            if(row[i] > maxVal){
                int cnt = 0, maxLen = row[i];
                for(int j = i; j < cols && cnt < maxLen && row[j] > cnt; j++, cnt++){
                    maxLen = Math.min(maxLen, row[j]);
                }
                maxVal = Math.max(maxVal, cnt);
            }
        }
    }
    return maxVal;
}

简单的来说, 就是找到可能的正方形左下角点以后, 向右搜索(cnt < maxLen && row[j] > cnt):

  • 一方面走的步数(cnt)不能大于目前已经走过的所有值的最小值(maxLen)
  • 另外一方面已经走过的值(row[j])必须大于当前走过的步数(cnt)

总而言之, 这是一个最坏情况O(N^3)的方法, 不过总体来说, 其实性能不算太差.

动态规划

如果一个点的它的左边, 左上, 上边至少构成某个长度(n)的正方形的话, 那么这个点应该能构成一个更大的正方形(n+1)
这样说起来可能有点绕...看例子吧:

0, 1, 1, 1, 0, 
0, 1, 0, 1, 0, 
0, 1, 1, 1, 0, 
1, 1, 2, 2, 1, 
1, 2, 0, 1, 2, 
1, 2, 1, 1, 2, 
0, 1, 2, 2, 0, 
0, 1, 2, 3, 0, 

题目中的例子整个状态空间如上图所示, 很显然...状态方程如下是成立的:

$$dp[i][j] = \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1$$

所以实现下来的话...

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;
    int rows = array.length, cols = array[0].length, maxVal = 0;
    
    int[][] dp = new int[rows][cols];
    for(int i = 0; i < rows; i++){
        if(array[i][0] == 1){
            dp[i][0] = 1;
            maxVal = 1;
        }
    }
    for(int j = 0; j < cols; j++){
        if(array[0][j] == 1){
            dp[0][j] = 1;
            maxVal = 1;
        }
    }

    for(int i = 1; i < rows; i++){
        for(int j = 1; j < cols; j++){
            if(array[i][j] == 1){
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
            maxVal = Math.max(maxVal, dp[i][j]);
        }
    }
    return maxVal;
}

总而言之, 这是一个最坏情况O(N^2)的方法, 只用把数组扫描一遍即可Orz

总结

动态规划的主要难点在于想出状态方程...