DSA

2023-04-25

java

Word count: 16.2k | Reading time≈ 75 min

DSA

Concepts

Time complexity:

This paper analyzes from the following five points:

What is time complexity anyway
What’s a big O
Differences in data sizes
Simplification of complex expressions
What is the base of log in -O (log n)?

究竟什么是时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。

那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。

什么是大O

这里的大O是指什么呢，说到时间复杂度，大家都知道O(n)，O(n^2)，却说不清什么是大O。

算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2) 。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，**所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)**。

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。如图所示：时间复杂度4，一般情况下的时间复杂度

我们主要关心的还是一般情况下的数据形式。

面试中说道算法的时间复杂度是多少指的都是一般情况。但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

#不同数据规模的差异

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

时间复杂度，不同数据规模的差异

在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项的时候）。

就像上图中 O(5n^2) 和 O(100n) 在n为20之前很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度，而且要默认O(n) 优于O(n^2) 呢？

这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

但是也要注意大常数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了。

#复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)，而是一个复杂的表达式，例如：

1	O(2n^2 + 10n + 1000)

那这里如何描述这个算法的时间复杂度呢，一种方法就是简化法。

去掉运行时间中的加法常数项（因为常数项并不会因为n的增大而增加计算机的操作次数）。

1	O(2n^2 + 10n)

去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。

1	O(n^2 + n)

只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：

O(n^2)

如果这一步理解有困难，那也可以做提取n的操作，变成O(n(n+1)) ，省略加法常数项后也就别变成了：

O(n^2)

所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

也可以用另一种简化的思路，其实当n大于40的时候，这个复杂度会恒小于O(3 × n^2)， O(2 × n^2 + 10 × n + 1000) < O(3 × n^2)，所以说最后省略掉常数项系数最终时间复杂度也是O(n^2)。

#O(logn)中的log是以什么为底？

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？如下图所示：

时间复杂度1.png

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不难理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。

抽象一下就是在时间复杂度的计算过程中，log以i为底n的对数等于log 以j为底n的对数，所以忽略了i，直接说是logn。

这样就应该不难理解为什么忽略底数了。

#举一个例子

通过这道面试题目，来分析一下时间复杂度。题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）。

如果是暴力枚举的话，时间复杂度是多少呢，是O(n^2)么？

这里一些同学会忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单，除了n^2 次的遍历次数外，字符串比较依然要消耗m次操作（m也就是字母串的长度），所以时间复杂度是O(m × n × n)。

接下来再想一下其他解题思路。

先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起，然后在遍历一遍n个字符串，这样就找到两个相同的字符串了。

那看看这种算法的时间复杂度，快速排序时间复杂度为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的操作，就是O(m × n × log n) 。

之后还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m × n × logn + n × m)。

我们对O(m × n × log n + n × m) 进行简化操作，把m × n提取出来变成 O(m × n × (logn + 1))，再省略常数项最后的时间复杂度是 O(m × n × log n)。

最后很明显O(m × n × logn) 要优于O(m × n × n)！

所以先把字符串集合排序再遍历一遍找到两个相同字符串的方法要比直接暴力枚举的方式更快。

这就是我们通过分析两种算法的时间复杂度得来的。

当然这不是这道题目的最优解，我仅仅是用这道题目来讲解一下时间复杂度。

#总结

本篇讲解了什么是时间复杂度，复杂度是用来干什么，以及数据规模对时间复杂度的影响。

还讲解了被大多数同学忽略的大O的定义以及log究竟是以谁为底的问题。

再分析了如何简化复杂的时间复杂度，最后举一个具体的例子，把本篇的内容串起来。

相信看完本篇，大家对时间复杂度的认识会深刻很多！

各类语言的性能比较，底层

因为在简历上写了我熟悉C, Python, Java, 所以要了解一下这三种语言的底层实现，逻辑；要会比较三种语言的运行速度。

首先我们从底层实现开始：

底层实现

JAVA

Questions

Greedy algorithm:

1. 455. Assign Cookies (Easy)

题目描述：每个孩子都有一个满足度 grid，每个饼干都有一个大小 size，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。

给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。
因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。

在以上的解法中，我们只在每次分配时饼干时选择一种看起来是当前最优的分配方法，但无法保证这种局部最优的分配方法最后能得到全局最优解。我们假设能得到全局最优解，并使用反证法进行证明，即假设存在一种比我们使用的贪心策略更优的最优策略。如果不存在这种最优策略，表示贪心策略就是最优策略，得到的解也就是全局最优解。

证明：假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，可以给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。

