LeetCode 集锦（二十五） - 第 108 题 Convert Sorted Array To Binary Search Tree

发表于 2019-06-12 | 分类于算法 |

问题

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

 Example:


Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

翻译:

给定一个按升序排列元素的数组，将其转换为高度平衡的BST。
对于该问题，高度平衡二叉树定义为每个节点的两个子树深度相差不超过1的二叉树。
例子:
给定排序后的数组:[-10，-3,0,5,9]，
一个可能的答案是:[0，-3,9，-10,null,5]，表示高度平衡BST:
1
2
3
4
5
6
>      0
>     / \
>   -3   9
>   /   /
> -10  5
>

解题思路

本题是相对而言比较复杂，需要一个高度平衡的二叉树，但是这边参数很特定，是一个排序的数组，排序的数组，变成高度平衡的二叉树，那不是只要对半折开就好了嘛，那不就是一颗树了嘛？

解题方法

按照分治法

public TreeNode sortedArrayToBST(int[] nums) {
     if (nums.length <= 0) {
         return null;
     }
     return sortedArrayToBST(nums, 0, nums.length - 1);


 }


 private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
     if (left > right) {
         return null;
     }
     if (left == right) {
         return new TreeNode(nums[left]);
     }
     int mid = (left + right+1) / 2;
     TreeNode leftNode = sortedArrayToBST(nums, left, mid - 1);
     TreeNode rightNode = sortedArrayToBST(nums, mid + 1, right);
     TreeNode treeNode = new TreeNode(nums[mid]);
     treeNode.left = leftNode;
     treeNode.right = rightNode;
     return treeNode;

 }

时间复杂度: 该方案用了二分法的方式，所以为O(n)=O(nlogn)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，根据二分法的方式，来解决对半拆分的情况。其实这边应该是有规律的，比如应该是和中间节点是有倍数关系的，但是具体我也没有去验证。

LeetCode 集锦（二十六） - 第 110 题 Balanced Binary Tree

发表于 2019-06-12 | 分类于算法 |

问题

Given a binary tree, determine if it is height-balanced. 

 For this problem, a height-balanced binary tree is defined as: 

 a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 

 Example 1: 

 Given the following tree [3,9,20,null,null,15,7]: 

    3
   / \
  9  20
    /  \
   15   7 

 Return true. 
Example 2: 
 Given the following tree [1,2,2,3,3,null,null,4,4]: 

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

 Return false.

翻译:

给定一个二叉树，判断它是否高度平衡。
对于该问题，定义高度平衡二叉树为:
一种二叉树，其中每个节点的两个子树的深度相差不超过1。
示例1:
给定如下树[3,9,20,null,null,15,7]:
1
2
3
4
5
6
>    3
>   / \
>  9  20
>    /  \
>   15   7 
>

返回 true
示例2:
给定如下树[1,2,2,3,3,null,null,4,4]:
1
2
3
4
5
6
7
8
>       1
>      / \
>     2   2
>    / \
>   3   3
>  / \
> 4   4
>

返回 false

解题思路

本题是相对而言比较简单，判断一棵树是不是平衡二叉树。平衡二叉树的限制条件就是一个树的每个节点的左右子节点的深度相差不能超过1。按照这个思路，其实可以递归遍历出每个树节点的深度，判断左右节点是否差过1，就ok了

解题方法

按照分治法

public boolean isBalanced(TreeNode root) {
     if (root == null) {
         return true;
     }
     return deap(root) != -1;

 }

 private int deap(TreeNode root) {
     if (root == null) {
         return 0;
     }

     int left = deap(root.left) + 1;

     int right = deap(root.right) + 1;
     if (left == 0 || right == 0) {
         return -1;
     }
     if (Math.abs(left - right) > 1) {
         return -1;
     }
     return Math.max(left, right);
 }

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，通过遍历的方式，来获取左右节点的高度，判断是否相差1，其实这边还可以优化，那就是获取高度的时候是不是0，如果不符合了就不需要在走下面的方式了。

java基础(一)-面向对象思想

发表于 2019-06-11 | 分类于 java |

前言

java是一门面向对象的语言，在学习java前，先要理解面向对象这个概念，区别于c这类的面向过程语言，面向对象有着什么一样的特点呢？先上一张思维导图吧：
面向对象思维导图

对象

什么是对象

问题空间中的元素及其在解空间中的表示

