leetcode 130,200,207,329,491,494,416,547,51

130 被围绕的区域

    boolean[][] flag;
    char[][] bod;
    int deep,width;
    public  void solve(char[][] board) {
        if (board.length == 0){
            return;
        }
         deep = board.length;
         width = board[0].length;
        bod = board;
        flag = new boolean[deep][width];

        for (int i = 0; i < deep; i++) {
            for (int j = 0; j < width; j++) {
                if ( (i == 0 || i == deep-1 || j == 0 || j == width-1) && (bod[i][j] == 'O')){
                    dfs(i,j);
                }
            }
        }

        for (int i = 0; i < deep; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == 'O' && !flag[i][j]){
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(int x,int y){
        if (flag[x][y] == true){
            return;
        }
        flag[x][y] = true;

        if (x-1>0 && bod[x-1][y] == 'O'){
            dfs(x-1,y);
        }
        if (x+1<deep && bod[x+1][y] == 'O'){
            dfs(x+1,y);
        }
        if (y-1>0 && bod[x][y-1] == 'O'){
            dfs(x,y-1);
        }
        if (y+1<width && bod[x][y+1] == 'O'){
            dfs(x,y+1);
        }



    }

}

200 岛屿的数量  简单题重拳出击

 　　

  char[][] grid;
    int deep,width;
    public int numIslands(char[][] grids) {
        deep = grid.length;
        width = grid[0].length;
        this.grid = grids;
        int result = 0;
        for (int i = 0; i < deep; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == '1'){
                    result++;
                    dfs(i,j);
                }
            }
        }
        return result;
    }

    public void dfs(int x,int y){
        grid[x][y] = '0';
        if (x-1>0 && grid[x-1][y] == '1'){
            dfs(x-1,y);
        }
        if (x+1<deep && grid[x+1][y] == '1'){
            dfs(x+1,y);
        }
        if (y-1>0 && grid[x][y-1] == '1'){
            dfs(x,y-1);
        }
        if (y+1<width && grid[x][y+1] == '1'){
            dfs(x,y+1);
        }
    }

207 课程表闭环

    Map<Integer, List<Integer>> map;
    Map<Integer,Boolean> flag;
    Set<Integer> set;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        map = new HashMap<>();
        flag = new HashMap<>();
        set = new HashSet<>();
        for (int[] prerequisite : prerequisites) {
            List<Integer> integers = map.get(prerequisite[0]);
            if (integers == null){
                integers = new ArrayList<>();
                map.put(prerequisite[0],integers);
            }
            integers.add(prerequisite[1]);
        }
        Set<Integer> integers = map.keySet();
        for (Integer integer : integers) {
            if (!dfs(integer)){
                return false;
            }
            set.clear();
        }

        return true;

    }

    public boolean dfs(int num){

        Boolean current = flag.get(num);
        if (current != null){
            flag.put(num,current);
            return current;
        }
        if (set.contains(num)){
            flag.put(num,false);
            return false;
        }
        set.add(num);
        List<Integer> nexts = map.get(num);
        if (nexts == null || nexts.isEmpty()){
            flag.put(num,true);
            return true;
        }
        boolean dfs = true;
        for (Integer next : nexts) {
           // if (next)
             dfs &= dfs(next);
        }
        flag.put(num,dfs);
        return dfs;
    }

211 添加与搜索单词

 DicNode root;
    /** Initialize your data structure here. */
    public DFS5() {
        root = new DicNode('o');
    }

    public void addWord(String word) {
        char[] chars = word.toCharArray();
        DicNode tp = root;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            DicNode son = tp.son.get(c);
            if (son == null){
                son = new DicNode(c);
                tp.son.put(c,son);
            }
            if (i == chars.length-1){
                son.end = true;
            }
            tp = son;
        }
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        List<DicNode> values = root.getSon(chars[0]);
        if (values != null){
            for (DicNode value : values) {
                if (find(word,0,value)){
                    return true;
                }
            }

        }

        return false;
    }

    public boolean find(String word,int index,DicNode node){
        if (node == null)return false;
        char c = word.charAt(index);
        if (c == '.' || c == node.val){
            if (index == word.length()-1){
                return node.end;
            }
            List<DicNode> values = node.getSon(word.charAt(index+1));
            if (values != null){
                for (DicNode value : values) {
                    if (find(word,index+1,value)){
                        return true;
                    }
                }
            }

        }
        return false;
    }

    static class DicNode{

        char val;
        boolean end;
        Map<Character,DicNode> son;

        public DicNode(char val) {
            this.val = val;
            this.son = new HashMap<>();
        }

        public List<DicNode> getSon(char c){
            if (c == '.'){
                return new ArrayList<>(son.values());
            }else {
                DicNode dicNode = son.get(c);
                if (dicNode == null)return null;
                List<DicNode> data= new ArrayList<>();
                data.add(dicNode);
                return data;
            }
        }
    }