public int findContentChildren(int[] g, int[] s) {

      if(g==null||s==null) return 0;

      Arrays.sort(g);

      Arrays.sort(s);

      int gi=0;

      int si=0;
  
     while(gi<g.length&&si<s.length){

          if(s[si]>=g[gi]){

             gi++;

             si++;

          }

         else si++;

      }

      return gi;

  }

2. 435. Non-overlapping Intervals (Medium)

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

solution:

先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。

在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。

按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。结束时间越早越好

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
    int cnt = 1;
    int end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            continue;
        }
        end = intervals[i][1];
        cnt++;
    }
    return intervals.length - cnt;
}

Arrays.sort(intervals, new Comparator<int[]>() {
     @Override
     public int compare(int[] o1, int[] o2) {
         return (o1[1] < o2[1]) ? -1 : ((o1[1] == o2[1]) ? 0 : 1);
     }
});
//这里是让数组中，各个区间的末尾按照正序也就是升序来排序，所以是用o1[1]<o2[1],也可以用return o1[1]-o2[1],但可能会溢出

3. 452. Minimum Number of Arrows to Burst Balloons

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

该题思路基本和第二题一致，只是要求最多不重叠的区间数，然后射出这么多箭即可。而且注意边界值。

class Solution {
    class myComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] o1,int[] o2){
            return (o1[1] < o2[1]) ? -1 : ((o1[1] == o2[1]) ? 0 : 1);
          //如果使用return o1[1]-o2[1],可能会出现int越界的问题，所以用比较符号来
        }
    }
    public int findMinArrowShots(int[][] points) {
    if(points==null){
        return 0;
    }
    Arrays.sort(points,new Solution.myComparator());
    int cnt=1;
    int end=points[0][1];
    for(int i=1;i<points.length;i++){
        if(points[i][0]<=end){
            continue;
        }
        cnt++;
        end=points[i][1];
    }
    return cnt;

    }
}

4. 406. Queue Reconstruction by Height(Medium)

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

思路: 为了使插入操作不影响后续的操作，身高较高的学生应该先做插入操作，否则身高较小的学生原先正确插入的第 k 个位置可能会变成第 k+1 个位置。

身高 h 降序、个数 k 值升序，然后将某个学生插入队列的第 k 个位置中。

Solution:

class Solution {
    class myComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] o1,int[] o2){
            if(o1[0]!=o2[0]){
                return o2[0]-o1[0];
            }
            else{
                return o1[1]-o2[1];
            }
        }
    }
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0 || people[0].length == 0) {
        return new int[0][0];
        }
        Arrays.sort(people,new myComparator());// equals to Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
        List<int[]> queue = new ArrayList<>();
        for(int[] p:people){
            queue.add(p[1],p);
        }
        return queue.toArray(new int[queue.size()][]);

    }
}

5. 121. Best Time to Buy and Sell Stock (Easy)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

Idea:

只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。

Solution:

public int maxProfit(int[] prices) {
   int n = prices.length;
   if (n == 0) return 0;
   int soFarMin = prices[0];
   int max = 0;
   for (int i = 1; i < n; i++) {
       if (soFarMin > prices[i]) soFarMin = prices[i];
       else max = Math.max(max, prices[i] - soFarMin);
   }
   return max;
   }

6. 122. Best Time to Buy and Sell Stock II (Easy)

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。总利润为 4 + 3 = 7 。

Idea:

题目描述：可以进行多次交易，多次交易之间不能交叉进行，可以进行多次交易。

对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。

Solution:

class Solution {
    public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += (prices[i] - prices[i - 1]);
        }
    }
    return profit;
    }
}

Linked List

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

如图所示：链表1

了解完链表的类型，再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：

链表3

这个链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起。

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
JavaScript:

class ListNode {
  val;
  next = null;
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

203. remove a node

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

Solution1. 使用dummy node. 这样子在移除头节点的时候可以使用虚拟节点将其移出，其他的节点都是依靠后面的节点来进行删除的

 public ListNode removeElements(ListNode head, int val) {
    ListNode dummy= new ListNode(-1);
    dummy.next=head;
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
    }
}

Solution2. 不使用dummy node, 直接将

 public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;//如果头为空，则往后移
        }
        if(head==null){
            return head;
        }
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                pre.next = cur.next;
            }else{
                pre=cur;
            }
            cur=cur.next;

        }
           return head;
    }
}

707 design myLinkedList

solution1

