Code – 第96页

LeetCode 537. Complex Number Multiplication

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:
Input: “1+1i”, “1+1i”
Output: “0+2i”
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
Input: “1+-1i”, “1+-1i”
Output: “0+-2i”
Explanation: (1 – i) * (1 – i) = 1 + i2 – 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:

The input strings will not have extra blank.
The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

题目大意：给两个复数，求两个数的乘积～

分析：使用sscanf和ssprinf，(m+ni)*(p+qi)=(m*p-n*q)*(n*p+m*q) i

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        char t[200];
        int m, n, p, q;
        sscanf(a.c_str(), "%d+%di", &m, &n);
        sscanf(b.c_str(), "%d+%di", &p, &q);
        sprintf(t, "%d+%di", (m*p-n*q), (n*p+m*q));
        string ans = t;
        return ans;
    }
};

class Solution {

public:

string complexNumberMultiply(string a, string b) {

char t[200];

int m, n, p, q;

sscanf(a.c_str(), "%d+%di", &m, &n);

sscanf(b.c_str(), "%d+%di", &p, &q);

sprintf(t, "%d+%di", (m*p-n*q), (n*p+m*q));

string ans = t;

return ans;

}

};

LeetCode 654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.

Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

6
/ \
3 5
\ /
2 0
\
1
Note:
The size of the given array will be in the range [1,1000].

分析：用递归，l和r分别表示使用在nums[l]到nums[r]区间内的数字进行建树，每次通过idx找到l到r之间的最大值对应的下标idx，使用nums[idx]值new一个新TreeNode结点root，然后将root的左边用l～idx-1建树，右边用idx+1～r建树，然后返回root结点即完成了建树～

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(0, nums.size()-1, nums);
    }
private:
    int n;
    TreeNode* build(int l, int r, vector<int>& nums) {
        if (l > r) return NULL;
        int idx = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > nums[idx]) idx = i;
        }
        TreeNode* root = new TreeNode(nums[idx]);
        root->left = build(l, idx-1, nums);
        root->right = build(idx+1, r, nums);
        return root;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

return build(0, nums.size()-1, nums);

}

private:

int n;

TreeNode* build(int l, int r, vector<int>& nums) {

if (l > r) return NULL;

int idx = l;

for (int i = l + 1; i <= r; i++) {

if (nums[i] > nums[idx]) idx = i;

}

TreeNode* root = new TreeNode(nums[idx]);

root->left = build(l, idx-1, nums);

root->right = build(idx+1, r, nums);

return root;

}

};

pair的用法 make_pair

pair<string, int> p1(“123”, 99), p2, p3;

p2.first = “abc”, p2.second = 2;

p3 = make_pair(“dce”, 1);

cout << p1.first << ” “ << p1.second;

pair<string, int> 相当于一个类型名称，如果要创建一个这个类型的数组，可以写vector<pair<string, int>>

bitset 位运算

#include <bitset>

0101101010 //一个bitset类型的变量
9876543210 //对应元素的下标

初始化
bitset在定义时，要明确bitset含有多少位，不满左边会自动补0
bitset<5> bit1(“11101”); //最简单的初始化
bitset<n> b; //b有n位，每位都为0
bitset<n> b(u); //b是unsigned long型u的一个副本
bitset<n> b(s); //b是string对象s中含有的位串的副本

查找
bit1.size()//返回二进制总位数
bit1.count() // 返回bit1里1的个数
bool flag = bit1.any(); // 等价于bit1.count() != 0时返回true
bool flag = bit1.none(); // 等价于bit1.count() == 0时返回true
bool flag = bit1.test(5); // bit[5]等于1的时候返回true，表示这一位被设置了数

操作
bit1.set()//所有位设为1
bit1.set(pos)//下标为pos的位设为1
bit1.reset//所有位设为0
bit1.reset(pos)//下标为pos的位设为0
bit1.flip()//所有位取反
bit1.flip(pos)//pos位取反
bit1.to_ulong()//返回一个unsigned long long 整数

binary_search()、upper_bound()、lower_bound() 二分查找

vector<int> a = {0,1,2,2,3,4}; 使用前提是a已经是升序排列

cout << binary_search(a.begin(), a.end(), 3); // 找是否存在3，return false or true

auto it = upper_bound(a.begin(), a.end(), 2);// 从左到右返回第一个大于2的数字的地址
auto itt = lower_bound(a.begin(), a.end(), 2);// 从左到右返回第一个大于等于2的数字的地址
// 找不到就返回a.end()

sort()、stable_sort()、partial_sort()、nth_element()、greater()、is_sorted()

sort(a, a+5); // 默认从小到大,int数组的排序
sort(v.begin(), v.end()); // vector数组排序
sort中使用的是快排和插排

stable_sort(v.begin(), v.end());

partial_sort(a, a+2, a+n); // 前2个数字将是正确顺序
partial_sort(v.begin(), v.begin() + 3, v.end()); // 对数组中元素部分排序，前3个将是正确顺序

nth_element(v.begin(), v.begin() + 6, v.end()); // 只有v[6]处放置的是正确的元素，其余不管～

sort(v.begin(), v.end(), greater<int>()); // 从大到小排，algorithm头文件

bool flag = is_sorted(a, a+n);
bool flag = is_sort(v.begin(), v.end());