算法模板

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n; // 我们定义target在左闭右开的区间里，[left, right)  
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，因为是左闭右开的区间，nums[middle]一定不是我们的目标值，所以right = middle，在[left, middle)中继续寻找目标值
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在 [middle+1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值的情况，直接返回下标
            }
        }
        return right;
    }
};

void kmp(int* next, const string& s){
    next[0] = -1;
    int j = -1;
    for(int i = 1; i < s.size(); i++){
        while (j >= 0 && s[i] != s[j + 1]) {
            j = next[j];
        }
        if (s[i] == s[j + 1]) {
            j++;
        }
        next[i] = j;
    }
}

二叉树的定义：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

树:

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

Q:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 private boolean dfs(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return false;//定义出口 boolean lson = dfs(root.left, p, q); boolean rson = dfs(root.right, p, q); if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) { ans = root; } return lson || rson || (root.val == p.val || root.val == q.val); } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { this.dfs(root, p, q); return this.ans; }

Q:给定一个二叉树，找出其最小深度 public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int min_depth = Integer.MAX_VALUE; if (root.left != null) { min_depth = Math.min(minDepth(root.left), min_depth); } if (root.right != null) { min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1; } Q:前中序遍历 public void preOrderTraverse1(TreeNode root) { if (root != null) { System.out.print(root.val+" “);//前序 preOrderTraverse1(root.left); System.out.print(root.val+” “);//中序 preOrderTraverse1(root.right); System.out.print(root.val+” “);//后序 } } public void OrderTraverse2(TreeNode root) { Stack stack = new Stack<>(); TreeNode pNode = root; while (pNode != null || !stack.isEmpty()) { if (pNode != null) { System.out.print(pNode.val+” “);//前序遍历 stack.push(pNode); pNode = pNode.left; } else { TreeNode node = stack.pop(); System.out.print(pNode.val+” “);//中序遍历 pNode = node.right; } } } Q:后序遍历 public static void posOrder1(TreeNode node) { if(node==null) return; Stack s = new Stack();

    TreeNode curNode = node; //当前访问的结点
    TreeNode lastVisitNode = null; //上次访问的结点

    //把currentNode移到左子树的最下边
    while(curNode!=null){
        s.push(curNode);
        curNode = curNode.left;
    }
    while(!s.empty()){
        curNode = s.pop();  //弹出栈顶元素
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if(curNode.right!=null&&curNode.right!=lastVisitNode){
            //根节点再次入栈
            s.push(curNode);
            //进入右子树，且可肯定右子树一定不为空
            curNode = curNode.right;
            while(curNode!=null){
                //再走到右子树的最左边
                s.push(curNode);
                curNode = curNode.left;
            }
        }else{
            //访问
            System.out.println(curNode.val);
            //修改最近被访问的节点
            lastVisitNode = curNode;
        }
    }

} Q:层序遍历 public void levelTraverse(TreeNode root) { if (root == null) { return; } LinkedList queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.val+” “); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } }

int getDepth(TreeNode* node) {
    if (node == NULL) return 0;
    return 1 + max(getDepth(node->left), getDepth(node->right));
}

int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

    int n = 1005; // 更具题意而定 
    int father[1005];

    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
    // 判断 u 和 v是否找到同一个根
    bool same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }