回溯定义

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

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

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

递归

这两道题目都是判断一个数字是不是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;
    }

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

记得在之前的一个面试中遇到了这个算法题， 但是当时没怎么想好如何判断两个字符串之间的大小，比如 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

找出最长的不重复的子字符串

首先一拿到这个题目的时候想到利用set集合来存储子字符串，当发现含有重复的字符的时候就将这个set清零。这个做法有一个明显的缺点就是当子字符串中的某一个字符和后面的重复的话，那么后面不行同的也会被清楚：例如dfvfab，在这个里面vfab应该是最短的子字符串，但是这时候这个方法会输出错误的值。

思路：

自己想不到解法之后就参考了Solution2，这个方法想了下也挺好的，遂记录下：
该方法是设置两个游标，一个在前，一个在后(定义为i,j)，当前面的一个发现在set集合中含有重复的字符，那此时停止i,然后j自增，当发现在set集合中已经将重复的那个字符剔除之后，此时在i自增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public int lengthOfLongestSubstring(String s) {
        //错误的思路，以为存入set就可以
        // if (s == null || s.length() == 0){
        //     return 0;
        // }
        // Set<Character> set =new HashSet<>();
        // int max=0;
        // for (int i =0 ;i< s.length() ;i++){
        //     char c = s.charAt(i);
        //     if (set.contains(c)){
        //         set.clear();
        //     }
        //     set.add(c);
        //     if (set.size() > max){
        //         max = set.size();
        //     }
        // }
        // return max;
        if(s == null || s.length() ==0){
            return 0;
        }
        Set<Character> set =new HashSet<>();
        int i=0,j=0,result=0,n=s.length();
        while(i < n && j <n){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                result=Math.max(result,j-i);
            }else{
                set.remove(s.charAt(i++));
            }
        }
        return result;
    }