月度归档： 2021年9月

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int tmpMin = min;
            int tmpMax = max;
            if (num < 0){
                max = Math.max(num, tmpMin * num);
                min = Math.min(num, tmpMax * num);
            }else{
                max = Math.max(num, tmpMax * num);
                min = Math.min(num, tmpMin * num);
            }
            res = Math.max(res,max);
        }
        return res;
    }
}

动态规划，解释起来就是，因为没有小于1或者大于-1的小数，所以在数值上肯定乘得越多越大。

又，当遇到一个负值的时候会使最大值变成最小，最小值变成最大，需要额外判断下。

又，最大最小值其实都可能为负数，所以仍需要和当前位置的值比较下，如果符合条件的，指当前值比之前的最大值乘以当前值还大，之类的这种情况（最小同理），那么就取当前的值为最大值，从逻辑上也表示了子序列乘积的从当前位置之前断开了。

有点抽象，我自己也绕了好久

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

乍得一眼看起来很简单，今天的每日一题，直接上来一个遍历啊，比较前后的大小关系，且题面中也说明了数组边界前一位和后一位都为负无穷，且相邻两位的数值保证不相等

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1){
            return 0;
        }
        int i = 0;
        while (i< nums.length){
            if (getArrIndex(nums,i-1)< getArrIndex(nums,i) && getArrIndex(nums,i) > getArrIndex(nums,i+1)){
                return i;
            }
            i++;
        }
        return i;
    }

    public int getArrIndex(int[] nums,int index){
        if ( index<0 || index >= nums.length ){
            return Integer.MIN_VALUE;
        }
        return nums[index];
    }
}

提交，也过了，不过这边其实是有问题的，主要是以下两点

1.复杂度要求的O（Log N），单次全数组遍历的话，时间复杂度在O（N），并不符合题面中要求的O（Log N）。而因为题面的说的

导致遍历的时间消耗其实并不是很大。

2.Integer.MIN_VALUE的问题，因为入参给的就是int[]，导致最小值就是Integer.MIN_VALUE，实际并不是负无穷，而测试用例里就有一个这个用例，但是因为要求的数组中相邻的两个值不相等，且在代码里判断了数组长度为1导致规避掉了这个问题，实际在逻辑上来说，这个作法是错误的

那么接下来，因为要求的O（Log N）时间复杂度，就自然会想到往二分查找的方向上去靠拢。

如果有曲线的话，可以对比下看下，如果当前值比后面的值小，则说明需要往后挪，则left指针往后挪动，否则把right指针往前挪动。在新的方法中我也把比较边界外的值单独写了方法比较，而不是假设定为Integer.MIN_VALUE

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0,r = nums.length-1;
        while (l < r){
            int mid = l + (( r - l )>>1);
            if (isTop(nums,mid)){
                return mid;
            }
            if (compareToNext(nums, mid)){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return l;


    }

    boolean compareToNext(int[] nums, int index){
        if (index == nums.length-1){
            return true;
        }
        return nums[index] > nums[index+1];
    }

    boolean isTop(int[] nums, int index){
        boolean leftSmaller,rightSmaller;
        if (index == 0){
            leftSmaller = true;
        }else{
            leftSmaller = nums[index] > nums[index-1];
        }
        if (index == nums.length-1){
            rightSmaller = true;
        }else{
            rightSmaller = nums[index] > nums[index+1];
        }
        return leftSmaller && rightSmaller;
    }
}

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

题解

每一个房间有两种情况，偷或者不偷，

如果当前房间不偷，则能获得的总金额为上一个房间偷或者不偷两种情况中较大的一个。

如果当前房间偷，则上一个房间只能不偷，那么这时能得到的最大金额应当是上一个房间不偷的金额+这个房间的金额

动态转移方程：

dp[n][0] = max(dp[n − 1][0], dp[n − 1][1]);
dp[n][1] = dp[n − 1][0] + nums[n];

代码：

class Solution {
    public int rob(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][1] = nums[0];
        int i = 1;
        for (; i < nums.length; i++) {
            //dp[i][0]表示当前不偷，p[i][1]表示当前偷
            //如果当前房间不偷，则前一个房间偷或者不偷都可以，取最大值
            dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);
            //如果当前房间偷，则前一个房间不能偷
            //此处本质上是Math.max(dp[i-1][0],dp[i-1][0]+nums[i]);
            //但是必然如果前一个房间不偷这个房间偷，这个房间偷的金额一定比前一个房间不偷的金额大
            dp[i][1] = dp[i-1][0]+nums[i];
        }
        i--;
        return Math.max(dp[i][0],dp[i][1]);
    }
}

同样的，滚动数组压缩成两个的写法

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

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

今日每日一题

先按照题面说明来一版直接计算比较的

