常见算法

常见算法

1.链表反转

例：

输入：1 -> 2 -> 3 -> 4 -> 5

输出：5 -> 4 -> 3 -> 2-> 1

解法1：迭代

（1）while循环遍历链表

（2）声明3个变量：curr指向当前遍历节点，next临时存放下一个节点，pre临时存放当前节点(初始值为null)

（3）循环执行如下，结束条件是curr==null;

     -  临时变量next存放下一个节点：next = cure.next;

     -  当前节点的next指向pre：curr.next = pre;

     - 临时变量pre存放当前节点：pre = curr;

     - curr移到下一个节点：cure = next;

public Node iterate(Node head) {
  Node curr = head;
  Node next;
  Node pre = null;
  while (curr != null) {
    next = curr.next;
    curr.next = pre;
    pre = curr;
    curr = next;
  }
  return pre;
}

解法2：递归

（1）递归结束条件是head==null或head.next==null

（2）每个单元操作：

    - 当前节点的下一个节点的next指向当前节点：head.next.next = head;

    - 断开原有指针：head.next = null;

public Node recursion(Node head) {
  //递归结束条件：链表是null或递归到链表的最后一个节点
  if (head == null || head.next == null) {
    return head;//<1>
  }
  // 否则 进行递归操作。对下一个单元调用该方法
  Node newHead = recursion(head.next);//返回的是<1>处的值
  
  //对每个单元操作
  head.next.next = head;
  head.next = null;
  
  return newHead;
}

2.素数个数统计

统计n以内的素数个数

素数：只能被1和自己整除的自然数，0，1 除外

例：输入：100

    输出：25

解法1：暴力法

public int bf(int n) {
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (isSuShu(i)) count++;
  }
  return count;
}

private boolean isSuShu(int n) {
  for (int i = 2; i < n; i++) { // 此处条件判断可以优化为 i*i < n
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

可以优化一下，如上注释。

解法2：埃筛法

当找出一个素数2时，那么2✖️2，2✖️3，2✖️4，等待都不是素数，后面再循环判断就是浪费，可以用一个数组给标记出来，标记出来的数就不用再判断是否时素数了。

public int esf(int n) {
  boolean[] isHeShu = new boolean[n];
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (!isHeShu[i]) {
      count++;
      for(int j = 2*i; j<n; j+=i) {//i是素数，那么i的倍数都不是素数，标记为true
        isHeShu[j] = true;
      }
    }
  }
  return count;
}

同样可以优化：

i=2时，2✖️2，2✖️3，2✖️4

i=3时，2✖️3，3✖️3，4✖️3

j = 2✖️i可以优化为j = i✖️i

3.删除排序数组中的重复项

一个有序数组nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
不能使用额外的数组空间，必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

例：输入：[0,1,2,2,3,3,4]
输出：5

解法：双指针算法

双指针算法：

数组完成排序后，可以用两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针，初始状态j=i+1。

当nums[i] != nums[j] 时，i指针和j指针同时向后移动；

当nums[i] == nums[j]，就对j自增以跳过重复项，此时，把nums[j] 的值复制到nums[i+1]，即i++；

接着将再次重复相同的过程，直到j到达数组的末尾为止。

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]) { //等同于nums[i] == nums[j]时，只往后移动j指针。
            i++;//j已经在for循环中可自增
      nums[i]=nums[j];
    }
    }
    
    return i+1;//新数组长度等于i指针下标 加1；
}

4.寻找数组的中心下标

给定一个整数数组nums，请编写一个能够返回数组“中心下标”的方法。

中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心下标，返回-1。如果数组有多个中心下标，应该返回最靠近左边的那一个。
注意：中心下标可能出现在数组的两端。

解法：

先统计出整个数组的总和，然后从第一个元素开始叠加
总和递减当前元素，叠加递增当前元素，直到两个值相等

public int pivotIndex (int[] nums){
  int sum2=Arrays.stream(nums).sum();
  int sum1=0;
  for(int i=0; i<nums.length; i++){
    sum1 += nums[i];
    if(sum1 == sum2){//index=i的元素 sum1和sum2都加了，如果相等，说明i就是中心下标。
        return i;
    }
    // 否则，右侧sum减去nums[i]，接着进行下一轮循环。
    sum2 = sum2 - nums[i];
  }
  return −1;
}

