leetcode 238 & leetcode 152 & leetcode 228

lc238 Product of Array Except Self

遍历两次数组用一个res[] 记录答案

1）第一次，从左往右遍历 res[i] 记录0~i-1的乘积

2）第二次，从右往左遍历 res[i] *= right right *= nums[i]

　　注意两者顺序，right初值为1，更新步骤一定要在res[i]乘完之后，因为res *= right的目的是补上i+1~j这一部分的乘积，而不是i~j。

 class Solution {

     public int[] productExceptSelf(int[] nums) {

         if(nums == null || nums.length < 2)

             return nums;

         int len = nums.length;

         int[] res = new int[len];

         res[0] = 1;

         for(int i=1; i<len; i++){

             res[i] = res[i-1] * nums[i-1];

         }

         int right = 1;

         for(int i=len-1; i>=0; i--){

             res[i] *= right;

             right *= nums[i];

         }

         return res;

     }

 }

lc152 Maximum Product Subarray

本质上还是一个dp，dp[i] = Math.max(dp[i-1]*i, i)，然后用一个res记录所有dp里的最大值。

不过因为是乘法所以要考虑正负性的问题，可能负负得正，min乘完i反而是max

有两种解决方案

1）记录每次i的max和min乘积，若nums[i] 为负，则交换max和min，因为max*nums[i] 肯定为负，不如试一试min*nums[i]。

intuitive是min其实记录的yes负数里的“最大值“ （例如-982 < -32 --> 982 > 32），此时我们只要乘以一个负数，min*i有可能是最大值

 class Solution {

     public int maxProduct(int[] nums) {

         if(nums == null || nums.length == 0)

             return 0;

         int len = nums.length;

         int res = nums[0];

         int max = res, min = res;

         for(int i=1; i<len; ++i){

             if(nums[i] < 0){

                 int tmp = max;

                 max = min;

                 min = tmp;

             }

             max = Math.max(nums[i], max*nums[i]);

             min = Math.min(nums[i], min*nums[i]);

             res = Math.max(res, max);

         }

         return res;

     }

2）在写max和min更新方程的时候，考虑正负性，1）中分析了，min*i可能是最大值，同理max*i也可能是最小值，所以我们的更新方程应该写成：

max = Math.max(nums[i], Math.max(max*nums[i]), min*nums[i]);

min = Math.min(nums[i], Math.min(min*nums[i], man*nums[i]));

lc228 Summary Ranges

1）观察这个数组，由于是有序且不重复的，这些差值为1的元素，他们与index的差值也是相同的 index: 0 1 2 3 4 5 6 nums: 2 4 5 7 8 9 12 差值: 2 3 3 4 4 4 6 我们可以通过这个规律来解决这个问题

2）另一种更直观的想法就是：检查nums[i+1] – nums[i]是否 == 1 一个for循环，里面套一个while， while里面判断i+1和i的差值是否为1，为1就i++，否则停止

若更新了，那么原来的nums[i]肯定与现在的不同，所以我们for里第一句用一个tmp存储原来的nums[i] while之后，

若tmp ！= nums[i]，说明tmp ~ nums[i]之间有多个连续的元素，为什么能肯定是多个？因为while的判断条件，没有多个，i不变，tmp == nums[i]，然后for进行下一次循环。

若tmp == nums[i], 说明tmp这个元素单独成一组

 class Solution {

     public List<String> summaryRanges(int[] nums) {

         if(nums == null || nums.length == 0){

             List<String> res = new ArrayList<>();

             return res;

         }

         int len = nums.length;

         List<String> res = new ArrayList<>();

         if(len == 1){

             res.add(nums[0] + "");

             return res;

         }

         for(int i=0; i<len; i++){

             int tmp = nums[i];

             while(i+1 < len && nums[i+1] - nums[i] == 1){

                 i++;

             }

             if(tmp != nums[i]){

                 res.add(tmp+"->"+nums[i]);

             }else

                 res.add(tmp+"");

         }

         return res;

     }

 }

巴特西

leetcode 238 & leetcode 152 & leetcode 228

最新文章

热门文章