这句话摘抄自java编程思想，是一句很难理解的话语（果然大佬的总结概括不是一般的抽象）。那么什么是问题空间？什么是在解空间呢？

问题空间：问题空间是问题解决者对一个问题所达到的全部认识状态，它是由问题解决者利用问题所包含的信息和已贮存的信息主动地构成的。一般来说包括3部分：
- 初始状态 – 开始时的不完全的信息或令人不满意的状况，
- 目标状态 – 你希望获得的信息或状态或者说是目标状态
- 操作 –为了从初始状态迈向目标状态，你可能采取的步骤
如果拿方法来类比这段内容，初始状态也就是入参，目标状态是结果或者返回值，操作就是方法体啦。
在解空间：emmmm这个没有找到具体的解释，不过有解空间的解释，应该类似：n元齐次线性方程组的解集S={x|Ax=0}是一个向量空间，称为齐次线性方程组的解空间。相当于问题的结果集。
大致概念解释完成了，貌似还是不好理解，用个人的话来讲：问题空间其实就是我们的问题，这个问题有什么条件，运算的过程，和问题解决后的状态。问题空间的元素都可以是一个对象。对象可以是一个有着独立特性的实体。解空间就是结果集了。问题的结果也是一个对象。简单的说，对象其实就是一个可描述的实体，一个可描述的实体都可以是对象

对象的五个基本特性

万物皆对象（也就是所以可以描述的实体都可以是一个对象）
程序是对象的集合，它们通过发送消息的方式告知彼此要做的事情（发送消息其实就是方法的调用，或者通知）
每个对象都有着自己的以及其他对象所构成的存储（对象的构成可以是其他的对象组合，或者自己本身的一下特性组合而成）
每个对象都有着其类型：对象都有着自己的归属标示，比如它是属于那一类的对象，是人还是其他的可描述的类别。每一个对象都是其归属标示的一个实例
某一特定类型的所有对象都可以接收相同的信息（也就是它们对外开发的通信方式都是一致的）

以上就是对象的全部概念了，解释完了对象，那就要解释下对象的归属标示了，在java中这个称之为类

什么是类

在上文有提到过每个对象都拥有其类型，这个类型在java中称之为类，类是具有相同特性（数据元素和行为）的对象集合

数据元素：我们一般当成特征，即该对象中有着那些属性来描述，比如长方形的长和宽。
行为：是方法的总称，如果我们把对象比作个体，那么方法就是个体可以做的事情，拥有的行为

上文解释了对象的概念，但是我们主要还是讲解一下面向对象，所有来解释下面向对象的内容吧。

面向对象

什么是面向对象

面向对象思想可以看作一种在程序中包含各种独立而又互相调用的对象的思想。
与面向过程的做法不同，面向过程我们可以理解为流水线似操作，类似与我们现在机器化操作，对应特定过程，制定特定的方法。而面向对象就不同了，面向对象是基于对象，也就是说由对象的相互交流，协作来完成问题的解决，相当于我们的工人们做一些活，他们有着自己的技能，可以适用与不同的场景，交互配合实现。
面向对象和面向过程区别
第一眼看貌似都是一样，无非就是面向对象多了一个维修工多概念，没错，维修工其实就是一个对象，面向对象把流程的实现都封装到了对象中，由对象的行为或者属性来处理问题。维修工是一个归类，不同的维修工是其具体表现。对于场景，流程是不会变的，更多是变化细节，在面向过程中，没错改动就是修改流程，而面向对象则是修改其行为，似的该对象的行为能适配流程。具有很强的灵活性和可维护性

面向对象的三大特征

封装
隐藏一切可隐藏的细节，只暴露最简单的行为。也就是说通信方不需要知道被通信方的实现，只需要知道如何通信即可，也就是被通信方的实现对通信方而言是透明对
在java中，我们一般只会暴露类的api，而不会告知是如何实现的，对于调用方而言，实现细节都是透明的。
继承
继承指的是一种能力，是由当前类派生出新类的过程，可以在现有类的基础上构建新的类。
在java中：由继承创建的新类我们统称为子类/派生类；而被继承的类称为父类/基类。Object是所有的父类。还有一点java中，是单继承模式的。
多态
是同一种行为具有不同表现活形态的能力，是对象的多种表现能力的体现。
多态基础是继承，允许子对象赋予父对象不同的能力。
形成多态的条件有：
1. 继承基类
2. 重写
3. 父类引用指向子类对象
  在java中与多态有关系的是重写：由子类重新定义父类的行为，也就是条件2。而重载却不是，重载是类内部多个相同行为，不同参数的一个多样化。和多态没有关系。

