201. Bitwise AND of Numbers Range

描述

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

分析

第一眼看这是一道很简单很直接的题目,但做了这么多Leetcode,也很容易想到这肯定是一道技巧性很强的题目,直接做的结果就是超时或者超内存。

所以我们必须在时间和空间上做出优化,首先观察到的是,如果下界m==0,那么无论经过多少次运算,其结果最终都为0.

但仅有这一点还不够,所以要从别的角度考虑。

所以我们举几个例子观察一下: m==5,n==7时,返回4

101->111
10->11
1->1

m==2,n==4,返回

010->100
1->10

我们看到,如果每次让m,n右移一位,直到m,n相等为止。记录右移次数count,让最后的m左移count位,就是我们需要的结果。

水平有限,不能给出详尽的数学证明,但可以给出正确结论,即:m到n范围内所有数字相与的结果就是m和n在二进制表示下的”公共首部”

代码如下:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count=0;
        while(m!=n){
            count++;
            m=m>>1;
            n=n>>1;
        }
        return m<<count;
    }
};

78. Subsets

描述

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

分析

这道题要求返回一个给定数组的全部子集,那么我们想到的最简单的方法就是进行枚举,但随着数组中元素数量增加,要枚举的次数也会越来越多,显然这是不现实的。所以我们要从别的角度进行考虑。

假如我们第一次向结果中加入一个空集,结果的状态应该如下:

[   
    [ ]
]

之后我们加入1这个元素

[   
    [ ]
    [1]
]

然后加入2

[   
    [ ]
    [1]
    [1 2]
    [2]
]

然后加入3

[   
    [ ]
    [1 2 3]
    [2 3]
    [3]
]

………………

如此往复最后一定可以得到我们需要的结果,据此我们可以看出,全部子集就是每次先克隆上一个状态,接着向这个克隆的结果中添加新的一个元素,直到所有元素都被添加进去为止。这是一种利用迭代解决此问题的方法,代码如下:

/*Solution1 ,Iteration*/
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res(1);
        for(int i=0;i<S.size();++i){
            int size=res.size();
            for(int j=0;j<size;j++){
                res.push_back(res[j]);
                res.back().push_back(S[i]);
            }
        }
        return res;
    }
};

这个问题还可以利用Backtracking算法来解,准确地说,Backtracking算法是解决这类解为一个空间的问题的通用方法。

我们以[1 2 3 4]为例,分析如何用递归的方式处理这个问题。

subsets([1 2 3 4])=[]
                   //push(1)
                   [1,subsets[2 3 4]]
                   //pop,push(2)
                   [2,subsets[3,4]]
                   //pop,push(3)
                   [3,subsets[4]]
                   //pop,push(4)
                   [4,subsets[]]
                   //pop

避免重复计入,我们每次需要做一次pop操作

那么我们需要从第一个数字开始,通过递归的方式尝试所有的可能,如果结果合法,我们将其放入结果中,如果不合法,我们就需要进行回溯,代码如下:

/*Solution2 Recursion*/
class Solution {
private:
    void backtracking(vector<int> & nums,vector<int> & sub,vector<vector<int>> & subs,int start){
        subs.push_back(sub);
        for(int i=start;i<nums.size();++i){
            sub.push_back(nums[i]);
            backtracking(nums,sub,subs,i+1);
            sub.pop_back();
        }
    }
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> subs;
        vector<int> sub;
        backtracking(S,sub,subs,0);
        return subs;
    }
};

Power of K问题

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

要求判断一个整数是否是2的幂次方,最简单的办法就是不断除以2,判断最后出现的数字是不是1。

但是这样过程过于复杂,而且没有用到位操作的知识。所以我们写出几个2的幂次方数进行观察。

1   1
2   10
4   100
8   1000
16  10000
32  100000

由位操作的知识我们可以得到一个结论,如果一个数是2的幂次方,那么其二进制表示中只有首位存在一个1,其余均为0.

所以如果我们让n&(n-1)并且得到的值为0,我们就可以确认只有首位为1,其余均为0.那么这道题就找到了解决方案,代码如下:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&!(n&(n-1));
    }
};

326. Power of Three

Given an integer, write a function to determine if it is a power of three.

这道题有些变化,要求判断一个整数是否是3的幂次方。

3的幂次方似乎没有什么特殊的性质(反正我没看出来),所以我们就要利用一下数学知识了,即:如果一个数是3的整数幂次方,那么其以3为底的对数必然是一个整数。

所以这个问题转化为判断一个运算结果是否是整数,在C++中,判断整数的方法是:num-(int)num==0

但是这里需要注意一点,C++中的内建函数log,其底数是e,也就是自然对数。所以我们需要利用一下换底公式,但如果直接利用换底公式又会遇到另一个问题。

n=243时:

log(243) = 5.493061443340548    log(3) = 1.0986122886681098
   ==> log(243)/log(3) = 4.999999999999999

这是一个很尴尬的问题,243应该是3的5次幂,但在这里我们对3取对数后却没有得到5,而是一个十分接近5的浮点数。这是什么原因呢?

这是因为在计算机中,log(3)的计算值实际上比真值要略大一些,就导致了这个比值变小了。

要消除这个误差,我们需要用常用对数(內建)来计算以3为底的对数。代码如下:

class Solution {
public:
    bool isPowerOfThree(int n) {
        double res=log10(n)/log10(3);
        return (res-(int)(res))==0? true:false;
    }
}; 

当然这道题也有一个投机取巧的算法,不推荐:

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && (1162261467 % n == 0);
    }
}; 

因为1162261467是32位int的范围中最大的3的幂次方数。

(然而你都知道3的幂次方有哪些数了你还算啥呀?!)

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example: Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

这次要求判断4的幂次方,我们很容易想到,一个数如果是4的幂次方,那么它一定也是2的幂次方,反之则不然。

所以我们可以先找出全部2的幂次方,再观察4的幂次方有哪些特殊的性质。

1   0000 0001
4   0000 0100
16  0001 0000
2   0000 0010
8   0000 1000

通过观察,我们发现2的幂次方和4的幂次方都是只有一个1,但是如果是4的幂次方那么1一定出现在奇数位上,所以我们需要取出其奇数位上的1(如果有的话)。

所以我们构造一个只有奇数位上有1,其余位上都为0的数字,我们想到了0x5==(0101)B,那么考虑int类型,我们采用0x 5555 5555==‭01010101010101010101010101010101‬来取出需要的位。

代码如下:

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num>0&&!(num&(num-1))&&(num&(0x55555555));
    }
};

另外,4的幂次方还有一个性质,即减1以后可以被3整除,利用此法也可以进行判断,不再赘述。

这些题给我们一个警示,计算机在进行一些精密的计算时有时候会有一些我们意想不到的误差。

我们对计算机的理解还远远不够,所以,每时每刻都要Stay hungry,Stay Foolish.

有时候我们需要在两个或多个字符串之间建立映射,以便用来解决一些匹配问题,那么我们可以用unordered_map来建立这个映射,同时在字符集较小的情况下,我们可以动用一些编程技巧。

先复习一道简单的题目:

299. Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"

In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

这道题干比较长的题目其实并不是很难,问题的关键在于我们要建立两个字符串之间的映射,并且弄清楚元素进入这个映射的条件。

那么考虑到字符集较小,我们用数组模拟hash,这是一个很节省空间的编程技巧。

对两个字符串同时进行遍历,两个字符相同时则记为一个Bull,不同时,则让两个字符在数组中对应的元素加1,也就是用来统计出现次数。

最后,要统计cow,对两个数组进行遍历,每次只加较小值,否则会造成cow的重复计数,代码如下:

class Solution {
public:
    string getHint(string secret, string guess) {
        if(secret.empty()||guess.empty())
            return "0A0B";
        vector<int> countS(10,0);
        vector<int> countG(10,0);
        string res;
        int countA=0,countB=0;
        for(int i=0;i<secret.size();i++){
            if(secret[i]==guess[i])
                countA++;
            else{
                countS[secret[i]-'0']++;
                countG[guess[i]-'0']++;
            }
        }
        for(int i=0;i<countS.size();i++)
            countB+=min(countS[i],countG[i]);
        res=to_string(countA)+'A'+to_string(countB)+'B';
        return res;
    }
};

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true.

pattern = “abba”, str = “dog cat cat fish” should return false.

pattern = “aaaa”, str = “dog cat cat dog” should return false.

pattern = “abba”, str = “dog dog dog dog” should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

这道题还是需要建立一个映射,但最开始需要做的并不是马上建立映射,需要用一点编程技巧将str拆分成以空格为间隔的字符串。

拆分完成后,我们需要整理一下新元素进入映射的条件 1.pattern中的字母存在于hash,那么查看以pattern为key的元素是否等于当前的word,不等,直接返回false。 2.不存在时,也不能立即将其加入hash,需要遍历整个hash,查看是否有某个之前的字母已经映射到了当前的word,如果有,直接返回false。

分析清楚后,代码就很简单了。

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> res=divideStr(str);
        unordered_map<string,string> hash;
        istringstream in(str);
        int i=0;
        for(string word;in>>word;i++){
            if(hash.find(pattern[i])!=hash.end()){
                if(hash[pattern[i]]!=word)
                    return false;
            }
            else{
                for(unordered_map<char,string>::iterator it=hash.begin();it!=hash.end();it++){
                    if(it->second==word)
                        return false;
                }
                hash[pattern[i]]=word;
            }
        }
        return i==pattern.size();
    }
};

再来看另一道

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example, Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

