中等

使用方法

无重复字符的最长字串—滑动窗口

给定一个字符串s，找出其中不含有重复字符的最长字串的长度。（连续的）

  1. int lengthOfLongestSubstring(char * s){
  2.     int res = 0;
  3.     int len = strlen(s);
  4.     /* 存储 ASCII 字符在子串中出现的次数 */
  5.     int freq[256] = {0};  
  6.     /* 定义滑动窗口为 s[l...r] */
  7.     int l = 0, r = -1; 
  8.     while (l < len) {
  9.         /* freq 中不存在该字符，右边界右移，并将该字符出现的次数记录在 freq 中 */
  10.         if (r < len - 1 && freq[s[r + 1]] == 0) {
  11.             freq[s[++r]]++;
  12.         /* 右边界无法拓展，左边界右移，刨除重复元素，并将此时左边界对应的字符出现的次数在 freq 的记录中减一 */
  13.         } else {
  14.             freq[s[l++]]--;
  15.         }
  16.         /* 当前子串的长度和已找到的最长子串的长度取最大值 */
  17.         res = fmax(res, r - l + 1);
  18.     }
  20.     return res;
  21. }
  • 滑动窗口，“窗口”内存的数子串不一定是按照原字符串那样存
  • strlen(str)，求字符串的长度
  • 字符作为数组下标，可
  • fmax(a, b)，求出两个数的最大值

正则匹配—动态规划

image.png

注意，’‘匹配的意思是：前面的那个字母被匹配的次数是0次或多次，而不是自己匹配的，要与前面的一个字母一起匹配。’.*’可以匹配任意字符串

使用动态规划，定义一个状态存储器dp[][]，dp[i][j]表示的是s[i]与p[j]的匹配情况，与其前面的匹配情况有关。再定义状态转移方程。m为s的长度，n为p的长度，则sp[m][n]表示最终的匹配结果。
image.png

此外，为了考虑边界情况，令dp的规模为[m+1][n+1]，设dp[0][0]为true，即两个长度为0时是匹配的，然后按照上图给dp赋值时，都要给dp的i与j加一，最后dp[m+1][n+1]表示最后结果。 又，单独考虑dp的第零行的情况，如果p[j]==’‘，则dp[0][j+1]=dp[0][j-1]，就考虑成，s为空时，p有字母与’‘，然后 *将其前的字母匹配0次。

  1. /**
  2. * @param {string} s
  3. * @param {string} p
  4. * @return {boolean}
  5. */
  6. var isMatch = function(s, p) {
  7.   // 动态规划
  8.   var m = s.length, n = p.length;
  9.   var dp = [];
  10.   for (let i in [...Array(m+1).keys()]){
  11.     dp[i] = [];
  12.     for(let j in [...Array(n+1).keys()]){
  13.       dp[i][j] = false;
  14.     }
  15.   }
  16.   dp[0][0] = true;
  17.   for (let j = 0; j < n; j++){
  18.     if(p[j] === '*'){
  19.       dp[0][j+1] = dp[0][j-1];
  20.     }
  21.   }
  22.   for (let i = 0; i< m; i++){
  23.     for(let j = 0; j < n; j++){
  24.       if(s[i] === p[j] || p[j] === '.'){
  25.         dp[i+1][j+1] = dp[i][j];
  26.       }else if(s[i] !== p[j] && p[j] != '*'){
  27.         dp[i+1][j+1] = false;
  28.       }else if(p[j] === '*'){
  29.         if(s[i] === p[j-1] || p[j-1] === '.'){
  30.           dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1];
  31.         }else {
  32.           dp[i+1][j+1] = dp[i+1][j-1];
  33.         }
  34.       }
  35.     }
  36.   }
  37.   return dp[m][n];   // 最后是在上面跳出循环的结果
  38. };

盛最多水的容器—双指针

image.png
容积就是 两个数之间的距离 乘以 两者间较小的数值。
我自己写的代码：5%

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var maxArea = function(height) {
  6.     let ob = [], n = height.length, maxS = 0, tmp = 0;
  7.     for (let i = 0; i < n; i++){
  8.         ob[i] = {};
  9.         ob[i].ind = i;
  10.         ob[i].val = height[i];
  11.     }
  12.     ob.sort((x, y) => {
  13.         return y.val - x.val;
  14.     });
  15.     for (let i = 0 ; i < n-1; i++){
  16.         let ran = Math.pow(n, 0.6);
  17.         for (let j = i+1; j<n; j++){
  18.             if(ran <= 0) break;
  19.             tmp = (Math.abs(ob[i].ind - ob[j].ind)) * ob[j].val;
  20.             if(tmp > maxS){
  21.                 maxS = tmp;
  22.             }else ran--;
  23.         }
  24.     }
  25.     return maxS;
  26. };

解析的，用双指针，一个从数组左、一个从数组右开始，每次计算两个的容积，再向中间移动较小值处的指针。

三数之和 — 双指针

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
如：

  1. 输入：nums = [-1,0,1,2,-1,-4]
  2. 输出：[[-1,-1,2],[-1,0,1]]

