重塑矩阵
题目:在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例 1:
输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:
输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：
给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
思路：这道题依然有不明白的地方。我在不断的用测试案例测试。测试的结果好像就是把之前已有的元素重新排列。不能多一个元素也不能少一个元素、其实按照面积来讲就是面积要不变。比如3-4.可以变成4-3,2-6,6-2,1-12,12-1这种。剩下的就是顺序往里填充数而已。感觉也没那么难啊。个人思路先判断长乘宽，如果面积变了直接返回原矩形，面积不变再顺序填充。我去做做看。
思路是对的，就是性能差点：
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
if(nums.length*nums[0].length!=r*c) return nums;
int[] arr = new int[nums.length*nums[0].length];
int index = 0;
for(int i = 0;i<nums.length;i++){
for(int j = 0;j<nums[0].length;j++){
arr[index] = nums[i][j];
index++;
}
}
index = 0;
int [][] res = new int[r][c];
for(int k = 0;k<r;k++){
for(int l = 0;l<c;l++){
res[k][l]=arr[index];
index++;
}
}
return res;
}
}
如图所示逻辑，第一步判断能不能改，不能改直接返回原数组。第二部原数组元素都取出来排序，再顺序往新数组里面填充。
我感觉我这个取出再放的过程可能是影响性能的主要原因。其实应该是可以做到直接从原数组取出直接存。数组下标也是有规律的，我去想想能怎么优化：
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
if(nums.length*nums[0].length!=r*c) return nums;
int [][] res = new int[r][c];
for(int k = 0;k<r;k++){
for(int l = 0;l<c;l++){
int n = k*c+l;
res[k][l]=nums[n/nums[0].length][n%nums[0].length];
}
}
return res;
}
}
优化版，代码大大的省略，两个循环变成一个，然而，性能并么有任何进步！我还是直接看性能第一的代码吧。代码逻辑差不多，只不过多了1ms而已，差了百分之五十的排名，啧啧。。
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int row = nums.length;
int col = nums[0].length;
if (row * col != r * c) {
return nums;
}
int[][] ans = new int[r][c];
int k = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ans[k/c][k%c] = nums[i][j];
k++;
}
}
return ans;
}
}
另一个树的子树
题目：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
题目截图
题目截图
思路：这个题，我个人思路遍历s，并每个节点和t判断是否相等，有相等则返回true，遍历完都没true则返回false。
嗯，思路对的，这是是双递归。首先提出一个方法递归判断两个节点是否相等（判断节点值和左右节点直到都为叶子节点）。然后另一个主方法要递归s的节点直到为null或者有和s相等的节点。直接上代码：
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s==null && t==null) return true;
if(s==null || t==null) return false;
return isSameTree(s,t)||isSubtree(s.left,t) || isSubtree(s.right,t);
}
public boolean isSameTree(TreeNode s, TreeNode t){
if(s==t) return true;
if(s != null && t != null && s.val == t.val){
return isSameTree(s.left,t.left)&&isSameTree(s.right,t.right);
}
return false;
}
}
分糖果
题目：给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:
输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
示例 2 :
输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
注意:
数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。
思路：这个题很简单啊，不就是一共看有多少种糖果，如果糖果数不小于于总数的一半，妹妹可以分到总数一半的种类水果、（给弟弟的都是边角料）。如果种类不大于总数的一半，妹妹可以获得所有种类的水果。我去写代码
class Solution {
public int distributeCandies(int[] candies) {
Set<Integer> set = new TreeSet<Integer>();
for(int i:candies){
set.add(i);
}
return set.size()>=candies.length/2?candies.length/2:set.size();
}
}
这里用到了set的不存重复元素的特性。简单明了性能不好。对，性能不好。。我估计是因为我用了set的原因。看了性能排行第一的代码。就是一个手动计算数组不重复个数的过程。怎么说呢，好几个循环，但是因为没用现成数据结构性能还是不错的，但是基于开发效率的考虑（我不承认是我懒），我还是不照着那种想法写了。下一题吧。
最短无序连续子数组
题目：给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
思路：就是判断前面的元素是否是最小的升序排序，后面的元素是否是最大的升序排序？感觉看着很简单，实践起来应该不容易。我理理思路。
理完思路了，就是另外复制此数组升序排列，对比前面的后面的元素，恰好在其位置不用重拍，不然要排序。
class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] temp = new int[nums.length];
for(int i = 0;i<nums.length;i++ ){
temp[i]=nums[i];
}
Arrays.sort(temp);
int left = 0;
int right = nums.length-1;
while(left<right){
if(temp[left] == nums[left]){
left++;
}else{
break;
}
}
//说明正好升序，则不需要子串了
if(left==right) return 0;
//能走到这说明肯定不是自然升序，等break就行了
while(true){
if(temp[right] == nums[right]){
right--;
left++;
}else{
break;
}
}
return nums.length-left;
}
}
性能依然不行，但是起码我自己明白逻辑了。不用看我都知道我是哪里导致的性能不行。就是这个Arrays.sort()呗。我去看看性能好的代码：emmmm....很复杂，就是简单地东西复杂化了我觉得。
思路第一遍遍历：如果后面的比前面的小说明需要更换位置，所以最右边的更换点就是这个位置不对的元素的下标。如果最后一个是最大值则不会走进if中，R也就不会变。同理倒数第二个位置也对的话也不会触发if，R也不会变。所以能确定R就是需要交换的后面的那个元素位置。
同样的道理判断前面的，如果前面的小于后面的说明位置对了，不会进入if，不会改变L。当位置不对，也就是前面的值小于后面的才会进入if，L保存的就是需要交换的左边的值。
整个子集的长度就是右边元素-左边元素+1（这个+1的原因是要包含左右的。）另外一种情况就是L=R说明自然顺序。两个都是0，所以不需要交换，直接返回0.
class Solution {
public int findUnsortedSubarray(int[] arr) {
if(arr == null || arr.length < 2){
return 0;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int R = 0;
int L = 0;
for (int i = 0; i < arr.length; i++) {
if(max > arr[i]) {
R = i;
}
max = Math.max(max, arr[i]);
}
for (int i = arr.length - 1; i >= 0; i--) {
if(min < arr[i]) {
L = i;
}
min = Math.min(min, arr[i]);
}
return R == L ? 0 : R - L + 1;
}
}
自己做用了五分钟，看别人代码理思路用了半个小时，哎，我现在越来越会偷懒了。
N叉树的前序遍历
题目：给定一个 N 叉树，返回其节点值的前序遍历。
题目
思路：emmmmm...这个题我做过，昨天做了一个N叉树的最大深度。刚刚为了回忆又重新做了一下那个题。做过的记住了，很欣慰。继续说当时在各种调试测试的时候我不知不觉已经完成过这道题了。所以接下来直接写代码了。
N叉树的最大深度
很喜欢这种送分题啊，双百，美滋滋~~直接贴代码：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
getAllNode(root,list);
return list;
}
public void getAllNode(Node root,List<Integer> list){
if(root==null) return;
list.add(root.val);
for(int i = 0;i<root.children.size();i++){
getAllNode(root.children.get(i),list);
}
}
}
image.png
这道题没啥好讲的，就是N叉树的遍历。虽然题目让我迭代，但是迭代用的Queue真的头疼。。我还是递归了。接下来尽量试试迭代的方法实现：
第一版本的递归实现完了，然后不对。我这个是按照层级来遍历的，但是结果要求是按照分支前序遍历的。。我寻思寻思怎么改（附上层级遍历的代码以做参考）：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()){
Node n = queue.poll();
if(n!=null) list.add(n.val);
if(n!=null && n.children.size()>0){
for(int i =0;i<n.children.size();i++){
queue.add(n.children.get(i));
}
}
}
return list;
}
}
我觉得我的问题应该是在queue取值这错了，不应该一层层往里放，应该可着一个节点拿到没。我去改了，改不完了，完全不知道怎么写，所以看了题解，队列不行，这里人家用的都是栈。。。再回忆一下栈和队列的区别：栈：先入后出。队列先入先出。回忆完毕，换栈去实现看看。
从双百到只超过百分之11，鬼知道我心里路程哟~！
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
Stack<Node> stack = new Stack<Node>();
if(root==null) return list;
stack.push(root);
while(!stack.isEmpty()){
Node n = stack.pop();
list.add(n.val);
if(n!=null && n.children.size()>0){
for(int i =n.children.size()-1;i>=0;i--){
stack.push(n.children.get(i));
}
}
}
return list;
}
}
这里有几点需要注意：最主要的就是这个push要从最后往前push。这样取的时候才能从前往后取出来。哎，关于栈其实我还是不咋熟。看评论里的大佬说的贼清楚：所谓递归实际是调用了隐式栈 所以转换成迭代也仅仅需要把栈显式化罢了？？？？反正我现在才知道递归就是调用隐式栈。。感觉越做题不会的越多，哎。
N叉树的后序遍历
题目：给定一个 N 叉树，返回其节点值的后序遍历。
题目
思路：我有一个比较害羞的新想法，就是上面那道题的答案reverse一下。哈哈。其实理论上讲就是上面那道题的反转吧，不管是递归还是迭代都可以照着思路逆着来？我去试试。
第一版本的递归一次成功：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Integer> list = new LinkedList<Integer>();
addAllNode(root,list);
return list;
}
public void addAllNode(Node root,LinkedList<Integer> list){
if(root==null) return;
list.addFirst(root.val);
for(int i =root.children.size()-1;i>=0;i--){
addAllNode(root.children.get(i),list);
}
}
}
第二版本的迭代我去碰运气：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Integer> res = new LinkedList<Integer>();
Stack<Node> stack = new Stack<Node>();
if(root==null) return res;
stack.push(root);
while(!stack.isEmpty()){
Node n = stack.pop();
res.addFirst(n.val);
if(n!=null && n.children.size()>0){
for(int i = 0;i<n.children.size();i++){
stack.push(n.children.get(i));
}
}
}
return res;
}
}
完全上一道题的反着来的代码，一点可说的都没有。
这篇笔记就到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论