Skip to content

Commit 260ade2

Browse files
D1StreamEngD1StreamEng
committed
update for week03
1 parent a44f89b commit 260ade2

5 files changed

Lines changed: 272 additions & 0 deletions

File tree

‎Week_03/Leet105.scala‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Week_03
2+
3+
//根据一棵树的前序遍历与中序遍历构造二叉树。
4+
//
5+
// 注意:
6+
//你可以假设树中没有重复的元素。
7+
//
8+
// 例如，给出
9+
//
10+
// 前序遍历 preorder = [3,9,20,15,7]
11+
//中序遍历 inorder = [9,3,15,20,7]
12+
//
13+
// 返回如下的二叉树：
14+
//
15+
// 3
16+
// / \
17+
// 9 20
18+
// / \
19+
// 15 7
20+
// Related Topics 树 深度优先搜索 数组
21+
// 👍 794 👎 0
22+
23+
24+
//leetcode submit region begin(Prohibit modification and deletion)
25+
/**
26+
* Definition for a binary tree node.
27+
*/
28+
class TreeNode(var _value: Int) {
29+
var value: Int = _value
30+
var left: TreeNode = null
31+
var right: TreeNode = null
32+
}
33+
34+
object Leet105 {
35+
def buildTree(preorder: Array[Int], inorder: Array[Int]): TreeNode = {
36+
if (preorder == null || preorder.length == 0) return null
37+
val rootValue = preorder(0)
38+
val rootIndex = inorder.indexOf(rootValue)
39+
val root = new TreeNode(rootValue)
40+
root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex))
41+
root.right = buildTree(preorder.slice(rootIndex + 1, preorder.length), inorder.slice(rootIndex + 1, inorder.length))
42+
root
43+
}
44+
}
45+
46+
//leetcode submit region end(Prohibit modification and deletion)

‎Week_03/Leet236.scala‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package Week_03
2+
3+
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
4+
//
5+
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
6+
//一个节点也可以是它自己的祖先）。”
7+
//
8+
// 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
9+
//
10+
//
11+
//
12+
//
13+
//
14+
// 示例 1:
15+
//
16+
// 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
17+
//输出: 3
18+
//解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
19+
//
20+
//
21+
// 示例 2:
22+
//
23+
// 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
24+
//输出: 5
25+
//解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
26+
//
27+
//
28+
//
29+
//
30+
// 说明:
31+
//
32+
//
33+
// 所有节点的值都是唯一的。
34+
// p、q 为不同节点且均存在于给定的二叉树中。
35+
//
36+
// Related Topics 树
37+
// 👍 870 👎 0
38+
39+
40+
//leetcode submit region begin(Prohibit modification and deletion)
41+
/**
42+
* Definition for a binary tree node.
43+
*/
44+
class TreeNode(var _value: Int) {
45+
var value: Int = _value
46+
var left: TreeNode = null
47+
var right: TreeNode = null
48+
}
49+
50+
51+
object Leet236 {
52+
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode = {
53+
trait Result
54+
case class Found(ancestor: TreeNode) extends Result
55+
case class AtLarge(missing: Set[TreeNode]) extends Result
56+
def getState(o: TreeNode, target: Set[TreeNode]): Result = {
57+
if (o == null) AtLarge(target)
58+
else {
59+
val tNew = target - o
60+
if (tNew.isEmpty) {
61+
Found(o)
62+
}
63+
else getState(o.left, tNew) match {
64+
case Found(x) if target.contains(o) => Found(o)
65+
case Found(x) => Found(x)
66+
case AtLarge(t1) =>
67+
getState(o.right, t1) match {
68+
case Found(x) if target == t1 => Found(x)
69+
case Found(x) => Found(o)
70+
case AtLarge(t2) => AtLarge(t2)
71+
}
72+
}
73+
}
74+
}
75+
76+
getState(root, Set(p, q)) match {
77+
case Found(o) => o
78+
case _ => root
79+
}
80+
}
81+
}
82+
83+
//leetcode submit region end(Prohibit modification and deletion)
84+