329 　　矩阵最长递增路径

 　　这题感觉就是记忆画搜索，每次遍历的时候要记住当前值代表的最长递增路径，这样一下次又遍历到这个值的时候就可以直接使用。

    int[][] forward = {{1,0},{0,1},{-1,0},{0,-1}};
    int[][] dp;
    int[][] ma;
    int width,deep;

    public int longestIncreasingPath(int[][] matrix) {
        deep = matrix.length;
        width = matrix[0].length;
        dp = new int[deep][width];
        ma = matrix;
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < deep; i++) {
            for (int j = 0; j < width; j++) {
                result = Math.max(dfs(i,j),result);
            }
        }
        return result;
    }

    public int dfs(int x,int y){
        if (dp[x][y] != 0){
            return dp[x][y];
        }
        dp[x][y] = 1;
        for (int[] ints : forward) {
            int tx = x+ints[0],ty = y+ints[1];
            if (tx>=0 && tx <deep && ty>=0 && ty<width && ma[tx][ty] > ma[x][y]){
                dp[x][y] = Math.max(dp[x][y],dfs(tx,ty)+1);
            }

        }
        return dp[x][y];
    }

491 所有递增子序列

 我的解法效率那是相当低

public class DFS7 {

    public static void main(String[] args) {
        System.out.println(findSubsequences(new int[]{4, 6, 7, 7}));
    }
    public static List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int c = nums[i];

            List<List<Integer>> tp = new ArrayList<>();
            for (List<Integer> re : res) {
                if (c>=re.get(re.size()-1)){
                    List<Integer> list = new ArrayList<>(re);
                    list.add(c);
                    tp.add(list);
                }
            }
            res.addAll(tp);
            res.add(Arrays.asList(c));
        }
        Iterator<List<Integer>> iterator = res.iterator();
        while (iterator.hasNext()){
            List<Integer> next = iterator.next();
            if (next.size() == 1){
                iterator.remove();
            }
        }
        List<List<Integer>> resp = new ArrayList<>(res);
        return resp;
    }
}

　　其实这儿涉及到的一个关键点应该是去重，比如 4.6.7.7   就会出现两个47 47，明显不能一起计算，所以如何果能够高效去重应该是很重要的。我用的全局set去重，这样效率非常低。然后看了下官方题解，具体的题解比较长，所以这儿就不贴了，关键在于遍历的时候如何决定是否走当前节点不选择。

 int[] nums;
    List<Integer> tps ;
    List<List<Integer>> res ;
    public List<List<Integer>> findSubsequences(int[] nums) {
        this.nums = nums;
        tps = new ArrayList<>();
        res = new ArrayList<>();
        dsf(0,Integer.MIN_VALUE);
        return res;
    }

    public void dsf(int cu,int last){
        if (cu == nums.length){
            if (tps.size() > 1){
                res.add(new ArrayList<>(tps));
            }
            return;
        }
        int k =nums[cu];
        //选择当前元素
        if (k>=last){
            tps.add(k);
            dsf(cu+1,k);
            tps.remove(tps.size()-1);
        }
        //如果不选择当前元素
        if (k != last)
        dsf(cu+1,last);

    }

494 目标和

 　　暴力解法应该是如下,官解有动态规划，因为解析比较长这儿就不贴了

class Solution {
    int result ;
    int nums[];
    int s;
    public int findTargetSumWays(int[] nums, int S) {
        result = 0;
        this.nums = nums;
        s = S;
        dfs(nums[0],1);
        dfs(-nums[0],1);
        return result;
    }

    public void dfs(int current,int index){
        if (index == nums.length){
            if (current == s){
                result++;
            }
            return;
        }
        dfs(current+nums[index],index+1);
        dfs(current-nums[index],index+1);

    }
}