单链表

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }
    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
  //可以不用addAtIndex方法来实现
          public void addAtHead(int val) {
        size++;
        ListNode node = new ListNode(val);
        if (head.next == null) {
            head.next = node;
        } else {
        ListNode temp = head.next;
        head.next = node;
        node.next = temp;
        }
}

    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
	    return;
        }
        ListNode pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

solution2

双链表

//双链表
class ListNode{
    int val;
    ListNode next,prev;
    ListNode() {};
    ListNode(int val){
        this.val = val;
    }
}


class MyLinkedList {  

    //记录链表中元素的数量
    int size;
    //记录链表的虚拟头结点和尾结点
    ListNode head,tail;
    
    public MyLinkedList() {
        //初始化操作
        this.size = 0;
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        //这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
        head.next=tail;
        tail.prev=head;
    }
    
    public int get(int index) {
        //判断index是否有效
        if(index<0 || index>=size){
            return -1;
        }
        ListNode cur = this.head;
        //判断是哪一边遍历时间更短
        if(index >= size / 2){
            //tail开始
            cur = tail;
            for(int i=0; i< size-index; i++){
                cur = cur.prev;
            }
        }else{
            for(int i=0; i<= index; i++){
                cur = cur.next; 
            }
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        //等价于在第0个元素前添加
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        //等价于在最后一个元素(null)前添加
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        //index大于链表长度
        if(index>size){
            return;
        }
        //index小于0
        if(index<0){
            index = 0;
        }
        size++;
        //找到前驱
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        //新建结点
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;
        
    }
    
    public void deleteAtIndex(int index) {
        //判断索引是否有效
        if(index<0 || index>=size){
            return;
        }
        //删除操作
        size--;
        ListNode pre = this.head;
        for(int i=0; i<index; i++){
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
    }
}

160 交叉链表的最简单解法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while (l1 != l2) {
    l1 = (l1 == null) ? headB : l1.next;
    l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}

//递归写法    
public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    private ListNode reverse(ListNode pre, ListNode cur){
        if(cur==null){
            return pre;
        }
        ListNode temp = cur.next;
        cur.next=pre;
        return reverse(cur,temp);
    }

//从后向前的递归
ListNode reverseList(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }

Trees

leetcode 104

Double pointers

leetcode 167

Sorting

p10

p11

p12

p13

p14

p15

p16

p17

p18

p19

p20

p21

Arrays

leetcode 704

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

public int search(int[] nums, int target) {
  int left = 0, right = nums.length-1;
  while(left<=right){
  int mid = left + ((right - left) >> 1);
  if(target>nums[mid]) left = mid+1;
  else if(target<nums[mid]) right = mid-1;
  else return mid;
	}
return -1;
 }

leetcode 27

快慢指针

Brute

0,1,2,3,3,0,4,2

0,1,3,3,0,4,2,[2]

0,1,3,3,0,4,[2,2]

1,3,3,4,5 i=1 result = 5

1,3,4,5,[5] i=1 result = 4

public int removeElement(int[] nums, int val) {
    int result=nums.length;
    for(int i = 0;i<result;i++){
        if(nums[i]==val){
            for(int j=i+1;j<result;j++){
                nums[j-1]=nums[j];
            }
            result--;
            i--;
        }
    }
    return result;
}

Fast and slow pointer

gif0_dsa

 public int removeElement(int[] nums, int val) {
// 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    
    }

//相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

Leetcode 977

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

int right = nums.length-1;
int left = 0;
//construct a new array to store otherwise it will cause o(n^2) in time complexity
int[] result = new int[nums.length];
int index = result.length - 1;
while(left<=right){
if(nums[left]*nums[left]>nums[right]*nums[right]){
    result[index]=nums[left]*nums[left];
    index--;
    left++;
}
else{
    result[index]=nums[right]*nums[right];
    index--;
    right--;
}
}
return result;
    }

Leetcode 209

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [nums_l, nums_l+1, …, nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例：3

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

Brute

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

Sliding Windows/滑动窗口:

 public int minSubArrayLen(int s, int[] nums) {
    int left = 0;
    int sum = 0;
    int result = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= s) {
            result = Math.min(result, right - left + 1);
            sum -= nums[left];
          	left++;
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
}

gif1_dsa

Leetcode 59

注意边界条件, 坚持左闭右开的原则.

循环的次数等于n/2

public int[][] generateMatrix(int n) {
        int start=0;
        int count=1;
        int loop=0;
        int[][] nums = new int[n][n]; 
        int i,j;
        while(loop++<n/2){
            for(j = start ; j<n-loop ; j++){
               nums[start][j] = count++;
            }
            for(i = start;i<n-loop;i++){
                nums[i][j]=count++;
            }
            for(;j>=loop;j--){
                nums[i][j]=count++;
            }
            for(;i>=loop;i--){
                nums[i][j]=count++;
            }
            start++;
        }
           if(n%2==1){
                nums[n/2][n/2]=n*n;
            }
        return nums;
    }

Summary of Array

数组下标都是从0开始的。
数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

我们来举一个Java的例子，例如： int[][] rating = new int[3][4]; ，这个二维数组在内存空间可不是一个 3*4 的连续地址空间

看了下图，就应该明白了：

算法通关数组3

所以Java的二维数组在内存中不是 3\*4 的连续地址空间，而是四条连续的地址空间组成！

Hash table

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

哈希表3

一般哈希碰撞有两种解决方法，拉链法和线性探测法。

#拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

哈希表4

（数据规模是dataSize，哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

#线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

哈希表5

其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。

hash表是牺牲空间减少时间cost

Leetcode 242

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

242.有效的字母异位词

public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for(char c:s.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = map.getOrDefault(c, 0);
            if (count == 0) {
                return false;
            }
            if (count == 1) {
                map.remove(c);
            } else {
                map.put(c, count - 1);
            }
        }
        
        return map.isEmpty();
    }

更简单的做法是用数组

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

/**
 * 242. 有效的字母异位词 字典解法
 * 时间复杂度O(m+n) 空间复杂度O(1)
 */
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        
        for (int count: record) {
            if (count != 0) {               // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        return true;                        // record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
}

Leetcode 349

public int[] intersection(int[] nums1, int[] nums2) {
    if(nums1==null||nums2==null||nums1.length==0||nums2.length==0){
    return new int[0];
    }
    Set<Integer> set = new HashSet<>();
    Set<Integer> resSet = new HashSet<>();
    for(int i:nums1){
        set.add(i);
    }
    for(int i:nums2){
        if(set.contains(i)){
            resSet.add(i);
        }
    }
     int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        
        return arr;

    }

Leetcode 202 快乐数

这个题讨论3种假设情况

最后n1->n2->…->1 true
最后循环下来了,n1->n2->…->n1 false
越加越大

但是事实上不会越加越大，拿9来举例，9^2=81,99->162, ….999->243,9999->324,99999->405这样加下去，不会超其本身，所以不会越加越大。所以我们只需要讨论前两种方案，只要在循环过程中出现了重复的，就停止循环并返回，出现1了也停止循环并返回。

public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
         
    }
    private int getNextNumber(int n){
    int res=0;
    while(n>0){
        int temp = n%10;
        res+=temp*temp;
        n=n/10;
    }
    return res;
    
}

Leetcode 1 两数之和

Brute force:

