回溯定义

按照维基百科上给到的定义：回溯是一种最优选择法，如果发现某一些选择不符合目标，那么就会进行退回操作

在了解回溯算法之前，首先就不得不提到一个概念「递归」，递归 和 回溯 在基本的逻辑上其实是差不多的，只不过回溯都含有撤销操作，而递归则是一条路走到底，两者都属于暴力搜索法。

最经典的题目就属于「八皇后」

递归

在Leetcode上有一道题目，如下：

In a deck of cards, each card has an integer written on it.
Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:
Each group has exactly X cards.
All the cards in each group have the same integer.

这一题就是一个求最大公约数的题目，当任意两组的公约数为1的时候，那么此时就说明，他们的分组数量不相等就可以直接返回false了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for(int val : deck){
            count[val]++;
        }

        int sum = -1;
        for(int val: deck){
            if(sum == -1){
                sum = count[val];
            } else {
                sum = getGcd(sum,count[val]);
            }
            if(sum == 1){
                return false;
            }
        }
        return true;

    }

这两道题目都是判断一个数字是不是2(第一题)，3(第二题)的n次方，在做第一题的时候思路基本上和标准解法想法相同，但是在做第二题的时候，看到了许多比较有创意的解法，所以记录下

判断一个数是不是2的n次方

解法一

这个解法也就是我第一次就想到的一个解法，就是做 & 运算，因为一个数字若是2的n次方，那么很明显就是这个数字的2进制肯定只会有一个1，例如：
32=100000 ,64 =1000000。所以只需要判断 n 与 n-1 做一个& 运算就可以知道了。

1
2
3
4
5
6

public boolean isPowerOfTwo(int n) {
        if( n <1){
            return false;
        }
        return (n & ( n-1)) ==0;
    }

说到动态规划，离不开一个爬楼梯的问题和一个铺砖快的问题。
爬楼梯的问题：

一个N层的楼梯，一次可以走一步或者两步，求走到楼梯顶部的所有步数

铺砖快的问题：

一个2*n的地方，需要铺上瓷砖，但是瓷砖的规格只有 2x1 的，求多少种铺法。

计算到顶层的最小问题：

字符串数组拼接出一个最小的数字

记得在之前的一个面试中遇到了这个算法题， 但是当时没怎么想好如何判断两个字符串之间的大小，比如 23 和 223 之间，其组合起来绝对是 23 大于 223，所以 223是需要放在前面的。

思路

其实可以将两个字符串相加，例如 22323 < 23223 ，所以 223 是需要放在 23 前面的，下面就是代码.

代码

在Leetcode上有一道算法题目判断最后一位是不是一位的，题目的意思是当在一个数组中如果存在10或者00，那么这个就是一个连续的。这个数组的最后一位永远都是0。

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).
Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

思路：

刚开始错误的理解题目的意思了，导致一直在纠结数组的最后两位和三位，后来看了答案之后觉得自己的思路没有想到电子上，所以在此记录一下。

解法一：

二叉树的中序遍历

题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

意思就是需要求出一个二叉树中绝对值最小的值。

刚开始的第一个想法就是递归，然后比较当前节点和其左右两个节点的值，但是发现有一个缺陷就是如果一个根节点是3，其左节点是10，10的右节点是4，那么最小的值便是1，然后通过递归只能是 10-3，10-4 。所以当时就放弃了

题目如下:

1
2
3
4
5
6

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

也就是一个乱序的数组，然后将数组中的前三大的数组换成指定的字符串。其中有一个解法是比较有新意的，其思路如下：

另外再开辟一个数组，然后数组的长度是原数组中数字最大的那个值，那么在进行遍历的时候，新建的数组中最后三位肯定是最大的，然后依次将其原索引找出来即可。

具体的代码如下:

首先是Leetcode上两道比较好的一个题目，分别如下：

• https://leetcode.com/problems/letter-case-permutation/description/ Letter Case Permutation
• https://leetcode.com/problems/max-area-of-island/description/ Max Area of Island

关于字符串的那一题便是将一个字符串里面的任意一个字符进行大小写的变换，此题有两种解法，一种是 BFS 按照字符窜中的字符遍历，将其变成大小写，然后存入栈中，最后便每一次向后迭代，然后再存入即可。另一种则是 DFS ，通过一种不断递归的方式来进行大小写的变换的，和爬楼梯的那个算法极其类似

字符串

字符串的BFS

对于Manacher算法自己研究了一会，总算是理解了其中的含义，乘着有时间正好可以过来记录下：

思路：

1. 将字符串变成奇数，通过加非字符串里面的符号表示，不过一般都是加的#
2. 找出以当前索引为中点的最长回文数长度，并且记录，例如：#a#b#a,这个字符串所对应的长度便是[1,2,1,2,1,1],因为在#的时候组成不了回文，所以#这里是1，而到了a这里，因为#a#组成了回文，所以a的最长回文字符串长度是2,以此类推
3. for循环开始比较，在这里一般来讲是首先需要定义一个字符串的边界变量，以防止数组越界，另外一个就是最长回文字符串的中点坐标，以此类推就可以

代码：

将填充符号计入到需要匹配的的字符串中