leetcode221. 最大正方形

思路

用dp数组来做，每次遍历matrix的元素，就把该元素作为正方形的右下角，看和其左边+上边+左上是否可以构成一个正方形。如何判断是否可以构成呢，就是只要三个位置的最小值都不是0就可以构成正方形，并且边长+1.

1.定义dp数组

因为有边界问题，所以dp数组定义为dp[i+1][j+1]表示以matrix[i][j]为下标的元素可以构成的正方形的边长。

2.dp数组初始化

dp数组全部为0即可。

3.递推公式

当前元素为1是，才有可能作为正方形的边长，所以，先进行判断在取值。只要是能作为边，就是上，左，左上三个方向的边长的最小值+1，就是dp[i][j]的长度。

if(matrix[i-1][j-1] == 1){ dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1; }

4.遍历顺序

正序遍历即可。

5.打印dp数组

取dp数组最大的数就是最大正方形的边。

代码

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int [][] dp = new int[m+1][n+1];
        int res = 0;
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(matrix[i-1][j-1] == 1){
                    dp[i][j] = Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                    res = Math.max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
}

思路

依次将所有元素压如栈中，然后将栈中元素弹出栈和链表的元素比较，如果值不相等就返回false。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        
        while(temp != null){
           stack.push(temp.val);
           temp = temp.next;
        }
        while(stack.size() != 0){
            if(stack.pop() != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }
}

思路

1.暴力方法，每次都把排除自己下标的算一遍。

2.用两个for循环从左右扫描数组两边。依次算当前数的左边数的和，依次计算右边的数的和。然后将两个结果合并为最后的结果。

代码

暴力方法，直接超时

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        
        for(int i = 0;i<length;i++){
            res[i] = fun(nums,i);
        }
        return res;
    }
    public int fun(int[] nums,int except){
        int sum = 1;
        for(int i = 0;i<nums.length;i++){
            if(i != except){
                sum*=nums[i];
            }
        }
        return sum;
    }
}

两此for循环：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        int[] left = new int[length];
        int[] right = new int[length]; 
        left[0] = 1;
        for(int i = 1;i<length;i++){
            left[i] = left[i-1]*nums[i-1];
        }
        right[length-1] = 1;
        for(int i = length-1;i>0;i--){
            right[i-1] = right[i]*nums[i];
        }
        for(int i =0;i<length;i++){
            res[i] = left[i]*right[i];
        }
        return res;   
    }
}