 public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length;j++){
                if(i==j){
                    continue;
                }
                if((nums[i]+nums[j])==target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
}

HashMap:

本解法有四个重点：

为什么会想到用哈希表
哈希表为什么用map
本题map是用来存什么的
map中的key和value用来存什么的

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if(nums==null||nums.length==0){
        return res;
    }
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int temp = target-nums[i];
        if(map.containsKey(temp)){
            res[0]=i;
            res[1]=map.get(temp);
            break;
        }
        map.put(nums[i],i);
    }
    return res;

Leetcode 454 四数相加

 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map = new HashMap<>();
        int temp;
        int res=0;
        for(int i:nums1){
            for(int j:nums2){
                temp=i+j;
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            }
        }
        for(int i:nums3){
            for(int j:nums4){
                temp=i+j;
                if (map.containsKey(0 - temp)) {
                    res += map.get(0 - temp);
                }
            }
        }
        return res;
    }
}

String type question

344. Reverse the String

使用双指针，left和right

循环swap left 和 right 直到 left>=right

public void reverseString(char[] s) {
    int i = 0;
    int j = s.length-1;
    while(i<j){
        swap(s,i,j);
        i++;
        j--;
    }
}
    private void swap(char s[], int i, int j){
    char temp=s[i];
    s[i]=s[j];
    s[j]=temp;
}

541. Reverse the String II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

public String reverseStr(String s, int k) {
    int length = s.length();
    StringBuilder res = new StringBuilder();
    int count = 0;
    int remain = length;
    
    while (remain >= 2 * k) {
        res.append(reverse(s, 0 + 2 * k * count, k + 2 * k * count));
        res.append(s.substring(k + 2 * k * count, 2 * k + 2 * k * count));
        remain -= 2 * k;
        count++;
    }
    
    if (remain >= k) {
        res.append(reverse(s, 0 + 2 * k * count, k + 2 * k * count));
        res.append(s.substring(k + 2 * k * count));
    } else {
        String sub = s.substring(0 + 2 * k * count);
        res.append(reverse(sub, 0, sub.length()));
    }
    
    return res.toString();
}