面向对象的5大原则

S.O.L.I.D简称面向对象的5大原则，分别是：单一原则，开放封闭原则，里氏替换原则，接口隔离原则，依赖倒置原则。虽然大多数我们在编写程序的时候是不太会记得这些原则，这些原则也不应该使用在编写程序上，而是在设计程序上面。准确来说，这是一个基本的优化原则。

单一原则

指某一个类的功能，职责要单一，不能包罗万象。

也就是对于类要足够的细化，对行为足够的明确，隔离不必要的行为。

开放封闭原则

一个模块在扩展性方面应该是开放的，而在更改性上面应该是封闭的。

这个其实很好理解，比如我们在一个模块中需要新增一个功能（不是扩展性的），而这个新功能和其中一个功能有很大一部分相似，一般情况下，我们修改下原接口，多个特判形式的编写，其实就可以解决问题，但是这样子做不符合开放封闭原则。我们不应该在更改上面是开放的，改动之前的逻辑，而是应该新开一个接口，扩展功能，并把两部分相同的地方抽象出来。
里氏替换原则

子类可以出现在父类能够出现的任何地方，并代替它

这句话就是父类能使用的地方，子类也都可以代替它。
依赖倒置原则

实体必须依赖抽象而不是具体实现

这个就不太好理解了,换个方式说:

高层次的模块不应该依赖低层次的实现
高层次的模块应该依赖抽象
emmm更加不好理解了，最简单的来说，就是程序应该依赖抽象接口，而不是依赖具体的实现。拿很简单的例子而言，我们在代码中声明对象的时候，是否都是XXX x=new XXX(),其实这种就是依赖了具体的实现，因为后面指待的就是特定的XXX类，那么应该怎么样的？这边就要借助设计模式中的抽象工厂模式（注意是抽象哦，因为不依赖具体的实现），利用工厂模式来代替直接声明，这样子做有个很大好处，一旦某一天XXX类要被替换了，那安装之前的方式，我们是不是要该全部XXX类所在的地方？这样子很容易出现遗漏。而利用了抽象工厂模式，我们其实只要该该工厂模式内部的实现一个地方就好了，如果要替换工厂模式，也直接替换工厂模式的实现就好了（所以为嘛是抽象工厂模式了），这样程序就有很好的扩展性和灵活性。

接口隔离原则

拆分非常庞大臃肿的接口成为更小和更具体的接口

个人理解上呢，这个相当于是接口的单一原则，也就是接口的职责要足够细化，功能单一，这样子使用方就不需要依赖它实现不使用的方法了

总结

大致内容就这样子描述完了，这章基本描述了对象，面向对象思想里面的部分内容，讲了大概的概念，全是文字，好枯燥的呦。

LeetCode 集锦（二十四） - 第 107 题 Binary Tree Level Order Traversal

发表于 2019-06-10 | 分类于算法 |

问题

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). 
For example: 
Given binary tree [3,9,20,null,null,15,7], 
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as: 
[
  [15,7],
  [9,20],
  [3]
]

翻译:

给定一个二叉树，返回其节点值的自底向上顺序遍历。(即从左到右，从叶到根，一层一层地)。

例如:
给定二叉树[3,9,20,null,null,15,7]，
1
2
3
4
5
6
>   3
>  / \
> 9  20
>   /  \
>  15   7 
>

返回自底向上的顺序遍历，如下:
[
[15,7],
[9,20],
[3]
]

解题思路

本题是倒叙输出一棵树的层次，哎呦，不就是层级遍历嘛，上一篇刚刚写过，至于倒序，那就是小问题了。咱们用linkedArrayList代替队列（虽然是由这个实现的，但是没有用到队列的特点。所以直接用了list，这边使用替换，代替了上次操作的remove，相对来说，效率会好一点

解题方法

按照层级遍历的方式

