leetCode刷题记录

leetCode数独

随着年关将至，虽然依然在苦逼的上班但是已经感觉瞬间整个人都轻松了不少，所以闲来无事，来传说中的leetCode溜了一圈，看到了一个hard

QQ截图20190130161400.png

题目大致的意思是根据9*9的格子给出的数字填充没有填充数字的格子，我相信大部分人应该都玩过这个填字游戏，不过这次不是用笔而是用代码的方式来实现。这有点类似于开外挂的意思o(∩_∩)o

第一眼看过去如果是用笔来填我们很容易就能解决，但是采用编码的方式 感觉有一点摸不着头脑了。这里也不详细说了，解题的思路大部分都在代码里面了，感兴趣的同学可以看看代码，这里还有许多可以改进的地方，但是由于是在公司上班期间。也不敢再多思索了，如果有更好的思路欢迎留言。

package com.example.bstdemo.bst;

import com.google.common.collect.Maps;

import java.util.*;

/**
 * @ClassName Solution
 * @Description TODD 定义数独的数据结构用来解决 数独的自动解析问题
 * @Author MG01857
 * @Date 2019/1/30
 * @Version 1.0
 **/


public class Solution {
    //分析问题： 根据数独的特性 可以将数独看成一个9*9的二维数组
    // 数独 横竖以及对应位置的3*3的格子中不能有重复并且1-9 如何采用广度优先搜索的方式 根据已经给定的确定的值获取对应的 其他的数独中未知的数用以填充

    private static int[][] arrs;//初始化二维数组

    private static Map<String, Set<Integer>> maps = Maps.newHashMap();

    private  static Stack<String> stacks = new Stack<>();//根据第一次遍历确定的
    /**
     * @Author MG01857
     * @Description //TODO 初始化
     * @Date 13:52 13:52
     * @Param []
     * @return void
     **/

    public static  void init(){
         arrs = new int[][]{
                 {5, 3, 0, 0, 7, 0, 0, 0, 0},
                 {6, 0, 0, 1, 9, 5, 0, 0, 0},
                 {0, 9, 8, 0, 0, 0, 0, 6, 0},
                 {8, 0, 0, 0, 6, 0, 0, 0, 3},
                 {4, 0, 0, 8, 0, 3, 0, 0, 1},
                 {7, 0, 0, 0, 2, 0, 0, 0, 6},
                 {0, 6, 0, 0, 0, 0, 2, 8, 0},
                 {0, 0, 0, 4, 1, 9, 0, 0, 5},
                 {0, 0, 0, 0, 8, 0, 0, 7, 9},
         };
    }

    /**解析数独 并将对应的解加入对应的数组中*/
    public static  void analysis(){
        init();
        System.out.println("===================================初始化之后的结果===============================");
        for(int i=0;i<arrs.length;i++){
            for(int j=0;j<arrs[i].length;j++){
                System.out.printf(arrs[i][j]+" ");
            }
            System.out.println("");
        }
        // 解决数独首先需要找出其中的 突破点再由突破点进行解决 如果解决不了，还需要用的到假设法 如果同时存在两个不确定
        // 1.解决方案 每个数组中的值 对应的横竖 以及对应的3*3中的格数是不能有相同的出现
        // 每次循环遍历所有的不为0的数用来判断有哪些是可以确定的值 如果是确定的值则 填充到对应的二维数组中的位置
        // 这种方式的缺点 算法复杂度过高 但是对于格数不是很多的情况下 还是可以接受的
        // 这里还需要建立一个 对应二维数组中的一个map
        for(int i=0;i<arrs.length;i++){
            for(int j=0;j<arrs[i].length;j++){
                if(arrs[i][j] != 0){
                    putMapsValue(i,j,arrs[i][j]);
                }
            }
        }
        // 测试遍历
        System.out.println("===============================第一次遍历之后的结果============================");
        for(int i=0;i<arrs.length;i++){
            for(int j=0;j<arrs[i].length;j++){
                System.out.printf(arrs[i][j]+" ");
            }
            System.out.println("");
        }


        while (!stacks.empty()){
            String pop = stacks.pop();
            String[] split = pop.split("-");
            putMapsValue(Integer.parseInt(split[0]),Integer.parseInt(split[1]),arrs[Integer.parseInt(split[0])][Integer.parseInt(split[1])]);
        }
        System.out.println("===============================最终遍历之后的结果===============================");
        for(int i=0;i<arrs.length;i++){
            for(int j=0;j<arrs[i].length;j++){
                System.out.printf(arrs[i][j]+" ");
            }
            System.out.println("");
        }
    }

    public static void putMap(String key,int val){
        if(maps.containsKey(key)) maps.get(key).add(val);
        else {
            Set<Integer> set = new HashSet<>();
            maps.put(key,set);
            maps.get(key).add(val);
        }
        // 这里将数据放入对应的set集合之后需要做一次检查 如果满足了只差一个数那个就需要将这个位置 填充
        if(maps.get(key).size() == 8){
            if(!maps.get(key).contains(1)) split(key,1);
            else if(!maps.get(key).contains(2)) split(key,2);
            else if(!maps.get(key).contains(3)) split(key,3);
            else if(!maps.get(key).contains(4)) split(key,4);
            else if(!maps.get(key).contains(5)) split(key,5);
            else if(!maps.get(key).contains(6)) split(key,6);
            else if(!maps.get(key).contains(7)) split(key,7);
            else if(!maps.get(key).contains(8)) split(key,8);
            else split(key,9);
            stacks.push(key);
        }

    }

    public static  void split(String key,int v){
        String[] split = key.split("-");
        arrs[Integer.parseInt(split[0])][Integer.parseInt(split[1])] = v;
    }


    public static void analysisCell(int x,int y,int val){
        for(int i=(x/3)*3;i<(x/3)*3 +3;i++){
            for(int j=(y/3)*3;j<(y/3)*3+3;j++){
                if(arrs[i][j] == 0){
                    String key = String.valueOf(i)+"-"+String.valueOf(j);
                    putMap(key,val);
                }
            }
        }
    }

    /**通过检查 将对应的不能容许存在的值set进集合中*/
    public static void putMapsValue(int x,int y,int val){
        for(int i=0;i<arrs[x].length;i++){
            if(arrs[x][i] == 0 ){
                String key = String.valueOf(x)+"-"+String.valueOf(i);
                putMap(key,val);
            }
        }
        for(int j=0;j<arrs.length;j++){
            if(arrs[j][y] == 0){
                String key = String.valueOf(j)+"-"+String.valueOf(y);
                putMap(key,val);
            }
        }
        // 判断xy对应的点属于哪一个3*3
        analysisCell(x,y,val);
    }
    public static void main(String[] args) {
        analysis();
    }

}

结果和预期结果一致，暂时是解决这个问题了。但是其实这里还有一个隐藏问题，就是可能会出现不能完全确定的一个点时的情况，这种情况就如上文所说 需要用到，假设成立 然后用假设成立的结果来反推最终的结果从而来决定是否采用这个点。因为时间仓促，这里代码就不写了。感兴趣的可以接着往下写

QQ截图20190130162146.png