算法小日常03

2次阅读

共计 2380 个字符，预计需要花费 6 分钟才能阅读完成。

重点回顾题
题外话：可能是以前参加 ACM 比赛时，被一道需要利用动态规划的题绊住了，导致到现在为止，只要看到跟动态规划有关的题，就打怵?，这是留下了多大的阴影啊
假设当前判断的回文是从第 0 个字符，到第 4 个字符，那么就是推导 s[0] === s[4] && s[1-3] 是回文。
定义二维数组 dp，横坐标表示起始字符，纵坐标表示当前新加入字符，得到 dpi = s[i] === s[j] && dpi-1。
时间复杂度是 O(n*n/2)

var longestPalindrome = function(s) {if (s === '') return''
  
  let arr = s.split('')
  let dp = new Array(arr.length).fill([])
  for (let i = 0; i < dp.length; i++) {dp[i] = new Array(arr.length).fill(false)
  }

  let max = 1
  let maxStart = 0
  let maxEnd = 0
  
  for (let i = 0; i < arr.length; i++) {for (let j = 0; j <= i; j++) {if (i === j) {dp[i][j] = true
      }

      if (i - j === 1) {dp[i][j] = arr[i] === arr[j]
        if (dp[i][j] && max < 2) {
          max = 2
          maxStart = j
          maxEnd = i
        }
      }

      if (i - j > 1) {dp[i][j] = arr[i] === arr[j] && dp[i-1][j+1]
        const len = i - j + 1
        if (dp[i][j] && max < len) {
          max = len
          maxStart = j
          maxEnd = i
        }
      }
    }
  }
  
  let result = ''
  for (let i = maxStart; i <= maxEnd; i++) {result += arr[i]
  }
  return result
};

本题需要注意有符号和无符号，还有存储范围, 按照程序化一步步操作就好

var myAtoi = function (str) {const numreg = /^[0-9]*$/

    const num = str.trim()
    const result = parseInt(str) || 0


    if (isNaN(result)) {return 0;}
    if (num[0] == '-') {const min = Math.pow(-2, 31)
        return result < min ? min : result
    }
    else if (numreg.test(num[0]) || num[0] == '+') {// 开头是数字
        const max = Math.pow(2, 31) - 1
        return result > max ? max : result
    }
    else {return 0;}
};

也可以用 parseInt 来处理

var myAtoi = function(str) {str = str.trim();
    var max = Math.pow(2,31)-1;
    var min = -Math.pow(2,31);
    str = parseInt(str);
    if(str>=max){return max;}
    if(str<=min){return min;}
    if(isNaN(str)){return 0;}else{return str;}
};

初看，转换成数学题，是求最大面积，所以又是一道动态规划题
看了官方题解的思路，双指针法是最优解法

var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let max = 0;
    while(left < right) {const area = (right - left) * Math.min(height[right], height[left]);
        if (area > max) {max = area}
        if (height[left] < height[right]) {left++;} else {right--;}
    }
    return max;
};

看上去不难，但是有额外要求 :不要使用除法，且在 O(_n_) 时间复杂度
思路：记录每个元素左面所有元素的乘积（不包括自身）
右边的乘积不需要记录，直接和左面乘积相乘


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let v = 1
  let result=[1]
  for (let i = 1; i < nums.length; i++) {v *= nums[i - 1]
    result[i] = v
  }
   v = 1
  for (let i = nums.length - 1; i > 0; i--) {v *= nums[i]
    result[i - 1] *= v
  }
  return result
};

给定一组 不含重复元素 的整数数组 _nums_，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。
看到「子集」、「组合」这样的词语，首先想到回溯算法。
全排列：N!
组合：N!
子集：2^N，每个元素都可能存在或不存在。

var subsets = function(nums) {
    const n = nums.length;
    const result = [];
    if (nums.length < 1) return [[]];
    const backTrace = (arr, currentIndex) => {result.push(arr);
        if (currentIndex >= n) return;
        for (let i = currentIndex; i < n; ++i) {arr.push(nums[i]);
            backTrace(arr.slice(), i+1);
            arr.pop();}
    }
    backTrace([], 0);
    return result;
};

小结：果然上了中等难度后，就真的开始变难了，好久不碰算法，记忆都模糊了，加油~

正文完