剑指 Offer 39. 数组中出现次数超过一半的数字

该题因为涉及到计数问题，所以一定是可以用哈希表解决的。

优化方法是使用摩尔投票法，

我们假设当前的数即为众数并且权重加一，之后如果不相等则权重减一，权重为0时重新定义当前数为众数，重复前面的操作。因为众数的个数是大于数组的一半的，所以无论怎么去操作，最后权重一定是大于0的，一定可以找到众数。

/*** @param {number[]} nums* @return {number}*/
var majorityElement = function(nums) {var vote = 0,x;for(var i of nums){if(vote == 0)x = i;if(x == i)vote+=1;else vote-=1;}return x;
};

使用了常数变量来存储结果，空间复杂度为1，而哈希表为n

剑指 Offer 66. 构建乘积数组

该题不允许使用除法除以当前的数来获取其他数的乘积，如果使用暴力方法时间复杂度为0

(n)，不会ac。

构建两个乘积数组，一个是left表示当前下标为i的左边所有数的乘积，right为右边所有数的乘积。

最开始时建立两个数组，利用fill方法赋值每一位为1，之后利用两次循环来计算两个数组的值，left从第二位开始（因为第一位就是计算右边所有的值，其left应为1），计算公式为left[i]=left[i-1]*a[i-1]，之后右边相反计算即可。

最后再进行一次循环左右乘积来获取最终结果。

code：

/*** @param {number[]} a* @return {number[]}*/
var constructArr = function(a) {var left = new Array(a.length).fill(1);var right = new Array(a.length).fill(1);for(var i = 1;i<a.length;i++){left[i] = left[i-1]*a[i-1];}for(var i = a.length-2;i>=0;i--){right[i] = right[i+1]*a[i+1];}var res = new Array(a.length);for(var i=0;i<a.length;i++){res[i] = left[i]*right[i];}return res;
};

剑指 Offer 14- I. 剪绳子

1：动态规划

状态定义：dp[i]表示i长的绳子所能实现的最大的剪绳子方法。

转移方程：dp[i] = Math.max(dp[i],(i-j)*j,j*dp[i-j]);dp[i]是为了寻找在剪不同的j的时候的最大值，i-j*j是为了防止有的绳子长度不需要与前面的dp产生联系，j*dp[i-j]是为了寻找剪去j长后与前面dp相×的最大值

初始状态：本题因为有i-j*j存在于转移方程当中，因此不需要赋值初始值，这本来就是计算初始不使用dp的值。

返回值：return dp[n]

code：

/*** @param {number} n* @return {number}*/
var cuttingRope = function(n) {var dp = new Array(n+1).fill(0);for(var i=2;i<n+1;i++){for(var j=0;j<i;j++){dp[i] = Math.max(dp[i],(i-j)*j,j*dp[i-j]);}}return dp[n];
};

时间复杂度空间复杂度均为n

2：贪心解法

我们根据规律寻找可以发现，我们可以尽力去剪长度为3的绳子，而在剪三过后如果有剩余的4就分割为2x2，如果不能剩余4则×剩余的数，此时为最大的解决方案。

code:

/*** @param {number} n* @return {number}*/
var cuttingRope = function(n) {var res = 1;if(n == 2)return 1;else if(n==3)return 2;else if(n==4)return 4;else{while(n>4){n-=3;res*=3;}if(n==4)return res*4;return res*n;}
};

剑指 Offer 57 - II. 和为s的连续正数序列

图片转自：力扣 

 由图可以看出清晰的步骤，初始时定义i=1，j=2，s=i+j，利用这三个数来进行数组中的滑动窗口，

最开始时是1,2，如果小于目标值后，j的值增加1，s的值增加j，这样就是i到j之间的所有整数相加

如果大于目标值的情况下，需要减小i，过程是先减小当前的i值，让窗口中的数组左边向右移动一位，然后i的值增加1

如果等于则进行添加结果，并且此处操作大于目标值的情况进行的操作。

观察可以发现算法是永远先寻找数组最长的，最后i>j跳出循环。

code：

/*** @param {number} target* @return {number[][]}*/
var findContinuousSequence = function(target) {var res = [];var i=1,j=2,s=3;while(i<j){if(s == target){var res1 = []for(var temp = i;temp<=j;temp++){res1.push(temp);}res.push(res1);}if(s >= target){s-=i;i++;}else{j++;s+=j;}}return res;
};

滑动窗口的算法框架：

let left = 0, right = 0;while (right < s.size()) {`// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left++;}
}作者：gang-feng
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/song-gei-qian-duan-tong-xue-tong-su-yi-d-u7z9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。