896. Monotonic Array
https://leetcode.com/contest/weekly-contest-100/problems/monotonic-array/
这道题就是判断是不是单调非减或单调非增。要注意的是边界条件。
public boolean isMonotonic(int[] A) {
int l = A.length;
if(l == 1) return true;
Boolean up = null;
for(int i = 0; i < l-1; i++){
if(A[i] == A[i+1]) continue;
if(up == null){
up = A[i] < A[i+1];
}else if((A[i] < A[i+1]) != up) return false;
}
return true;
}
897. Increasing Order Search Tree
https://leetcode.com/contest/weekly-contest-100/problems/increasing-order-search-tree/
这道题要按顺序构成BST，那么其实就是把BST通过中序遍历，转换为链表，同时不用左孩子。
List<TreeNode> l = new ArrayList<>();
public TreeNode increasingBST(TreeNode root) {
if(root == null) return null;
inOrder(root);
for(int i = 0; i < l.size()-1; i++){
TreeNode cur = l.get(i);
cur.left = null;
cur.right = l.get(i+1);
}
return l.get(0);
}
private void inOrder(TreeNode root){
if(root == null) return ;
inOrder(root.left);
l.add(root);
inOrder(root.right);
}
优化下解法,把LIST 的空间给节约了
TreeNode pre = null;
TreeNode r = null;
public TreeNode increasingBST(TreeNode root) {
if(root == null) return null;
inOrder(root);
pre.left = null;
pre.right = null;
return r;
}
private void inOrder(TreeNode root){
if(root == null) return ;
inOrder(root.left);
if(r == null) r = root;
if(pre != null){
pre.left = null;
pre.right = root;
}
pre = root;
inOrder(root.right);
}
898. Bitwise ORs of Subarrays
https://leetcode.com/contest/weekly-contest-100/problems/bitwise-ors-of-subarrays/
这道题消耗了我大量时间，感觉比HARD的那道还要难些。HARD的难道，就一个TRICK其实挺简单。
我们来分析下这道。
常规的暴力解法就是N^2,在50000的数据量下一定不过。
想到位运算，就想到能否用到常数32，随后接着想或运算，是只加不减。就是你没法通过或运算来让一个大的数变小。
根据这个性质我们知道，对一个数来说，他最大能变到的就是每个位都置为1了。那么这个时间复杂度就能变成O 32N
时间复杂度够了。我们该怎么求解呢。
用常规O N^2的解法，最后一次遍历，也就是最后一个单独元素加进SET里。
那么我可以反过来处理这个情况。先从最后一个单独元素开始，再从每一次产生的解，去和左边的那个元素或。又产生一批新的后。再放进去总结果集，依次循环。
public int subarrayBitwiseORs(int[] A) {
int l = A.length;
Set<Integer> s = new HashSet<>();
Set<Integer> pre = new HashSet<>();
for(int i = l-1; i >= 0; i--){
int cur = A[i];
Set<Integer> now = new HashSet<>();
now.add(cur);
for(int j : pre){
now.add((j|cur));
}
for(int j : now) s.add(j);
pre = now;
}
return s.size();
}
思考 如果是AND 应该怎么改这个算法呢？
public int subarrayBitwiseORs(int[] A) {
int l = A.length;
Set<Integer> s = new HashSet<>();
Set<Integer> pre = new HashSet<>();
for(int i = l-1; i >= 0; i--){
int cur = A[i];
Set<Integer> now = new HashSet<>();
now.add(cur);
for(int j : pre){
now.add((j&cur));
}
for(int j : now) s.add(j);
pre = now;
}
return s.size();
}
899. Orderly Queue
https://leetcode.com/problems/orderly-queue/description/
这道题就是给你个K，说只有前K个，你可以挑一个移动到最后，然后可以移动任意次。求最小的字母序。
当K>=2，证明等价于可以交换任意2个字母。
我们假设要交换的2个字母0<=i < j <l。 分别是第I个 和 第J个。
就会有如下结构
数组结构： [L] I [M] J [R]
一直把第一个放到最后 -》I [M] J [R][L]
一直把第二个放到最后-》I J [R][L][M]
把I 放最后 -》J [R][L][M] I
永远把第二个放到最后 -》 J [M] I [R] [L]
一直把第一个放最后 -》 [L] J[M] I [R]
完成。
public String orderlyQueue(String S, int K) {
String min = S;
if(K == 1){
for(int i = 1; i < S.length(); i++){
String cur = S.substring(1)+S.charAt(0);
if(cur.compareTo(min)<0) min = cur;
S = cur;
}
return min;
}
char[] cs = S.toCharArray();
Arrays.sort(cs);
String tar = new String(cs);
return tar;
}
