Skip to content

Commit d61a3aa

Browse files
jxnu-liguobinjxnu-liguobin
committed
2017题目
1 parent 0d39b44 commit d61a3aa

12 files changed

Lines changed: 489 additions & 0 deletions

‎Java-Learning-Summary/src/cn/edu/jxnu/leetcode/scala/Leetcode_337_Tree.scala‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package cn.edu.jxnu.leetcode.scala
2+
3+
import cn.edu.jxnu.leetcode.TreeNode
4+
import cn.edu.jxnu.leetcode.ListNodeConstants
5+
6+
/**
7+
* 间隔遍历
8+
*
9+
3
10+
/ \
11+
2 3
12+
\ \
13+
3 1
14+
*
15+
* 337. House Robber III (Medium)
16+
*
17+
* Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
18+
*
19+
* @author 梦境迷离
20+
* @time 2018年8月10日
21+
* @version v1.0
22+
*/
23+
object Leetcode_337_Tree extends App {
24+
25+
def rob(root: TreeNode): Int = {
26+
if (root == null) return 0
27+
var vart = root.value
28+
if (root.left != null) vart += rob(root.left.left) + rob(root.right.right)
29+
if (root.right != null) vart += rob(root.right.right) + rob(root.right.right)
30+
var valt = rob(root.left) + rob(root.right)
31+
math.max(valt, vart)
32+
}
33+
34+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/leetcode/scala/Leetcode_637_Tree.scala‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package cn.edu.jxnu.leetcode.scala
2+
3+
import cn.edu.jxnu.leetcode.TreeNode
4+
import scala.collection.mutable.Queue
5+
6+
/**
7+
* 层次遍历
8+
* 使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
9+
*
10+
* 637. Average of Levels in Binary Tree (Easy)
11+
* 一棵树每层节点的平均数
12+
* @author 梦境迷离
13+
* @time 2018年8月10日
14+
* @version v1.0
15+
*/
16+
object Leetcode_637_Tree extends App {
17+
18+
def averageOfLevels(root: TreeNode): List[Double] = {
19+
val ret = List()
20+
if (root == null) return ret
21+
val queue = Queue[TreeNode]()
22+
queue :+ root
23+
while (!queue.isEmpty) {
24+
var cnt = queue.size
25+
var sum = 0
26+
for (i <- 0 until cnt) {
27+
val node = queue.dequeue()
28+
sum += node.value
29+
if (node.left != null) queue :+ node.left//向尾部追加
30+
if (node.right != null) queue :+ node.right
31+
}
32+
ret.+:(sum / cnt)
33+
}
34+
ret
35+
}
36+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/leetcode/scala/Leetcode_671_Tree.scala‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package cn.edu.jxnu.leetcode.scala
2+
3+
import cn.edu.jxnu.leetcode.TreeNode
4+
5+
/**
6+
* 找出二叉树中第二小的节点
7+
*
8+
* 671. Second Minimum Node In a Binary Tree (Easy)
9+
* 给定一个非空的特殊二叉树，由具有非负值的节点组成，其中该树中的每个节点都有两个或零个子节点。如果节点有两个子节点，那么该节点的值是其两个子节点之间的较小值。
10+
* 如果不存在这样的第二最小值，则输出- 1代替。
11+
* @author 梦境迷离
12+
* @time 2018年8月10日
13+
* @version v1.0
14+
*/
15+
object Leetcode_671_Tree extends App {
16+
17+
def findSecondMinimumValue(root: TreeNode): Int = {
18+
if (root == null) return -1
19+
if (root.left == null && root.right == null) return -1
20+
var leftVal = root.left.value
21+
var rightVal = root.right.value
22+
if (leftVal == root.value) leftVal = findSecondMinimumValue(root.left)
23+
if (rightVal == root.value) rightVal = findSecondMinimumValue(root.right)
24+
if (leftVal != -1 && rightVal != -1) return Math.min(leftVal, rightVal)
25+
if (leftVal != -1) return leftVal
26+
return rightVal
27+
}
28+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/BinaryRepresentation.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package cn.edu.jxnu.practice;
2+
3+
import java.util.HashSet;
4+
5+
/**
6+
* 给定一个数将其转换为二进制（均用字符串表示），如果这个数的小数部分不能在 32 个字符之内来精确地表示，则返回 "ERROR"。
7+
*
8+
* @author 梦境迷离
9+
* @time 2018年8月10日
10+
* @version v1.0
11+
*/
12+
public class BinaryRepresentation {
13+
14+
/**
15+
* 注意不能用Double.parseDouble, 会出现精度错误。正确做法是把其分两段，整数位和小数位都用long 来表示。
16+
* 小数的二进制转换是将其乘以2, 再取100000的模(假定初始小数部分为5位数）
17+
*/
18+
private String parseInteger(String str) {
19+
int n = Integer.parseInt(str);
20+
if (str.equals("") || str.equals("0")) {
21+
return "0";
22+
}
23+
String binary = "";
24+
while (n != 0) {
25+
binary = Integer.toString(n % 2) + binary;
26+
n = n / 2;
27+
}
28+
return binary;
29+
}
30+
31+
private String parseFloat(String str) {
32+
double d = Double.parseDouble("0." + str);
33+
String binary = "";
34+
HashSet<Double> set = new HashSet<Double>();
35+
while (d > 0) {
36+
if (binary.length() > 32 || set.contains(d)) {
37+
return "ERROR";
38+
}
39+
set.add(d);
40+
d = d * 2;
41+
if (d >= 1) {
42+
binary = binary + "1";
43+
d = d - 1;
44+
} else {
45+
binary = binary + "0";
46+
}
47+
}
48+
return binary;
49+
}
50+
51+
public String binaryRepresentation(String n) {
52+
if (n.indexOf('.') == -1) {
53+
return parseInteger(n);
54+
}
55+
String[] params = n.split("\\.");
56+
String flt = parseFloat(params[1]);
57+
if (flt == "ERROR") {
58+
return flt;
59+
}
60+
if (flt.equals("0") || flt.equals("")) {
61+
return parseInteger(params[0]);
62+
}
63+
return parseInteger(params[0]) + "." + flt;
64+
}
65+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/DifferentNumberOfBinaryBits.scala‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@ package cn.edu.jxnu.practice
33
import scala.io.StdIn
44

55
/**
6+
* 两个整数的二进制有多少不同位
67
* @author 梦境迷离.
78
* @time 2018年8月2日
89
* @version v1.0

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/DifferentNumberOfBinaryBits_Java.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package cn.edu.jxnu.practice;
2+
3+
/**
4+
* 两个整数的二进制有多少不同位
5+
*
6+
* @author 梦境迷离
7+
* @time 2018年8月10日
8+
* @version v1.0
9+
*/
10+
public class DifferentNumberOfBinaryBits_Java {
11+
12+
public static int bitSwapRequired(int a, int b) {
13+
int count = 0;
14+
for (int c = a ^ b; c != 0; c = c >>> 1) {
15+
count += c & 1;
16+
}
17+
return count;
18+
}
19+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/MaximumProductSubarray.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package cn.edu.jxnu.practice;
2+
3+
import java.util.List;
4+
5+
/**
6+
* 找出一个序列中乘积最大的连续子序列（至少包含一个数）。
7+
*
8+
* @author 梦境迷离
9+
* @time 2018年8月10日
10+
* @version v1.0
11+
*/
12+
public class MaximumProductSubarray {
13+
14+
public int maxProduct(List<Integer> nums) {
15+
int[] max = new int[nums.size()];
16+
int[] min = new int[nums.size()];
17+
18+
min[0] = max[0] = nums.get(0);
19+
int result = nums.get(0);
20+
for (int i = 1; i < nums.size(); i++) {
21+
min[i] = max[i] = nums.get(i);
22+
if (nums.get(i) > 0) {
23+
max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
24+
min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
25+
} else if (nums.get(i) < 0) {
26+
max[i] = Math.max(max[i], min[i - 1] * nums.get(i));
27+
min[i] = Math.min(min[i], max[i - 1] * nums.get(i));
28+
}
29+
30+
result = Math.max(result, max[i]);
31+
}
32+
33+
return result;
34+
}
35+
36+
public int maxProduct2(int[] nums) {
37+
int[] max = new int[nums.length];
38+
int[] min = new int[nums.length];
39+
40+
min[0] = max[0] = nums[0];
41+
int result = nums[0];
42+
for (int i = 1; i < nums.length; i++) {
43+
min[i] = max[i] = nums[i];
44+
if (nums[i] > 0) {
45+
max[i] = Math.max(max[i], max[i - 1] * nums[i]);
46+
min[i] = Math.min(min[i], min[i - 1] * nums[i]);
47+
} else if (nums[i] < 0) {
48+
max[i] = Math.max(max[i], min[i - 1] * nums[i]);
49+
min[i] = Math.min(min[i], max[i - 1] * nums[i]);
50+
}
51+
52+
result = Math.max(result, max[i]);
53+
}
54+
55+
return result;
56+
}
57+
58+
public int maxProduct3(int[] nums) {
59+
int[] max = new int[nums.length];
60+
int[] min = new int[nums.length];
61+
62+
min[0] = max[0] = nums[0];
63+
int result = nums[0];
64+
for (int i = 1; i < nums.length; i++) {
65+
min[i] = max[i] = nums[i];
66+
if (nums[i] > 0) {
67+
max[i] = Math.max(max[i], max[i - 1] * nums[i]);
68+
min[i] = Math.min(min[i], min[i - 1] * nums[i]);
69+
} else if (nums[i] < 0) {
70+
max[i] = Math.max(max[i], min[i - 1] * nums[i]);
71+
min[i] = Math.min(min[i], max[i - 1] * nums[i]);
72+
}
73+
74+
result = Math.max(result, max[i]);
75+
}
76+
77+
return result;
78+
}
79+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/O1checkPowerOf2.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package cn.edu.jxnu.practice;
2+
3+
/**
4+
* 用 O(1) 时间检测整数 n 是否是 2 的幂次。
5+
* @author 梦境迷离
6+
* @time 2018年8月10日
7+
* @version v1.0
8+
*/
9+
public class O1checkPowerOf2 {
10+
11+
public boolean checkPowerOf2(int n) {
12+
if (n <= 0) {
13+
return false;
14+
}
15+
return (n & (n - 1)) == 0;
16+
}
17+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/practice/SlidingWindowMedian.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package cn.edu.jxnu.practice;
2+
3+
import java.util.ArrayList;
4+
import java.util.TreeSet;
5+
6+
/**
7+
* 给定一个包含 n 个整数的数组，和一个大小为 k
8+
* 的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的中位数。(如果数组个数是偶数，则在该窗口排序数字后，返回第 N/2 个数字。)
9+
*
10+
* @author 梦境迷离.
11+
* @time 2018年8月2日
12+
* @version v1.0
13+
*/
14+
public class SlidingWindowMedian {
15+
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
16+
int n = nums.length;
17+
TreeSet<Node> minheap = new TreeSet<Node>();
18+
TreeSet<Node> maxheap = new TreeSet<Node>();
19+
ArrayList<Integer> result = new ArrayList<Integer>();
20+
21+
if (k == 0)
22+
return result;
23+
24+
int half = (k + 1) / 2;
25+
for (int i = 0; i < k - 1; i++) {
26+
add(minheap, maxheap, half, new Node(i, nums[i]));
27+
}
28+
for (int i = k - 1; i < n; i++) {
29+
add(minheap, maxheap, half, new Node(i, nums[i]));
30+
result.add(minheap.last().val);
31+
remove(minheap, maxheap, new Node(i - k + 1, nums[i - k + 1]));
32+
}
33+
return result;
34+
}
35+
36+
void add(TreeSet<Node> minheap, TreeSet<Node> maxheap, int size, Node node) {
37+
if (minheap.size() < size) {
38+
minheap.add(node);
39+
} else {
40+
maxheap.add(node);
41+
}
42+
if (minheap.size() == size) {
43+
if (maxheap.size() > 0 && minheap.last().val > maxheap.first().val) {
44+
Node s = minheap.last();
45+
Node b = maxheap.first();
46+
minheap.remove(s);
47+
maxheap.remove(b);
48+
minheap.add(b);
49+
maxheap.add(s);
50+
}
51+
}
52+
}
53+
54+
void remove(TreeSet<Node> minheap, TreeSet<Node> maxheap, Node node) {
55+
if (minheap.contains(node)) {
56+
minheap.remove(node);
57+
} else {
58+
maxheap.remove(node);
59+
}
60+
}
61+
}
62+
63+
class Node implements Comparable<Node> {
64+
int id;
65+
int val;
66+
67+
Node(int id, int val) {
68+
this.id = id;
69+
this.val = val;
70+
}
71+
72+
public int compareTo(Node other) {
73+
Node a = (Node) other;
74+
if (this.val == a.val) {
75+
return this.id - a.id;
76+
}
77+
return this.val - a.val;
78+
}
79+
}

0 commit comments

Comments
 (0)