leetcode 448

448. Find All Numbers Disappeared in an Array

Input:

[4,3,2,7,8,2,3,1]

Output:

[5,6]

思路：把数组的内容和index进行一一对应映射，映射规则是取反，由此可知，重复出现两次的数字会变为正，出现一次的为负。

需要注意的是，如果不能增加额外空间的话，要在本数组上面进行映射，这时候就需要内容-1=index，因为index是从0开始，内容从1开始

class Solution {

public:

    vector<int> findDisappearedNumbers(vector<int>& nums) {

        int len = nums.size();

        for(int i=; i<len; i++) {

            int m = abs(nums[i])-; // index start from 0

            nums[m] = nums[m]> ? -nums[m] : nums[m];

        }

        vector<int> res;

        for(int i = ; i<len; i++) {

            if(nums[i] > ) res.push_back(i+);

        }

        return res;

    }

};

455. Assign Cookies

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.

You have 3 cookies and their sizes are big enough to gratify all of the children,

You need to output 2.

思路：先对小孩和饼干进行排序，逐个对应匹配。若当前小孩符合，则下一个小孩和下一个饼干；否则下一个饼干匹配当前小孩。

class Solution {

public:

      int findContentChildren(vector<int>& g, vector<int>& s) {

        sort(g.begin(),g.end());

        sort(s.begin(),s.end());

        int i = , j=;

        while(i<g.size() && j<s.size()){

            if(s[j]>=g[i])

                i++; // when the child get the cookie, foward child by 1

            j++;

        }

        return i;

    }

};

461. Hamming Distance

Input: x = 1, y = 4

Output: 2

Explanation:

1   (0 0 0 1)

4   (0 1 0 0)

       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

class Solution {

public:

    int hammingDistance(int x, int y) {

        int dist = , n = x ^ y; //按位异或

        while (n) {

            ++dist;

            n &= n - ; //效果循环右移，左补零

        }

        return dist;

    }

};

459. Repeated Substring Pattern

Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

思路：

法一：从str的一半开始，用

class Solution {

public:

    bool repeatedSubstringPattern(string str) {

        string nextStr = str;

        int len = str.length();

        if(len < ) return false;

        for(int i = ; i <= len / ; i++){

            if(len % i == ){  //若能整除，表示源字符串可以划分成正数个子字符串

                nextStr = leftShift(str, i); //将源字符串左移一个子字符串，若左移后和源字符串相等，则判断为符合；这里也可以使用一个子字符串乘以个数得到的串和源字串比较

                if(nextStr == str) return true;

            }

        }

        return false;

    }

    string leftShift(string &str, int l){

        string ret = str.substr(l);

        ret += str.substr(, l);

        return ret;

    }

};

法二：

将源字符串变成两倍，然后去掉首尾字符，剩下的串里面寻找源字串，若存在则判符合。

内部思想，如果源字符串不存在重复子字符串，则两倍后的字符串去掉前后字母后，里面必定不存在源字符串；否则必定存在源字符串。

bool repeatedSubstringPattern(string str)

    {

        return (str + str).substr(, str.size() *  - ).find(str)!=-;

    }

476. Number Complement

Input: 5

Output: 2

Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

//使用mask来统计num二进制的位数
class Solution {

public:

    int findComplement(int num) {

        unsigned mask = ~;

        while (num & mask) mask <<= ;

        return ~mask & ~num;

    }

};

For example,

num          =

mask         =

~mask & ~num =

//使用i来统计num二进制的位数
class Solution(object):

    def findComplement(self, num):

        i = 1

        while i <= num:

            i = i << 1

        return (i - 1) ^ num

巴特西

leetcode 448 - 476

476. Number Complement

最新文章

热门文章