private String reverse(String s, int i, int j) {
    char[] a = s.substring(i, j).toCharArray();
    int left = 0;
    int right = a.length - 1;
    
    while (left < right) {
        swap(a, left, right);
        left++;
        right--;
    }
    
    return new String(a);
}

private void swap(char[] s, int i, int j) {
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

这题就是注意边界值的处理，别的没什么。

剑指offer05

public String replaceSpace(String s) {
    StringBuilder sb = new StringBuilder();
    char[] ch = s.toCharArray();
    for(char c: ch){
        if(c==32){
            sb.append("%20");
        }else{
            sb.append(c);
        }
    }
    return sb.toString();
}

双指针法，很巧妙

public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

151 翻转字符串里的单词

My solution: use a stack

public String reverseWords(String s) {
String[] words = s.split("\\s+");
Stack<String> stack = new Stack<>();
for(String word: words){
    stack.push(word);
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
    sb.append(stack.pop());
    sb.append(" ");
}
return sb.toString().trim();
    }

public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    } 

private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;//这两行是为了去除头部和尾部的空格
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }

剑指offer58 II

基本解法:

public String reverseLeftWords(String s, int n) {
    char[] ss= s.toCharArray();
    StringBuilder sb = new StringBuilder();
    for(int i=n;i<s.length();i++){
        sb.append(ss[i]);
    }
    for(int i=0;i<n;i++){
        sb.append(ss[i]);
    }
    return sb.toString();
}

解法二，省空间

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chars = s.toCharArray();
        reverse(chars, 0, chars.length - 1);
        reverse(chars, 0, chars.length - 1 - n);
        reverse(chars, chars.length - n, chars.length - 1);
        return new String(chars);
    }

    public void reverse(char[] chars, int left, int right) {
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

leetcode 28

解法1:

public int strStr(String haystack, String needle) {
    if(needle.length()>haystack.length()){
        return -1;
    }
    if(haystack.equals(needle)){
        return 0;
    }
    char[] s1 = haystack.toCharArray();
    int nLen = needle.length();
    for(int i=0;i<=(s1.length-nLen);i++){
        if(s1[i]==needle.charAt(0)){
            if(haystack.substring(i,i+nLen).equals(needle)){
                return i;
            }
        }
    }
    return -1;
}

解法2: KMP

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

next数组求法

构造一个getNext方法，传入next数组和模式串作为参数

1.初始化

2.讨论前缀和后缀不同的情况

3.讨论前缀和后缀相同的情况

4.更新next数组

getNext(int[] next,String s){

  int j=0;

  next[0]=0;

  for(int i=0;i<s.size();i++){

      while(s[i]!=s[j]&&j>0){
				j=next[j-1];
      }
    	if(s[i]==s[j]){
        j++;
      }
	next[i]=j;
  }

}

Leetcode 459

重复的字串

使用kmp算法的解法. 对整个字符串求next前缀数组，可以得到最长的相等前后缀长度，然后用字符串减去这个长度，就可以算得重复字串长度，如果该字符串是由这个字串重复构成的话，那么它是能被字符串长度整除的。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len=s.length();
        if (s.equals("")) return false;
        int j=0;
        int[] next = new int[len];
        next[0]=0;
        for(int i=1;i<len;i++){
            while(j>0&&s.charAt(j)!=s.charAt(i)){
                j=next[j-1];
            }
            if(s.charAt(j)==s.charAt(i)){
                j++;
            }
            next[i]=j;
        }
        if(len%(len-next[len-1])==0&&next[len-1]>0){
            return true;
        }
    return false;
    }
}

栈与队列

leetcode 232

用栈实现队列

import java.util.Stack;

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1=new Stack();
        s2=new Stack();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        int result=s2.pop();
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
        return result;


    }
    
    public int peek() {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        int result=s2.peek();
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
        return result;
    }
    
    public boolean empty() {
        return s1.isEmpty();
    }
}

这里面有四次将s1的元素和s2的元素互相倒过去或者倒回来的，所以我们可以将这一步抽象成一个方法。

leetcode 225

用队列实现栈

class MyStack {

    Queue<Integer> queue1; // 和栈中保持一样元素的队列
    Queue<Integer> queue2; // 辅助队列

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在辅助队列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
    }
  //在这里让队列push元素的方法使得最后保持pop的时候和栈的pop顺序一样就行
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