public class Solution{
    public String findLongestWord(String s, List<String> dictionary) {
        String str = "";
        int deleteCount;
        for (String s1 : dictionary) {
            deleteCount = deleteCount(s,s1);
            if(deleteCount >=0){
                if (s1.length() > str.length()){
                    str = s1;
                }else if (s1.length() == str.length()){
                    str = dictionaryCompare(s1,str)>0? s1:str;
                }
            }
        }
        return str;
    }


    /**
     * 从字符串  asdfgh 删除字母变成  sf
     * @param a
     * @param b
     * @return
     */
    public int deleteCount(String a ,String b){
        int count = 0;
        //i表示a上的指针，j表示b上的指针
        int i = 0,j = 0;
        while (i< a.length() && j < b.length()){
            if (a.charAt(i)==b.charAt(j)){
                j++;
                count++;
                if (count == b.length()){
                    break;
                }
            }
            i++;
        }
        if (count == b.length()){
            return a.length()-count;
        }
        return Integer.MIN_VALUE;
    }


    public int dictionaryCompare(String a, String b){
        int i = 0;
        while (i < a.length()){
            if (a.charAt(i) == b.charAt(i)){
                i++;
            }else{
                if (a.charAt(i) > b.charAt(i)){
                    return -1;
                }
                return 1;
            }
        }
        return 0;
    }
}

deleteCount函数计算从一个字符串中能否通过删除字母得到另一个字符串，如果可以则返回需要删除的字符个数，不能则返回一个负数。dictionaryCompare用来比较两个字符串的字典排序，逐个字符进行对比，相等则返回0，不等则根据比较情况返回1或者-1。

题面要求，找出字典里的最长字符串，可以试试先讲字典数组排序，修改主函数为如下

public String findLongestWord(String s, List<String> dictionary) {
    String str = "";
    int deleteCount;
    dictionary.sort(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.length()-o1.length();
        }
    });
    for (String s1 : dictionary) {
        deleteCount = deleteCount(s,s1);
        if(deleteCount >=0){
            if (str.length()==0){
                str = s1;
            }else if (s1.length() == str.length()){
                str = dictionaryCompare(s1,str)>0? s1:str;
            }else{
                break;
            }
        }
    }
    return str;
}

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 10⁹

先整个简单的直接dfs，在超时的边缘不断试探

class Solution {
    int max;
    int count = 1;
    public int findIntegers(int n) {
        max = n;
        dfs(1);
        return count;
    }

    public void dfs(int n){
        if(n > max)return;
        count++;
        if((n & 1)==1){
            dfs(n<<1);
        }else{
            dfs(n<<1);
            dfs((n<<1)+1);
        }
    }
}

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 互不相同

9月13日 今天的每日一题

就，摁解，遍历求解每一个点，和其他点距离相同的个数，比如有点的几个【P1,P2,P3,P4】，从P1开始，算出P1与所有点的距离情况，并统计出距离相同的情况个数。

假设有3个连线的距离相等，这3条线为L1（P1，P2）,L2（P1，P3）,L3（P1，P4）,则这三条线仍然有不同的组合可能，（L1，L2）、（L1、L3）、（L2、L4），已知公式两两组合的可能性个数为n*（n-1）/2，又因为题面中提出了有顺序不同，可以反向也算一种，那么就可以把底部的除2约掉

则统计出有n条长度相同的线的话就可以得到 有n*（n-1）种可能组合

代码

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        final int[] count = {0};
        int[] point1,point2;
        for (int i = 0; i < points.length; i++) {
            point1 = points[i];
            hashMap.clear();
            for (int j = 0; j < points.length; j++) {
                if (i==j)continue;
                point2 = points[j];
                int distance = (point1[0]-point2[0])*(point1[0]-point2[0]) + (point1[1]-point2[1])*(point1[1]-point2[1]);
                hashMap.put(distance,hashMap.getOrDefault(distance,0)+1);
            }
            hashMap.forEach((key, value) -> {
                if (value > 1) {
                    count[0] += value * (value - 1);
                }
            });
        }
        return count[0];
    }
}

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题解

常见的求数组区间合的话，那么最先想到的就还是前缀和数组。

那么遍历这个前缀和数组途中，以第n位结束的前缀和减去n位置之前最小的一个前缀和就代表的是这个以n位置结束的区间合能取到的最大值。

接下来当移动到n+1位的时候，n+1位的值和只要和之前n位的时候取到的n位之前最小的前缀和相比较，得到较小的一个就是此时之前最小的前缀和了。

class Solution {
    public int maxSubArray(int[] nums) {
        int i = 1;
        for (; i < nums.length; i++) {
            nums[i] = nums[i] + nums[i-1];
        }
        int max = nums[0];
        int beforMin = 0;
        for (i = 0; i < nums.length; i++) {
            max = Math.max(max,nums[i]-beforMin);
            beforMin = Math.min(nums[i],beforMin);
        }

        return max;
    }
}

本质还是动态规划没毛病，在n+1位置的时候的判断取值，依赖于之前在n位置的时候取到的值和当前n+1位置取到的值的逻辑判断结果。