5.x的平方根

在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分

解法1: 二分法

属于暴力解法的优化

//二分查找
public int binarySearch (int x){
  //定义最左最右两个数值
  int l = 0;
  int r = x;
  
  int index = -1;//为记住mid值

  while(l <= r){
    int mid = l + (r-l)/2;//l和r之间的中间值等于 右值减去左值，再加上左值
    if(mid * mid <= x){ //说明x的平方根在mid的y右侧
      index = mid;
            l = mid + 1;//最左数变为mid+1
    } else {
      r = mid - l;
    }
  }
  
  return index;
}

解法2: 牛顿送代

等同于 n*n = x ，求n

那么 n = x/n

double res = (n + x/n)/2，然后递归，让res无限接近n，直到等于。

public int newton(int x) {
  if (x == 0) {
    return 0;
  }
  return sqrt(x, x);//第一个参数可以随意取值
}

public double sqrt(double n, int x) {
  double res = (n + x/n)/2;
  if (res == n) {
    return n;
  } else {
    return sqrt(res, x);
  }
}

6.两数之和

给定一个整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。

返回两数的下标值，以数组形式返回。

解法1: 暴力解法

使用两个for循环，遍历判断。

优化点：第2层for循环的起始下标可以时i+1

解法2: 使用Map标记

在解法1上优化，x+y=target，那么y=target-x

使用一个for循环找y，对于不满足的放入Map<数,下标>，

后面循环可以先判断这个map中是否已经存在，存在时直接返回相应下标，不存在时放入。

解法3: 有序时，二分法

对于有序数组，可以用二分法，low和high分别表示数组中0号和末尾的数值，

相加后，满足target直接返回；

大于target时，high移动到mid左侧1位，

小于target时，low移动到mid右侧1位，

解法4: 有序时，双指针法

类似二分法，只是用index指针来分别指向最低和最高位，

两位对应值相加大于target时，右边指针左移1位，

小于target时，左侧指针向右移动1位，

直到两位对应值相加值等于target。

7.斐波那契数列

求取斐波那契数列第N位的值。

麦波那契数列：每一位的值等于他前两位数字之和。前
两位固定0,1,1,2,3,5.8。。。。

解法1:暴力递归

public int calculate(int n) {
  if (n == 0 || n == 1) {//前两位固定
    return n;
  }
  //以后每位都等于前两位只和
  return calculate(n-1) + calculate(n-2);
}

解法2:去重递归

对解法1降低时间复杂度

比如计算c(5) = c(4)+c(3) = c(3)+c(2) + c(2)+c(1) = ...

重复计算了c(3)、c(2)、c(1) 等，可以去重，对已经计算过的值进行保存，以后遇到了直接用。

对每位得值存入对应数组中

public int calculate(int n) {
  // 用一个数组来存放对于位置的斐波那列数
  int[] arr = new int[n + 1];
  
  return indexValue(arr, n-1) + indexValue(arr, n-2)
}

// 返回的是对于位值，并对于对应位值为0的下标赋值
private int indexValue(int[] arr, int n) {
  if (n == 0 || n == 1) {
    return n;
  }
  
  if (arr[n] != 0) { //说明对于位已有值，直接返回值即可
    return arr[n];
  }
  
  //还是递归填值
  arr[n] = indexValue(arr, n-1) + indexValue(arr, n-2);
  return arr[n];
}

解法3:双指针迭代

对解法2降低空间复杂度

不需要对每位的斐波那列数都存放在数组里，其实只需要存放两位即可，然后重复利用两位

public int iterate(int n) {
  if (n == 0 || n == 1) {
    return n;
  }
  
  int low = 0;
  int high = 1;
  for (int index = 2; index <= n; index++) {
    int sum = low + high;
    low = high;
    high = sum;
  }
  return high;
}

8.排列硬币

总共有n枚硬币，将它们摆成一个阶梯形状，第k行就必须正好有k枚硬币。
给定一个数字n，找出可形成完整阶梯行的总行数。
n是一个非负整数，并且在32位有符号整型的范围内。

解法1: 暴力解法

每排完一行，计算剩余的硬币个数，看是否排出下一行。

