Eighteen Blog

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。
阅读全文
Algorithm

题目描述

题目有点长，我就截个图展示了。
在这里插入图片描述

解题思路

这跟我之前做的那个旋转数组有相似之处，都是两个有序序列的组合。
JavaScript：leetcode_33. 搜索旋转排序数组（二分法）

看题目限制，肯定又是不能用遍历的O(n)。而且对获取mountain的值有100次的限制。

那么自然就想到了二分法，结合题目，mountain长度为10000那么大概分十几次就完事儿了。基本不会把一百次用完。

我的思路是，用二分法找到mountain的山顶top，将其分为两个有序序列，然后分别用二分法查找。

最终算法时间复杂度为 O(log n)

  1. findTop 查找山顶top
  2. findLeftTarget 左序查找target，左序列为升序序列。
  3. findRightTarget 右序列查找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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * function MountainArray() {
 *     @param {number} index
 *     @return {number}
 *     this.get = function(index) {
 *         ...
 *     };
 *
 *     @return {number}
 *     this.length = function() {
 *         ...
 *     };
 * };
 */

/**
 * @param {number} target
 * @param {MountainArray} mountainArr
 * @return {number}
 */
var findInMountainArray = function(target, mountainArr) {
    let length = mountainArr.length();
    let left_v = mountainArr.get(0);
    let right_v = mountainArr.get(length - 1);
    if (target < left_v && target < right_v) {
        return -1
    }
    let resMid = findTop(0, length - 1, mountainArr)
    let top = resMid.mid;
    let topV = resMid.mid_v;
    if (target > topV) {
        return -1;
    }
    let left_target = findLeftTarget(0, top, mountainArr, target);
    return left_target === -1 ? findRightTarget(top, length-1, mountainArr, target) : left_target;
};
var findTop = function(left, right, mountainArr) {
    let mid = left + ((right - left) >> 1);
    let mid_lv = mountainArr.get(mid - 1);
    let mid_v = mountainArr.get(mid);
    let mid_rv = mountainArr.get(mid + 1);
    if (mid_v > mid_lv) {
        if (mid_v > mid_rv) {
            return {
                mid: mid,
                mid_v: mid_v,
            }
        } else {
            return findTop(mid, right, mountainArr)
        }
    } else if (mid_v < mid_lv) {
        return findTop(left, mid, mountainArr)
    }
}
var findLeftTarget = function(left, right, mountainArr, target) {
    if (right - left <= 1) {
        let left_v = mountainArr.get(left);
        if (left_v === target) {
            return left;
        }
        let right_v = mountainArr.get(right);
        if (right_v === target) {
            return right;
        }
        return -1
    }
    let mid = left + ((right - left) >> 1);
    let mid_v = mountainArr.get(mid);
    if (mid_v < target) {
        return findLeftTarget(mid+1, right, mountainArr, target)
    } else if (mid_v > target) {
        return findLeftTarget(left, mid, mountainArr, target)
    } else {
        return mid;
    }
    return -1
}
var findRightTarget = function(left, right, mountainArr, target) {
    if (right - left <= 1) {
        let left_v = mountainArr.get(left);
        if (left_v === target) {
            return left;
        }
        let right_v = mountainArr.get(right);
        if (right_v === target) {
            return right;
        }
        return -1
    }
    let mid = left + ((right - left) >> 1);
    let mid_v = mountainArr.get(mid);
    if (mid_v > target) {
        return findLeftTarget(mid+1, right, mountainArr, target)
    } else if (mid_v < target) {
        return findLeftTarget(left, mid, mountainArr, target)
    } else {
        return mid;
    }
    return -1
}

扩展 二分法详解

解释：

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

  • 基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较， 如果当前位置arr[k]值等于key，则查找成功；
    • 若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；
    • 若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，
    • 直到找到为止,时间复杂度:O(log(n))
使用方法
  • 序列必须是有序的，无序序列无法使用二分法。
  • 通过递归查找，直至序列长度缩小到2或者1。
模拟实现

以 nums[1,2,3,4,5]为例，找到数组中值为1的下标

  1. left为 0，right为 4, 声明函数find(left,right)
  2. 求出中间点 mid = left + ((right - left) >> 1) 。 （>> 为位运算，相当于缩小2倍）
  3. 得到 mid 为 2；判断 nums[2] === 1 ?，若等返回mid，nums[2] 为 3，不等 1 ，进入下一步
  4. 判断nums[mid] > 1,由于nums[2] ===3 > 1,进入左序列find(0, 2)
  5. 求出中间点 mid = 0+ ((2- 0) >> 1),
  6. 得到mid 为 1；判断 nums[1] === 1 ?，若等返回mid，nums[1] 为 2，不等 1 ，进入下一步
  7. 判断nums[mid] > 1,由于nums[1] ===2 > 1,进入左序列find(0, 1)
  8. 求出中间点 mid = 0+ ((1 - 0) >> 1),
  9. 得到mid 为 0；判断 nums[0] === 1 ?，若等返回mid，nums[0] 为 1，等 1 ，return mid；

至此得到最后结果 下标为 0；

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let nums = [1,2,3,4,5] ;
let target = 1;
var find = function(left, right, target, nums) {
    let mid = (left + ((right - left) >> 1));  
    if (nums[mid] == target) {
        return mid;
    }
    if (nums[mid] > target) {
	    return find(left, mid, target, nums);
    }
    if (nums[mid] < target) {
        return find(mid + 1, right, target, nums);
    }
}
find(0,4,1, nums)

这种是数组中一定包含target的情况下。如果不确定是否包含，需要在值只剩下1-2个的时候做出判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let nums = [1,2,3,4,5] ;
let target = 1;
var find = function(left, right, target, nums) {
	if (right- left <= 1) {
		return nums[left] === target ? left : (nums[right] ===target ? right: -1)
	}
    let mid = (left + ((right - left) >> 1));  
    if (nums[mid] == target) {
        return mid;
    }
    if (nums[mid] > target) {
	    return find(left, mid, target, nums);
    }
    if (nums[mid] < target) {
        return find(mid + 1, right, target, nums);
    }
}
find(0,4,1, nums)

这样如果不存在返回 -1

Algorithm

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
阅读全文
Algorithm

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

 

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

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

限制：

2 <= nums <= 10000
阅读全文
Algorithm

题目描述

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

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
	5=5
	5=1+1+1+1+1
	示例2:

 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
	10=10
	10=5+5
	10=5+1+1+1+1+1
	10=1+1+1+1+1+1+1+1+1+1
说明：

注意:

你可以假设：

0 <= n (总金额) <= 1000000
阅读全文
Algorithm

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解题思路

对二叉树进行中右左顺序遍历，以此顺序，记录每个层级第一个被遍历的节点。

阅读全文
Algorithm

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1
示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
阅读全文
Algorithm

4 / 6