【5】最长回文串
重点回顾题
题外话：可能是以前参加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};【8】字符串转换整数（atoi）
本题需要注意有符号和无符号，还有存储范围,按照程序化一步步操作就好
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; }};【11】 盛最多水的容器
初看，转换成数学题，是求最大面积，所以又是一道动态规划题
看了官方题解的思路，双指针法是最优解法
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;};【238】除自身以外数组的乘积
看上去不难，但是有额外要求 :不要使用除法，且在 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};【78】子集
给定一组不含重复元素的整数数组 _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;};小结：果然上了中等难度后，就真的开始变难了，好久不碰算法，记忆都模糊了，加油~