‎Week_03/Leet46.scala‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package Week_03
2+
3+
//给定一个 没有重复 数字的序列，返回其所有可能的全排列。
4+
//
5+
// 示例:
6+
//
7+
// 输入: [1,2,3]
8+
//输出:
9+
//[
10+
// [1,2,3],
11+
// [1,3,2],
12+
// [2,1,3],
13+
// [2,3,1],
14+
// [3,1,2],
15+
// [3,2,1]
16+
//]
17+
// Related Topics 回溯算法
18+
// 👍 1044 👎 0
19+
20+
21+
//leetcode submit region begin(Prohibit modification and deletion)
22+
object Leet46 {
23+
def permute(nums: Array[Int]): List[List[Int]] = {
24+
if (nums.length == 1) List(nums.toList)
25+
else if (nums.length == 2) List(nums.toList, nums.reverse.toList)
26+
else {
27+
(for {num <- nums.toList
28+
rest = nums.diff(Array(num))
29+
prev = permute(rest)
30+
res = prev.map(List(num) ++ _)
31+
} yield res).flatten
32+
}
33+
}
34+
}
35+
36+
//leetcode submit region end(Prohibit modification and deletion)

‎Week_03/Leet47.scala‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package Week_03
2+
3+
//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
4+
//
5+
//
6+
//
7+
// 示例 1：
8+
//
9+
//
10+
//输入：nums = [1,1,2]
11+
//输出：
12+
//[[1,1,2],
13+
// [1,2,1],
14+
// [2,1,1]]
15+
//
16+
//
17+
// 示例 2：
18+
//
19+
//
20+
//输入：nums = [1,2,3]
21+
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
22+
//
23+
//
24+
//
25+
//
26+
// 提示：
27+
//
28+
//
29+
// 1 <= nums.length <= 8
30+
// -10 <= nums[i] <= 10
31+
//
32+
// Related Topics 回溯算法
33+
// 👍 545 👎 0
34+
35+
36+
//leetcode submit region begin(Prohibit modification and deletion)
37+
object Leet47 {
38+
def permuteUnique(nums: Array[Int]): List[List[Int]] = {
39+
solver(List((List[Int](), nums.sorted.toList))) map (x => x._1)
40+
}
41+
42+
@scala.annotation.tailrec
43+
def solver(l: List[(List[Int], List[Int])]): List[(List[Int], List[Int])] = {
44+
if (l forall (x => x._2 == Nil)) l
45+
else solver(l flatMap f)
46+
}
47+
48+
def f(x: (List[Int], List[Int])): List[(List[Int], List[Int])] = x._2 match {
49+
case Nil => List(x)
50+
case _ => g(x._1)(Nil, x._2, Nil)
51+
}
52+
53+
@scala.annotation.tailrec
54+
def g(x: List[Int])(xs1: List[Int], xs2: List[Int], acc: List[(List[Int], List[Int])]): List[(List[Int], List[Int])] = xs2 match {
55+
case Nil => acc.distinct
56+
case h :: t => g(x)(xs1 :+ h, t, (h :: x, xs1 ++ t) :: acc)
57+
}
58+
}
59+
60+
//leetcode submit region end(Prohibit modification and deletion)

‎Week_03/Leet77.scala‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Week_03
2+
3+
import scala.collection.mutable.ListBuffer
4+
5+
//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
6+
//
7+
// 示例:
8+
//
9+
// 输入: n = 4, k = 2
10+
//输出:
11+
//[
12+
// [2,4],
13+
// [3,4],
14+
// [2,3],
15+
// [1,2],
16+
// [1,3],
17+
// [1,4],
18+
//]
19+
// Related Topics 回溯算法
20+
// 👍 456 👎 0
21+
22+
23+
//leetcode submit region begin(Prohibit modification and deletion)
24+
object Leet77 {
25+
def combine(n: Int, k: Int): List[List[Int]] = {
26+
val result = new ListBuffer[List[Int]]()
27+
val path = new ListBuffer[Int]
28+
combineWithResult(n,k,result,path,1)
29+
result.to(List)
30+
}
31+
def combineWithResult(n: Int, k: Int, result :ListBuffer[List[Int]],path: ListBuffer[Int],index:Int) :Unit = {
32+
if(n<k){
33+
return
34+
}
35+
if(k == 0){
36+
result.addOne(path.toList)
37+
}
38+
for(i <- index to n){
39+
val pathTemp = new ListBuffer[Int]().addAll(path)
40+
pathTemp.addOne(i)
41+
combineWithResult(n,k-1,result,pathTemp,i+1)
42+
}
43+
}
44+
}
45+
//leetcode submit region end(Prohibit modification and deletion)
46+

0 commit comments

Comments
 (0)