力扣爆刷第121天之CodeTop100五连刷91-95

力扣爆刷第121天之CodeTop100五连刷91-95

一、695. 岛屿的最大面积

题目链接：https://leetcode.cn/problems/max-area-of-island/description/
思路：求最大岛屿面积，经典深度优先算法，遇到岛屿就开始递归计数，途中把岛屿的1给置为0，防止重复递归。全局变量计数，统计即可。还有控制好边界条件。

class Solution {
    int max = 0, k = 0;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1) {
                    dfs(grid, i, j);
                }
                max = Math.max(max, k);
                k = 0;
            }
        }
        return max;
    }

    void dfs(int[][] grid, int x, int y) {
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return;
        k++;
        grid[x][y] = 0;
        dfs(grid, x-1, y);
        dfs(grid, x+1, y);
        dfs(grid, x, y-1);
        dfs(grid, x, y+1);
    }
}

二、227. 基本计算器 II

题目链接：https://leetcode.cn/problems/basic-calculator-ii/description/
思路：利用栈来做，用一个符号位记录运算符，当再次遇到运算符时，就把之前记录的数和之前的运算符相运算，入栈，更新运算符，最后注意边界条件，别漏掉最后一个数的计算。

class Solution {
    public int calculate(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int n = 0;
        char sign = '+';
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(Character.isDigit(c)) {
                n = n * 10 + (c - '0');
            }
            if(!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
                switch(sign) {
                    case '+':
                        stack.push(n);
                        break;
                    case '-':
                        stack.push(-n);
                        break;
                    case '*':
                        stack.push(stack.pop() * n);
                        break;
                    case '/':
                        stack.push(stack.pop() / n);
                        break;
                    
                }
                n = 0;
                sign = c;
            }
            
        }
        n = 0;
        while(!stack.isEmpty()) {
            n += stack.pop();
        }
        return n;
    }
}

三、83. 删除排序链表中的重复元素

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/
思路：双指针，慢指针记录前一个位置，然后比较是否相等，相等就删除后一个。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pro = head, cur = head.next;
        while(cur != null) {
            if(cur.val == pro.val) {
                cur = cur.next;
                pro.next = cur;
            }else{
                pro = pro.next;
                cur = cur.next;
            }
        }
        return head;
    }
}

四、198. 打家劫舍

题目链接：https://leetcode.cn/problems/house-robber/description/
思路：题目要求不能连着打劫，所以依赖前两天的状态，然后根据偷与不偷当前家，与前两家联系起来。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

五、139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/description/
思路：本题动态规划可以做，回溯也可以做，回溯的话就是一个组合问题，集合元素无重，可复选。
下面用动态规划来做，定义dp[i]表示以s[i]为结尾的字符串可以被表示出来，故，只要当前这一段可以被表示出来，那么当前位置的状态取决于上一段的结尾。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 0; i < s.length(); i++) {
            for(String w : wordDict) {
                int k = w.length();
                if(k > i+1 || dp[i+1] || !dp[i-k+1]) continue;
                dp[i+1] = isTrue(s, w, i);
            }
        }
        return dp[s.length()];
    }
    
    boolean isTrue(String s, String w, int end) {
        int i = end, j = w.length()-1;
        while(j >= 0) {
            if(s.charAt(i) != w.charAt(j)) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
    
}