public List<List<Integer>> levelOrderBottom(TreeNode root) {
     if (root == null) {
         return new ArrayList<>();
     }
     List<List<Integer>> lists = new LinkedList<>();
     List<TreeNode> queue = new LinkedList<>();
     List<Integer> list = new ArrayList<>();
     list.add(root.val);
     lists.add(list);
     putNode(root, queue);
     while (queue.size() > 0) {
         List<Integer> resultTmep = new ArrayList<>();
         List<TreeNode> temp = new LinkedList<>();
         for (TreeNode treeNode : queue) {
             resultTmep.add(treeNode.val);
             putNode(treeNode, temp);
         }
         queue = temp;
         lists.add(0,resultTmep);
     }
     return lists;


 }

 private void putNode(TreeNode treeNode, List<TreeNode> list) {

     if (treeNode == null) {
         return;
     }
     if (treeNode.left != null) {
         list.add(treeNode.left);
     }
     if (treeNode.right != null) {
         list.add(treeNode.right);
     }
 }

时间复杂度: 该方案用了层级遍历的方式，时间复杂度相当于每一个的遍历，所以为O(n)=O(n)

空间复杂度: 该方案使用了额外的空间，使用了数组暂存树，相当于把树转化为了数组，所以空间复杂度O(n)=O(n)

总结

本题的大致解法如上所诉，相对于空间开销是差不多，效率提升不少，果然remove还是有点麻烦的。

LeetCode 集锦（二十三） - 第 104 题 Maximum Depth of Binary Tree

发表于 2019-06-09 | 分类于算法 |

问题

Given a binary tree, find its maximum depth. 

 The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 

 Note: A leaf is a node with no children. 

 Example: 

 Given binary tree [3,9,20,null,null,15,7], 

    3
   / \
  9  20
    /  \
   15   7 

 return its depth = 3.

翻译:

给定一个二叉树，求它的最大深度。
最大深度是从根节点到最远叶节点的最长路径上的节点数。
注意:叶子是没有子节点的节点。
例子:
给定二叉树[3,9,20,null,null,15,7]，
1
2
3
4
5
6
>   3
>  / \
> 9  20
>   /  \
>  15   7 
>

返回结果是3

解题思路

本题是获取一棵树的深度，一般设计到树到题还是有点麻烦到，第一步想到算深度？是否可以按层级遍历，不就知道有多少层了嘛。这是一种方式，但是换一个角度想，一棵树的深度，不就是由它的左右节点决定的嘛，如果有左右节点就加一，同理，左右节点的深度又是由它们的子左右节点决定的，选择大的那个深度值，貌似就可以解决此题了

解题方法

按照层级遍历的方式

public int maxDepth(TreeNode root) {

    if (root == null) {
        return 0;
    }
    int result = 1;
    //定义一个队列
    List<TreeNode> list = new LinkedList<>();
    putNode(root, list);
    while (list.size() > 0) {
        //通过遍历的方式把队列里面的数据获取，并把左右子节点塞入
        int size = list.size();
        while (--size >= 0) {
            TreeNode treeNode = list.get(size);
            putNode(treeNode, list);
            list.remove(size);
        }
        result++;
    }
    return result;

}

private void putNode(TreeNode treeNode, List<TreeNode> list) {

    if (treeNode == null) {
        return;
    }
    if (treeNode.left != null) {
        list.add(treeNode.left);
    }
    if (treeNode.right != null) {
        list.add(treeNode.right);
    }
}

class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;

   TreeNode(int x) {
       val = x;
   }
}

时间复杂度: 该方案用了层级遍历的方式，时间复杂度相当于每一个的遍历，所以为O(n)=O(n)

空间复杂度: 该方案使用了额外的空间，使用了数组暂存树，相当于把树转化为了数组，所以空间复杂度O(n)=O(n)

递归分治法：

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}


public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

时间复杂度: 该方案用了递归遍历的方式，时间复杂度相当于每一个的遍历，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，按层级遍历其实效果不怎么理想，个人估计是remove的操作导致的，如果可以不删除，直接数组代替树，效果可能会好一点。

LeetCode 集锦（二十二） - 第 101 题 Symmetric Tree

发表于 2019-06-08 | 分类于算法 |

问题

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

 For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3




 But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

 Note:
Bonus points if you could solve it both recursively and iteratively.

翻译:

给定一个二叉树，检查它是否是自身的镜像(即围绕其中心对称)。
例如，这个二叉树[1,2,2,3,4,4,3]是对称的:
1
2
3
4
5
6
7
>     1
>    / \
>   2   2
>  / \ / \
> 3  4 4  3
>
>

但是下面的[1,2,2,null,3,null,3]不是:
1
2
3
4
5
6
>    1
>   / \
>  2   2
>   \   \
>   3    3
>

注意:
如果你能递归地和迭代地解出它，那就更好了。

