liuchuo – 第163页

LeetCode 374. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.

分析：二分查找法解决，不过要注意mid = low + (high – low) / 2 不要写成 mid = (low + high) / 2 ，后者超过了Int类型的最大值，相加变成负数，会导致超时～～

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int low = 1, high = n;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            int temp = guess(mid);
            if(temp == 1)
                low = mid + 1;
            else if(temp == -1)
                high = mid - 1;
            else
                return mid;
        }
    }
};

// Forward declaration of guess API.

// @param num, your guess

// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0

int guess(int num);

class Solution {

public:

int guessNumber(int n) {

int low = 1, high = n;

while(low <= high) {

int mid = low + (high - low) / 2;

int temp = guess(mid);

if(temp == 1)

low = mid + 1;

else if(temp == -1)

high = mid - 1;

else

return mid;

}

};

LeetCode 396. Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), …, F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

分析：算出每个F[i]，求出最大值maxn～每个F[i]可由前一步F[i-1]得到，F[i] = F[i – 1] + sum – len * A[len – i]，其中sum为A[i]总和，len为A[i]长度～找到这个关系后就能求得F[i]的所有值～

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int len = A.size(), sum = 0;
        if(len == 0)
            return 0;
        vector<int> F(len);
        for(int i = 0; i < len; i++) {
            sum += A[i];
            F[0] += i * A[i];
        }
        int maxn = F[0];
        for(int i = 1; i < len; i++) {
            F[i] = F[i - 1] + sum - len * A[len - i];
            maxn = max(F[i], maxn);
        }
        return maxn;
    }
};

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

int len = A.size(), sum = 0;

if(len == 0)

return 0;

vector<int> F(len);

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

sum += A[i];

F[0] += i * A[i];

}

int maxn = F[0];

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

F[i] = F[i - 1] + sum - len * A[len - i];

maxn = max(F[i], maxn);

}

return maxn;

}

};

LeetCode 401. Binary Watch

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”]

分析：小时数h从0～11，分钟数m从0～59，把他们每一个转换为一个二进制整体，初始化为bitset，看bitset中1的个数是否为num，如果是就将h和m构成一个字符串加入到result字符串数组中，最后返回result～～

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int h = 0; h < 12; h++) {
            for(int m = 0; m < 60; m++) {
                bitset<10> b(h << 6 | m);
                if(b.count() == num) {
                    string temp = to_string(h) + ":";
                    if(m < 10)
                        temp += "0";
                    temp += to_string(m);
                    result.push_back(temp);
                }
            }
        }
        return result;
    }
};

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> result;

for(int h = 0; h < 12; h++) {

for(int m = 0; m < 60; m++) {

bitset<10> b(h << 6 | m);

if(b.count() == num) {

string temp = to_string(h) + ":";

if(m < 10)

temp += "0";

temp += to_string(m);

result.push_back(temp);

}

return result;

}

};

【C++】bitset的用法

bitset用来处理二进制位非常方便。头文件是#include <bitset>，在std命名空间里面～

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<5> b("11"); //5表示5个二进位
    // 初始化方式：
    // bitset<5> b; 都为0
    // bitset<5> b(u); u为unsigned int，如果u = 1,则被初始化为10000
    // bitset<5> b(s); s为字符串，如"1101" -> "10110"
    // bitset<5> b(s, pos, n); 从字符串的s[pos]开始，n位长度
    for(int i = 0; i < 5; i++)
        cout << b[i];
    cout << endl << b.any(); //b中是否存在1的二进制位
    cout << endl << b.none(); //b中不存在1吗？
    cout << endl << b.count(); //b中到1的二进制位的个数
    cout << endl << b.size();  //b中二进制位到个数
    cout << endl << b.test(2); //测试下标为2处是否二进制位为1
    b.set(4); //把b的下标为4处置1
    b.reset(); //所有位归零
    b.reset(3); //b的下标3处归零
    b.flip(); //b的所有二进制位逐位取反
    unsigned long a = b.to_ulong(); //b转换为unsigned long类型
    return 0;
}

#include <bitset>

#include <iostream>

using namespace std;

int main() {

bitset<5> b("11"); //5表示5个二进位

// 初始化方式：

// bitset<5> b; 都为0

// bitset<5> b(u); u为unsigned int，如果u = 1,则被初始化为10000

// bitset<5> b(s); s为字符串，如"1101" -> "10110"

// bitset<5> b(s, pos, n); 从字符串的s[pos]开始，n位长度

for(int i = 0; i < 5; i++)

cout << b[i];

cout << endl << b.any(); //b中是否存在1的二进制位

cout << endl << b.none(); //b中不存在1吗？

cout << endl << b.count(); //b中到1的二进制位的个数

cout << endl << b.size(); //b中二进制位到个数

cout << endl << b.test(2); //测试下标为2处是否二进制位为1

b.set(4); //把b的下标为4处置1

b.reset(); //所有位归零

b.reset(3); //b的下标3处归零

b.flip(); //b的所有二进制位逐位取反

unsigned long a = b.to_ulong(); //b转换为unsigned long类型

return 0;

}

LeetCode 151. Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

分析：我用的方法是把字符串中的所有单词放入栈里，然后将栈里的所有字符串弹栈到字符串s中～

class Solution {
public:
    void reverseWords(string &s) {
        stack<string> sstack;
        int flag = 0;
        string temp = "";
        for(int i = 0; i < s.length(); i++) {
            if(s[i] != ' ' && flag == 0) {
                temp = "";
                temp += s[i];
                flag = 1;
            } else if(s[i] != ' ') {
                temp += s[i];
            } else if(s[i] == ' ' && flag == 1){
                sstack.push(temp);
                flag = 0;
            }
            if(i == s.length() - 1 && flag == 1)
                sstack.push(temp);
        }
        s = "";
        while(!sstack.empty()) {
            string temp = sstack.top();
            s += temp;
            sstack.pop();
            if(!sstack.empty())
                s += " ";
        }
    }
};

class Solution {

public:

void reverseWords(string &s) {

stack<string> sstack;

int flag = 0;

string temp = "";

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

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

temp = "";

temp += s[i];

flag = 1;

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

temp += s[i];

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

sstack.push(temp);

flag = 0;

}

if(i == s.length() - 1 && flag == 1)

sstack.push(temp);

}

s = "";

while(!sstack.empty()) {

string temp = sstack.top();

s += temp;

sstack.pop();

if(!sstack.empty())

s += " ";

}

};

LeetCode 350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

分析：将nums1的每一个数字以及对应数字的个数存储在map里面，遍历nums2中的所有元素，如果当前元素在map中存在，就把它放入result数组中，并将其数量-1。最终返回result即为所求交集～

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        map<int, int> m;
        for(int i = 0; i < nums1.size(); i++)
            m[nums1[i]]++;
        for(int i = 0; i < nums2.size(); i++) {
            if(m[nums2[i]] != 0) {
                m[nums2[i]]--;
                result.push_back(nums2[i]);
            }
        }
        return result;
    }
};

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

vector<int> result;

map<int, int> m;

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

m[nums1[i]]++;

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

if(m[nums2[i]] != 0) {

m[nums2[i]]--;

result.push_back(nums2[i]);

}

return result;

}

};