力扣刷题记录_热题100（自学）_力扣热题

1、 无重复字符的最长子串（力扣3）

//1.滑动窗口
    public int lengthOfLongestSubstring(String s) {
        if(s.length() < 2) return s.length();

        Map<Character,Integer> map = new HashMap<Character,Integer>();
        int left = 0,right = 0,max = 0;
        while(right < s.length()){
            if(map.containsKey(s.charAt(right))){
                //以“abba”为例，防止left被原来的数据影响
                left = Math.max(map.get(s.charAt(right)) + 1,left);
            }
            map.put(s.charAt(right),right);
            max = Math.max(max,right - left + 1);
            right ++;
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、 Z 字形变换（力扣6）

//1.
    /*
    * 0   4   8
    * 1 3 5 7 9
    * 2   6   10
    *
    * */
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        String[] rows = new String[Math.min(s.length(),numRows)];
        Arrays.fill(rows,"");
        int curRow = 0;
        //用来判断是不是向下的
        boolean goingDown = false;

        for(char c : s.toCharArray()){
            rows[curRow] += c;
            //每当为第一行和最后一行时，调整方向
            if(curRow == 0 || curRow == numRows - 1){
                goingDown = !goingDown;
            }
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder sb = new StringBuilder();
        for(String str : rows){
            sb.append(str);
        }
        return sb.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3、 字符串转换整数 (atoi)（力扣8）

//1.从前向后遍历，理清各种情况
    public int myAtoi(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        int index = 0;
        // 去掉前导空格
        while(index < len && chars[index] == ' '){
            index ++;
        }
        //去掉前导空格以后到了末尾了
        if(index == len) return 0;
        //判断是否是负数
        boolean negative = false;
        if(chars[index] == '-'){
            negative = true;
            index ++;
        }else if(chars[index] == '+'){
            index ++;
        }else if(chars[index] - '0' > 9 || chars[index] - '0' < 0){
            return 0;
        }
        //ans:记录最终数值
        int ans = 0;
        //当满足是数字时继续向下进行
        while(index < len && chars[index] - '0' <= 9 && chars[index] - '0' >= 0){
            int digit = chars[index] - '0';
            //判断是否会越界
            if(ans > (Integer.MAX_VALUE - digit) / 10){
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit;
            index ++;
        }
        return negative ? -ans : ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4、盛最多水的容器（力扣11）

//1.双指针
    public int maxArea(int[] height) {
        int len = height.length;
        //左指针，右指针，最大值
        int left = 0,right = len - 1,max = 0;
        while(left < right){
            max = Math.max(max,(right - left) * Math.min(height[left],height[right]));
            //选择短板进行移动
            if(height[left] <= height[right]){
                left ++;
            }else{
                right --;
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5、合并两个有序链表（力扣21）

//1.迭代
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        //设置哑结点，便于返回头节点
        ListNode yummy = new ListNode(-101);
        ListNode root = yummy;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                root.next = list1;
                list1 = list1.next;
            }else{
                root.next = list2;
                list2 = list2.next;
            }
            root = root.next;
        }

        if(list1 != null){
            root.next = list1;
        }
        if(list2 != null){
            root.next = list2;
        }
        return yummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//2.递归
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6、括号生成（力扣22）

//1.回溯
    List<String> list;
    StringBuilder sb;
    public List<String> generateParenthesis(int n) {
        list = new ArrayList<>();
        sb = new StringBuilder();
        backTracking(n,n);
        return list;
    }

    //leftNum：可用的‘（’数量  rightNum：可用的‘）’数量
    public void backTracking(int leftNum,int rightNum){
        if(leftNum == 0 && rightNum == 0){
            list.add(sb.toString());
            return;
        }
        //如果已经加入的右括号比左括号多，非法，直接返回
        if(leftNum > rightNum){
            return;
        }
        //优先加入左括号
        if(leftNum > 0){
            sb.append('(');
            backTracking(leftNum - 1,rightNum);
            sb.deleteCharAt(sb.length() - 1);
        }
        if(leftNum < rightNum){
            sb.append(')');
            backTracking(leftNum,rightNum - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

7、合并K个升序链表（力扣23）

//1.分治算法
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return sort(lists,0,lists.length - 1);
    }

    public ListNode sort(ListNode[] lists,int left,int right){
        if(right - left == 0) return lists[left];
        int mid = left + ((right - left) >> 1);
        //分
        ListNode leftNode = sort(lists,left,mid);
        ListNode rightNode = sort(lists,mid + 1,right);
        //治
        return mergeTwoLists(leftNode,rightNode);
    }
    //合并两个升序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode yummy = new ListNode(-101);
        ListNode root = yummy;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                root.next = list1;
                list1 = list1.next;
            }else{
                root.next = list2;
                list2 = list2.next;
            }
            root = root.next;
        }

        if(list1 != null){
            root.next = list1;
        }
        if(list2 != null){
            root.next = list2;
        }
        return yummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

8、两数相加（力扣2）

//1.遍历
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

9、K 个一组翻转链表（力扣25）

10、下一个排列（力扣31）

//1.
    /*
    * 以 13876为例
    * 第一个变小的数为3，最后一个比3大的数为6，交换3和6，变成16873，再对873重新排序即为结果
    * */
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if(len == 1) return;
        //left和right分别定义为头和尾，防止出现321这种情况
        int left = 0,right = len - 1;
        //相当于从后往前找到第一个变小的数
        for(int i = 0;i < len - 1;i ++){
            if(nums[i] < nums[i + 1]){
                left = i;
            }
        }
        //从第一个变小的数的下一个位置开始找最后一个大于他的位置
        for(int i = left + 1;i < len;i ++){
            if(nums[i] > nums[left]){
                right = i;
            }
        }
        //交换两个位置的数
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        //对后面的数重新排序
        Arrays.sort(nums,left + 1,len);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

11、最长有效括号（力扣32）

//1.动态规划
    public int longestValidParentheses(String s) {
        int max = 0;
        //dp[i]表示以s.charAt(i)结尾的字符串的 最长有效括号子串 的长度
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            //如果当前字符为右括号
            if (s.charAt(i) == ')') {
                //如果前一个字符为左括号
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

12、搜索旋转排序数组（力扣33）

//1.二分查找
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            //前半部分有序
            if (nums[left] <= nums[mid]) {
                //目标值在前半部分，二分查找
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    //如果目标值不在前半部分，则去后半部分查找
                    left = mid + 1;
                }
                //后半部分有序
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }

        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

13、 旋转图像（力扣48）

public void rotate(int[][] matrix) {
        int len = matrix.length;
        //先转置
        for(int i = 0;i < len;i ++){
            for(int j = 0;j < i;j ++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        //再左右反转
        int left = 0,right = len - 1;
        while(left < right){
            for(int i = 0;i < len;i ++){
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
            }
            left ++;
            right --;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

14、 颜色分类（力扣75）

//1.计数排序
    public void sortColors(int[] nums) {
        int[] arr = new int[3];
        for(int i = 0;i < nums.length;i ++){
            arr[nums[i]] ++;
        }

        for(int i = 0;i < arr[0];i ++){
            nums[i] = 0;
        }

        for(int i = arr[0];i < arr[0] + arr[1];i ++){
            nums[i] = 1;
        }

        for(int i = arr[0] + arr[1];i < nums.length;i ++){
            nums[i] = 2;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//2.
    public void sortColors2(int[] nums) {
        int num0 = 0, num1 = 0, num2 = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                nums[num2++] = 2;
                nums[num1++] = 1;
                nums[num0++] = 0;
            }else if(nums[i] == 1) {
                nums[num2++] = 2;
                nums[num1++] = 1;
            }else {
                nums[num2++] = 2;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//3.快排
    public void sortColors3(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] nums,int l,int r){
        if (l < r) {
            //将选择的基准值和数组的最后一个数值交换
            swap(nums, l + (int) (Math.random() * (r - l + 1)), r);
            //数组长度为2，划分之后等于区域的左边界和右边界
            int[] p = partition(nums, l, r);
            quickSort(nums, l, p[0] - 1);
            quickSort(nums, p[1] + 1, r);
        }
    }

    public int[] partition(int[] nums,int l,int r){
        //小于区右边界
        int less = l - 1;
        //大于区左边界
        int more = r;
        while (l < more) {//l表示当前数的位置
            //当前数小于划分值
            if (nums[l] < nums[r]) {
                swap(nums, ++less, l++);
                //当前数大于划分值
            } else if (nums[l] > nums[r]) {
                //因为此时l位置的数是新换过来的，所以l不动
                swap(nums, --more, l);
                //当前数等于划分值
            } else {
                l++;
            }
        }
        //最后再将划分值和大于区第一个数交换
        swap(nums, more, r);
        //返回新的边界值
        return new int[] { less + 1, more };
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

15、 单词搜索（力扣79）

//1.回溯算法
    public boolean exist(char[][] board, String word) {
        for(int i = 0;i < board.length;i ++){
            for(int j = 0;j < board[i].length;j ++){
                if(backTracking(board,word,i,j,0)) return true;
            }
        }
        return false;
    }

    public boolean backTracking(char[][] board,String word,int i,int j,int k){
        if(k == word.length()) return true;
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length) return false;
        if(board[i][j] != word.charAt(k)) return false;

        char c = board[i][j];
        board[i][j] = '0';
        boolean res = (backTracking(board,word,i - 1,j,k + 1) || backTracking(board,word,i + 1,j,k + 1) ||
                backTracking(board,word,i,j - 1,k + 1) || backTracking(board,word,i,j + 1,k + 1));
        board[i][j] = c;
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

16、 最大矩形（力扣85）

public int maximalRectangle(char[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        //根据字符数组重构int型数组
        int[][] arr = new int[m][n];
        for(int i = 0;i < m;i ++){
            for(int j = 0;j < n;j ++){
                int temp = matrix[i][j] - '0';
                if(i > 0 && temp != 0){
                    arr[i][j] = temp + arr[i - 1][j];
                }else{
                    arr[i][j] = temp;
                }
            }
        }

        int res = 0;
        for(int i = 0;i < m;i ++){
            res = Math.max(res,getMax(arr[i]));
        }
        return res;
    }

    //1.单调栈
    public int getMax(int[] nums){
        int len = nums.length;
        int[] newNums = new int[len + 2];
        for(int i = 0;i < len;i ++){
            newNums[i + 1] = nums[i];
        }

        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1;i < len + 2;i ++){
            if(newNums[i] > newNums[stack.peek()]){
                stack.push(i);
            }else if(newNums[i] == newNums[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                while(!stack.isEmpty() && newNums[i] < newNums[stack.peek()]){
                    int h = newNums[stack.pop()];
                    if(!stack.isEmpty()){
                        int l = stack.peek();
                        int r = i;
                        max = Math.max(max,h * (r - l - 1));
                    }
                }
                stack.push(i);
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

17、 二叉树展开为链表（力扣114）

//1.迭代
    public void flatten(TreeNode root) {
        if(root == null) return;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode preNode = root;
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != root){
                preNode.right = node;
                preNode.left = null;
            }
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
            preNode = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//2.递归
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.left);
        flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        while(root.right != null){
            root = root.right;
        }
        root.right = temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

18、 二叉树中的最大路径和（力扣124）

//1.递归
    private int ret = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        /**
         对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
         1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
         2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
         **/
        getMax(root);
        return ret;
    }

    public int getMax(TreeNode root) {
        if(root == null) return 0;
        int left = Math.max(0, getMax(root.left)); // 如果子树路径和为负则应当置0表示最大路径不包含子树
        int right = Math.max(0, getMax(root.right));
        ret = Math.max(ret, root.val + left + right);
        return Math.max(left, right) + root.val;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

19、 LRU 缓存（力扣146）

定义一个双向链表，表头放最近使用的，表为放最近最久未使用的

//双向链表节点
    class DoubleNode{
        int key;
        int value;
        DoubleNode pre;
        DoubleNode next;
        public DoubleNode(){};
        public DoubleNode(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    private int size;
    private int capacity;
    private Map<Integer,DoubleNode> map = new HashMap<>();
    //伪头结点，伪尾节点
    private DoubleNode head,tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DoubleNode();
        tail = new DoubleNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DoubleNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DoubleNode node = map.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DoubleNode newNode = new DoubleNode(key, value);
            // 添加进哈希表
            map.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DoubleNode tail = removeTail();
                // 删除哈希表中对应的项
                map.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }
	// 在表头添加
    private void addToHead(DoubleNode node){
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }
	// 删除节点
    private void removeNode(DoubleNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
	// 将当前节点移动到表头
    private void moveToHead(DoubleNode node){
        removeNode(node);
        addToHead(node);
    }
	// 删除当前节点并返回
    private DoubleNode removeTail(){
        DoubleNode temNode = tail.pre;
        removeNode(temNode);
        return temNode;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

20、 排序链表（力扣148）

//1.归并排序 2.合并两个有序链表 3.怎样找到链表的中间节点
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergeSort(head);
    }

    public ListNode mergeSort(ListNode head){
        if(head.next == null) return head;
        ListNode fast = head,slow = head,pre = null;
        while(fast != null && fast.next != null){
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }

        //断开为两个链表
        pre.next = null;
        ListNode p = mergeSort(head);
        ListNode q = mergeSort(slow);
        return twoLinkList(p,q);
    }

    //合并两个有序链表
    public ListNode twoLinkList(ListNode node1,ListNode node2){
        ListNode yummy = new ListNode(0);
        ListNode preNode = yummy;
        while(node1 != null && node2 != null){
            if(node1.val <= node2.val){
                preNode.next = node1;
                node1 = node1.next;
            }else{
                preNode.next = node2;
                node2 = node2.next;
            }

            preNode = preNode.next;
        }

        if(node1 != null){
            preNode.next = node1;
        }
        if(node2 != null){
            preNode.next = node2;
        }

        return yummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

21、 乘积最大子数组（力扣152）

//1.动态规划
    /*
    * 因为存在负数，最大值有可能变为最小值，最小值也有可能变温最大值
    * */
    public int maxProduct(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        //dp[i][0]:以nums[i]结尾的子数组的最小值  dp[i][1]:以nums[i]结尾的子数组的最大值
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        for(int i = 1;i < len;i ++){
            dp[i][0] = Math.min(dp[i - 1][0] * nums[i],Math.min(dp[i - 1][1] * nums[i],nums[i]));
            dp[i][1] = Math.max(dp[i - 1][0] * nums[i],Math.max(dp[i - 1][1] * nums[i],nums[i]));
        }

        int max = nums[0];
        for(int i = 1;i < len;i ++){
            max = Math.max(max,dp[i][1]);
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//2.空间优化
    public int maxProduct2(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int curMax = nums[0],curMin = nums[0];
        int max = nums[0];
        for(int i = 1;i < len;i ++){
            int tempMin = curMin;
            curMin = Math.min(curMin * nums[i],Math.min(curMax * nums[i],nums[i]));
            curMax = Math.max(tempMin * nums[i],Math.max(curMax * nums[i],nums[i]));
            max = Math.max(max,curMax);
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

22、 最小栈（力扣155）

//栈里存放二维数组，分别是 当前数值，当前最小数值
    private Deque<int[]> stack = new LinkedList<>();

    public MinStack() {

    }

    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(new int[]{val,val});
        }else{
            stack.push(new int[]{val,Math.min(val,stack.peek()[1])});
        }
    }

    public void pop() {
        stack.poll();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

23、岛屿数量（力扣200）

//dfs:   0 海洋 1 陆地 2 已经遍历过的
    public int numIslands(char[][] grid) {
        int islandNum = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    infect(grid, i, j);
                    islandNum++;
                }
            }
        }
        return islandNum;
    }
    //感染函数
    public void infect(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length ||
                j < 0 || j >= grid[0].length || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';
        infect(grid, i + 1, j);
        infect(grid, i - 1, j);
        infect(grid, i, j + 1);
        infect(grid, i, j - 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// bfs
	public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int r = grid.length;
        int c = grid[0].length;
        int num = 0;

        for (int i = 0; i < r; i ++) {
            for (int j = 0; j < c; j ++) {
                if (grid[i][j] == '1') {
                    num ++;
                    grid[i][j] = '0';
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i,j});
                    while (!queue.isEmpty()) {
                        int[] arr = queue.peek();
                        queue.poll();
                        int row = arr[0],col = arr[1];
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            queue.add(new int[]{row - 1,col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < r && grid[row+1][col] == '1') {
                            queue.add(new int[]{row + 1,col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            queue.add(new int[]{row,col - 1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < c && grid[row][col+1] == '1') {
                            queue.add(new int[]{row,col + 1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }
        return num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

24、课程表（力扣207）

public boolean canFinish(int numCourses, int[][] prerequisites) {
        int len = prerequisites.length;
        if(len == 0) return true;
        int[] pointer = new int[numCourses];
		// 记录修课程的情况
        Queue<int[]> queue = new LinkedList<>();
        for(int[] p : prerequisites){
        	// 统计每门课程需要修多少次
            pointer[p[0]] ++;
            queue.add(p);
        }

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i ++){
                int[] p = queue.poll();
                // 如果发现当前课程不用修，则需要修完此课程才能修的其他课程数量就减1
                if(pointer[p[1]] == 0){
                    pointer[p[0]] --;
                }else{
                    queue.add(p);
                }
            }
            // 发现是一个死循环
            if(queue.size() == size){
                return false;
            }
        }

        return queue.size() == 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

25、岛屿的周长（力扣463）

//1.dfs
    public int islandPerimeter(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    return infect(grid, i, j);
                }
            }
        }
        return 0;
    }

    //遍历返回有三种情况；1.超出格子范围 2.遇到海洋格子 3.遇到已经走过的格子
    //前两种会构成岛屿的边界，因此，统计前两种情况的数量即可
    public int infect(int[][] grid,int i,int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
            return 1;
        }
        if(grid[i][j] == 0) return 1;
        if(grid[i][j] != 1) return 0;

        grid[i][j] = 2;
        return infect(grid, i + 1, j) + infect(grid, i - 1, j) 
        + infect(grid, i, j + 1) + infect(grid, i, j - 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//2.直接遍历
    public int islandPerimeter2(int[][] grid) {
        int res = 0;
        //从上到下
        for(int i = 0;i < grid.length;i ++){
            //从左到右
            for(int j = 0;j < grid[0].length;j ++){
                if(grid[i][j] == 1){
                    res += 4;
                    //如果上边已经遍历过了，计数-2
                    if(i > 0 && grid[i - 1][j] == 2){
                        res -= 2;
                    }
                    //如果左边已经遍历过了，计数-2
                    if(j > 0 && grid[i][j - 1] == 2){
                        res -= 2;
                    }
                    //标识已经遍历过了
                    grid[i][j] = 2;
                }
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

26、岛屿的最大面积（力扣695）

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

    //感染函数
    public int infect(int[][] grid,int i,int j){
        if(i < 0 || i >= grid.length ||
                j < 0 || j >= grid[0].length || grid[i][j] != 1){
            return 0;
        }

        grid[i][j] = 2;
        return 1 + infect(grid, i + 1, j) + infect(grid, i - 1, j) +
                infect(grid, i, j + 1) + infect(grid, i, j - 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24