Leetcode20

括号匹配问题

这个题主要有一点比较巧妙，我们来遍历整个字符串，遇到左括号，我们就往栈里面push其相应的右括号，在遇到右括号就开始判断这个栈首元素和这个右括号是否匹配，如果不匹配或者说栈已经空了，那么就是返回false。最后完成字符串扫描后，如果栈内还没pop干净也说明没匹配上。

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        if(s.length()%2!=0){
            return false;
        }
        char[] ss = s.toCharArray();
        Deque<Character> dq = new LinkedList<>();
        for(char c:ss){
            if(c=='('){
                dq.push(')');
            }
            else if(c=='{'){
                dq.push('}');
            }
            else if(c=='['){
                dq.push(']');
            }
            else if(dq.isEmpty()||dq.peek()!=c){
                return false;
            }else{
                dq.pop();
            }
        }
        return dq.isEmpty();
    }
}

Leetcode 1047 删除字符串中的所有相邻重复项

这道题和上一道括号匹配问题类似，都是用栈来解决

import java.util.*;

class Solution {
    public String removeDuplicates(String s) {
        char[] ss = s.toCharArray();
        Deque<Character> dq = new LinkedList<>();
        for(char c:ss){
            if(!dq.isEmpty()&&dq.peek()==c){
                dq.pop();
            }
            else{
                dq.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!dq.isEmpty()){
            sb.append(dq.pollLast());
        }
        return sb.toString();
    }
}

Leetcode150 逆波兰式表达式求值

public int evalRPN(String[] tokens) {
       Deque<String> dq = new LinkedList<>();
       for(String s:tokens){
           if(s.equals("+")){
               int a = Integer.parseInt(dq.pop());
               int b = Integer.parseInt(dq.pop());
               dq.push(Integer.toString(a+b));
           }
           else if(s.equals("*")){
               int a = Integer.parseInt(dq.pop());
               int b = Integer.parseInt(dq.pop());
               dq.push(Integer.toString(a*b));
           }
           else if(s.equals("-")){
               int a = Integer.parseInt(dq.pop());
               int b = Integer.parseInt(dq.pop());
               dq.push(Integer.toString(b-a));
           }
           else if(s.equals("/")){
               int a = Integer.parseInt(dq.pop());
               int b = Integer.parseInt(dq.pop());
               dq.push(Integer.toString(b/a));
           }
       else{
           dq.push(s);
       }
       }
       return Integer.parseInt(dq.pop());
   }

Leetcode239 滑动窗口的最大值

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    //同时判断队列当前是否为空
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }
    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }
    //队列队顶元素始终为最大值
    int peek() {
        return deque.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        //存放结果元素的数组
        int[] res = new int[len];
        int num = 0;
        //自定义队列
        MyQueue myQueue = new MyQueue();
        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[num++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
            myQueue.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            myQueue.add(nums[i]);
            //记录对应的最大值
            res[num++] = myQueue.peek();
        }
        return res;
    }
}

树/Tree

树的种类

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树 (有序树):

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

**平衡二叉树AVL(Adelson-Velsky and Landis): **它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

树的实现

链式存储（使用指针），顺序存储（使用数组）

树的遍历

1.DFS:

先往深走，遇到叶子节点再往回走

前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）

2.BFS:

一层一层的去遍历。

层次遍历（迭代法）

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

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉树递归遍历,DFS

前序遍历: 中左右 leetcode 144

中序遍历: 左中右 leetcode 145

后序遍历: 左右中 leetcode 94

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

N叉树的前序和后序遍历, leetcode 589,590

前序:

public List<Integer> preorder(Node root) {
    List<Integer> res = new ArrayList<>();
    if(root==null){
        return res;
    }
    pre(root,res);
    return res;
}
public void pre(Node root, List<Integer> list){
    if(root==null){
        return;
    }
    list.add(root.val);
    for(Node child : root.children){
        pre(child,list);
    }
}

后序:

public List<Integer> postorder(Node root) {
    List<Integer> res = new ArrayList<>();
    if(root==null){
        return res;
    }
    post(root,res);
    return res;
}
public void post(Node root,List<Integer> list){
    if(root == null){
        return;
    }
    for(Node child:root.children){
        post(child,list);
    }
    list.add(root.val);
}

二叉树遍历，迭代法, DFS

使用栈来进行迭代

前序

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }

中序

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }

后序

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null){
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.left != null){
            stack.push(node.left);
        }
        if (node.right != null){
            stack.push(node.right);
        }
    }
    Collections.reverse(result);
    return result;
}

