1. 两数之和 https://leetcode-cn.com/problems/two-sum/
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    unordered_map<int,int> mp1;
    vector<int> twoSum(vector<int>& nums, int target) {
        for( int i=0;i<nums.size();i++ ){
            if( mp1.count(target-nums[i]) ) return vector<int>{i,mp1[target-nums[i]]};
            else mp1[nums[i]]=i;
        }
        return vector<int>();
    }
};
  1. 搜索二维矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c++ 
https://leetcode-cn.com/problems/search-a-2d-matrix/
lower_bound( begin,end,num)//找第一个>=   从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)//找第一个> 从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix[0].empty())
            return false;
        int col[10005];
        int col_num = matrix.size();
        int row_num = matrix[0].size();
        if(matrix[0][0] > target || matrix[col_num-1][row_num-1] < target)
            return false;
        for(int i=0;i<col_num;i++)
            col[i] = matrix[i][0];
        int line = upper_bound(col, col+col_num, target) - col;
        line--;
        return binary_search(matrix[line].begin(), matrix[line].end(), target);
    }
};
  1. 1524. 和为奇数的子数组数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        long long even_pre_sum = 1; // [num] 可以理解为0 + num
        long long odd_pre_sum = 0;
        long long sum = 0;
        int ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            if (sum & 1) {
                ans += even_pre_sum;
                odd_pre_sum++;
            } else {
                ans += odd_pre_sum;
                even_pre_sum++;
            }
            ans %= 1000000007;
        }
        return ans;
    }
};
  1. 字符的最短距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <unordered_map>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s = "aaba";
    char c = 'b';
    vector<int> ans;
    ans.reserve(10000);
    vector<int> c_arr;
    c_arr.reserve(10000);
    int len = s.length();
    int j = 0;
    for(int i = 0; i < len; i++) {
        if(s[i] == c) {
            c_arr[j] = i;
            j++;
        }
    }
    cout<<"j:"<<j<<endl;
    int k = 0;
    for(int i = 0; i < j; i++) {
        if(i == 0) {
            for (k = 0; k <= c_arr[i]; k++) {
                ans.push_back(c_arr[i] - k);
                cout<<ans[k]<<" "<<endl;
            }
        } else {
            int range = c_arr[i];
            if (i == j-1)
                range = len;
            for (; k < range; k++) {
                int temp = min(abs(c_arr[i] - k), abs(c_arr[i-1] - k));
                ans.push_back(temp);
                cout<<ans[k]<<" "<<endl;
            }
        }
    }
    return 0;
}
  1. 最长无重复字符的子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
//动态规划、或滑动窗口，维护终点是j的不存在相同字符的子串


#include <unordered_map>
#include <iostream>
#include <string>

using namespace std;

int main () {
    string s="abcabcbb";
    int length = s.length();
    int dp[50005] = {1};
    unordered_map<char, int> map1;
    if(length == 0) {
        return 0;
    }
    map1[s[0]] = 1;
    int j = 0, ans = 1;
    for(int i = 1; i < length; i++) {
        if(!map1[s[i]]) {
            dp[i] = dp[i-1] + 1;
        } else {
            dp[i] = i - (map1[s[i]] - 1);
            while(j < map1[s[i]]) {
                map1[s[j]] = 0;
                j++;
            }
        }
        if (ans < dp[i]) {
            ans = dp[i];
        }
        map1[s[i]] = i+1;
    }
    cout<<ans<<endl;
    return 0;
}
  1. 森林里的兔子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    std::vector<int> vec = {1, 1, 2};//3, 3, 3, 3, 3, 3, 5, 5};
    unordered_map<int, int> map1;
    int length = vec.size();
    for(int i = 0; i < length; i++) {
        map1[i]++;
    }
    unordered_map<int, int>::iterator pr;
    int ans = 0;
    for(pr = map1.begin(); pr != map1.end(); pr++) {
        ans += (((pr->second) / (pr->first + 1) )
            + (((pr->second) % (pr->first + 1) == 0) ? 0 : 1))
            * (pr->first + 1);
        cout<<ans<<" ";
    }
    cout<<ans;
}