[Java/C++] Clean Code


  • 12

    Java

    class Solution {
        private static int[][] delta = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    
        public int numDistinctIslands(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            Set<List<List<Integer>>> islands = new HashSet<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    List<List<Integer>> island = new ArrayList<>();
                    if (dfs(i, j, i, j, grid, m, n, island))
                        islands.add(island);
                }
            }
            return islands.size();
        }
    
        private boolean dfs(int i0, int j0, int i, int j, int[][] grid, int m, int n, List<List<Integer>> island) {
            if (i < 0 || m <= i || j < 0 || n <= j || grid[i][j] <= 0) return false;
            island.add(Arrays.asList(i - i0, j - j0));
            grid[i][j] *= -1;
            for (int d = 0; d < 4; d++) {
                dfs(i0, j0, i + delta[d][0], j + delta[d][1], grid, m, n, island);
            }
            return true;
        }
    }
    

    C++

    class Solution {
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            int m = grid.size(), n = grid[0].size();
            set<vector<vector<int>>> islands;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    vector<vector<int>> island;
                    if (dfs(i, j, i, j, grid, m, n, island))
                        islands.insert(island);
                }
            }
            return islands.size();
        }
    
    private:
        int delta[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0};
    
        bool dfs(int i0, int j0, int i, int j, vector<vector<int>>& grid, int m, int n, vector<vector<int>>& island) {
            if (i < 0 || m <= i || j < 0 || n <= j || grid[i][j] <= 0) return false;
            island.push_back({i - i0, j - j0});
            grid[i][j] *= -1;
            for (int d = 0; d < 4; d++) {
                dfs(i0, j0, i + delta[d][0], j + delta[d][1], grid, m, n, island);
            }
            return true;
        }
    };
    

  • 0
    T

    Your solution is nice! But I am wondering how set compares two list<Integer> lists in java? if list1 has same elements as list2, are they equal in Set? Since I transform list into string in this question, so I am curious whether we really can directly use set.contains(list) to check whether list1 is equal to list2 under the condition that list1 and list2 have same elemets?


  • 1

    Nice! I was wandering how to express each island.


  • 1

    @tiandiao123 Set<T> compares T by calling T.equals(Object other), in this case ArrayList. ArrayList inherit the equals(Obect other){...} from List, which is defined so that lists with same item in same order are equal lists.


  • 0
    J

    Hi, I've read a lot of your elegant C++ codes.
    I also focus on C++, so I'm always wondering how to generate such concise and clean codes like yours.
    Taking this problem as example, I got a similar idea, that is record each island and shift them so that make coordinates of first point to (0,0). But it took me almost 40 minutes to write a very verbose solution.
    So how can I get improved? Thank you !


  • 0
    T

    @alexander Thanks!Got it!


  • 3

    @alexander said in [Java/C++] Clean Code:

        island.add(new ArrayList<Integer>(Arrays.asList(i - i0, j - j0)));
    

    Why not just this?

            island.add(Arrays.asList(i - i0, j - j0));

  • 0

    @StefanPochmann Thank you for pointing out! Yes it is not necessary, and I don't know why I did it that way :)


  • 1

    @JadenPan said in [Java/C++] Clean Code:

    Taking this problem as example, I got a similar idea, that is record each island and shift them so that make coordinates of first point to (0,0). But it took me almost 40 minutes to write a very verbose solution.

    Thank you for saying that. Just take some practice. Usually if you meet same problem or similar problem again and again, each time you will have a slightly different and probably better & cleaner approach to solve it. Verbose is not a big deal, most important thing is you get something that works :)


  • 0
    J

    @alexander Thank you, I'll keep working hard


  • 0
    W

    @alexander said in [Java/C++] Clean Code:

    Arrays.asList(i - i0, j - j0)

    Excuse me, what does Arrays.asList(int, int) do? I only know Arrays.asList(int[]) to change an int array to list.


  • -1

    @w1024020103 Can't you look up the documentation? Can't you try it out? Can't you take a guess? And I don't think you actually know Arrays.asList(int[]). That creates a list of length 1, the single element being the whole int-array. That's pretty useless and thus I highly doubt that that's what you thought it does.


  • 0
    F

    Hi, @alexander. Thank you for your amazing solution.
    I was wondering why you should return a boolean in your dfs function? I use void return type, it also works. In your dfs function, after go to four directions, it will always return true to main function. So I think

    if (dfs(i, j, i, j, grid, m, n, island))
    

    this condition is unnecessary too. We can call dfs directly and after that, add island into islands. Correct me if I was wrong! Thank you.

    class Solution {
        public int numDistinctIslands(int[][] grid) {
            Set<List<List<Integer>>> islands = new HashSet<>();
            int count = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        List<List<Integer>> island = new ArrayList<>(); 
                        dfs(grid, i, j, i, j, island);
                        islands.add(island);
                    }
                }
            }
            return islands.size();
        }
        public void dfs(int[][] grid, int i, int j, int i0, int j0, List<List<Integer>> island) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
                return;
            }
            grid[i][j] = -1;
            island.add(Arrays.asList(i - i0, j - j0));
            int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int[] d: dir) {
                dfs(grid, i + d[0], j + d[1], i0, j0, island);
            }
        }
    }
    

  • 0
    F

    oops! It's my fault. I didn't noticed that the entrance to go to dfs in your solution is different from me. In your solution, you will try every cells as entrance. But when you met a 0 or -1, you will return false. Only if you met 1, you will continue to search four directions and finally return true to let "islands" add "island".

    for (int i = 0; i < m; i++) {
         for (int j = 0; j < n; j++) {
              List<List<Integer>> island = new ArrayList<>();
              if (dfs(i, j, i, j, grid, m, n, island))
                  islands.add(island);
           }
     }
    

  • 6

    Nice.
    My solution beats 98%. I just use the direction string and hash it. :)

    public int numDistinctIslands(int[][] grid) {
        Set<String> set = new HashSet<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] != 0) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, i, j, sb, "o"); // origin
                    grid[i][j] = 0;
                    set.add(sb.toString());
                }
            }
        }
        return set.size();
    }
    private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
        if(i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] == 0) return;
        sb.append(dir);
        grid[i][j] = 0;
        dfs(grid, i-1, j, sb, "u"); // up
        dfs(grid, i+1, j, sb, "d"); // down
        dfs(grid, i, j-1, sb, "l"); // left
        dfs(grid, i, j+1, sb, "r"); // right
        sb.append("b"); // back
    }

  • 0
    X

    I'm wondering if DFS is favored over BFS when doing search in the matrix/graph?
    The code looks shorter for DFS.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.