BFS

Leetcode 102/107

需要队列来实现/或者递归

public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> res = new ArrayList<List<Integer>>();
       if(root==null){
           return res;
       }
       Queue<TreeNode> que = new LinkedList<TreeNode>();
       que.offer(root);

       while(!que.isEmpty()){
           List<Integer> list = new ArrayList<Integer>();
           int len = que.size();//记录了每一层的节点个数，方便我们进入下一层。
           while(len>0){
               TreeNode tem = que.poll();
               list.add(tem.val);
               if(tem.left!=null) que.offer(tem.left);
               if(tem.right!=null) que.offer(tem.right);
               len--;

           }
           res.add(list);
       }
       return res;
}

Leetcode 199 返回二叉树的右视图

还是bfs，不过不用构造整棵二叉树，就返回每一层最右边的那个值

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            while(len>0){
                TreeNode node = que.poll();
                if(len==1){
                    res.add(node.val);
                }
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
                len--;
            }
        }
        return res;
    }

Leetcode 637

求每一层的平均值

public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<Double>();
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.offer(root);
       while (!queue.isEmpty()) {
           double sum = 0;
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               sum += node.val;
               TreeNode left = node.left, right = node.right;
               if (left != null) {
                   queue.offer(left);
               }
               if (right != null) {
                   queue.offer(right);
               }
           }
           averages.add(sum / size);
       }
       return averages;

   }

Leetcode 429

遍历n叉树

public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null){
    return res;
}
Queue<Node> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
    int size = que.size();
    List<Integer> list = new ArrayList<>();
    while(size>0){
        Node node = que.poll();
        list.add(node.val);
        for(Node child:node.children){
            if(child!=null){
                que.offer(child);
            }
        }
        size--;
    }
    res.add(list);
}
return res;
}

Leetcode 515

每一层的最大值

public List<Integer> largestValues(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if(root==null){
           return res;
       }
       Queue<TreeNode> que = new LinkedList<>();
       que.offer(root);
       while(!que.isEmpty()){
           int size = que.size();
           int max = Integer.MIN_VALUE;
           while(size>0){
               TreeNode node = que.poll();
               if(node.left!=null) que.offer(node.left);
               if(node.right!=null) que.offer(node.right);
               if(node.val>max) max=node.val;
               size--;
           }
           res.add(max);
       }
       return res;
   }

Leetcode 116/117

这两道题用这个答案都可以通过leetcode

添加next指针，注意处理一下引入previous结点

public Node connect(Node root) {
    if(root==null){
        return root;
    }
    Queue<Node> que = new LinkedList<>();
    que.offer(root);
    while(!que.isEmpty()){
        int len = que.size();
        Node previous = null;
        while(len>0){
            Node node = que.poll();
            if(previous!=null){
                previous.next=node;
            }
            if(len==1){
                node.next=null;
            }
            if(node.left!=null) que.offer(node.left);
            if(node.right!=null) que.offer(node.right);
            previous=node;
            len--;
        }
    }
    return root;
}

Leetcode 104

求最大深度递归就行了，不用遍历

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

Leetcode 111

求最小深度的时候要讨论树退化成线性的情况，因为如果直接递归的话，这样子返回的最小值是1，但是其实这颗树的最小深度是整颗树的高度。

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

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

Leetcode 226 翻转二叉树

public TreeNode invertTree(TreeNode root) {
       if(root==null) return null;
       TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
       root.left=invertTree(root.right);
       root.right=invertTree(left);
       return root;
   }

Leetcoed 100 相同的二叉树

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

Leetcode 101 对称二叉树

递归法

public boolean isSymmetric(TreeNode root) {
       if(root==null) return false;
       return sym(root.left,root.right);
}
   private boolean sym(TreeNode t1, TreeNode t2){
       if(t1==null&t2==null){
           return true;
       }
       if(t1==null||t2==null){
           return false;
       }
       if(t1.val!=t2.val){
           return false;
       }
       return sym(t1.left,t2.right)&&sym(t2.left,t1.right);
   }

迭代法，使用队列

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

Leetcode 222

完全二叉树的个数

public int countNodes(TreeNode root) {
      if(root==null){
          return 0;
      }
      return countNodes(root.left)+countNodes(root.right)+1;
  }

Leetcode 110

平衡二叉树

这道题和求最大深度不一样，子树中要是最大深度差大于一了也不是平衡二叉树。