解题思路

本题判断两个树是否镜像树，镜像树的特点，在于它的左节点和右节点是一样的，根据这个特点我们可以解决这个问题。

解题方法

按照思路代码如下

 public boolean isSymmetric(TreeNode root) {
     if (root == null) {
         return true;
     }

     return isSymmetric(root.left, root.right);

 }

 public boolean isSymmetric(TreeNode left, TreeNode right) {

     if (left == null && right == null) {
         return true;
     }

     boolean isSame = left == null;
     isSame = isSame ? false : right != null && left.val == right.val;

     return isSame && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);

 }

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

时间复杂度: 该方案用了递归遍历树，不要判断时间复杂度，而且树的遍历复杂度都说不好，且记为 O(n)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是 O(n)=O(1);

总结

本题的大致解法如上所诉，按照特点我们可以很简单的解决这个问题，其实也可以按层进行对比，判断每一层是否镜像，可以用队列来解决。

LeetCode集锦（二十一） - 第100题 Same Tree

发表于 2019-06-07 | 分类于算法 |

问题

Given two binary trees, write a function to check if they are the same or not. 

 Two binary trees are considered the same if they are structurally identical and the nodes have the same value. 

 Example 1: 


Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true


 Example 2: 


Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false


 Example 3: 


Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

翻译:

给定两棵二叉树，编写一个函数来检查它们是否相同。
如果两个二叉树在结构上是相同的，并且节点具有相同的值，则认为它们是相同的。
示例1:
1
2
3
4
5
6
>            1         1
>           / \       / \
>          2   3     2   3
>         [1,2,3],   [1,2,3]
>
>

输出:true
示例2:

>          1         1
>         /           \
>        2             2
>       [1,2],[1,null, 2)
>

输出:false
示例3:

>           1         1
>          / \       / \
>         2   1     1   2
>        [1,2,1],   [1,1,2]
>

输出:false

解题思路

本题判断两个树是否相等，我们第一时间想到的就是遍历树节点，看看树节点是否一致（内容）。遍历树的方法有前序遍历，中序遍历，和后序遍历，这边选择了后序遍历。

解题方法

后序遍历方式，代码如下

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }

    boolean left = isSameTree(p.left, q.left);
    boolean right = isSameTree(p.right, q.right);

    return left && right && p.val == q.val;
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

时间复杂度: 该方案用了递归遍历树，不要判断时间复杂度，而且树的遍历复杂度都说不好，且记为O(n)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

总结

本题的大致解法如上所诉按照正常遍历树的方式来就好，选择自己喜欢的遍历方式，但是就是不会算树的时间复杂度。。。

LeetCode集锦（二十） - 第88题 merge sorted array

发表于 2019-06-07 | 分类于算法 |

问题

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. 

 Note: 


 The number of elements initialized in nums1 and nums2 are m and n respectively. 
 You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. 


 Example: 


Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

翻译:

给定两个排序整数数组nums1和nums2，将nums2合并为一个排序数组nums1。
注意:
nums1和nums2中初始化的元素数量分别为m和n。
您可以假设nums1有足够的空间(大小大于或等于m + n)来容纳nums2中的其他元素。
例子:
输入:
nums1 = [1,2,3,0,0,0]， m = 3
nums2 = [2,5,6]， n = 3
输出:[1、2、2、3、5、6)

解题思路

本题是要合并两个数组，正常来说，我们可以新建一个数组来作为临时数组，把两个值都放进去，然后返回该数组，但是本题要在原数组上改，当然本题也可以这样子，新建一个临时数组，代替其中一个，在一个个遍历覆盖数组1，但是这样子就有多余都开销了。除了这个方法，我们也可以先把数组2添加到数组1中，然后进行排序，但是这样重复做了一次排序，如果是两个无序的，那么可以使用这种方式。那还有别的方式嘛？当然，我们习惯把小的放前面，那么是不是也可以把大的放后面呢？大的值肯定是按顺序放入，小的值还不能保证替换后的顺序，所以本题可以倒序遍历，把大的值往后放。

解题方法

先合并两个数组，在排序的方式，代码如下

//先把数组合并
    for (int i = m, j = 0; i < m + n; i++, j++) {
        nums1[i] = nums2[j];
    }

    //排序
    for (int i = 0; i < m + n; i++) {
        for (int j = i; j < m + n; j++) {
            if (nums1[i] > nums1[j]) {
                nums1[i] = nums1[i] ^ nums1[j];
                nums1[j] = nums1[j] ^ nums1[i];
                nums1[i] = nums1[j] ^ nums1[i];
            }
        }
    }

