算法笔记

递归

特征

• 自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。
• 终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。

解决递归问题三步曲

• 第一步，定义函数功能
• 第二步，寻找递归终止条件
• 第二步，递推函数的等价关系式

递归存在的问题

• 递归调用层级太多，导致栈溢出问题
  • 调大JVM的栈空间内存
  • 优化一下你的递归
• 递归重复计算，导致效率低下
  • 备忘录

「题目：」 翻转一棵二叉树。

https://leetcode-cn.com/problems/invert-binary-tree/

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
 public TreeNode invertTree(TreeNode root) {
        //节点为空 或 不为叶子节点
        if (root == null || (root.left == null && root.right == null)) {
            return root;
        }
        //翻转左子树
        invertTree(root.left);
        //翻转右子树
        invertTree(root.right);
        //将当前节点的左右子树交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

字符串相关

BF算法（Brute Force）

我们将模式串和主串进行比较，一致时则继续比较下一字符，直到比较完整个模式串

public int strStr(String haystack, String needle) {
       char[] haystackChars = haystack.toCharArray();
       char[] needleChars = needle.toCharArray();
       if (haystackChars.length < needleChars.length || StringUtils.isBlank(haystack) || StringUtils.isBlank(needle)) {
           return -1;
       }
       for (int i = 0; i < haystackChars.length; i++) {
           int j;
           for ( j= 0; j < needleChars.length; j++) {
               if (haystackChars[i+j] != needleChars[j]) {
                   break;
               }
           }
           if (j == needleChars.length) {
               return i;
           }
       }
       return -1;
   }