在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;
    }

二叉树的中序遍历

题目如下:

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;
    }