这道题其实和上面那道题很相似,如果用hash的话代码几乎没有什么变化。因为只有字母,所以我们用一个编程技巧,即用数组模仿hash,代码如下:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int map1[256]={0},map2[256]={0},i=0;
        for(i=0;i<s.size();i++){
            if(map1[s[i]]!=map2[t[i]])
                return false;
            map1[s[i]]=map2[t[i]]=i+1;
        }
        return i==s.size();
    }
};

最后看一道有难度的题目

49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

这道题算是一个对变位词进行归类的题目,那么和我们讨论的用hash进行字符串之间的映射有什么关系呢?

要归类,那么必须要有一个具体且确定的标准,既然是变位词,那么互为变位词的字符串在排序过后一定是相同的,将其作为主键即可。

遍历每一个词,将其加入unordered_map即可。最后需要归类时,遍历unordered_map,将每个主键对应的vector压入结果即可。代码如下:

class Solution {
private:
    string strSort(string& str){
        int count[26]={0},p=0,size=str.size();
        string res(size,'a');
        for(int i=0;i<str.size();i++)
            count[str[i]-'a']++;
        for(int i=0;i<26;i++)
            for(int j=0;j<count[i];j++)
                res[p++]+=i;   
        return res;
    }
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        if(strs.empty())
            return {};
        unordered_map<string,vector<string>> hash;
        vector<vector<string>> anagrams;
        for(string s:strs){
            string t=strSort(s);
            // sort(t.begin(),t.end());
            hash[t].push_back(s);
        }
        for(unordered_map<string,vector<string>>::iterator pos=hash.begin();pos!=hash.end();pos++){
            vector<string> anagram(pos->second.begin(),pos->second.end());
            anagrams.push_back(anagram);
        }
        return anagrams;
    }
};

这里考虑到全部都是小写字母,用库函数中的排序太浪费时间,于是我们自己写一个计数排序可能效率会更高一些,这也是一个编程技巧。

对于找出一个序列中的Majority element,有很多种方法,可以Brute force,可以借助hashmap。

但我们要想做到O(n)的时间复杂度和O(1)的空间复杂度,就必须要使用Majority Voting Algorithm。

Majority Voting Algorithm

描述:

The algorithm is carried out in two steps:

1.Eliminate all elements except one.

Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: if the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.

2.Determine if the remaining element is a valid majority element.

With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence’s length. If so, the candidate is the majority. Otherwise, the sequence doesn’t contain a majority.

简单的说,就是维护一个curIndex,用来记录当前的候选元素,count用来记录得票数,具体规则如下: 1.如果当前元素与候选元素相同,得票;不相同,减去一票 2.如果票数为0,则候选元素切换为当前元素,票数从1重新计算 3.检查候选元素是否过半

JAVA实现如下:

public int majorityElement(int[] num) {
        int n = num.length;
        int candidate = num[0], counter = 0;
        for (int i : num) {
            if (counter == 0) {
                candidate = i;
                counter = 1;
            } else if (candidate == i) {
                counter++;
            } else {
                counter--;
            }
        }

        counter = 0;
        for (int i : num) {
            if (i == candidate) counter++;
        }
        if (counter <= n / 2) return -1;
        return candidate;

    }

那么我们以例题来认识Majority Voting Algorithm的实际应用。

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

那么这道题就是典型的多数投票的应用,我们直接上代码:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int curIndex=0,count=0,i=0;
        for(i=0;i<nums.size();i++){
            nums[curIndex]==nums[i]?count++:count--;
            if(!count){
                curIndex=i;
                count=1;
            }
        }
        return nums[curIndex];
    }
};

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?

Do you have a better hint?

这道题和上面的题唯一的区别在于这个题目中要求找出的是出现次数超过 n/3 的元素。应用多数投票算法前,我们首先要想一轮投票过后能够选出最多多少个元素。

这道题很明显有可能会出现两个多数元素。所以我们需要设置两个候选元素,其余规则不变,代码如下:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int curIndex1=0,curIndex2=0,count1=0,count2=0;
        int size=nums.size(),i=0,tri=size/3;
        vector<int>res;
        for(i=0;i<nums.size();i++){
            if(nums[i]==nums[curIndex1])
                count1++;
            else if(nums[i]==nums[curIndex2])
                count2++;
            else if(!count1){
                count1=1;
                curIndex1=i;
            }
            else if(!count2){
                count2=1;
                curIndex2=i;
            }
            else{
                count1--;
                count2--;
            }
        }
        count1=0;
        count2=0;
        for(i=0;i<nums.size();i++){
            if(nums[i]==nums[curIndex1])
                count1++;
            else if(nums[i]==nums[curIndex2])
                count2++;
        }
        if(count1>tri)
            res.push_back(nums[curIndex1]);
        if(count2>tri)
            res.push_back(nums[curIndex2]);
        return res;
    }
};