Weekly Contest 154

1189. Maximum Number of Balloons

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

1 2	>Input: text = "nlaebolko" >Output: 1

1 2	>Input: text = "loonbalxballpoon" >Output: 2

1 2	>Input: text = "leetcode" >Output: 0

Weekly Contest 155

1200. Minimum Absolute Difference

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

• a, b are from arr
• a < b
• b - a equals to the minimum absolute difference of any two elements in arr

1 2 3

Input: arr = [4,2,1,3] Output: [[1,2],[2,3],[3,4]] Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Biweekly Contest 9

1196. How Many Apples Can You Put into the Basket

You have some apples, where arr[i] is the weight of the i-th apple. You also have a basket that can carry up to 5000 units of weight.

Return the maximum number of apples you can put in the basket.

1 2 3

>Input: arr = [100,200,150,1000] >Output: 4 >Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

区间问题

在当前选择局部最优解，依次这样选择能够到达全局最优解。

区间选点

• 1、将每个区间按右端点从小到大排序；
• 2、从前往后依次枚举每个区间，如果当前区间已经包含点，则pass；否则选择当前区间的右端点。

证明：按照上述规则选出来的所有点数记为cnt，题目要求为ans，则ans<=cnt，cnt同时代表了我们目前有cnt个区间，因此ans最少需要cnt个点，因此ans>=cnt，因此上述cnt便是解。

[编程题]山寨金闪闪

链接：https://www.nowcoder.com/questionTerminal/9363dcb83ca44c61a2c1a8f65aa722b8来源：牛客网
金闪闪死后，红A拿到了王之财宝，里面有n个武器，长度各不相同。红A发现，拿其中三件武器首尾相接，组成一个三角形，进行召唤仪式，就可以召唤出一个山寨金闪闪。（例如，三件武器长度为10、15、20，可以召唤成功。若长度为10、11、30，首尾相接无法组成三角形，召唤失败。）红A于是开了一个金闪闪专卖店。他把王之财宝排成一排，每个客人会随机抽取到一个区间[l,r],客人可以选取区间里的三件武器进行召唤（客人都很聪慧，如果能找出来合适的武器，一定不会放过）。召唤结束后，客人要把武器原样放回去。m个客人光顾以后，红A害怕过多的金闪闪愉悦太多男人，于是找到了你，希望你帮他统计出有多少山寨金闪闪被召唤出来。

链接：https://www.nowcoder.com/questionTerminal/9363dcb83ca44c61a2c1a8f65aa722b8
来源：牛客网

第一行武器数量:n <= 110^7
第二行空格分隔的n个int，表示每件武器的长度。
第三行顾客数量：m <= 110^6
后面m行，每行两个int l，r，表示每个客人被分配到的区间。（l<r）

判断两个字符串是否为变形词

给定两个字符串str1和str2，如果str1和str2中出现的字符种类出现的一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请判断str1和str2是否为变形词。

1	输入包括3行，第一行包含两个整数n，m(1 \leq n,m\leq 10^5)(1≤n,m≤105)分别代表str1和str2的长度，第二行和第三行为两个字符串，分别代表str1和str2。

把一个array拷贝到vector

其中的copy方法里，copy(&dataArray[0], &dataArray[dataArraySize], back_inserter(dataVec)); 不会拷贝dataArray[dataArraySize] 元素；例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

int arr[] = {1,4,2,4,56,5,43,2,2,5};
int main()
{
    int size = sizeof(arr) / sizeof(int);
    vector<int> table;
    copy(&arr[0], &arr[3], back_inserter(table));
    for (auto  i : table)
        cout << i << " ";
    cout << endl;
}
//打印到arr[2]处为止；
$main
1 4 2

累加map中的元素

accumulate函数模板：

• Returns the result of accumulating all the values in the range [first,last) to init

模板行为：

1
2
3
4
5
6
7
8
9

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

two sum

• 解析：用哈希表放入每一个，下一次检查每一个target的减数是否在表中；

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> imap;   
        for(int i=0;; ++i){
            auto it = imap.find(target-nums[i]);
            
            if(it != imap.end())
                return vector<int>{i, it->second};     
            imap[nums[i]] = i;
        }
    }
};