翻转矩阵后的得分
题目：有一个二维矩阵 A 其中每个元素的值为 0 或 1 。移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。返回尽可能高的分数
示例：
输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
提示：
1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] 是 0 或 1
思路：虽然没什么必然的联系，但是这个题让我莫名其妙想到了了魔方。回归正题，首先想要数字大，肯定是尽可能的1多0少。又因为这个大小由最高位决定，所以肯定是可着最前面的1优先。大概的翻转要求应该就这样，剩下的就是看具体怎么转了。其实第一行肯定都要是1的。我去实际看下代码要怎么写。
第一版代码出来了，除了性能不好剩下没啥问题，我直接贴出来：
class Solution {
public int matrixScore(int[][] A) {
for(int i = 0;i<A.length;i++) {
if(A[i][0] == 0) {
for(int j = 0;j<A[0].length;j++) A[i][j] = Math.abs(A[i][j]-1);
}
}
for(int i = 1;i<A[0].length;i++) {
int one = 0;
for(int j = 0;j<A.length;j++) if(A[j][i] == 1) one++;
//这一列1少于一半，则翻转
if(one<=A.length/2) {
for(int j = 0;j<A.length;j++) A[j][i] = Math.abs(A[j][i]-1);
}
}
int res = 0;
for(int[] i : A) {
StringBuffer sb = new StringBuffer();
for(int j:i) sb.append(j);
res += Integer.parseUnsignedInt(sb.toString(), 2);
}
return res;
}
}
没啥技术含量，反正就是暴力法。唯一算得上思路的就是第一位一定要是1，所以不是1的就翻转。其余的就是这一列1多不管，0多翻转。我觉得我这个性能不好应该是处理上的。毕竟各种循环。但是我自己调优有点做不到了，我去看看性能第一的代码吧。
class Solution {
public int matrixScore(int[][] A) {
int m = A.length, n = A[0].length;
int ret = m * (1 << (n - 1));
for (int j = 1; j < n; j++) {
int nOnes = 0;
for (int i = 0; i < m; i++) {
if (A[i][0] == 1) {
nOnes += A[i][j];
} else {
nOnes += (1 - A[i][j]); // 如果这一行进行了行反转，则该元素的实际取值为 1 - A[i][j]
}
}
int k = Math.max(nOnes, m - nOnes);
ret += k * (1 << (n - j - 1));
}
return ret;
}
}
不出所料的处理上的优化，各种二进制操作简直是我的知识盲区。这个题就这样吧，下一题。
任务调度器
题目：给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
示例 3：
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]
思路：这个题的思路，可着出现次数最多的来，别的往它空闲的时候插入。当插无可差时就待机好了，有一个简单的思路。记录下一个固定元素要等待的时候，当前没有等待时间为0的就待机。我去代码实现试试。
第一版代码ac了,直接贴代码：
class Solution {
public int leastInterval(char[] tasks, int n) {
if(n == 0) return tasks.length;//没有间隔的话全部执行就完了
int[] count = new int[26];
for (int i = 0; i < tasks.length; i++) count[tasks[i]-'A']++;
Arrays.sort(count);
int maxCount = 1;
//最多元素的元素数有几个
for (int i = 24; i >= 0; i--) {
if(count[i] != count[25]) break;
maxCount++;
}
//这里注意一个计算，当元素正好或者中间要待机，应该是(最大数-1)*(间隔+1)+频率最高的个数是必须的。
//但是这里还有一种就是没有待机时间，所以这里直接返回tasks的长度就行了。
return Math.max((count[25] - 1) * (n + 1) + maxCount , tasks.length);
}
}
这个思路是要看的。其实写出来以后我觉得还可以细判断，但是我懒得判断了，我们通过间隔数和出现频率最多的元素数就可以判断出用不用有待机时间。没有待机时间直接返回数组长度，有的话才需要插入待机。这样才会用到这个公式：如果有待机时间说明是以频率最多的元素为基准：
X - - - X - - - X - - - X。
如上图。这个- - -是间隔时间，本质上算上X。应该是间隔时间+1算是一组。一共是有X的出现次数-1组。最后还要加上最后一个X。
这种情况是最高频率只有一个。但是如果有两个，就会变成：
X O - - X O - - X O - - X O。
这样的话，算法还是（间隔时间+1）*（X的次数-1），但是最后加的不是一个X，而是X O两个。这个2其实就是最多频率的元素数。
由此得出最后一个公式：
(count[25] - 1) * (n + 1) + maxCount
反正这个题的规律仔细看其实就能看出来，不算难，挺喜欢的一道题，下一题了。
将数组拆成斐波那契序列
题目：给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。形式上，斐波那契式序列是一个非负整数列表 F，且满足：0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；F.length >= 3；对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579"
输出：[123,456,579]
示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示：
1 <= S.length <= 200
字符串 S 中只含有数字。
思路：传说中的斐波那契数列。。动归的爸爸级。但是这个题应该没那么难，我初步的想法就是从后往前遍历。或者从前往后遍历。。最直观的想法就是回溯。毕竟这些个元素都要试数字的，怎么拆分啥的
一遍ac，直接贴代码：
class Solution {
int len;
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> res = new ArrayList<Integer>();
len = S.length();
return dfs(res,0,S)?res:new ArrayList<Integer>();
}
public boolean dfs(List<Integer> res,int idx,String s) {
int size = res.size();
//说明遍历完了，看总元素数是不是3个及以上
if(idx == len) return size>2;
int cur = 0;
for(int i = idx;i<len;i++) {
//第一个数是0不用往下判断了
if(s.charAt(idx)=='0' && i>idx) break;
cur = cur*10+(s.charAt(i)-48);
//溢出了，肯定不行
if(cur<0) break;
//回溯模板，当前元素添加进去。判断
if(size<2 || cur==res.get(size-1)+res.get(size-2)) {
res.add(cur);
if(dfs(res, i+1, s))return true;
res.remove(Integer.valueOf(cur));
}
}
return false;
}
}
其实代码还算是简单，主要是前面两个元素可以试数，后面的就看符合不符合规范了。但凡dfs代码走到false都说明是断层了，整个就fasle了，逻辑挺清楚的一个代码。这个性能超过百分之九十三的人了，我再去看看性能排行第一的代码吧，指不定有什么惊喜呢：
看完回来了，大概思路是一样的，就是代码的细节处理。我这里是每次都获取倒数两个list中的元素求和。人家是直接记录了，我先贴代码：
class Solution {
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> list = new ArrayList<Integer>();
boolean flag = backtrack(list, S, S.length(), 0, 0, 0);
if (flag) {
return list;
} else {
return new ArrayList<Integer>();
}
}
public boolean backtrack(List<Integer> list, String S, int length, int index, int sum, int prev) {
if (index == length) {
return list.size() >= 3;
}
long currLong = 0;
for (int i = index; i < length; i++) {
if (i > index && S.charAt(index) == '0') {
break;
}
currLong = currLong * 10 + S.charAt(i) - '0';
if (currLong > Integer.MAX_VALUE) {
break;
}
int curr = (int) currLong;
if (list.size() >= 2 && curr != sum) {
continue;
}
list.add(curr);
if (backtrack(list, S, length, i + 1, prev + curr, curr)) {
return true;
} else {
list.remove(list.size() - 1);
}
}
return false;
}
}
这个题就这样吧，感觉也没啥可说的了，标准的回溯。下一题。
设计循环队列
题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
思路：这种开放式题最烦的一点就是你实现了，别人也实现了，你是运气好所以才低空掠过的，别人是各种调优算法高性能完成甚至有点意犹未尽。。。哎，继续说这个题。demo中的前六个指令不说了，重点是这个deQueue()是移除了哪个元素啊。。。有点懵逼。。初步猜测把1删除了。4插入到1的位置了。然后下一个弹出的指针在2。。就这么循环的。计划这个题是双指针，一个指向存放的位置，一个指向删除的位置。我去代码试试。
思路完全没问题，实现起来比较麻烦但是也是粗心的原因，代码没啥难度。我直接贴代码：
class MyCircularQueue {
int[] arr;
int put;
int push;
int k;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
this.k = k;
this.arr = new int[k];
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if(put-push==k) return false;
arr[put++%k] = value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if(put==push) return false;
push++;
return true;
}
/** Get the front item from the queue. */
public int Front() {
//等于put说明当前没有元素。所以-1
if(push >= put) return -1;
return arr[push%k];
}
/** Get the last item from the queue. */
public int Rear() {
if(put == push) return -1;
return arr[(put-1)%k];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return put==push;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return put==(push+k);
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
这个题就是双指针，一个指向put的下标，一个指向push的下标。因为会绕圈，所以这里递增，然后取余。判断最大元素数不能超过k，最少元素数不能是-1就行了。不过因为细节很多，所以面向测试案例编程，一次发现个小bug，最终版反正性能还不错，对自己挺满意，哈哈。这种开放式的题目也没必要多说啥，反正就这样吧，下一题。
在二叉树中增加一行
题目：给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
题目截图
注意:
输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。
思路：说真的这种需求提出来怕不是要被打死的吧，太SB了。。至于这个题的实现。我打算用栈遍历的方式。到了这一层中间插入一层，其实我觉得不管是显式栈还是隐式dfs都可以实现的，但觉这种题也不至于卡性能，我直接去撸代码了。
不出所料的这个题，没有想得难，一次ac，我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
if(d == 1) {
TreeNode res = new TreeNode(v);
res.left = root;
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int h = 1;
while(!queue.isEmpty()) {
int size = queue.size();
if(h+1 < d) {//正常往下遍历
for(int i = 0;i<size;i++) {
TreeNode cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
}else {//到了这个父树节点，插入一层
for(int i = 0;i<size;i++) {
TreeNode cur = queue.poll();
TreeNode left = cur.left;
cur.left = new TreeNode(v);
cur.left.left = left;
TreeNode right = cur.right;
cur.right = new TreeNode(v);
cur.right.right = right;
}
return root;
}
h++;
}
return null;
}
}
就好像思路中说的，这个不管是循环还是dfs其实都可以实现的。我这里没用dfs。只要判断是不是要插入的那层就行了。我去看下性能排行第一的代码，没啥问题的话这个题可能就要直接过了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int depth, v;
TreeNode res;
public TreeNode addOneRow(TreeNode root, int v, int d) {
if(d==1){
TreeNode t = new TreeNode(v);
t.left = root;
return t;
}
depth = d-1;
this.v = v;
res = root;
dfs(root, 1);
return res;
}
public void dfs(TreeNode node, int dep){
if(node == null){
return;
}
dfs(node.left, dep+1);
dfs(node.right, dep+1);
if(dep == depth){
TreeNode l = node.left;
TreeNode r = node.right;
node.left = new TreeNode(v);
node.right = new TreeNode(v);
node.left.left = l;
node.right.right = r;
}
}
}
思路差不多，就不多说了，下一题。
网友评论