[关闭]
@thousfeet 2018-02-20T22:04:05.000000Z 字数 4860 阅读 1010

来刷题啊 2.20

LeetCode

easy

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is 2, its length is 1.

Note: Length of the array will not exceed 10,000.

【思路】
一道签到题我打了有20分钟...orz
先是被数组长度为1的时候wa样例，于是特判了一下长度，然后是最后末尾段没有一个递减的数会出错，于是又特判了一下i+1 == numsSize-1的时候- -..真是打得丑...

【代码】

  1. int findLengthOfLCIS(int* nums, int numsSize) {
  3.     if(numsSize == 1) return 1;
  5.     int res = 0;
  6.     int len = 1;
  7.     for(int i = 0; i < numsSize-1; i++)
  8.     {
  9.         if(nums[i+1] > nums[i])
  10.         {
  11.             len++;
  12.             if(i+1 == numsSize-1) res = max(res,len);
  13.         } 
  14.         else
  15.         {
  16.             res = max(res,len);
  17.             len = 1;
  18.         } 
  19.     }
  20.     return res;
  21. }

665. Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

又是一道打了半小时的签到题...哇，老漏边界条件也是没谁了...

【思路】
遍历数组，递增得好好的遇到一个递减的就count++，出现2个或以上就GG，如果只有一个递减的point还有救，要不就扔掉这个point（但point+1的数值得比point-1大），要不就扔掉point-1（但point得比point-2大），然后再考虑下边界，前一种情况如果point是最后一个值可以直接扔，后一种如果point-1是第一个值可以直接扔（想象这串数字的最起始是个很小很小的值，最末端是个很大很大的值）。
然后愉快的wa掉了压根没point的情况（

【代码】

  1. bool checkPossibility(int* nums, int numsSize) {
  2.     if(numsSize == 1) return true;
  4.     int point = -1;
  5.     int count = 0;
  6.     for(int i = 1; i < numsSize; i++)
  7.     {
  8.         if(nums[i] < nums[i-1])
  9.         {
  10.             count++;
  11.             if(count >= 2) return false;
  12.             point = i;
  13.         }
  14.     }
  15.     if(point == -1 || point == numsSize-1 || nums[point+1] >= nums[point-1] || point == 1 || nums[point] >= nums[point-2]) return true;
  16.     return false;
  17. }

medium

713. Subarray Product Less Than K

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], 5, 2, 6, [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:
0 < nums.length <= 50000.
0 < nums[i] < 1000.
0 <= k < 10^6.

被k=0和1的边界情况卡了三个wa- -...

【思路】
因为子序列连续，所以还是滑动窗口那样的捡一个扔一个。只要窗口内的乘积不会 >= k，就继续乘nums[i]，如果超过了，就从begin处开始扔，一直扔到 < k 结束。
这时候，在这个窗口中，所有以 i 位置结尾的子序列都是一个可行解，共有 i-begin+1 个。如example1里面，当i = 3时，窗口为[5,2,6]，以 6 结尾的可行解有6，[2,6]，[5,2,6]这三个。（只要能想到这一点其他都不是事，我没想到，是偷瞄的orz）
因此就这样捡一捡扔一扔，找到所有可行的窗口，全部累加就好了。

然后就是要注意一下k=0和1的情况，直接return 0就好了，因为任何正整数相乘都不可能得到一个小于0或1的数。

（我一开始一直在想找到最大可行窗口，然后整个窗口中的所有子序列个数是(1+n)*n/2，但是这样避免不了重叠问题....以 i 结尾的一组子序列为划分集，真是妙啊）

【代码】

  1. int numSubarrayProductLessThanK(int* nums, int numsSize, int k) {
  2.     int mul = 1;
  3.     int count = 0;
  4.     int begin = 0;
  6.     if(k <= 1) return 0;
  8.     for(int i = 0; i < numsSize; i++)
  9.     {
  10.         mul *= nums[i];
  11.         while(mul >= k) mul /= nums[begin++];
  12.         count += i-begin+1;
  13.     }
  14.     return count;
  15. }

670. Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

The given number is in the range [0, 108]

【思路】
三秒签到题。
题意就是要尽量把越大的越往前摆。所以 sort 一下从大到小排序，然后和原来的 num 从高位到低位一一比较，如果不是排序后应在那个位置上的数，就找到越末尾的那个的数，swap 一下。

【代码】

  1. int a[100000007]; 
  2. int cmp(const void* a, const void* b){
  3.   return *(int*)a - *(int*)b;
  4. } 
  6. int maximumSwap(int num) {
  7.     int len = 0; 
  8.     while(num)
  9.     {
  10.         a[len++] = num%10;
  11.         num /= 10;
  12.     }
  14.     int b[len];
  15.     for(int i = len-1; i >= 0; i--)
  16.         b[i] = a[i];
  17.     qsort(b,len,sizeof(int),cmp);
  19.     int k;
  20.     for(k = len-1; k >= 0; k--)
  21.         if(b[k] != a[k]) 
  22.         {
  23.             for(int i = 0; i < len; i++)
  24.             {
  25.                 if(a[i] == b[k]) 
  26.                 {
  27.                     int tmp = a[i];
  28.                     a[i] = a[k];
  29.                     a[k] = tmp;
  30.                 }
  31.             }
  32.             break;
  33.         }
  36.     int res = 0;
  37.     for(int i = len-1; i >= 0; i--)
  38.     {
  39.         res *= 10;
  40.         res += a[i];
  41.     }
  43.     return res;
  44. }

hard

128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这题面还真是有个性2333
想了半天除了sort一下遍历（O(nlogn)），或者开一个数组桶排序那样的，存在一个a就map[a]=1，然后遍历，可是没给数据范围...

【思路】
看到这个题解，真tm强 My really simple Java O(n) solution - Accepted
用的是hashmap（put和get都是O(1)）。方法是在序列的边界上，保存序列的长度。比如如果存在这样的序列：{1, 2, 3, 4, 5}, 那么 map.get(1) 或 map.get(5) 都应该返回 5。

考虑一个新的数 n 加入进来，如果 n-1 和 n+1 存在的话，那太好了可以凑进去变成一个更长的序列，长度为 map.get(n - 1) + map.get(n + 1) + 1。把 n 加入map，并且把这个长序列的边界更新成新的长度：

  1.     for (int n : num) {
  2.         if (!map.containsKey(n)) {
  3.             int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
  4.             int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
  5.             // sum: length of the sequence n is in
  6.             int sum = left + right + 1;
  7.             map.put(n, sum);
  9.             // keep track of the max length 
  10.             res = Math.max(res, sum);
  12.             // extend the length to the boundary(s) of the sequence
  13.             // will do nothing if n has no neighbors
  14.             map.put(n - left, sum);
  15.             map.put(n + right, sum);
  16.         }
  17.         else {
  18.             // duplicates
  19.             continue;
  20.         }
  21.     }

开始没看懂为什么只更新边界（序列内部位置的值是没意义的）。想了想似乎不更新序列内部也确实没关系，因为如果会要get序列内部的某个位置，那说明这个数必然是序列内的数，但是既然都形成序列了，内部的数值必然在之前已经加入过了，而遇到一个之前加入过的数是直接continue的，只有遇到非已有序列的新数才会有动作，也就是n-1、n+1只可能是别的序列的边界，或不是序列。

真是妙啊...

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注