我想的是，如下：

  1. /**
  2. * @param {number[]} nums
  3. * @return {number[][]}
  4. */
  5. var threeSum = function(nums) {
  6.   var results = [], flag = 0, rn = 0;
  7.   nums = nums.sort(sortNumber);
  8.   // 先排序，再去除多余的重复数字
  9.   for (var k = 0; k < nums.length-1; k++) {
  10.     flag = 0;
  11.     for (var m = k+1; m < nums.length; m++){
  12.       if (nums[k] == nums[m]) {
  13.         flag++;
  14.       }else {
  15.         if (flag > 2 && nums[k] == 0){
  16.           nums.splice(k+3, flag-2);flag = 0;
  17.           break;
  18.         }else if (flag > 1 && nums[k] != 0){
  19.           nums.splice(k+2, flag-1);flag = 0;
  20.           break;
  21.         }
  22.       }
  23.     }
  24.     // nums数组的最后有一些重复的数字
  25.     if (m == nums.length && flag > 1) {
  26.       if (nums[k] == 0 && flag > 2) {
  27.         nums.splice(k+3, flag-2);
  28.       }else if(nums[k] != 0) {
  29.         nums.splice(k+2, flag-1);
  30.       }
  31.     }
  32.   }
  33.   // 收集三元组
  34.   for (var k = 0; k < nums.length-2 && nums[k] <= 0; k++){
  35.     for (var i = k+1; i < nums.length-1; i++) {
  36.       for (var j = i+1; j < nums.length; j++) {
  37.         if (nums[i] + nums[k] + nums[j] === 0){
  38.           results[rn++] = [nums[k], nums[i], nums[j]].sort(sortNumber);
  39.           break;
  40.         }
  41.       }
  42.     }
  43.   }
  44.   results = results.sort(sortNumber);
  45.   // 去除掉重复的三元组
  46.   for (i = 0; i < results.length-1; i++) {
  47.     for (j = i+1; j < results.length; j++) {
  48.       flag = 0;
  49.       for (k = 0; k < 3; k++){
  50.         if (results[i][k] == results[j][k]){
  51.           flag++;
  52.         }
  53.       }
  54.       if(flag == 3) {
  55.         results.splice(j,1);
  56.         j--;   // 为什么不加这个就不能去掉最后一个子数组呢？
  57.       }
  58.     }
  59.   }
  60.   return results;
  61. };
  62. // 针对负数的排序
  63. function sortNumber(a, b) {
  64.   return a - b;
  65. }

题解：
image.png

最接近的三数之和 — 双指针

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。3<=n<=1000。
返回这三个数的和。
假定每组输入只存在恰好一个解。

我自己也想到了双指针，但是写的时候前面还好，中间有一个判断的地方没想到，想复杂了。下面是查看方法后改的，只在我写的基础上改了中间的if-else if -else

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var threeSumClosest = function(nums, target) {
  7.     if(nums.length < 3) return;
  8.     var res = nums[0] + nums[1] + nums[2], n = nums.length;
  9.     nums = nums.sort(sortNumber);  // 排序
  11.     for (var i = 0; i < n-2; i++){
  12.         var j = i+1, p = n-1;
  14.         while(j < p){
  15.             var tmp = nums[i] + nums[j] + nums[p];
  16.             var tmp_res = Math.abs(tmp-target);
  17.             if(tmp_res < Math.abs(res - target)){
  18.                 res = tmp;
  19.             } 
  21.             if(tmp > target)
  22.                 p--;
  23.             else if(tmp < target)
  24.                 j++;
  25.             else 
  26.                 return target            
  27.         }
  28.     }
  29.     return res;
  30. };
  31. function sortNumber(a, b) {
  32.   return a - b;
  33. }

时间复杂度 O(n2)

找规则

Z字形变换

实际是N字型变换，给定一个字符串s和一个行数numRows，以从上往下、从左往右进行N字形排列。
比如输入字符串PAYPALISHIRING行数为3，则排列如下：

  1. P   A   H   N
  2. A P L S I I G
  3. Y   I   R

则对应输出为PAHNAPLSIIGYIR，按每行输出。

实际是找字符串s中的每个字符的下标与排列中位置所在的行的关系

查看的一个解说才写出的代码：
image.png

  1. /**
  2. * @param {string} s
  3. * @param {number} numRows
  4. * @return {string}
  5. */
  6. var convert = function(s, numRows) {
  7.   let strings = [[]], f = 2*numRows-2;
  9.   if(numRows == 0) return '';
  10.   if(numRows == 1) return s;
  11.   for (let i = 0; i < s.length; i++){
  12.     let tmp = i % f;
  13.     if(i < numRows){
  14.       strings[i] = s[i];
  15.     }else {
  16.       if(tmp < numRows){
  17.         strings[tmp] += s[i];
  18.       } else {
  19.         strings[Math.abs(f-tmp)] += s[i];
  20.       }
  21.     }
  22.   }
  23.   let result = '';
  24.   for (let i of strings){
  25.     result += i;
  26.   }
  27.   return result;
  28. };