剑指offer

用两个栈实现队列

入栈需要考虑stackA，但是一开始是空数组，一直在插入和删除，不需要考虑大小。

出栈需要考虑stackB，同时stackB的出栈需要依赖stackA的状态。

push进去不需要返回，pop出去需要返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var CQueue = function() {
    this.stackA = []
    this.stackB = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    **return** this.stackA.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(this.stackB.length) {
        return this.stackB.pop()
    }else {
        while(this.stackA.length) {
            this.stackB.push(this.stackA.pop())
        }
        if(!this.stackB.length) {
            return -1
        }else {
            return this.stackB.pop();
        }
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

30包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

用空间换时间，制造了一个minStack和Stack同Push同pop，不过push进去的的时候放入每次放入的最小值。这是时候栈从下到上，依次表示最小值，而且也表示这最小值变换的位置。

Infinity 正无穷大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var MinStack = function{
	this.stack = [];
	this.minStack = [Infinity];
}

MinStack.prototype.push(value){
	this.stack.push(value);
	this.minStack.push(Math.min(this.minStack[this.minStack.length - 1] , value))
}

MinStack.prototype.pop(){
	this.stack.pop()
	this.minStack.pop()
}

MinStack.prototype.top(){
	return this.stack[this.stack.length - 1]
}

MinStack.prototype.min(){
	return this.minStack[this.minStack.length - 1]
}

06从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

//利用了数组把链表的数据放进去，然后调用reverse()方法得到每个节点的值。

1
2
3
4
5
6
7
8
9
var reversePrint = function(head){
	if(head === null) return []
	const res = []
	while(head){
		res.push(head)
		 head = head.next;
	}
	return res.reverse()
}

//反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
function reverseLink(head){
	if(head === null || head.next === null) return head
	let p = head.next
    head.next = null
    let tmp = null
    while(p !== null){
    	tmp = p.next
    	p.next = head
    	head = p
    	p = tmp
    }
    return head
}

24反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

对于没有的值先赋值，最后两个操作肯定是要复位。

1
2
3
4
5
6
7
8
9
10
var reverseList = funtion(head){
	let pre = null
	let cur = head;
	while(cur){
		const tmp = cur.next
		cur.next = pre
		pre = cur
		cur = tmp
	}
}

35复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

使用map记录新节点，然后再来操作、把map中value设置为new Node很新奇，以后记得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function Node(val, next, random) {
   	this.val = val;
	this.next = next;
  	this.random = random;
 };
 
 var copyRandomList = function(head){
 	if(!head) return head
 	let map = new Map();
 	let node = head
 	while(node){
 		map.set(node , new Node(node.val))
 		node = node.next
 	}
 	node = head
 	while(node){
 		map.get(node).next = map.get(node.next) !== undefined ? map.get(node.next) : null
 		map.get(node).random = map.get(node.random)
 		node = node.next
 	}
 	return map.get(head)
 }

05替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

string split() join

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//分割
var replaceSpace = funtion(){
	s = s.split(' ').join('%20')
	return s
}
//正则
function replaceSpace(s: string): string{
	return s.replace(/\s/g,'%20')
}
//遍历
function replaceSpace(s:string):string{
	let result: string = ""
	for(let i of s){
		if(i === " ")
			result += '%20'
		else
			result += i
	}
	return result
}

58 II 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

string返回一个新的字符处啊你，并且不会改动原字符串 [)

1
2
3
4
5
var reverseLeftWords = function(s,n){
	let temp = s.slice(0,n)
	s = s.slice(n.s.length)
	return s + temp
}

查找（二分 或者 map）

03数组中重复的数字

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

（map）

map[c] === undefined也能查找这个数是不是在里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var findRepeatNumber = function(nums){
	let map = {};
	let ans = null;
	for(let i = 0, n = nums.length ; i < n ; i++){
		let c = nums[i];
		if(map[c] === undefined){
			map[c] = 1;
		}else{
			ans = c;
			break;
		}
	}
	return ans;
}

53I在排序数组中查找数字I

统计一个数字在排序数组中出现的次数。 示例中数组是有序的。

(二分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var search = function(nums,target){
	let count = 0,
		n = nums.length,
		left = 0,
		right = n - 1;
		while(left < right){
			mid = (left + right) >> 1;
			if(nums[mid] === target){
				left = mid;
				break;
			}else if(nums[mid] < target){
				left = mid + 1;
			}else{
				right = mid -1;
			}
		}
		if(nums[left] !== target) return 0;
		let copy = left - 1
		while(copy >= 0 && nums[copy] === target){
			copy--;
			count++
		}
		while(left < n && nums[left] === target){
			left++;
			count++;
		}
		return count;
}

53 II 0~n-1中确实的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
自己做的，题库没有
var missingNumber = function(nums) {
    for(let i = 0 , n = nums.length; i < n ; i++){
        if(i !== nums[i]){
            return i
        }
    }
    return nums.length
};

//二分法
var missingNumber = function(nums){
	let l = 0 , right = nums.length - 1;
	while( l <= r){
		let m = Math.floor( ( left + right ) / 2);
		if(nums[m] === m){
			l = m + 1;
		}else{
			r = m - 1;
		}
	}
	return l;
}

04 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Array.prototype.flat() 会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//写起来简单，但是复杂度高
var findNumberIn2DArray = function(matrix, target) {
    return matrix.flat(Infinity).includes(target)
};

//二分
var findNumberIn2DArray = function(martix ,target){
	for(const item of target){
		let left = 0,right = item.length - 1;
		while(left <= right){
			const mid = Math.floor((left + right ) / 2);
			if(item[mid] === target){
				return true
			}else if(item[mid] < target){
				left = mid + 1
			}else{
				right = mid - 1
			}
		}
	}
	return false;
}

11旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//投机
var minArray = function(numbers) {
  return Math.min(...numbers)
};
//二分法
//由于这个有序数组无论处理几次始终是一个环状结构，最小值要么在开头要么在最大值的后一个，当中点的值相等于右指针的值时，由于无法确定最小值在中点的左边还是右边，则直接将右指针左移一位缩小范围，到最后左右指针一定会在最小值的位置相遇
// targrt设置为右那个数。
var  minArray = function(numbers){
	let l = 0, right = numbers.length - 1;
    while(l < r){
		let mid = (l + r ) >> 1;
		if(numbers[mid] < numbers[r]){
			r = mid;
		}else if(numbers[mid] > numbers[r]){
			l = mid + 1;
		}else{
			r--;
		}
	}
	return numbers[l];
}

//查找第一个前者大于后者的数字，若没有则是位置为零的数字
var minArray = function(numbers){
	for(let i = 0 ; i < numbers.length ; i++){
		if(numbers[i] > numbers[i + 1]){
			return numbers[i + 1];
		}
	}
	return numbers[0];
}

50第一只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

Array.prototype.indexOf()indexOf() 方法返回在数组中可以找到给定元素的第一个索引，如果不存在，则返回 -1。

1
indexOf(searchElement, fromIndex)开始查找的位置。如果该索引值大于或等于数组长度，意味着不会在数组里查找，返回 -1。如果参数中提供的索引值是一个负值，则将其作为数组末尾的一个抵消，即 -1 表示从最后一个元素开始查找，-2 表示从倒数第二个元素开始查找，以此类推。注意：如果参数中提供的索引值是一个负值，并不改变其查找顺序，查找顺序仍然是从前向后查询数组。如果抵消后的索引值仍小于 0，则整个数组都将会被查询。其默认值为 0。

利用循环找出第一个数的位置，再次查询这个数位置之后是否还存在相同的数字，存在则继续，不存在则输出

1
2
3
4
5
6
7
8
9
10
var firstUniqChar = function(s){
	for(let i = 0; i < s.length ; i++){
		k = s.indexOf(s[i]);
		e = s.indexOf(s[i],k+1);
		if(e == -1) return s[i];
	}
	return " "
}
不能吧k = s.indexOf(s[i])去掉，e中的k换为i。
因为，每次都要找相同数的第一个的位置之后才找。不是目前数字的后面一个位置去找。

搜索与回溯算法

32I 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

Array.prototype.shift() 会转移并回传队列的第一个元素。此方法会改变队列的长度。

**unshift()**方法会增加一个或多个元素至队列的开头，并与回传队列的新长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 按照同一层从左到右的顺序打印，因此使用广度优先遍历，先将同一层的遍历完，再遍历下一层的
// 要实现树的广度优先遍历策略，需要借助队列先进先出的特点，不然每次都还是会做成深度优先，树的左右节点性质就决定了每次会先遍历左节点
var levelOrder = function(root){
	let res = []
	if(!root){
		return res;
	}
	 // 初始化队列
	let queue = [root];
	// 跳出条件，队列为空，即所有节点都遍历完成
	while(queue.length){
		// 拿出队首节点
		let node = queue.shift();
		res.push(node.val);				//node.val
		if(node.left){
			queue.push(node.left);		//queue
		}
		if(node.right){
			queue.push(node.right);		//queue
		}
	}
	return res
}

32 II从上到下打印二叉树II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

运用了一个tmp来进行对某一层的元素的存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var levelOrder = function(root){
	const res = [];
	if(!root){
		return res
	}
	let queue = [root];
	while(root.length){
		let len = queue.length;
		let temp = [];
		for(let i = 0 ; i < len ; i++){
			let node = queue.shift();
			temp.push(node.val);	//.val
			if(node.left){
				queue.push(node.left)	//queue
			}
			if(ndoe.right){
				queue.push(node.right)
			}
		}
		res.push(temp)
	}
	return res
}

32III从上到下打印二叉树III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

采用不同level中对tmp的push()还是unshift()来进行区分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var levelOrder = function(root){
	let level = 1;
	const res = [];
	const queue = [root];
	while(queue.length){
		let tmp = [];
		let len = queue.length;
		for(let i = 0 ; i < len ; i++){
			let node = queue.shift();
			if(level % 2 === 1){
				tmp.push(node.val);
			}else{
				tmp.unshift(node.val);
			}
		}
		if(node.left) queue.push(node.left)
		if(node.right) queue.push(node.right)
		res.push(tmp);
		level++;
	}
	return res;
}

026 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
记录下js解法
判断是不是子树，同时传A.left B.left
如果B是A的子树
要么从A开始 B是子树
要么B是A左子树的子结构
要么B是A右子树的子结构

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    if(!B || !A) return false
    return find(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

function find(A, B){
    if(!B) return true
    if(!A || A.val != B.val) return false
    return find(A.left,B.left) && find(A.right, B.right)
}

27二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var mirrorTree = function(root){
	if(!root) return null;
	[[root.left,root.right]] = [[root.right],[root.left]];
	mirrorTree(root.left);
	mirrorTree(root.right);
	return root
}
//2
var mirrotTree = function(root){
	if(!root) return null;
	let tmp = root.left;
	root.left = mirrorTree(root.right);
	root.right = mirrorTree(tmp);
	return root;
}

动态规划

10 I 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//1
var fib = funciton(n){
	const dp = [0,1];
	for(let i = 2; i <= n; i++){
		dp[i] = (dp[i-1] + dp[i - 2]) % 1000000007;
	}
	return dp[n];
}
//2
var fib = function(n){
	if(n < 2){
		return n;
	}
	let p = 0 , q = 0 , r = 1;
	for(let i = 2 ; i <= n; i++){
		p = q;
		q = r;
		r = (p + q) % 1000000007;
	}
	return r;
}

10 II 青蛙跳台问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
var numWays = function(n){
	cosnt dp = [1,1];
	for(let n = 2;i <= n ; i++){
		dp[i] = (dp[i-1] + dp[i-2]) %1000000007;
	}
	return dp[i];
}

63股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

1
2
3
4
5
6
7
8
9
var maxProfit = function(prices){
	var minCost = prices[0];
	var dp = 0;
	for(var i = 0;i < prices.length ; i++){
		minCost = Math.min(minCost,prices[i]);
		dp = Math.max(dp,prices[i] - minCost);
	}
	return dp;
}

42连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

1
2
3
4
5
6
7
8
var manSubArray = function(nums){
	let dp = [nums[0]];
	for(let i = 1 ; i <= nums.length ;  i++){
		dp[i] = Math.max(nums[i] , dp[i-1] + nums[i]);
	}
	return Math.max(...dp);	
}

47礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

1
2
3
4
5
6
7
8
9
10
11
12
13
//只求最后价值所以把原数组破坏了，如果不想就初始化一个新的全是0的dp数组。
var maxValue = function(girid){
	if(!grid.length) return 0;
	for(let i = 0; i < grid.length ; i++){
		for(let j = 0; j < grid[0].length ; j++){
			if(i === 0 && j === 0) continue;
			if(i === 0) grid[i][j] += grid[i][j - 1];
			if(j === 0) grid[i][j] += grid[i - 1][j];
			if(i !== 0 && j !== 0) grid[i][j] = Math.max(grid[i - 1][j] , grid[i][j - 1]);
		}
	}
	return grid[grid.length - 1][grid[0].length - 1];
}

46 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

​ 数字每每一位或者两位判断，转换成字符串，然后进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var translateNum = function(num){
	if(num < 10) return 1;
	let str = num + '';
	let dp = [1,1];
	for(let i = 1 ; i < str.length ; i++){
		let tmp = parseInt(str.slice(i - 1 , i + 1) , 10) || 0;
		if(tmp >= 10 && tmp <= 25){
			dp[i + 1] = dp[i] + dp[i -1];
		}else{
			dp[i + 1] = dp[i];
		}
	}
	return dp[dp.length - 1];
}

48最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

​ 该**lastIndexOf()**方法给定一个参数：要搜索的子字符串，搜索整个调用字符串，并返回指定子字符串最后一次出现的索引。给定第二个参数：一个数字，该方法返回指定子字符串在小于或等于指定数字的索引处的最后一次出现。

关于字符串的不重复字符串，需要不重复字符串的首位索引，本题最后只要求字符串的长度，所以直接pop。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var lengthOfLongestSubstring = function(s) {
    if(!s.length) return 0;
    let dp = [1];
    for(let i=0,j=1;j<s.length;j++){
        let k = s.slice(0,j).lastIndexOf(s[j]);
        if(k < i){
            dp[j] = dp[j-1] > j-i+1 ? dp[j-1] :j-i+1;
        }else{
            i = k + 1;
            dp[j] = dp[j-1] > j-i+1 ? dp[j-1] :j-i+1;
        }
    }
    return dp.pop();
};

双指针

18删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function ListNode(val){
	this.val = val;
	this.next = null;
}
var deleteNode = function(head,val){
	if(!head) return head;
	let dummy = new ListNode(0);
	dummy.next = head;
	let cur = dummy;
	while(cur && cur.next){
		cur.next.val === val ? cur.next = cur.next.next : cur = cur.next
	}
	return dummy.next;
}

22 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

1
2
3
4
5
6
7
8
9
10
11
var getKthFromEnd = function(head,k){
	let fast = head;
	let slow = head;
	let flag = 0;
	while(fast){
		if(flag >= k) slow = slow.next;
		fast = fast.next;
		flag++;
	}
	return slow;
}

25合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//普通方法
var mergeTwoLists = function(l1,l2){
	let newList = new ListNode(-1);
	let currNode = nweList;
	while(l1 && l2){
		if(l1.val < l2.val){
			currNode.next = l1;
			l1 = l1.next;
		}else{
			currNode.next = l2;
			l2 = l2.next;
		}
		currNode = currNode.next;
	}
	currNode.next = l1 || l2;				注意这里是两道杠
	return newList.next;
}
//递归
var mergeTwoLists = function(l1,l2){
	if(!l1) return l2;
	if(!l2) return l1;
	if(l1.val <= l2.val){
		l1.next = mergeTwoLists(l1.next,l2);
		return l1;
	}else{
		l2.next = mergeTwoLists(l1,l2.next);
		return l2;
	}
}
//迭代
function mergeTwoLists = function(l1,l2){
	let result : listNode = new ListNode(-1);
	let temp : listNode=  result;
	while(l1 && l2){
		if(l1.val <= l2.val){
			temp.next =  l1;
			l1 = l1.next;
		}else{
			temp.next = l2;
			l2 = l2.next;
		}
		temp = temp.next;
	}
	temp.next = l1 || l2;
	return result.next;
}

052两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//A前 + 公共 + B前  =  B前 + 公共 + A前
var getIntersectionNode = function(headA,headB){
	let tempA = headA,tempB = headB;
	while(tempA !== tempB){
		tempA = tempA ? tempA.next : headB;
		tempB = tempB ? tempB.next : headA;
	}
	return tempA;
}
//笨法，双指针，计算两条链表长度，遍历长的链表与短的链表的头结点是否相同。相同则停止；不同指导长链表长度与短链表长度相同，则长链表与短链表同时遍历并比较
var getIntersectionNode = function(headA,headB){
	if(headA || headB) return null;
	var A = headA;
	var ALength = 0;
	var B = headB;
	var BLength = 0;
	while(A){
		ALength++;
		A = A.next;
	}
	A = headA;
	while(B){
		BLength++;
		B = B.next;
	}
	B = headB;
	if(ALength <= BLenght){
		A = headB;
		B = headA;
		[ALength,BLenght] = [BLength,ALength];
	}
	while(A){
		if(A === B) return A;
		A = A.next;
		if(ALength <= BLength) B = B.next;
		ALength -= 1;
	}
	return null;
}

21调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//双指针：头尾遍历
var exchange  = function(array){
	let start = 0,end = array.length - 1;
	while(start < end){
		while(array[start] % 2 === 1) start++;
		while(array[end] % 2 === 0 ) end--;
		if(start < end) [array[start],array[end]] = [array[end],array[start]];
	}
	return array;
}
//双指针:两个指针同时从第一个元素触发。s1找偶数，s2找奇数。偶在奇前面就交换位置。否则偶数不动，不交换，继续找后面的奇数
var exchange = function(array){
	let s1 = 0, s2 = 0;
	const len = array.length - 1;
	while(s2 <= len && s1 <= len){
		while(array[s1] % 2 === 1) s1++;
		while(array[s2] % 2 === 0) s2++;
		if(s1 < s2){
			if(s2 <= len && s1 <= len){
				[array[s1] , array[s2]] = [array[s2],array[s1]]
			}
		}else{
			s2++
		}
	}
	return array;
}

057 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//双指针
var twoSum = function(nums,target){
	let left = 0 , right = nums.length - 1;
	let sum = 0;
	while(left < right){
		sum = nums[left] + nums[right];
		if(sum < targht){
			left++;
		}else if(sum > target){
			right--;
		}else{
			return [nums[left],nums[right]];
		}
	}
	return []
}
//哈希表
function twoSum(nums: number[], target: number):number[]{
	const map: Map<number,number> = new Map();
	for(let i of nums){
        if(!map.has(i))
            map.set(target - i);
        else
            return [i,map.get[i]];
	}
}

058反转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var reverseWords = function(s){
	let arr = s.trim().replace(/s+/g,' ').split(' ')
	let left = 0 , right = arr.length - 1;
	while(left < right){
		[arr[left],arr[right]] = [[arr.right],[arr.left]];
		left++;
		right--;
	}
	return arr.join(' ')
}
//或者
var reverseWords = function(s : string) : string{
	return s.trim().split(/s+/g).reverse().join(" ")
}

搜索与回溯算法（中等）

12矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var exist = function(board,word){
	for(let i = 0; i < board.length ; i++){
		for(let j = 0 ; j < board[0].length ; j++){
			if(dfs(board,word,i,j,0)) return true;		//忘了if的条件
		}
	}
	retrun false;
	function dfs(board,word,i,j,k){
			//递归的base case
		if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] !== word[k]){
			return false;
		}
		if(k === word.length - 1){
			console.log('k',k);
			return true;
		}
		board[i][j] = '';	//标记  ，别忘了[j]
		let res = dfs(board,word,i-1,j,k+1) || dfs(board,word,i+1,j,k+1) || dfs(board,word,i,j-1,k+1) || dfs(board,word,i,j+1,k+1);
		board[i][j] = word[k];
		return res;
	}
}

13机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//BFS
var movingCount = function(m,n,k){
	const arr = new Array(m).fill().map(_ => new Array(n).fill(0));
	const queue = [[0,0]];		//注意初始的是[0,0]
	let counter = 0;
	while(queue.length){
		const [x,y] = queue.shift()
		if(x >= m || y>= n ) continue;
		if(arr[x][y]) continue;
		arr[x][y] = 1;
		
		if(bitSum(x) + bitSum(y) <= k){
			counter++;
			queue.push([x+1,y],[x,y+1]);
		}
	}
	return counter;
	function bitSum(n){
		let res = 0;
		while(n){
			res += n % 10;
			n =  Math.floor(n / 10);
		}
		return res;
	}
}
//DFS
var movingCount = function(m,n,k){
	const arr = new Array(m).fill().map(_ => new Array(m).fill(0));
	let counter = 0;
	run(0,0);
	return counter;
	
	funciton run(i,j){
		if(i >= m || j >= n ) return;
		if(arr[i][j]) return 
		arr[i][j] = 1;
		if(bitSum(i) + bitSum(j) <= k){
			counter++;
			run(i+1,j);
			run(i,j+1);
		}
	}
	function bitSum(n){
		let res = 0;
		while(n){
			res += n % 10;
			n = Math.floor(n / 10);
		}
		return res;
	}
}

34二叉树中和维某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var pathSum = function(root,target){
	let res = [];
	function pathTree(root,target,path){
		if(!root) return 
		if(!root.left & !root.right && target === root.val){
			path.push(root.val);
			res.push(path.slice());
		}
		path.push(root.val);
		pathTree(root.left,target - root.val,path.slice());
		pathTree(root.right,target - root.val,path.slice());
		path.pop();
	}
	pathTree(root,target,[]);
	return res;
}

36二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var treeToDoublyList = funciton(root){
	function dfs(root){
		if(!root) return root;
		dfs(root.left);
		pre ? pre.right = root : head = root;
		root.left = pre;
		pre = root;
		dfs(root.right);
	}
	let pre = null, head = null;
	if(!root) return root;
	dfs(root);
	head.left = pre;
	pre.right = head;
	return head;
}

54二叉搜索树的第k大节点

给定一颗二叉搜索树，请找出其中第k大的节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
var kehLargest = function(root,k){
	let res = [];
	treeToSortedArr(root,res);
	return res[k-1];
	
	function treeToSortedArr(root,res){
		if(!root) return;
		treeToSortedArr(root.right,res);
		res.push(root.val);
		treeToSortedArr(root.left,,res);
	}
}

排序

45把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

1
2
3
4
5
var minNumber = function(nums){
	return minNums = nums.sort( (a,b) => {
		return Number(String(a) + b) - Number(String(b) + a)
	}).join('');
}

61扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//常规方法， 相邻两个的差 和 0 的情况
var isStraight = function(nums){
	nums.sort( (a,b) => {return a - b});
	let zeroN = nums.lastIndexOf(0) + 1;
	let c = 0;
	for(let i = 0 ; i < resetArr.length - 1 ; i++){
		if(resetArr[i] + 1 < resetArr[i + 1]){
			c += resetArr[i+1] - resetArr[i] - 1;
		}else if(resetArr[i+1] === resetArr[i]){
			return false;
		}
	}
	return c <= zeroN;
}
//用set，除了0不能有其他重复的牌，除0以外五张牌中最大的牌和最小的牌相差<=5
var isStraight = function(nums){
	const set = new Set();
	let max = 0,min = 14;
	for(let item of nums){
		if(item) continue;
		if(set.has(item)) return false;
		max = Math.max(item,max);
		min = Math.min(item,min);
		set.add(item);
	}
	return max - min < 5;
}

40最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//最简单
var getLeastNumber = function(arr,k){
	return arr.sort( (a,b) => return a - b).slice(0,k);
}
//快排
var getLeastNumber = function(arr,k){
	qSort(arr,0,arr.length - 1);
	return arr.slice(0,k);
	
	fucntion qSort(arr,low,high){
		if(low >= high) return
		let flag = arr[low];
         let left = low,right = high;
         while(left < right){
         	while(arr[right] >= flag && left < right) right--;
         	while(arr[left] <= flag && left < right) left++;
         	if(left < right){
         		let temp = arr[left];
         		arr[left] = arr[right];
         		arr[right] = temp;
         	}
         }
         arr[low] = arr[right];
         arr[right] = flag;
         if(right === k) return 
         k < right ? qSort(arr,low,right - 1) : qSort(arr,right + 1,high);	//优化一下，只对前k个排序
	}
}

41数据流中的中位数（困难） 没做————————

搜索与回溯算法（中等）

55 I 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//1递归
var maxDepth = function(root){
	if(!root) return 0;
	let left = maxDepth(root.left);
	let right = maxDepth(root.right);
	return Math.max(left,right) + 1;
}
//2 bfs+迭代
var maxDepth = function(root:TreeNode | null): number{
	if(!root) return 0;
	let queue = [root];
	let res = 0;
	while(queue.length){
		let len = queue.length;
		while(len >= 0){
			let node = queue.shift();
			if(node.left) queue.push(node.left);
			if(node.right) queue.push(node.right);
			len--;
		}
		res++;
	}
	return res;
}
//3 bfs
var maxDepth = function(root){
	if(!root) return 0;
	let queue = [root];
	let res = 0;
	while(queue.length > 0){
		let tmp = [];
		for(let i = 0 ; i < queue.length ; i++){
			if(queue[i].left) tmp.push(queue[i].left);
			if(queue[i].right) tmp.push(queue[i].right);
		};
		queue = tmp;
		res++;
	}
	return res;
}
//4 dfs+回溯 先序遍历
var maxDepth = function(root){
	let deep = 0 , max = 0;
	dfs(root);
	return max;
	
	function dfs(root){
		if(!root) return ;
		deep++;
		if(deep > max) max = deep;
		dfs(root.left);
		dfs(root.right);
		deep--;
	}
}
//5 dfs+递归 后序遍历  和1一样
var maxDepth = function(root){
	if(!root) return 0;
	return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}

55 II 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//遍历到当前结点的左右子节点，AB为根节点的树的左右子树深度差值不超过一
//recusive函数对二叉树进行深度优先遍历，而getDepth函数则获取树的深度
//recusive函数 退出条件：1 当前结点为null或者当前子节点的左右子节点均为null，说明遍历完成，返回true。2当前节点的左右子树深度相差超过1返回false
var isBalanced = function(root){
	return recusive(root);
}
var recusive = function(root){
	if(!root || (!root.left && !root.right)) return true;
	if(Math.abs( getDepth(root.left) - getDepth(root.right) ) > 1) return false;
	return recusive(root.left) && recusive(root.right);
}
var getDepth = function(root){
	if(!root) return 0;
	return Math.max(getDepth(root.left) , getDepth(root.right)) + 1;
}
//第二种形式
var isBalanced = function(root){
	return judge(root) !== -1;
}
const judge = (root) => {
	if(!root) return 0;
	let left = judge(root.left);
	if(left === -1) return -1;
	let right = judge(root.right);
	if(right === -1) return -1;
	return Math.abs(left - right) > 1 ? -1 : Math.max(left , right) + 1;
}

64 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1
2
3
4
5
6
7
8
9
//一行		前面的n是作为条件判断的
var sumNums = funciton(n){
	return n && n + sumNums(--n);
}
//或者
var sumNums = function(n){
	return n === 1 || (sumNums(n-1) + n);
}

68I 二叉搜索树的最近公共祖先（二叉搜索树，有序）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//
var lowestCommonAncestor = function(root,p,q){
	if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left,p,q);
	esle if(p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right,p,q);
	else return root;
}
//
var lowestCommonAncestor = function(root,p,q){
	while(root){
		//p q 是root两侧子节点说明root就是最近的公共祖先
		if((p.val - root.val) * (q.val - root.val) <= 0) return root;
		//这一步说明p q两个节点都在root同侧。
		else root = p.val > root.val ? root.right : root.left;
	}
	return root;
}

68 II 二叉树的最近公共祖先（无序值的二叉树）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var lowestCommonAncestor = functino(root,p,q){
	// 如果树为空，直接返回null
	if(!root) return null;
	// 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
	if(root.val === p || root.val === q) return root;
	 // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
	const left = lowestCommonAncestor(root.left,p,q);
	  // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
	const right = lowestCommonAncestor(root.right,p,q);
	 // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
	if(!left) return rihgt;
	 // 如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
    else if(!right) return left;
	//当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
	else return root;
}

分治法（中等）

07重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//1
var buildTree = function(preorder,inorder){
	if(!preorder.length || !inorder.length) return null;
	const root = inorder.findIndex(item => item === preorder[0]);
	const left = inorder.slice(0,index);
	const right = inorder.slice(index + 1);
	return {
		val: preorder[0];
		left: buildTree(preorder.slice(1,index+1),left);
		right:buildTree(preorder.slice(index + 1),right);
	}
}
//2
var buildTree = function(preorder , inorder){
	if(!preorder.length || !inorder.length) return null;
	const root = TreeNode(preorder[0]);
	let rootIndex = inorder.findIndex(item => item === preorder[0]);
	if(rootIndex === -1) return null;
	preorder.shift();
	root.left = buildTree(preorder,inorder(0,rootIndex));
	root.right = buildTree(preorder,inorder(rootIndex + 1));
	return root;
}
//3
var buildTree = function(preorder,inorder){
	// 递归返回条件
	if(!preorder.length || !inorder.length) return nulll;
	// 先序遍历的首元素为根结点，创建节点
	const root = new TreeNode(preorder[0]);
	const rootInIndex = inorder.indexOf(preorder[0]);
	 // 用If语句剪枝，减少递归层数（因为创建root时，left right 默认设置为null了，因为不必再设置）
    // 设置左右子节点，递归
	if(rootIndex != 0) root.left = buildTree(preorder.slice(1,1+rootInIndex),inorder.slice(0,rootInIndex));
	if(rootIndex != preorder.length - 1) root.right = buildTree(preorder.slice(1+rootInIndex),inorder.slice(rootInIndex + 1));
	return root;
}

16 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var myPow = function(x,n){
	if(x === 0) return 0;
	if(n === 0) return 1;
	if(n < 0){
		x = 1 / x;
		n = -n;
	}
	let result = 1;
	while(n > 0){
		if(n & 1 === 1){
			return *= x
		}
		x *= x;
		n >>>= 1;
	}
	return result;
}

33二叉搜索树的后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//二叉搜索树特点是右子树值永远大于左子树
后序遍历：左子树 -> 右子树 -> 根
取出左子树，取出右子树，判断右子树 和 根相比最小值是不是根值，否，则返回false
递归左子树和右子树，直到树中值元素<=2 返回true;
举例[1,6,3,2,5]，分为左子树[1],右子树[6,3,2],根[5], Math.min(6,3,2,5) !== 5, return false
时间空间复杂度： O(nlogn), O(n)
var verifyPostOrder = function(postorder){
	if(postorder.length <= 2) return true;
	const root = postorder[postorder.length -1];
	const idx = postorder.findIndex( (item) => item > root);
	const left = postorder.slice(0,idx);
	const right = postorder.slice(idx,-1);
	if(Math.min(root,...right) !== root) return false;
	return verifyPostorder(left) && verifyPostorder(right);
}

位运算

15二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

1
2
3
4
5
6
7
8
9
10
11
12
13
//按位与&,对应位数都为1则为1；,循环的条件：只要存在有1的情况n就不会为0；,退出循环时，说明n==0；,没循环一次count++；
var hammingWeight = function(n){
	let count = 0;
	while(n != 0){
		n = n & (n - 1);
		count++;
	}
	return count;
}
// toString()方法中传入的数字就是可以根据所传递的参数把数值转换为对应进制的数字字符串。
var hammingWeight = function(n){
	return n.toString(2).split("1").length - 1; 
}

65 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//
var add = function(a,b){
	while(b != 0){
		var c = (a ^ b)
		b = ((a & b) << 1)
		a = c
	}
	return a
}
//
var add = function(a,b){
	if((a & b) === 0) return a | b;
	let x = a ^ b,y = (a & b) << 1;
	return add(x,y);
}

56 I 数组中数字出现的次数——————

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

1

56 II 数组中数字出现的次数——————

1

数学（简单）

39数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//方法1：快排后，返回nums[n/2]
var majorityElement = function(nums){
	if(!nums || !nums.length) return -1;
	quickSort(nums,0,nums.length - 1);
	return nums[Math.floor(nums.length / 2)];
}
function quickSort(nums,lo,hi){
	if(lo >= hi) return ;
	let i = partition(nums,lo,hi);
	quickSort(nums,lo,hi);
	quickSort(nums,i + 1,hi);
}
function partition(nums,lo,hi){
	let pivot = nums[lo];
	let i = lo + 1,j = hi;
	while(i <= j){
		while(nums[i] < pivot && i <= j) i++;
		while(nums[j] > pivot && i <= j) j--;
		if(i < j){
		 let tmp = nums[i];
		 nums[i] = nums[j];
		 nums[j] =  tmpm;
		 i++;
		 j--;
		}
	}
}
//方法2：遍历数组将每个元素出现的次数存到map中，遍历map找到次数大于nums.length / 2的
var majorityElement = function(nums){
	let map = new Map();
	for(let i = 0; i < nums.length ; i++){
		let n = nums[i];
		if(!map.has(n)) map.set(n,1)
		else map.set(n,map.get(n) + 1)
		
		for([key,value] of map){
			if(value > nums.legnth >>1) return key;
		}
	}
}

66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
var constructArr = function(a){
	let n = a.length
	if(!n) return []		//特殊情况：非空判定
	let result = new Array(n).fill(1)	//结果中的任一元素 = 左边元素乘积 * 右边元素乘积
	let rightAccu = 1
	for(let i = 1 ; i < n ; i++){		//构建左边的乘积放在数组中
		result[i] = result[i-1] * a[i-1]
	}
	for(let i = n - 2 ; i >=0 ; i--){	
		rightAccu *= a[i + 1]		//构建右边的乘积
		result[i] *= rightAccu		//乘以左边的乘积就是结果
	} 
	return result
}
//暴力
var constructArr = fucntion(a){
	const res = []
	let n = a.length
	for(let i = 0 ; i < n ; i++){
		let temp = 1
		for(let j = 0; j < n ;j++){
			if(i != j){
				temp *= a[j]
			}
		}
		res.push(temp)
	}
	return res
}
//动态规划
var constructArr = function(a){
	if(a == null || !a.length) return a 		//边界条件判断
	let length = a.length
	let resLeft = []		//每个元素左边的乘积
	let resRight = []		//每个元素右边的乘积
	resLeft[0] = 1			//base case
	resRight[length - 1] = 1
	for(let i = 1; i < length ; i++){
		// 状态转移方程 resLeft[i]表示 当前元素左边的所有元素乘积（不包含当前元素）
        // resLeft[i - 1]不包括a[i - 1] 乘以✖️a[i-1]就表示当前 resLeft[i]
        resLeft[i] = resLeft[i - 1] * a[i -1]
	}
	   for (let  i = length - 2; i >= 0; i--) {
        resRight[i] = resRight[i + 1] * a[i + 1];
    }
    //左边乘以右边就是我们要求的结果
    let  res =  [];
    for (let  i = 0; i < length; i++) {
        res[i] = resLeft[i] * resRight[i];
    }
    return res;
}

数学（中等）

14-I 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
var cuttingRope = function(n){
	//s的初始值为n=2的情况
	var s = [1,1]		
	var len = s.length
	//从3开始
	for(var i = 3 ; i <= n ; i++){		
         //每次都更改最前面的那个因子
		s[0]++
		//如果因子等于4就要把它分成两个值为2的因子
		if(s[0] == 4){
			s[0] = 2
			s[++len] = 2
		}
		//因为每次更改最前面的，所以要确保最前面是6最小的
		s.sort((a,b) => a - b)
	}
	//用for循环把所有的因子乘起来就是n的最大值
	for(var i = 1 ; i < len ; i++){
		s[i] *= s[i-1]
		return s[len - 1]
	}
}
//动态规划
var cuttingRope = function(n){
	let i,j,dp = new Array(n+1).fill(0),nowBigger
	dp[2] = 1
	for(i = 2 ; i <= n ; i++){
		for(j = 1 ; j < i ; j++){
			nowBigger = Math.max(j * (i - j),j * dp[i - j])
			dp[i] = Math.max(dp[i],nowBigger)
		}
	}
	return dp[n]
}

57-II和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var findCotinuousSequence = function(target){
	let left = 1 ,right = 0,sum = 0,ans = []
	//最大不超过target的一半
	while(right <= Math.round(target / 2)){
		if(sum === target){
			//sum等于目标
			let temp = []
			for(let i = left ; i <= right ; i++){
				temp.push(i)
			}
			if(temp.length){
				ans.push(temp)
			}
			sum -= left
			left++
		}
		//sum大于目标数，左边-
		while(sum > target){
			sum -= left		// *** -= 和下面left移动的顺序要想清楚***
			left++
		}
		//sum小于目标数，右边+
		while(sum < target){
			sum += right
			right++
		}
	}
	return ans
}

62 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

1
2
3
4
5
6
7
var lastRemaining = function(n,m){
	let pos = 0
	for(let i = 2 ; i <= n ; i++){
		pos = (pos + m) % i
	}
	return pos
}

模拟（中等）

29 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var spiralOrder = function(matrix){
	if(matrix.length == 0) return []
	const res = []
	let top = 0
	let bottom = matrix.length - 1
	let left = 0
	let right = matrix[0].length - 1
	
	while(top < right && left < right){
		for(let i = left; i < right ; i++) res.push(matrix[top][i])
		for(let i = top ; i < bottom ; i++) res.push(matrix[i][right])
		for(let i = right ; i > left ; i--) res.push(matrix[bottom][i])
		for(let i = bottom ; i > top ; i--) res.push(mtrix[i][left])
		right--
		left++
		top--
		bottom++
	}
	if(top == bottom){
		for(let i = left ; i <= right ; i++){
			res.push(matrix[top][i])
		}
	}else if(left == right){
		for(let i = top ; i <= bottom ; i++){
			res.push(matrix[i][left])
		}
	}
	return res
}

剑指offerII

001 整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1

先把特殊情况排除，然后最先判断正负号，然后把负负情况改为正。创建结果。 用减法代替除法进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var divide = function(a,b){
	//排除特殊情况
	if(a === -Math.pow(2,31) & b === -1) return (Math.pow(2,31) - 1)
	//记录正负号
	let p = 0
	if(a < 0 & b < 0) { p = 0}
	else if(a > 0 & b > 0) { p = 0}
	else p = 1
	
	//处理负数，最后进行添加负号
	if(a < 0)  a = -a
	if(b < 0)  b = -b
	
	let result = 0
	//主要处理
	while(a >= b){
		a -= b
		result++
	}
	
	if(p === 1){result = -result}
	return result;
}