算法进阶

1.链表反转：将一条单链表反转。
解法思路1：单链表的节点有一条指针指向下一个节点，最后一个节点指向null，我需要腾出两个变量缓存当前节点和它的next节点，令下一个节点的next指向当前节点（第一个节点的next指向null），不断迭代，直到最后一个节点。
解法思路2：递归算法。既然能迭代，就能递归。代码如下。

public static ListNode recursion(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode newHead = recursion(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

2.统计素数个数：给一个正数n，输出小于n的素数的个数。
解法1：双循环遍历，第一个循环遍历每一个数，第二个循环遍历它的一半以内能不能被这个数整除，最终计数求和。
解法2：埃氏算法。记录合数的个数，剩下的就是素数的个数。

public static int eratosthenes(int n) {
  //对每个数字产生一个标记，false表示素数
  boolean[] isPrime = new boolean[n];
  int ans = 0;
  for (int i = 2; i < n; i++) {
    if (!isPrime[i]) {
      ans += 1;
      //对这个素数求每一个倍数，把它们都标记为合数
      for (int j = i * i; j < n; j += i) {
        isPrime[j] = true;
      }
    } 
  }
  return ans;
}

3.删除排序数组中的重复项：一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
解法思路：由于是有序的，所以重复必然是相邻的元素重复，可以产生两个指针，不断移动快指针，遇到不重复的就接在慢指针后面。

public int removeDuplicates(int[] nums) {
  if (nums.length == 0) return 0;
  int i = 0;
  for (int j = 1; j < nums.length; j++) {
    if (nums[j] != nums[i]) {
      i++;
      nums[i] = nums[j];
    }
  }
  return i + 1;
}

4.寻找数组中心下标：数组中某一个下标，左右两边的元素之后相等，该下标即为中心索引
解法思路：先统计出整个数组的总和，然后从第一个元素开始叠加，
总和递减当前元素，叠加递增当前元素，直到两个值相等
5.求平方根：给出一个能开出正整数的正整数n，求平方根
解法1：对0到n做迭代循环，找到一个自己乘以自己等于n的数。
解法2：二分查找比从一开始迭代更快找到乘方等于n的数字
解法3：牛顿迭代，递归算法。如果i是n的平方根，则满足i = (i + x / i) / 2，不断递归，直到满足条件。

public static int newton(int x) {
  if(x==0) return 0;
    return ((int)(sqrts(x,x)));
  }
public static double sqrts(double i,int x){
  double res = (i + x / i) / 2;
  if (res == i) {
    return i;
  } else {
    return sqrts(res,x);
  }
}

6.两数之和：给定一个升序排列的整数数组 numbers ，从数组中找出两个数满足相加之和等于目标数 target 。假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。返回两数的下标值，以数组形式返回。
解法1：暴力破解，双循环遍历每一个可能组合。
解法2：哈希表，在哈希表中找target-当前数的key值，如果不存在就存入当前值为key，下标作为value放进去。

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

解法3：二分查找，从第一个值开始固定，二分查找另一个配对值，找不到就顺序固定下一个值。

public int[] twoSearch(int[] numbers, int target) {
  for (int i = 0; i < numbers.length; ++i) {
    int low = i, high = numbers.length -1;
    while (low <= high) {
      int mid = (high - low) / 2 + low;
      if (numbers[mid] == target - numbers[i]) {
        return new int[]{i, mid};
      } else if (numbers[mid] > target - numbers[i]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
  }
}

解法4：双指针法，头部指针先固定指向数组左侧，尾部指针指向数组右侧，尾部指针向左移动，找到和为target的值。如果出现和小于target的情况，头部指针右移尾部指针重置，继续找。

public int[] twoPoint(int[] numbers, int target) {
  int low = 0, high = numbers.length - 1;
  while (low < high) {
    int sum = numbers[low] + numbers[high];
    if (sum == target) {
      return new int[]{low + 1, high + 1};
    } else if (sum < target) {
      ++low;
    } 
    else {
      --high;
    }
  }
  return new int[]{-1, -1};
}

7.斐波那契数列
解法1：递归算法。

public static int calculate(int num){
  if(num == 0 ){
    return 0;
  }
  if(num == 1){
    return 1;
  }
  return calculate(num-1) + calculate(num-2);
}

解法2：有数据缓存的递归。原理图中的中间结果缓存后能减少大量存储开销。

public static int calculate(int num){
  int[] arr = new int[num+1];
  return recurse(arr,num);
}
private static int recurse(int[] arr, int num) {
  if(num == 0 ){
    return 0;
  }
  if(num == 1){
    return 1;
  }
  if(arr[num] != 0){
    return arr[num];
  }
  arr[num] = recurse(arr,num-1) + recurse(arr,num-2);
  return arr[num];
}

解法3：双指针线性遍历。不断计算前两个数的和，直到算到目标数字。

public static int iterate(int num){
  if(num == 0 ){
    return 0;
  }
  if(num == 1){
    return 1;
  }
  int low = 0,high = 1;
  for(int i=2; i<= num; i++){
    int sum = low + high;
    low = high;
    high = sum;
  }
  return high;
}

8.链表成环：给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环。如果链表中存在环，则返回 true ，否则，返回 false 。
解法1：哈希表。遍历链表并存入Set，如果已有该节点说明成环。
解法2：双指针法。定义快慢指针，一直向前遍历，如果进入环中，总有一个时刻两者指向同一节点。两个解法时间复杂度都是O(n)，但解法2空间复杂度低。

public static boolean hasCycle(ListNode head) {
  if (head == null || head.next == null) {
    return false;
  }
  ListNode slow = head;
  ListNode fast = head.next;
  while (slow != fast) {
    if (fast == null || fast.next == null) {
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
}

9.排列硬币：总共有 n 枚硬币，将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围内。
解法1：暴力算法。从1开始累加，直到总和大于n。
解法2：二分查找。从n/2开始计算所需硬币数，根据与n比大小进行二分查找。
10.合并两个有序数组：两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
解法1：先连接数组合并，再排序。
解法2：双指针法。分别指向两个数组第一个元素，开始比较，小的放进目标数组，并对指针右移。

public void merge(int[] nums1, int m, int[] nums2, int n) {
  int [] nums1_copy = new int[m];
  System.arraycopy(nums1, 0, nums1_copy, 0, m);//拷贝数组1
  int p1 = 0;//指向数组1的拷贝
  int p2 = 0;//指向数组2
  int p = 0;//指向数组1
  //将数组1当成空数组，比较数组1的拷贝和数组2，将较小的放入空数组
  while ((p1 < m) && (p2 < n))
    nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
  //数组2和数组1不等长，将多出的元素拷贝
  if (p1 < m)
    System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
  if (p2 < n)
    System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
}

解法3：双指针优化

public void merge(int[] nums1, int m, int[] nums2, int n) {
  int p1 = m - 1;
  int p2 = n - 1;
  int p = m + n - 1;
  while ((p1 >= 0) && (p2 >= 0))
    nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
  System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}

11.柠檬水找零：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。必须给每个顾客正确找零。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
解法：贪心算法。转化为需要找5刀和15刀的情况，分别看池子里有没有这个存量。

public boolean lemonadeChange(int[] bills) {
  int five = 0, ten = 0;
  for (int bill : bills) {
    if (bill == 5) {
      five++;
    } else if (bill == 10) {
      if (five == 0) {
        return false;
      }
      five--;
      ten++;
    } else {
      if (five > 0 && ten > 0) {
        five--;
        ten--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
}

12.三角形最大周长：给定由一些正数（代表长度）组成的数组A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回0。
解法：贪心算法。先对A排倒序，从最左侧取三个数，如果构不成三角形，说明最左侧的数字和其他数字都不能构成三角形，右移一位，直到能构成三角形。
13.二叉树遍历
解法1：递归。

//前序遍历的例子
public static void preorder(TreeNode root) {
  if (root == null) {
    return;
  }
  System.out.println(root.val);
  preorder(root.left);
  preorder(root.right);
}

解法2：利用栈的特性。

//前序
public static void preOrder2(TreeNode head) {
  if (head != null) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.add(head);
    while (!stack.isEmpty()) {
      head = stack.pop();
      if(head != null){
        System.out.println(head.val);
        stack.push(head.right);
        stack.push(head.left);
      }
    }
  }
}

解法3：同样也可以用队列，换一下解法2中入栈顺序即可。