561. 数组拆分 I

思路：排序数组，然后首尾组队

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var arrayPairSum = function(nums) {
  6.   const len = nums.length / 2;
  7.   nums.sort((a, b) => a - b);
  8.   let sum = 0;
  9.   for (let i = 0; i < len; i++) {
  10.     sum += nums[i << 1];
  11.   }
  12.   return sum;
  13. };

410. 分割数组的最大值

思路：二分答案

分割的方案的上界是数组的和，下界是最大元素值，在这个范围内二分，并校验分割后的数组长度是否为m。
要点：
1、二分的区间选择
2、校验时，计算分割量循环后，也要检测是否有剩余，有，则校验结果+1

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} m
  4.  * @return {number}
  5.  */
  6. var splitArray = function(nums, m) {
  7.   const sum = _.reduce(nums, (r, v) => r += v, 0);
  8.   let l = _.max(nums), r = sum;
  9.   while (l <= r) {
  10.     // sum和
  11.     let mid = l + ((r - l) >>> 1);
  12.     let t = 0; s = -1;
  14.     for (let i = 0; i < nums.length; i++) {
  15.       s = s === -1 ? nums[i] : (s + nums[i]);
  16.       if (s > mid) {
  17.         s = -1;
  18.         s = nums[i];
  19.         t++;
  20.       }
  21.     }
  22.     if (s != -1 && s !== 0) {
  23.       t++;
  24.     }
  26.     if (t > m) {
  27.       l = mid + 1;
  28.     } else {
  29.       r = mid - 1;
  30.     }
  31.   }
  32.   return l;
  33. };

670. 最大交换

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function(num) {
  let s = [], i = 0, maxs=[], max = -1, maxIndex = -1;
  while (num > 0) {
    const last = num % 10;
    s.unshift(last);
    if (last > max) {
      max = last;
      maxIndex = i;
    }
    i += 1;
    maxs.unshift(maxIndex);
    num = (num - last)/10;
  }

  for (let i = 0; i < s.length; i ++) {
    const top = s[i];
    let maxIndex= s.length - maxs[i] - 1;
    if (s[maxIndex] > top) {
      s[i] = s[maxIndex];
      s[maxIndex] = top;
      break;
    }
  }
  return s.join('');
};

解法二: 扫描
题意是将num各位上大的数交换到高位，因为只能交换一次，所以题目的本质————找到尽可能高位的一个数，该数满足其右边的低位的最大值比其大，将这两个数交换即可，如果有多位为最大值，取最低位。

例1：2 7 3 6

满足条件的最高位为千位，比其右侧的最大值(百位)小，交换得到7 2 3 6

例2：9 8 5 6 8

满足条件的最高位为百位，比其右侧的最大值(个位)小，交换得到9 8 8 6 5

例3：8 9 5 6 9
满足条件的最高位为万位，比其右侧的最大值(千位和个位)小，取低位的个位交换得 9 9 5 6 8

作者：zdx-4n
链接：https://leetcode-cn.com/problems/maximum-swap/solution/onsuan-fa-si-lu-ben-zhi-jiu-shi-zhao-dao-hplc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int maximumSwap(int num) {
        int n = num, max = 0, maxloc = 0, high = 0, low = 0, i = 0, t;  // high记录高位，low记录低位，i记录当前位数，t记录当前可交换的高位与低位之差
        while(n > 0){
            if(n % 10 > max){           //如果当前位比之前记录的最大值大，则更新最大值和最大值下标
                max = n % 10;
                maxloc = i;
            }
            else if(n % 10 < max){      //如果当前位比最大值小，则说明该位可与最大值位进行替换，对变量进行更新
                t = max - n%10;         
                low = maxloc;           // 低位即max的位数maxloc
                high = i;               // 高位即当前被替换位i
            }
            n /= 10;
            ++i;
        }
        return num + t*pow(10, high) - t*pow(10, low);
    }
};

763. 划分字母区间

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
  const r = new Array(26), base = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - base;
    r[c] = r[c] || [s.length, -1];
    r[c] = [Math.min(i, r[c][0]), Math.max(i, r[c][1])];
  }

  r.sort((a, b) => a[0] - b[0]);
  const ans = [r[0]];
  for(let i = 1; i < r.length; i++) {
    const top = ans[ans.length - 1];
    const current = r[i];
    if (current) {
      if (current[0] < top[1]) {
        // top[0] = Math.min(top[0], current[0]);
        top[1] = Math.max(top[1], current[1]);
      } else {
        ans.push(current);
      }
    }
  }
  return ans.map(a => (a[1] - a[0] + 1));
};

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
  let r = new Array(26), base = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - base;
    r[c] = r[c] || [s.length, -1];
    r[c] = [Math.min(i, r[c][0]), Math.max(i, r[c][1])];
  }

  r = r.filter(Boolean).sort((a, b) => a[0] - b[0]);
  const ans = [r[0]];
  for (let i = 1; i < r.length; i++) {
    const top = ans[ans.length - 1];
    if (r[i][0] > top[1]) {
      ans.push(r[i]);
      continue;
    }
    if (top[1] < r[i][1]) {
      top[1] = r[i][1];
    }
  }
  return ans.map(a => a[1]).map((a, index) => {
    if (index === 0) {
      return a + 1;
    } else {
      return a - ans[index - 1][1];
    }
  });
};

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
  let r = new Array(26).fill(0), base = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - base;
    r[c] = Math.max(i, r[c]);
  }

  let ans = [], left = 0, right = 0;
  for (let i = 0; i < s.length; i++) {
    right = Math.max(right, r[s.charCodeAt(i) - base]);
    if (i === right) {
      ans.push(right - left + 1);
      left = i + 1;
    }
  }
  return ans;
};

1024. 视频拼接

/**
 * @param {number[][]} clips
 * @param {number} time
 * @return {number}
 */
var videoStitching = function(clips, time) {
  clips.sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    }
    return b[1] - a[1];
  });

  const s = [clips[0]];
  for (let i = 1; i < clips.length; i++) {
    const top = s[s.length - 1];
    const cur = clips[i];
    if (cur[1] <= top[1] ) {
      continue;
    }
    if (top[1] < time) {
      if (s.length >= 2 && cur[0] <= s[s.length - 2][1]) {
        s.pop();
      }
      s.push(cur);
    } else {
      break;
    }
  }
  let counts = new Set();
  for (let i = 0; i < s.length; i++) {
    for (let j = s[i][0]; j < Math.min(time, s[i][1]); j++) {
      if (!counts.has(j)) counts.add(j);
    }
  }
  return counts.size === time ? s.length : -1;
};