LeetCode OJ – 第41页 – 柳婼の blog

LeetCode 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 0; i < 32; i++) {
            ans = ans * 2 + n % 2;
            n = n / 2;
        }
        return ans;
    }
};

class Solution {

public:

uint32_t reverseBits(uint32_t n) {

uint32_t ans = 0;

for(int i = 0; i < 32; i++) {

ans = ans * 2 + n % 2;

n = n / 2;

}

return ans;

}

};

LeetCode 20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

class Solution {
public:
    bool isValid(string s) {
        stack<char> t;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                t.push(s[i]);
            } else if(s[i] == ')') {
                if(i == 0 ||  t.empty() || t.top() != '(') {
                    return false;
                }
                t.pop();
            } else if(s[i] == ']') {
                if(i == 0 || t.empty() || t.top() != '[') {
                    return false;
                }
                t.pop();
            } else if(s[i] == '}') {
                if(i == 0 || t.empty() || t.top() != '{') {
                    return false;
                }
                t.pop();
            }
        }
        return t.empty();
    }
};

class Solution {

public:

bool isValid(string s) {

stack<char> t;

for(int i = 0; i < s.length(); i++) {

if(s[i] == '(' || s[i] == '[' || s[i] == '{') {

t.push(s[i]);

} else if(s[i] == ')') {

if(i == 0 || t.empty() || t.top() != '(') {

return false;

}

t.pop();

} else if(s[i] == ']') {

if(i == 0 || t.empty() || t.top() != '[') {

return false;

}

t.pop();

} else if(s[i] == '}') {

if(i == 0 || t.empty() || t.top() != '{') {

return false;

}

t.pop();

}

return t.empty();

}

};

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.

class Solution {
public:
    string getHint(string secret, string guess) {
        int bull = 0, cow = 0;
        int s[10], g[10];
        memset(s, 0, sizeof(int) * 10);
        memset(g, 0, sizeof(int) * 10);
        for(int i = 0; i < secret.length(); i++) {
            if(secret[i] == guess[i]) {
                bull++;
            } else {
                s[secret[i] - '0']++;
                g[guess[i] - '0']++;
            }
        }
        
        for(int i = 0; i < 10; i++) {
            if(s[i] >= g[i]) {
                cow = cow + g[i];
            } else {
                cow = cow + s[i];
            }
        }
        
        string b = "";
        if(bull == 0)
            b = "0";
        while(bull) {
            char temp1 = (bull % 10 + '0');
            bull = bull / 10;
            b = temp1 + b;
        }
        
        string c = "";
        if(cow == 0)
            c = "0";
        while(cow) {
            char temp2 = (cow % 10 + '0');
            cow = cow / 10;
            c = temp2 + c;
        }
        
        string ans = b + 'A' + c + 'B';
        return ans;
    }
};

class Solution {

public:

string getHint(string secret, string guess) {

int bull = 0, cow = 0;

int s[10], g[10];

memset(s, 0, sizeof(int) * 10);

memset(g, 0, sizeof(int) * 10);

for(int i = 0; i < secret.length(); i++) {

if(secret[i] == guess[i]) {

bull++;

} else {

s[secret[i] - '0']++;

g[guess[i] - '0']++;

}

for(int i = 0; i < 10; i++) {

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

cow = cow + g[i];

} else {

cow = cow + s[i];

}

string b = "";

if(bull == 0)

b = "0";

while(bull) {

char temp1 = (bull % 10 + '0');

bull = bull / 10;

b = temp1 + b;

}

string c = "";

if(cow == 0)

c = "0";

while(cow) {

char temp2 = (cow % 10 + '0');

cow = cow / 10;

c = temp2 + c;

}

string ans = b + 'A' + c + 'B';

return ans;

}

};

LeetCode 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.

Note:
You may assume both s and t have the same length.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int len = s.length();
        int lent = t.length();
        if(len != lent)
            return false;
        map<char, char> stot;
        map<char, char> ttos;
        for(int i = 0; i < len; i++) {
            if(stot.find(s[i]) != stot.end() && stot[s[i]] != t[i] 
            || ttos.find(t[i]) != ttos.end() && ttos[t[i]] != s[i])
                return false;
            stot[s[i]] = t[i];
            ttos[t[i]] = s[i];
        }
        return true;
    }
};

class Solution {

public:

bool isIsomorphic(string s, string t) {

int len = s.length();

int lent = t.length();

if(len != lent)

return false;

map<char, char> stot;

map<char, char> ttos;

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

if(stot.find(s[i]) != stot.end() && stot[s[i]] != t[i]

|| ttos.find(t[i]) != ttos.end() && ttos[t[i]] != s[i])

return false;

stot[s[i]] = t[i];

ttos[t[i]] = s[i];

}

return true;

}

};

LeetCode 223. Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int maxae = A > E ? A : E;
        int mincg = C > G ? G : C;
        int maxfb = F > B ? F : B;
        int minhd = H > D ? D : H;
        int overlap;
        if(maxae >= mincg || maxfb >= minhd)
            overlap = 0;
        else
            overlap = (mincg - maxae) * (minhd - maxfb);
        return (C - A) * (D - B) + (G - E) * (H - F) - overlap;
    }
};

class Solution {

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int maxae = A > E ? A : E;

int mincg = C > G ? G : C;

int maxfb = F > B ? F : B;

int minhd = H > D ? D : H;

int overlap;

if(maxae >= mincg || maxfb >= minhd)

overlap = 0;

else

overlap = (mincg - maxae) * (minhd - maxfb);

return (C - A) * (D - B) + (G - E) * (H - F) - overlap;

}

};

LeetCode 219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> s;
        int t = 0;
        for(int i = 0; i < nums.size(); i++) {
            s.insert(nums[i]);
            if(s.size() == t) {
                for(int j = i - 1; j >= 0 && j >= i - k; j--) {
                    if(nums[i] == nums[j])
                        return true;
                }
            }
            t = s.size();
        }
        return false;
    }
};

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

set<int> s;

int t = 0;

for(int i = 0; i < nums.size(); i++) {

s.insert(nums[i]);

if(s.size() == t) {

for(int j = i - 1; j >= 0 && j >= i - k; j--) {

if(nums[i] == nums[j])

return true;

}

t = s.size();

}

return false;

}

};

标签： LeetCode OJ

LeetCode 190. Reverse Bits

LeetCode 20. Valid Parentheses

LeetCode 299. Bulls and Cows

LeetCode 205. Isomorphic Strings

LeetCode 223. Rectangle Area

LeetCode 219. Contains Duplicate II