算法练习笔记（六）

② 除自身以外数组的乘积

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self

思路：

参考：https://leetcode-cn.com/problems/product-of-array-except-self/solution/output-shu-zu-cheng-dan-liang-chong-jiao-se-yi-ci-/

代码：

var productExceptSelf = function(nums) {
    const len = nums.length
    const res = []
    //数组第一项没有左边积，初始化为1
    res[0] = 1
    //从左遍历，每个元素的左边积保存到结果数组
    for(let i=1;i=0;i--){
        res[i] *=temp
        temp *= nums[i]
    }
    //返回结果数组
    return res
};

11.16

①搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

思路：

参考：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/240sou-suo-er-wei-ju-zhen-tong-guo-cong-9mc0k/

代码：

var searchMatrix = function(matrix, target) {
    let m = matrix.length,n=matrix[0].length
    //定义左下角坐标
    let x=m-1,y=0
    while(x>=0&&ytarget){
            x--
        }else{
        //比目标值小应往右走
            y++
        }
    }
    return false
};

②寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3：

输入：nums = [1,1]
输出：1

示例 4：

输入：nums = [1,1,2]
输出：1

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number

思路：

参考：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/zhe-ge-shu-zu-you-dian-te-shu-suo-yi-ke-yi-yong-ku/

代码：

var findDuplicate = function(nums) {
    //定义最大区间[1,n]
    let left = 1,right = nums.length-1,mid
    while(left>1
        let count = 0
        //查找比mid小的元素
        for(let i=0;imid){
            right = mid
        }else{
            left = mid+1
        }
    }
    return left
};

11.17

①生命游戏

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/game-of-life

思路：

参考：https://leetcode-cn.com/problems/game-of-life/solution/289-sheng-ming-you-xi-zhong-xin-ding-yi-gg3ld/

代码：

var gameOfLife = function(board){
	const m = board.length,n=board[0].length
	//遍历加一，用于取负方便
	for(let i=0;i3))||(board[r][c]===1&&num===3)){
			//活细胞死亡或者死细胞复活，反转正负
			board[r][c]=-board[r][c]
		}
}

②摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

提示：

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wiggle-sort-ii

思路：

深拷贝数组并按升序排序。遍历原数组，将原数组奇数位元素变为新数组的大数，偶数位为新数组的小数，这样就可以达到nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

代码：

var wiggleSort = function(nums) {
    const sortNums = nums.slice().sort((a,b)=>a-b)
    //mid指向新数组的小数，r指向新数组的大数
    let r = nums.length,mid = Math.floor((nums.length+1)/2)
    for(let l=0;l

var increasingTriplet = function(nums){
	//假设min为数组第一位，mid为无穷大
	let min = nums[0],mid = Infinity
	for(let i=1;imid) return true
        //根据条件更新min或者mid
		nums[i]<=min?min=nums[i]:mid=nums[i]
	}
    return false
}

var topKFrequent = function(nums,k){
	const map = new Map()
	//使用map记录数组中每个元素出现的频率
	for(let num of nums){
		if(map.has(num)){
			let count = map.get(num)+1
			map.set(num,count)
		}else{
			map.set(num,1)
		}
	}
	const res = []
	for(let [key,val] of map){
		res.push({key,val})
	}
	//将对象数组按照频率排序
    res.sort((a,b)=>b.val-a.val)
    //返回前k个高频元素
    return res.slice(0,k).map((item)=>{
        return item.key
    })
}

const countInMatrix = function(matrix,midVal){
	const n = matrix.length
	let count = 0
	//从第一行最右元素开始比较
	let row = 0
	let col = n-1
	while(row=0){
		if(midVal>=matrix[row][col]){//大于等于当前行的最右元素
			count += col+1 			//统计个数
			row++          			//进入下一行
		}else{
			//否则留在当前行，继续和左边元素比较
			col--
		}
	}
	return count
}
const kthSmallest = function(matrix,k){
	const n = matrix.length
	//初始化值域范围
	let low = matrix[0][0]
	let high = matrix[n-1][n-1]
	while(low<=high){
		//计算中间值
		let midVal = low+((high-low)>>>1)
		//统计矩阵中不大于中间值的元素个数
		let count = countInMatrix(matrix,midVal)
		if(count

var RandomizedSet = function() {
    //数值保存在动态数组中
    this.nums = []
    //哈希表存储每个数值及其在数值nums的下标
    this.map = new Map()
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.map.has(val)){
        return false
    }
    this.map.set(val,this.nums.length)
    this.nums.push(val)
    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.map.has(val)){
        //获取被删元素在数组中的索引
        const len = this.nums.length
        const index = this.map.get(val)
        //用数组末位元素覆盖被删元素，并更新其索引值
        this.map.set(this.nums[len-1],index)
        this.nums[index] = this.nums[len-1]
        //删除元素
        this.nums.pop()
        this.map.delete(val)
        return true
    }
    return false
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    //得到随机索引
    const randomNumber = parseInt(Math.random()*this.nums.length)
    return this.nums[randomNumber]
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

/**
 * @param {number[]} nums
 */
var Solution = function(nums) {
    this.nums = nums
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function() {
    return this.nums
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
    //浅拷贝复制
    const nums = this.nums.slice()
    for(let i=0;i

var fourSumCount = function(nums1,nums2,nums3,nums4){
	const map = new Map();
	let count = 0;
	for(let a of nums1){
		for(let b of nums2){
			let res = a+b;
			map.has(res)?map.set(res,map.get(res)+1):map.set(res,1);
		}
	}
	for(let c of nums3){
		for(let d of nums4){
			let res = -(c+d);
			if(map.has(res)){
				count += map.get(res);
			}
		}
	}
	return count
}