public int getTheRow(int num) {
  for (int row = 1; row <= num; row++) {//第row行放row个硬币，最多肯定不超过num行
    int last = num - row; //放完第row行后还剩下last个硬盘
    num = last; // 把剩余的个数赋值给num
    if (num <= row) { // 如果剩余num数小于或等于当前row，那么说明下一个行（row+1）肯定不能形成一个完整的行
      return row;
    }
  }
  return 0;
}

解法2:二分法

有num个硬盘，排完后最多不超过num行，使用二分法在这num行中找出答案的x行，然后对1-x行的总和应该等于num

public int div(int num) {
  //申明2个边界变量
  int low = 0;
  int high = num; //假设最多就有num行
  
  while(low <= high) {
    int mid = (high - low)2 + low;
    int sum = mid*(mid + 1)/2; // mid行的之和硬币数
    
    if (sum == num) { //如果刚好相等，说明mid这一行就是最后一行，刚刚好
      return mid;
    } else if (sum > num) {//总和大了，high左移到mid左侧一位
      high = mid - 1;
    } else if (sum < num) {// 总和小了，low右移到mid右侧一位
      low = mid + 1;
    }
  }
}

解法3:牛顿迭代

假设答案是x，那么求和， num=(1+x)x/2. ---> x * x = 2 num - x

那么，x = (2 num - x)/x

public double newton(double x, int num) {
  double result = (2 * num - x) / x;
  if (result == x) {
    return result;
  } else {
    return newton(result, num);
  }
}

public int getRowValue(int num) {
  if (num == 0) return 0;
  
  return (int)newton(num, num);
}

9.环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达该节点，则链表中存在环
如果链表中存在环，则返回true。否则，返回false

解法1:常规

循环遍历，当遍历到曾经遍历过的节点，说明存在环。那么如何来判断曾经是否遍历过？

可以使用set集合，不能放进去的节点表面存在环。

public boolean isCycle(Node head) {
  Set<Node> set = new HashSet<>();
  while(head != null) {
    if(!set.add(head)) {
      return true;
    }
    head = head.next;
  }
  return false;
}

解法2:双指针法（快慢指针）

优化解法1的空间复杂度。

假设有两个指针，一个快一个慢，如果没环则最后快指针最先指向null；

如果有环，快指针先进入环，慢指针后进入环中，并且它们两肯定会相遇。

public boolean isCycle(Node head) {
  if (head == null || head.next == null) {
    return false;
  }
  
  //声明快慢指针
  Node slow = head;
  Node quick = head.next;
  while(slow != quick) {
    if (quick == null || quick.next == null) {
      return false;
    }
    slow = slow.next; // 慢指针每次走一步
    quick = quick.next.next;//快指针每次走两步
  }
  return true;//说明跳出来while循环，存在环
}

10.合并两个有序数组

两个有序整数数组num1，将num2，将num2合并到num1中，使num1成为一个有序数组。
初始化num1和num2的元素数量分别为m和n。假设num1的空间大小等于m+n，这样它就有足够的空间保存来自num2的元素。

例如：

num1={1,3,5,7,9,0,0,0,0}

num2={2,4,6,8}

解法1:常规法

先合并再排序

public int[] merge(int[] num1, int m, int[] num2, int n) {
  System.arraycopy(num2, 0, num1, m, n);
  Arrays.sort(num1);
  return num1;
}

解法2:双指针法

使用一个新的数组存放最后的结果，用2个指针分别指向已知的两个数组头部，两个指针指向的值比较，较小的那个值存放到结果数组。

这里为了方便演示，num1不需要例子中的0占位，返回的结果也不需要必须是num1

public int[] merge(int[] num1, int m, int[] num2, int n) {
  int[] result = new int[m+n]; //用一个新的数组来存放最后的结果
  
  int p1 = 0; //指向num1数组的头
  int p2 = 0; //指向num2数组的头
  int index = 0; //指向result数组的头
  
  while(p1 < m && p2 < n) {
    result[index++] = num1[p1] < num2[p2] ? num1[p1++] : num2[p2++];
  }
  
  //上述while循环跳出，说明肯定有一个数组遍历完了。下面两个if只有一个能执行。
  if (p1 < m) {//num1数组还有没遍历到的元素
    // 把num1数组从p1开始拷贝，拷贝到result数组（从index开始，拷贝m+n-index个元素）
    System.arraycopy(num1, p1, reuslt, index, m+n-index)；
  }
  if (p2 < n) {//num2数组还有没遍历到的元素
    System.arraycopy(num2, p2, reuslt, index, m+n-index)；
  }
  
  return result;
}

