Code – 第245页

LeetCode 58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt = 0;
        int flag = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(flag == 0 && s[i] == ' ') {
                continue;
            }
            if(s[i] != ' ') {
                flag = 1;
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
};

class Solution {

public:

int lengthOfLastWord(string s) {

int cnt = 0;

int flag = 0;

for(int i = s.length() - 1; i >= 0; i--) {

if(flag == 0 && s[i] == ' ') {

continue;

}

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

flag = 1;

cnt++;

} else {

break;

}

return cnt;

}

};

LeetCode 19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL || head->next == NULL)
            return NULL;
        ListNode *p = head;
        ListNode *q = head;
        for(int i = 1; i <= n; i++) {
            p = p->next;
        }
        if(p == NULL) {
            head = head->next;
            return head;
        }
        p = p->next;
        while(p != NULL) {
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;
        return head;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

if(head == NULL || head->next == NULL)

return NULL;

ListNode *p = head;

ListNode *q = head;

for(int i = 1; i <= n; i++) {

p = p->next;

}

if(p == NULL) {

head = head->next;

return head;

}

p = p->next;

while(p != NULL) {

p = p->next;

q = q->next;

}

q->next = q->next->next;

return head;

}

};

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;

}

};

分类： Code

LeetCode 58. Length of Last Word

LeetCode 19. Remove Nth Node From End of List

LeetCode 190. Reverse Bits

LeetCode 20. Valid Parentheses

LeetCode 299. Bulls and Cows

LeetCode 205. Isomorphic Strings