416  分割等和子集

 　　看着其实和上题比较像，我的解法如下，但是不知道为何提交成绩很差，好好不容易想到个dp问题的解法，哭辽。。。。

    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total+=num;
        }
        if (nums.length <2 || (total&1)!=0){
            return false;
        }
        int target = total/2;
        boolean[][] dp = new boolean[nums.length][total+1];
        dp[0][nums[0]] = true;
        dp[0][0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= total; j++) {
                dp[i][j] = dp[i-1][j];
                if (j>=nums[i]){
                    dp[i][j] |= dp[i-1][j-nums[i]];
                }
                if (j == target && dp[i][j]){
                    return true;
                }
            }
        }
        return dp[nums.length-1][total/2];
    }

　　后面查看官方的解才知道因为i只和i-1有关，所以可不用开辟很大的数组空间。并且可以只开辟target大小的数组而不是total，所以根据思路修改了下

 public boolean canPartition(int[] nums) {
        int total = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            total+=num;
            max = Math.max(max,num);
        }
        if (nums.length <2 || (total&1)!=0){
            return false;
        }
        int target = total/2;
        if (max>target){
            return false;
        }
        boolean[] pre = new boolean[target+1];
        boolean[] tp = new boolean[target+1];
        pre[nums[0]] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                tp[j] = pre[j];
                if (j>=nums[i]){
                    tp[j] |= pre[j-nums[i]];
                }
                if (j == target && tp[j]){
                    return true;
                }
            }
            pre = tp;
            tp = new boolean[target+1];
        }
        return tp[target];
    }

547 省份数量

 　　如果还是像之前的岛屿数量解法明显效率会非常低,因为会进行太多的无用计算。

public class Collect2 {
    int[][] grid;
    int deep,width;
    public int findCircleNum(int[][] grids) {
        deep = grids.length;
        width = grids[0].length;
        this.grid = grids;
        int result = 0;
        for (int i = 0; i < deep; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1){
                    result++;
                    dfs(i,j);
                }
            }
        }
        return result;
    }

    public void dfs(int x,int y){
        grid[x][y] = 0;
        for (int i = x-1; i >= 0 ; i--) {
            if (grid[i][y] == 1){
                dfs(i,y);
            }
        }
        for (int i = x+1; i < deep; i++) {
            if (grid[i][y] == 1){
                dfs(i,y);
            }
        }
        for (int i = y-1; i >=0; i--) {
            if (grid[x][i] == 1){
                dfs(x,i);
            }
        }
        for (int i = y+1; i <width; i++) {
            if (grid[x][i] == 1){
                dfs(x,i);
            }
        }
    }
}

 　　然后看了下官解的思路，感觉自己写的也太low了。

    int[][] grid;
    int deep,width;
    boolean[] visit;
    public int findCircleNum(int[][] grids) {
        deep = grids.length;
        width = grids[0].length;
        this.grid = grids;

        visit = new boolean[grids.length];
        int result = 0;
        for (int i = 0; i < grids.length; i++) {
            if (!visit[i]){
                dfs(i);
                result++;
            }
        }

        return result;
    }

    public void dfs(int x){
        for (int i = 0; i < grid.length; i++) {
            if (i != x && !visit[i] && grid[x][i] == 1 ){
                visit[i] = true;
                dfs(i);
            }
        }
    }

51 N皇后问题

Set<Integer> rows;
    Set<Integer> left;
    Set<Integer> right;
    int width;
    List<List<String>> result;
    public List<List<String>> solveNQueens(int n) {
        rows = new LinkedHashSet<>();
        left = new HashSet<>();
        right = new HashSet<>();
        width = n;
        result = new ArrayList<>();
        dfs(0);
        return result;
    }

    public void dfs(int level){
        if (level == width){
            generate();
            return;
        }
        for (int i = 0; i < width; i++) {
            //占用
            if (rows.contains(i) || right.contains(level+i) || left.contains(level-i)){
                continue;
            }
            right.add(level+i);
            left.add(level-i);
            rows.add(i);
            //下一轮
            dfs(level+1);
            //去掉
            right.remove(level+i);
            left.remove(level-i);
            rows.remove(i);
        }

    }

    public void generate(){
        List<String> list = new ArrayList<>();
        for (Integer rowIndex : rows) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < width; i++) {
                sb.append(rowIndex.equals(i)?"Q":"." );
            }
            list.add(sb.toString());
        }
        result.add(list);
    }