liuchuo – 第163页

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;

}

};

LeetCode 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

分析：使用multiset，因为是求第k小的，而且允许相同的元素，所以使用可以存储相同元素的multiset。当multiset里面的元素大于k个的时候，删除集合中最大的那个（即最后一个元素，也就是s.end()的前一个），最后输出最后一个元素即可～即 *s.rbegin()～

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        multiset<int> s;
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[i].size(); j++) {
                s.insert(matrix[i][j]);
                if(s.size() > k)
                    s.erase(--s.end());
            }
        }
        return *s.rbegin();
    }
};

class Solution {

public:

int kthSmallest(vector<vector<int>>& matrix, int k) {

multiset<int> s;

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

for(int j = 0; j < matrix[i].size(); j++) {

s.insert(matrix[i][j]);

if(s.size() > k)

s.erase(--s.end());

}

return *s.rbegin();

}

};