java-leetcode-note1

java 数组是如何在堆栈中存储的？

堆中分配连续内存空间，栈上临时变量指向堆

• https://www.zhihu.com/question/589576753
  image.png

463. 岛屿的周长

class Solution {
    public int islandPerimeter(int[][] grid) {
        int ret = 0;
        int r = grid.length;
        int c = grid[0].length;
        for (int i =0; i<r;++i) {
            
            for (int j = 0; j<c; ++j ){
                if (grid[i][j] == 1) {
                    // 每个grid  4个方向，上右下左
                    if (i == 0 || grid[i-1][j] == 0) {
                        ++ret;
                    }

                    if ( j == c -1 || grid[i][j+1] == 0) {
                       ++ret;
                    }
                    if (i == r -1 || grid[i+1][j] == 0) {
                       ++ret;
                    }
                    if (j == 0 || grid[i][j-1] == 0) {
                       ++ret;
                    }
                }
            }
        }
        return ret;
    }
}

462. 最小操作次数使数组元素相等 II

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int ret = 0, num = nums[nums.length/2];
        for(int item : nums) {
            ret += Math.abs(item - num);
        }
        return ret;
    }
}

539. 最小时间差

class Solution {
    public int findMinDifference(List<String> timePoints) {

        int total = timePoints.size();
        if (total < 2) {
            return 0;
        }
        List<Integer> nums = new ArrayList<Integer>();
        for(String s : timePoints) {
            String[] timeList = s.split(":");
            nums.add( Integer.parseInt(timeList[0])*60+ Integer.parseInt(timeList[1]) );
        }
        Collections.sort(nums);
        int ret = nums.get(1) - nums.get(0);
        int end = 23*60+59 + 1;
        for(int i=2;i<total;++i) {
            ret = Math.min(ret, nums.get(i) - nums.get(i-1));
        }
        ret = Math.min(ret, end - nums.get(nums.size()-1) + nums.get(0) );
        
        return ret;

    }
}

561. 数组拆分

class Solution {
    public int arrayPairSum(int[] nums) {

        Arrays.sort(nums);
        int ret = 0;
        int n = nums.length;
        for (int i=0;i<n;i += 2) {
            ret += nums[i];
        }
        return ret;
    }
}

695. 岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        Solution s = new Solution();
        int r = grid.length, c = grid[0].length;
        int ret = 0;
        for (int i = 0;i<r;++i) {
            for(int j=0;j<c;++j) {
                if (grid[i][j] == 1) {
                    ret = Math.max(s.dfs(grid,i,j,r,c), ret);
                }
            }
        }
        return ret;

    }

    public int dfs(int [][] grid, int i, int j, int r, int c) {
        if (grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        int ret = 1;
        // 4个方向
        if( i > 0 && grid[i-1][j] == 1) {
            ret += dfs(grid, i-1,j,r,c);
        }
        if (j < c -1 && grid[i][j+1] == 1) {
            ret += dfs(grid, i,j+1,r,c);
        }
        if ( i < r -1 && grid[i+1][j] == 1) {
            ret += dfs(grid, i+1,j,r,c);
        }
        if (j > 0 && grid[i][j-1] == 1) {
            ret += dfs(grid, i, j-1, r,c);
        }
        return ret;
    }
}