leetcode 447[hashtable] 401[backtracking] 409[hashtable] 387[hashtable]

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

给出一组坐标值，找出有多少种三点组合[i, j, k]使得i与k距离和i与j距离相等

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        unordered_map<int, int> dist_map;
        int res = 0;
        for (int i = 0; i < points.size(); ++i)
        {
            for (int j = 0; j < points.size(); ++j)
            {
                if (i == j)
                    continue;
                int d = getDistance(points[i], points[j]);

                if (dist_map.find(d) != dist_map.end())
                    dist_map[d] += 1;
                else
                    dist_map[d] = 1;
            }

            for (auto it = dist_map.begin(); it != dist_map.end(); ++it)
                res += it->second * (it->second - 1);
            dist_map.clear();
        }
        return res;

    }

private:
    int getDistance(pair<int, int> &point1, pair<int, int> &point2)
    {
        int dx = point1.first - point2.first;
        int dy = point1.second - point2.second;
        return dx * dx + dy * dy;
    }
};

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

给定位数列出二进制手表的所有可能的时间字符串

采用回溯法

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<int> hours({1, 2, 4, 8}), minutes({1, 2, 4, 8, 16, 32});
        vector<string> res;
        for (int i = 0; i <= num; i++)
        {
            vector<int> hour_list = getNumber(hours, i);
            vector<int> minute_list = getNumber(minutes, num - i);
            for (int hour : hour_list)
            {
                if (hour >= 12)
                    continue;
                for (int minute : minute_list)
                {
                    if (minute >= 60)
                        continue;
                    string str = to_string(hour) + ":" + (minute <= 9 ? "0" : "") + to_string(minute);
                    res.push_back(str);
                }
            }
        }
        return res;

    }

private:
    vector<int> getNumber(vector<int> &nums, int count)
    {
        vector<int> res;
        getNumberHelper(nums, count, 0, 0, res);
        return res;
    }

    void getNumberHelper(vector<int> &nums, int count, int start, int sum, vector<int> &res)
    {
        if (count == 0)
        {
            res.push_back(sum);
            return;
        }
        for (int i = start; i < nums.size(); ++i)
            getNumberHelper(nums, count-1, i+1, sum+nums[i], res);
    }
};

ven a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
“abccccdd”

Output:
7

Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.

给出一个由大写字母和小写字母组成的字符串，求由该字符串中的字符最长能构成的回文长度

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> chars(52, 0);
        for (char ch : s)
        {
            if (ch < 'a')
                chars[ch-'A']++;
            else
                chars[26+ch-'a']++;
        }
        int res = 0;
        bool hasOdd = false;
        for (int len : chars)
        {
            if (len % 2 == 0)
                res += len;
            else
            {
                res += len - 1;
                hasOdd = true;
            }
        }
        return res + (hasOdd ? 1 : 0);
    }
};

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> chars(26, 0);
        for (char ch : s)
            chars[ch-'a']++;
        for (int i = 0; i < s.length(); ++i)
        {
            if (chars[s[i]-'a'] == 1)
                return i;
        }
        return -1;

    }
};