public boolean isBalanced(TreeNode root) {
       return getHeight(root) != -1;
   }

   private int getHeight(TreeNode root) {
       if (root == null) {
           return 0;
       }
       int leftHeight = getHeight(root.left);
       if (leftHeight == -1) {
           return -1;
       }
       int rightHeight = getHeight(root.right);
       if (rightHeight == -1) {
           return -1;
       }
       // 左右子树高度差大于1，return -1表示已经不是平衡树了
       if (Math.abs(leftHeight - rightHeight) > 1) {
           return -1;
       }
       return Math.max(leftHeight, rightHeight) + 1;
   }

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

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

Leetcode 257 二叉树的所有路径

前序遍历法,在遍历的过程中记得时刻记录每一条路径，

public List<String> binaryTreePaths(TreeNode root) {
 List<String> res = new ArrayList<>();
 if (root == null) {
     return res;
 }
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);

 Stack<StringBuilder> paths = new Stack<>();
 StringBuilder sb = new StringBuilder();
 sb.append(Integer.toString(root.val));
 paths.push(sb);

 while (!stack.isEmpty()) {
     TreeNode node = stack.pop();
     sb = paths.pop();

     if (node.right != null) {
         stack.push(node.right);
         StringBuilder newPath = new StringBuilder(sb);
         newPath.append("->");
         newPath.append(Integer.toString(node.right.val));
         paths.push(newPath);
     }
     if (node.left != null) {
         stack.push(node.left);
         StringBuilder newPath = new StringBuilder(sb);
         newPath.append("->");
         newPath.append(Integer.toString(node.left.val));
         paths.push(newPath);
     }
     if (node.left == null && node.right == null) {
         String route = sb.toString();
         res.add(route);
     }
 }
 return res;
 }

迭代法

public List<String> binaryTreePaths(TreeNode root) {
       List<String> res = new ArrayList<>();// 存最终的结果
       if (root == null) {
           return res;
       }
       List<Integer> paths = new ArrayList<>();// 作为结果中的路径
       traversal(root, paths, res);
       return res;
   }

   private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
       paths.add(root.val);// 前序遍历，中
       // 遇到叶子结点
       if (root.left == null && root.right == null) {
           // 输出
           StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
           for (int i = 0; i < paths.size() - 1; i++) {
               sb.append(paths.get(i)).append("->");
           }
           sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
           res.add(sb.toString());// 收集一个路径
           return;
       }
       // 递归和回溯是同时进行，所以要放在同一个花括号里
       if (root.left != null) { // 左
           traversal(root.left, paths, res);
           paths.remove(paths.size() - 1);// 回溯
       }
       if (root.right != null) { // 右
           traversal(root.right, paths, res);
           paths.remove(paths.size() - 1);// 回溯
       }
   }

Leetcode 404 左叶子之和

寻找这课树左叶子结点的和，叶子结点是没有子节点的。

我们的思路是通过某个节点的父节点来判断他是否是叶子结点也就是node.left!=null&&node.left.left==null&&node.left.right==null;

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;  // 中
        return sum;
    }
}

Leetcode 513

寻找二叉树最左下角的值，注意不一定是最左边的值。

//递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

//迭代法
class Solution {

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}

随想练习

Leetcode 852山峰数组

线性查找, O(n)

public int peakIndexInMountainArray(int[] arr) {
        int len = arr.length;
        for(int i=0,j=len-1;i<len;i++,j--){
            if(arr[i]>arr[i+1]){
                return i;
            }
            if(arr[j-1]<arr[j]){
                return j;
            }
        }
        return -1;
    }

二分查找, O(log(n))

    public int peakIndexInMountainArray(int[] arr) {
    int left = 0;
    int right = arr.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

快速排序quicksort

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}
 
private static void quick(int[] array, int left, int right) {
 
    //递归结束条件:这里代表只有一个根   大于号：有可能没有子树  1  2  3   4  1为基准，pivot-1就越界了
    if(left >= right){
        return;
    }
 
    int pivot = partition(array, left, right);
    quick(array,left,pivot-1);
    quick(array,pivot+1,right);
}
 
public static int partition(int[] array,int start, int end){
    int i = start;//这里存开始时基准的下标，为了循环结束后，相遇值和基准值交换时能找到基准值的下标
    int key = array[start];//这是基准
    while (start < end){
        while (start < end && array[end] >= key){
            end--;
        }
        while (start < end && array[start] <= key){
            start++;
        }
        swap(array,start,end);
    }
    //到这里s和e相遇，把相遇值和基准值交换
    swap(array,start,i);
    return start;//返回基准下标
}

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.