解法3:尾部双指针

num1={1,3,5,7,9,0,0,0,0}

num2={2,4,6,8}

优化空间复杂度，不使用额外的数组。

用两个指针分别指向以上数组尾部（有效位），再弄一个指针指向num1最后（m+n），谁大就放在num1的最后。

public int[] merge(int[] num1, int m, int[] num2, int n) {
  int p1 = m-1; //指向num1数组的有效位的末尾
  int p2 = n-1; //指向num2数组的末尾
  int index = m+n-1; //指向num1的真末尾
  
  while(p1 >= 0 && p2 >= 0) {
    result[index--] = num1[p1] > num2[p2] ? num1[p1--] : num2[p2--];
  }
  
  // 如果num1数组的0号位的数比num2的0号位数小，那么num2肯定会移动完，此时正好满足num1就是最后结果；
  // 相反时，num2肯定有没移动完的数，此时需要拷贝。拷贝数的个数是p2+1（如果是上一种情况，p2=-1，也满足）
  System.arraycopy(num2, 0, num1, 0, p2+1)；
  
  return num1;
}

11.子数组最大平均数

给一个整数数组，找出平均数最大且长度为k的下标连续的子数组，并输出该最大平均数。
输入：[1,12,-5,-6,50,3], K=4
输出:12.75
最大平均数(12-5-6＋50)/4＝51/4＝12.75

解法：滑动窗口（固定差的双指针）

长度为k的区间窗口，在数组中移动，找出最大和的窗口。

先计算0-k区间的总和sum，然后移动后面那个指针，每移动一次得到的和sum等于上一次sum减去上一窗口的起始值再加上此次窗口的末尾值。

public double findMax(int[] nums, int k) {
  // 求一个窗口的和
  int sum = 0;
  for (int i = 0; i < k; i++) {
    sum += nums[i];
  }
  
  // 求所有窗口之中最大的和
  int max = sum;
  for (int i = k; i < nums.length; i++) {
    sum = sum - nums[i-k] + nums[i];
    max = Math.max(sum, max);
  }
  
  return 1.0 * max / k;
}

12.二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解法1:递归

深度优先

根节点（其实是每个节点）的最小深度等于左子树的最小深度 和 有子树的最小深度 两者之间的最小值，然后递归，递归结束标志是没有子节点（即到了叶子节点）。

public int minDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }
  
  // 其实，就是叶子节点时，深度是1；
  if (root.left == null && root.right == null) {
    return 1;
  }
  
  // 如果不是叶子节点，那么该节点的深度等于左右子树的最小深度中较小的那个，递归。
  int min = 0;
  if (root.left != null) {
    min = Math.min(minDepth(root.left), min);
  }
  if (root.right != null) {
    min = Math.min(minDepth(root.right), min);
  }
  
  // 那么该节点的最小深度就等于 子树的最小节点 ➕ 1
  return min + 1;
}

解法2:广度优先

从根节点开始，对于每遍历一个节点都放在队列中。然后对非空的队列进行取节点，根节点计最小深度为1，如果存在叶子节点，最小深度加1。。。

13.最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

解法：贪心算法

遍历数组，每次标记好起始位，然后往后遍历，到遍历到不满足要求的元素，计算最大长度，并重置其实位，依次往后，每次都是得到最大的值。

[1,2,3, 2,3,4, 3,4,5,6,7]

public int maxList(int[] nums) {
  int start = 0;
  int max = 0;
  for (int i = 1; i < nums.length; i++) {
    if (nums[i] < nums[i-1]) {
      max = Math.max(i - start, max);
      start = i;
    }
  }
}

14.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。必须给每个顾客正确找零
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回true，否则返回false.

解法：贪心算法

只有3中币种：5，10，20

对于5元，直接收下；

对于10元，只有一种找零，找5元；

对于20元，有两种找零方式，10+5，或 5+5+5；

但10+5找零是最优解，因为5元是万能的。