时间复杂度: 该方案用了循环m所以f(n)=(n^2)=n;所以O(f(n))=O(n^2),即T(n)=O(n^2)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

后序遍历，合并数组，代码如下

m--;
n--;
while (m >= 0 && n >= 0) {
    if (nums1[m] > nums2[n]) {
        nums1[m + n + 1] = nums1[m];
        m--;
    } else {
        nums1[m + n + 1] = nums2[n];
        n--;
    }
}
for(int i=0;i<=n;i++){
    nums1[i] = nums2[i];
}

时间复杂度: 该方案用了循环m所以f(n)=(n+m)=n;所以O(f(n))=O(m+n),即T(n)=O(n)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

总结

本题的大致解法如上所诉,有时候按照正常的逻辑来，可能很复杂，但是换个角度，肯定就很简单了。

LeetCode集锦（十九） - 第83题 Remove Duplicates from sorted list

发表于 2019-06-07 | 分类于算法 |

问题

Given a sorted linked list, delete all duplicates such that each element appear only once. 

 Example 1: 


Input: 1->1->2
Output: 1->2


 Example 2: 


Input: 1->1->2->3->3
Output: 1->2->3

翻译:

给定一个已排序的链表，删除所有重复项，使每个元素只出现一次。
示例1:
输入:1 - > 1 - > 2
输出:1 - > 2
示例2:
输入:1 - > 1 - > 2 - > 3 - > 3
输出:1 - > 2 - > 3

解题思路

本题思路很简单，由于链表是有序的，说明如果有重复的，肯定是下一个，按照顺序进行遍历，如果遇到当前节点和后一个节点相同，那么覆盖当前节点。遍历一次就搞定了

解题方法

按照我们的思路来编辑，代码如下

public ListNode deleteDuplicates(ListNode head) {

    if (head == null) {
        return head;
    }

    ListNode temp = head;
    while (head.next != null) {
        if (head.val == head.next.val) {
            head.next = head.next.next;
            continue;
        }
        head = head.next;
    }
    return temp;

}

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

时间复杂度: 该方案用了循环m所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

总结

本题的大致解法如上所诉,本题大致只有一种解题方式，直接遍历读取覆盖即可，我是通过当前节点和下一个节点进行比较，也可以和前一个节点进行比较。

LeetCode集锦（十八） - 第70题 Climbing Stairs

发表于 2019-06-07 | 分类于算法 |

问题

You are climbing a stair case. It takes n steps to reach to the top. 

 Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 

 Note: Given n will be a positive integer. 

 Example 1: 


Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


 Example 2: 


Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

翻译:

你正在爬楼梯。到达山顶需要n步。
每次你可以爬1或2级台阶。你可以用几种不同的方式爬到山顶?
注意:给定n是一个正整数。
示例1:
输入:2
输出:2
说明:爬到山顶有两种方法。

1步+ 1步

2步
示例2:
输入:3
输出:3
说明:爬到山顶有三种方法。

1步+ 1步+ 1步

1步+ 2步

2步+ 1步

解题思路

本题要求很明确，就是根据目标阶梯，预测一下需要多少中1，2组合方式走完整个阶梯，粗看貌似很麻烦，用循环来弄不知道有多少情况，各种if，但是换个角度来看，如果我们倒着推理，比如最后一级只可能是1步上来或者是2步上来，这样子逆退，就找出来一种递归的方式，但是这种方法比较耗时间，没有通过，不知道对不对，所以换一种方式，我们试试正向思维，3级是2步和一步跨上去的，那是不是2+1？同样4级，也是由两步和一步跨上去的，也就是n(4)=n(2)+n(3),哎呦，好像斐波那契数列哦。类似的推理，其实我们可以猜测出规律n(n)=n(n-1)+n(n-1).所以本题就解决了

解题方法

按照我们的思路来编辑，代码如下

if (n < 0) {
        return 0;
    }
    if (n <= 2) {
        return n;
    }
    int a = 1;
    int b = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }

    return result;

时间复杂度: 该方案用了循环m所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

总结

本题的大致解法如上所诉, 可以通过逆推来发现特定的规律，直接想可能是个很大的问题，所以可以考虑换个思维。

FightCrap

制造bug的永动机

GitHub E-Mail