LeetCode Weekly Contest 48解题思路
LeetCode Weekly Contest 48解题思路
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1435742
LeetCode Weekly Contest 48解题思路
详细代码可以fork下Github上leetcode项目，不定期更新。
赛题
本次周赛主要分为以下4道题：
- Leetcode 671. Second Minimum Node In a Binary Tree
- Leetcode 669. Trim a Binary Search Tree
- Leetcode 670. Maximum Swap
- Leetcode 672. Bulb Switcher II
Leetcode 671. Second Minimum Node In a Binary Tree
Problem:
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.
思路：
树的遍历+排序
public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
nodes = new ArrayList<>();
go(root);
Collections.sort(nodes);
int min = nodes.get(0);
int nxt = -1;
for (int i = 1; i < nodes.size(); ++i){
if (nodes.get(i) > min){
nxt = nodes.get(i);
break;
}
}
return nxt;
}
List<Integer> nodes;
public void go(TreeNode root){
if (root == null) return;
go(root.left);
nodes.add(root.val);
go(root.right);
}使用TreeSet来排除重复元素，因为TreeSet自然维护key的顺序，所以输出的第二个元素即为答案。
代码如下：
public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
set = new TreeSet<>();
go(root);
if (set.size() < 2) return -1;
else{
set.pollFirst();
return set.first();
}
}
TreeSet<Integer> set;
public void go(TreeNode root){
if (root == null) return;
go(root.left);
set.add(root.val);
go(root.right);
}Leetcode 669. Trim a Binary Search Tree
Problem:
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in L, R. You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:undefined 1 / \ 0 2 L = 1 R = 2 Output:undefined 1 \ 2
思路：
首先该树是BST，所以如果根结点不在L和R之间（两种情况），那么根必然在它的左子结点或者右子结点，否则即为根。
接着连接与否看左右子结点是否满足L, R，满足进行连接。
代码如下：
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val < L){
return trimBST(root.right, L, R);
}
if (root.val > R){
return trimBST(root.left, L, R);
}
TreeNode ans = null;
if (root.val >= L && root.val <= R){
ans = new TreeNode(root.val);
}
if (root.left != null)
ans.left = trimBST(root.left, L, R);
if (root.right != null)
ans.right = trimBST(root.right, L, R);
return ans;
}当然我们可以进一步精简代码如下：
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val < L){
return trimBST(root.right, L, R);
}
else if (root.val > R){
return trimBST(root.left, L, R);
}
else {
TreeNode ans = new TreeNode(root.val);
ans.left = trimBST(root.left, L, R);
ans.right = trimBST(root.right, L, R);
return ans;
}
}Leetcode 670. Maximum Swap
Problem:
Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973 Output: 9973 Explanation: No swap.
思路：
因为只允许交换一次，那么自然是把最大的那一位换到第一位，如果第一位恰好是最大的，那么继续寻找次大的换到第二位，有一次成功交换即返回。当然还需要注意一点，如果最大位重复了，尽可能找位置小的进行交换。
代码如下：
public int maximumSwap(int num) {
String ns = String.valueOf(num);
char[] cs = ns.toCharArray();
int id = findMax(cs, 0, cs.length - 1);
int j = 0;
while (j < cs.length && cs[j] == cs[id]){
j ++;
id = findMax(cs, j, cs.length - 1);
}
if (j == cs.length) return num;
swap(cs, j, id);
int ans = 0;
for (int i = 0; i < cs.length; ++i){
ans = 10 * ans + (cs[i] - '0');
}
return ans;
}
public void swap(char[] cs, int i, int j){
char tmp = cs[i];
cs[i] = cs[j];
cs[j] = tmp;
}
public int findMax(char[] cs, int i, int j){
int id = i;
for (int l = i; l <= j; ++l){
if (cs[l] >= cs[id]){
id = l;
}
}
return id;
}好吧，再给一种思路，尝试任意一对进行交换，不断更新最大值，时间复杂度为O(n2)O(n^2)
代码如下：
public int maximumSwap(int num) {
char[] s = Integer.toString(num).toCharArray();
int n = s.length;
int max = -1;
for(int i = 0;i < n;i++){
for(int j = i;j < n;j++){
{char d = s[i]; s[i] = s[j]; s[j] = d;}
max = Math.max(max, Integer.parseInt(new String(s)));
{char d = s[i]; s[i] = s[j]; s[j] = d;}
}
}
return max;
}还可以用一个bucket来记录每个数字的最后一位来替代寻找最小digit的id，这样时间复杂可以降为O(n)O(n)
代码如下：
public int maximumSwap(int num) {
char[] cs = String.valueOf(num).toCharArray();
int[] bucket = new int[10];
for (int i = 0; i < cs.length; ++i){
bucket[cs[i] - '0'] = i;
}
outer :for (int j = 0; j < cs.length; ++j){
for (int i = 9; i > cs[j] - '0'; --i){
if (bucket[i] > j){
char tmp = cs[bucket[i]];
cs[bucket[i]] = cs[j];
cs[j] = tmp;
break outer;
}
}
}
return Integer.valueOf(new String(cs));
}Leetcode 672. Bulb Switcher II
Problem:
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be. Suppose n lights are labeled as number 1, 2, 3 …, n, function of these 4 buttons are given below:
- Flip all the lights.
- Flip lights with even numbers.
- Flip lights with odd numbers.
- Flip lights with (3k + 1) numbers, k = 0, 1, 2, …
Example 1:
Input: n = 1, m = 1. Output: 2 Explanation: Status can be: on, off
Example 2:
Input: n = 2, m = 1. Output: 3 Explanation: Status can be: on, off, off, on, off, off
Example 3:
Input: n = 3, m = 1. Output: 4 Explanation: Status can be: off, on, off, on, off, on, off, off, off, off, on, on.
思路：
不要被n和m骗了，很容易想到m超过4之后，就“没用”了，比如当m=4时，可以是四种操作的组合，但对其任何操作+1次时，将回到m=3的情况（等于没有按那个按钮）。所以，我们只要遍历2^4 = 16种情况即可。
接着n的大小是否相关？可以通过对n枚举来判断，但还是觉得不够严谨，此题不如这样，把n分成（n1和n2）两部分，这样一来，我们可以根据不同的按钮操作得到n1的不同状态，那么n2是独立与n1么？
显然不是那么一回事，对n1状态的记录可以推出n2的状态（待证明），所以我们反过来思考，假设n很大很大，那么对其所有的操作得到了一个状态集合，那么把n截到20，它的状态集合个数依旧不变（没能力在截断时，生成新的状态）。
所以，有了咱们的遍历代码：
public int flipLights(int n, int m) {
n = Math.min(n, 16);
Set<Integer> ans = new HashSet<Integer>();
ans.add((1 << n) - 1);
for (int i = 0; i < 1 << 4; ++i){
int state = (1 << n) - 1;
int mask = (1 << n) - 1;
if (Integer.bitCount(i) <= m){
if ((i >> 4 & 1) != 0){
state = (~state & mask);
}
if ((i >> 3 & 1) != 0){
state = (state ^ 0x5555) & mask;
}
if ((i >> 2 & 1) != 0){
state = (state ^ 0xAAAA) & mask;
}
if ((i >> 1 & 1) != 0){
state = (state ^ 0x9249) & mask;
}
ans.add(state);
}
}
return ans.size();
}当然，你可以死算，枚举各种情况（不推荐）。
代码如下：
public int flipLights(int n, int m) {
if(m==0) return 1;
if(n==1) return 2;
if(n==2&&m==1) return 3;
if(n==2) return 4;
if(m==1) return 4;
if(m==2) return 7;
if(m>=3) return 8;
return 8;
}