public boolean change(int[] bills) {
  //初始状态，卖家手里没有钱
  //申明手里三种币种的张树，20元的不用管，因为20元收到后对找零这件事没帮助。
  int five = 0;
  int ten = 0;
  
  for (int bill : bills) {
    if (bill == 5) {//直接收下
      five++;
    } else if (bill == 10) {
      if (five == 0) {//手里没有5元的
        return false;
      }
      //否则 
      five--;
      ten++;
    } else { //20
      if(five > 0 && ten > 0) {
        five--;
        ten--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  
  return true;
}

15.三角形的最大周长

给定由一些正数(代表长度)组成的数组arr，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回0

解法：贪心算法

对数组排序，然后取最大的3个数，判断这个数中较小的两个数之和大于最大的那个数，那么就满足要求。

public int maxLength(int[] nums) {
  Arrays.sort(nums);
  for (int i = nums.length-1; i >= 2; i++) {
    if(nums[i] < nums[i-1] + nums[i-2]) {
      return nums[i] + nums[i-1] + nums[i-2];
    }
  }
  return 0;
}

16.二叉树遍历

解法1:递归

//前序遍历
void preOrder(TreeNode root){
  if(root == null){
    return;
  }
  System.out.println(root.val);
  preOrder(root.left);
  preOrder(root.right);
}

//中序遍历
void inOrder(TreeNode root){
  if(root == null){
    return;
  }
  preOrder(root.left);
  System.out.println(root.val);
  preOrder(root.right);
}


//后序遍历
void postOrder(TreeNode root){
  if(root == null){
    return;
  }
  preOrder(root.left);
  preOrder(root.right);
  System.out.println(root.val);
}

解法2:迭代

//前序遍历
void preOrder(TreeNode root){
  if(root == null){
    return;
  }
  
  Stack<TreeNode> stack = new Stack<TreeNode>();
  stack.push(root);
  
  while(!stack.empty()){
    TreeNode node = stack.pop();
    System.out.println(node.val);
    if(node.right!=null){
      stack.push(node.right);
    }
    if(node.left != null){
      stack.push(node.left);
    }
  }
}


//中序遍历
void inOrder(TreeNode root){
  Stack<TreeNode> stack = new Stack<TreeNode>();
  TreeNode current = root;
  while(current != null|| !stack.empty()){
    while(current != null){//把所有左树都放进stack里
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    System.out.println(current.val);
    current = current.right;
  }
}


//后序遍历

17.字符串查找

问题：字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置，不存在返回-1
例如：str1:“ABC12345de”,str2:"12345" 就是一个连续子串

解法1:暴力算法

// force find
int getIndexSubString(const string s1,const string s2){
    // 特殊情况
    if(s1.length()<1 || s2.length()<1 || s1.length()<s2.length()) return -1;
    
    // 正常情况：s1.length >=s2.length
    int j=0;
    for(int i=0;i<s1.length();i++){
        for(j=0;j<s2.length();j++){
            if(s1[i+j]!=s2[j]) break; // 只要有一个不相等就break
        }
        //没有break说明存在或者遍历完还没有
        if(j>s2.length()-1){
            return i;
        }
    }
    return -1;
}

解法2:kwp算法

18.打家劫舍

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋都被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入:[1,2,3,1] 输出：4

输入:[2,7,9.3,1] 输出：12

解法1:递归

第index位的数组的最优解等于，第index-1和第index-2最优解加上nums[index]两者中最大的值。

public int maxMoney(int[] nums, int index) {
  if(nums == null || index < 0) {
    return 0;
  }
  if (index = 0) {
    return nums[0];
  }
  return Math.max(maxMoney(nums, index-1), maxMoney(index-2) + nums[index]);
}

解法2:动态规划

以上递归解法，会出现重复计算某些index情况。优化：可以用一个数组来存放所有index情况下的最优值，动态迭代

public int maxMoney(int[] nums) {
  int length = nums.length;
  if(nums == null || length == 0) {
    return 0;
  }
  if (index = 1) {
    return nums[0];
  }
  
  //迭代来存放所有index情况下的最优解
  int[] dp = new int[nums.length];
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (int index = 2; index < nums.length; index++) {
    dp[index] = Math.max(dp[index-1], dp[index-2] + nums[index]);
  }
  return dp[length-1];
}

动态规划：最优子结构----递推----重叠子问题