Daily Algorithm Exercise

目录

  1. LeetCode 667
  2. LeetCode 664
  3. LeetCode 668
  4. projecteuler 60
  5. Projecteuler 62
  6. LeetCode224. 基础计算器
  7. LeetCode115
  8. LeetCode 122 & 123
  9. Projecteuler 77 计算数由质数相加的方法数
  10. Project 78 基础划分函数取模问题
  11. Leetcode87 递归子串问题
  12. Leetcode218 矩形相连求边界点问题

LeetCode 667

题目链接：https://leetcode.com/problems/beautiful-arrangement-ii/description/

题目

给定两个整数n，k，输出一个包含1~n的数组。假定数组是[a1,a2,…,an]，保证得到的序列[|a1-a2| , |a2-a3| , … , |an-1 - an|]包含了恰好k个不同的数字。

有多组解的情况下输出任意一组解

1<=k<n<=10000

题解：

这里最重要的是必须使用1~n的所有数字，为了保证能得到1~（n-1）的所有差值，必须左右来回取值保证差值最大，也就是1,n,2,n-1…，取到第k个的位置，因为剩下的数是连续的，那么保证他们的差值都为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
class Solution {
    public int[] constructArray(int n, int k) {
        int add = 0;
        int [] ans = new int[n];
        ans[0] = 1;
        int l = 2 , r=n;
        for(int i=1 ; i<k ; i++){
            if(i%2 == 1){
                ans[i] = r--;
            }
            else {
                ans[i] = l++;
            }
        }
        if(k%2 == 1){
            for(int i=k ; i<n ; i++) {
                ans[i] = ans[i - 1] + 1;
            }
        }
        else{
            for(int i=k ; i<n ; i++){
                ans[i] = ans[i - 1] - 1;
            }
        }
        return ans;
    }
}

LeetCode 664

题目链接：https://leetcode.com/problems/strange-printer/description/

题目

有一个奇怪的打印机满足以下两个要求：

1.每次打印一整个连续的序列使其对应位置上打印上同一个字母

2.每次打印可以任意选择起始位置和终点位置，之后的打印会覆盖前面的打印结果

问获得对应字符串需要至少打印多少次\

题解：

利用区间dp的思想，dp[i][j]表示打印好[i,j]的区间至少需要多少次

这里第一层循环是区间的间隔，第二层循环是区间的起始位置，第三个循环是断开的位置，用来将两个区间合并在一起计算

[i,k] [k+1,j]两个区间合并的时候如果s[k] = s[j]，那么打印次数可以减一，自己可以画画图看，但是为什么这个可以满足题目所需的所有情况，我还有点困惑需要解决。

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
public final int INF = 1000000000;
    public int strangePrinter(String s) {
        int len = s.length();
        if(s.length() == 0) return 0;
        int dp[][] = new int[len+1][len+1];
        for(int i=0 ; i<=len ; i++)
            for(int j=0 ; j<=len ; j++)
                if(i>j) dp[i][j] = 0;
                else dp[i][j] = INF;
        for(int i=0 ; i<len ; i++){
            dp[i][i] = 1;
        }
        for(int d=1 ; d<len ; d++){
            for(int i=0 ; i+d<len ; i++){
                int j = i+d;
                dp[i][j] = d+1;
                for(int k=i ; k<j ; k++){
                    if(s.charAt(k) != s.charAt(j)) dp[i][j] = Math.min(dp[i][k]+dp[k+1][j] , dp[i][j]);
                    else dp[i][j] = Math.min(dp[i][k]+dp[k+1][j]-1 , dp[i][j]);
                }
            }
        }
        return dp[0][len-1];
    }

LeetCode 668

题目链接：https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/

题目

有一张30000*30000的二维表，每个位置对应的坐标为(x,y)，其上的数字是xy的乘积，找到第k小的数字，即将所有数字从小到大排序后出现在第k个位置上的数字。

题解：

二分结果，每次二分根据每一行的数字，找到与之匹配的y的个数即可。

复杂度O(30000*log(30000^2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findKthNumber(int m, int n, int k) {
        int l = 1 , r = m*n , mid=0;
        int ret = 0;
        while(l<=r){
            mid = (l+r)>>1;
            long ans = 0;
            for(int i=1 ; i<=m ; i++){
                ans += (mid/i>=n?n:mid/i);
            }
            if(ans >= k){
                ret = mid;
                r = mid-1;
            }
            else l=mid+1;
        }
        return ret;
    }

project euler 60

题目链接：https://projecteuler.net/problem=60

题目：

找到5个素数，保证任意两个数字不论先后顺序连接（如11，7，可连接的到117和711）得到的数字都是素数，并保证这五个数字的和最小。

题目已经告诉你在四个素数的情况下是3,7,109,673.

题解：

暂且估计所有数字都不会超过10000，那么素数是1230个左右，那么我们可以将任意两个素数连接判断是否可以组合，可组合就连成一条边，那么最终的结果形成的图，一定是找一个具有5个点的最大团。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <cmath>
using namespace std;
#define MAX 2000000
#define LL long long
#define ls o<<1
#define rs o<<1|1
#define def_m int m=(l+r)>>1
#define MAXN 10000
bool edge[1250][1250]; //10000以内最多1230个左右的素数
bool vis[MAXN+5];
int pri[MAXN] , tot;
void init_pri()
{
    memset(vis , 0 , sizeof(vis));
	for(int i=2 ; i<=MAXN ; i++){
		if(!vis[i]){
			pri[tot++] = i;
		}
		for(int j=0 ; j<tot ; j++){
			if(i*pri[j]>=MAXN) break;
			vis[i*pri[j]] = true;
			if(i%pri[j] == 0) break;
		}
	}
}
bool isPri(int x)
{
    int a = (int)sqrt(x+0.5);
    for(int i=2 ; i<=a ; i++){
        if(x % i == 0) return false;
    }
    return true;
}
bool isMerge(int a , int b)
{
    int l1 = 1 , l2 = 1;
    int tmp = a;
    while(tmp){
        l1*=10 , tmp /= 10;
    }
    tmp = b;
    while(tmp){
        l2*=10 , tmp /= 10;
    }
    return isPri(b*l1+a) && isPri(a*l2+b);
}
void build_graph()
{
    init_pri();
    memset(edge , 0 , sizeof(edge));
    for(int i=0 ; i<tot ; i++){
        for(int j=i+1 ; j<tot ; j++){
            if(isMerge(pri[i] , pri[j])){
                edge[i][j] = edge[j][i] = true;
            }
        }
    }
    
}
int find5cycle()
{
    #define pii pair<int,int>
    #define a first
    #define b second
    vector<pii> vec;
    vec.clear();
    for(int i=0 ; i<tot ; i++){
        for(int j=i+1 ; j<tot ; j++){
            if(edge[i][j])
                vec.push_back(make_pair(i,j));
        }
    }
    int len = vec.size();
    int ans = 0x7fffffff;
    for(int i=0 ; i<len ; i++){
        for(int j=i+1 ; j<len ; j++){
            pii p1 = vec[i] , p2 = vec[j];
            if(p1.a != p2.a && p1.b != p2.a && p1.a != p2.b && p1.b != p2.b){
                if(edge[p1.a][p2.a] && edge[p1.a][p2.b] && edge[p1.b][p2.a] && edge[p1.b][p2.b]){
                    for(int c=0 ; c<tot ; c++){
                        if(c==p1.a || c==p1.b || c==p2.a || c==p2.b) continue;
                        if(edge[p1.a][c] && edge[p1.b][c] && edge[p2.a][c] && edge[p2.b][c]){
                            cout<<pri[p1.a]<<" "<<pri[p1.b]<<" "<<pri[p2.a]<<" "<<pri[p2.b]<<" "<<pri[c]<<endl;
                            ans = pri[p1.a]+pri[p1.b]+pri[p2.a]+pri[p2.b]+pri[c];
                        }
                    }
                }
            }
        }
    }
    return ans;
}
int main()
{
    build_graph();
    cout<<find5cycle()<<endl;
	return 0;
}

project euler 62

题目链接：https://projecteuler.net/problem=62

题目

找到一个立方数，而且这个立方数的各个数字重新排列位置能得到新的立方数，比如41063625 = 345^3 , 56623104 = 384^3 , 66430123 = 405^3

可以找到三个立方数，最小的是41063625

现在希望让你找到一个重排后产生5个立方数的最小数字

题解：

从结果数字出发太大了，考虑从立方的基数出发，最后产生的结果是不超过10000，实际代码过程中我把限制加到了100000，也依然在3s内运行完成。

将立方数根据0~9出现的个数转化成hash编码后，判断从1^3开始出现的次数，将出现了5次的，找到一个最小值。

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
#define LL long long
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
LL HashCode(LL x)
{
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    while(x){
        cnt[x%10] ++ ; x /= 10 ;
    }
    LL hash = 0;
    for(int i=0 ; i<=9 ; i++)
        hash = hash*10+cnt[i];
    return hash;
}
map<LL , LL> mp1 , mp2;
LL solution()
{
    mp1.clear() , mp2.clear();
    LL ans = 1e18;
    for(LL i=1 ; i<= 1000000 ; i++){
        LL x = i*i*i;
        LL tmp = ++mp1[HashCode(x)];
        if(tmp == 1) mp2[HashCode(x)] = x;
        if(tmp == 5) ans = min(ans , mp2[HashCode(x)]);
    }
    return ans;
}

LeetCode224. 基础计算器

题目链接：https://leetcode.com/problems/basic-calculator/description/

题目：

给你一个只包含+ - 运算带括号的字符串，求最后的答案

题解

用栈来存储数据，遇到右括号，一定要将直到第一个左括号这之间的数据计算出来

因为只有加减计算方式有很多种。

我的代码优点小问题在于为了方便我将符号也定义成了数字，单位了区分，我自己随机写的数字，如果计算过程中得到了这些数字，我的程序会将它当成符号来看，只是测试数据中没有遇到，正好就能Accept了。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public int calculate(String s) {
        final int LEFT = -180362041;
        final int ADD = -736723123;
        final int SUB = -326732012;
        int stack [] = new int [1000005];
        int top = 0;
        stack[top++] = LEFT;
        s = s+")";
       // System.out.println(s);
        boolean last_int = false; //判断前一位字符是不是数字
        int val = 0;
        for(int i=0 ; i<s.length() ; i++){
            if(s.charAt(i) == '('){
                stack[top++] = LEFT;
            } else if(s.charAt(i) == '-' || s.charAt(i) == '+'){
                if(last_int == true){
                    stack[top++] = val;
                    val = 0;
                    last_int = false;
                }
                if(s.charAt(i) == '-') stack[top++] = SUB;
                else stack[top++] = ADD;
            } else if(s.charAt(i) == ' '){
                continue;
            } else if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                last_int = true;
                val = val*10+(s.charAt(i)-'0');
            } else if(s.charAt(i) == ')'){
               // System.out.println(")))): "+stack[top-1]);
                if(last_int == true){
                    stack[top++] = val;
                    val = 0;
                    last_int = false;
                }
                int ret = 0;
                while(true){
                    if(stack[top-1] == LEFT){
                        top-- ;
                        break;
                    }
                    if(stack[top-1] != LEFT && stack[top-1] != SUB && stack[top-1] != ADD){
                        if(stack[top-2] == SUB){
                            ret -= stack[top-1];
                            top -= 2;
                        } else if(stack[top-2] == ADD){
                            ret += stack[top-1];
                            top -= 2;
                        } else if(stack[top-2] == LEFT){
                            ret += stack[top-1];
                            top -= 2;
                            break;
                        }
                    }
                }
                stack[top++] = ret;
            }
        }
        return stack[top-1];
    }

LeetCode 115

题目链接：https://leetcode.com/problems/distinct-subsequences/description/

题目

给定两个字符串序列S，T，找到有多少个S的子序列和T相同。

ACE是ABCDE的子序列，但是AEC就不是ABCDE的子序列。

如S = "rabbbit", T = "rabbit" Return 3

题解

一目了然的动态规划思想

f(i , j) 表示S前i个字符和T的前j个字符匹配得到的如问题描述中的方法数

那么状态转移就以第i个位置能否和第j个位置匹配作为标准

因为字符串下标从0开始，所以

f(i+1 , j+1) = f(i , j+1) + s[i] == t[j] ? f(i , j) : 0

当j为0的时候，初始化所有f(i , 0) = 1，其余情况均为0

那么代码就呼之欲出了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int numDistinct(String s, String t) {
        int dp [][] = new int [s.length()+1][t.length()+1];
        for(int i=0 ; i<s.length()+1 ; i++) {
            dp[i][0] = 1;
            for (int j = 1; j < t.length() + 1; j++)
                dp[i][j] = 0;
        }
        for(int i=0 ; i<s.length() ; i++){
            for(int j=0 ; j<t.length() ; j++){
                dp[i+1][j+1] = dp[i][j+1] + (s.charAt(i)==t.charAt(j)?dp[i][j]:0);
                //System.out.println((i+1)+" "+(j+1)+" "+dp[i+1][j+1]);
            }
        }
        return dp[s.length()][t.length()];
}

projecteuler 69

题目链接：https://projecteuler.net/problem=69

题目

定义了φ(n)为不大于n的所有和n互质的正整数的数量。

找到1000000以内，令n/φ(n)最大的n值

题解

φ(n)是符合积性函数的性质的

根据积性函数性质在i%pri[j] = 0时，那么φ(i∗pri[j]) = φ(i)∗φ(pri[j])

那么当 i%pri[j] != 0，可以分析得出，φ(i∗pri[j]) = φ(i)∗pri[j]

那么就能根据线性筛法在线性时间复杂度内求解出所有的φ(n)然后作比较即可。

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
#define clr(a,b) memset(a,b,sizeof(a))
#define N 1000000
bool vis[N+5];
int pri[N] , phi[N] , tot;
void mubius()
{
    clr(vis,0); tot = 0;
    for(int i=2 ; i<=N ; i++){
        if(!vis[i]){
            pri[tot++] = i;
            phi[i] = i-1;
        }
        for(int j=0 ; j<tot ; j++){
            if(pri[j]*i>=N) break;
            vis[pri[j]*i] = true;
            if(i%pri[j] == 0){
                phi[i*pri[j]] = phi[i] * pri[j];
                break;
            }
            else phi[i*pri[j]] = phi[i]*phi[pri[j]];
        }
       // if(i<=30) cout<<i<<" "<<phi[i]<<endl;
    }
}
int euler69()
{
    mubius();
    int ret = 0;
    double rate = 0;
    for(int i=2 ; i<=N ; i++){
        if(i*1.0 / phi[i] > rate){
            rate = i*1.0 / phi[i];
            ret = i;
        }
    }
    return ret;
}

LeetCode 122 & 123

题目链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

问题

给定一个物品价格序列，第i个数字代表第i天物品的价格，你可以通过买进买出来获得收益，保证每一次买进之前要保证当前没有物品或者物品已经卖光的，且一天只能买一个或者卖一个物品。

一次买卖视作一次交易

LeetCode 122 是问可以无限次交易，得到最大收益

LeetCode 123是问最多2次交易，得到最大收益

题解

LeetCode122：

every position has two states :

  1. sell operation with mark 0
  2. buy operation with mark 1

dp[i][0] = max(dp[j][1]+price[i])
dp[i][1] = max(dp[j][0]-price[i])

because the current item just influence the last item , so in this recursion , we don’t need array to save optimal value.

mx0 represents the optimal value before with mark 0 ;
mx1 represents the optimal value before with mark 0 ;

mx0 = max(mx0 , mx1+price[i])
mx1 = max(mx1 , mx0-price[i])

1
2
3
4
5
6
7
8
9
10
11
12
def maxProfit(self, prices):
        mx0 = 0 ; mx1 = -1000000000 # mx0表示前一个0状态下的答案为0 , mx1表示前一个1状态下的最优答案
        for i in range(0, len(prices)):
            if mx1 == -1000000000:
                mx1 = -prices[i]
            else:
                mx1 = max(mx1, mx0-prices[i])
    
            if mx1 != -1000000000:
                mx0 = max(mx0, mx1+prices[i])
    
        return mx0

LeetCode123

simple dynamic plan question
same to last question:Best Time to Buy and Sell Stock III
2 transactions at most
Record 4 states
mx[0][0] represent the optimal value of buying stock in first transaction
mx[0][1] represent the optimal value of selling stock in first transaction
mx[1][0] represent the optimal value of buying stock in second transaction
mx[1][1] represent the optimal value of selling stock in second transaction

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxProfit(self, prices):
        mx = [[-1000000000, -1000000000], [-1000000000, -1000000000]]
        for val in prices:
            if(mx[1][0] != -1000000000):
                mx[1][1] = max(mx[1][1], mx[1][0]+val)
            if(mx[0][1] != -1000000000):
                mx[1][0] = max(mx[1][0], mx[0][1]-val)
            if(mx[0][0] != -1000000000):
                mx[0][1] = max(mx[0][1], mx[0][0]+val)
            mx[0][0] = max(mx[0][0], -val)
        return max(mx[0][1], max(0, mx[1][1]))

Projecteuler 77

Problem link：https://projecteuler.net/problem=77

problem

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Method

dynamic plan can solve this question quickly.

In order to repetitive computation, I distinguish the smallest number from other numbers.
for example:
a = b + prime1
a = c + prime2
.
.
.
the ways to constitute a = the ways to constitute b (the smallest prime >= prime1)+ the ways to constitute c(the smallest prime number >= prime2)+ …

ways(i,j)presents how many ways can constitute number i with the smallest prime number pri[j]
the suffix sum of sum(i,j) = ways(i,j)+ways(i,j+1)+ways(i,j+2)+…+ways(i,maxn) is used to lower complexity.

code

in my github

Projecteuler 78

题目链接：https://projecteuler.net/problem=78

问题

将正整数n划分成正整数相加的形式的组合，换位置不算不同方法，实际上就是求n的分割函数p(n)。

找到第一个n，使p(n) % 1000000 = 0

题解

分割函数参考之前的文章

对1000000取模，可以在计算划分函数的过程中直接对1000000取模，最后找到n>=2下p(n)=0的第一个数字即可。根据我之前的文章，很容易就写成划分函数的代码。

复杂度O(nsqrt(n))

code

in my github

Leetcode 87

题目链接：https://leetcode.com/problems/scramble-string/description/

问题

可以将一个字符串转化成一个二分树，每一个节点生成两个子节点就是将当前节点任选一个位置切分开，不一定要求二分的，这点很重要，开始就是理解错了。

然后判断两个字符串是不是通过交换若干个左右儿子得到的。

题解：

递归处理，只要保证每一个对应子串是一个合理的节点即可，两个子串都在左侧，说明子树没有交换，一个在左一个在右说明子树交换。处理每一个切分位置的正确性，很简单递归处理即可。子树满足条件就是当前子树对应字符串的所有字符个数相同。

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
public boolean isSame(String s1 , String s2){
        int cnt[] = new int[256];
        for(int i=0 ; i<256 ; i++) cnt[i] = 0;
        for(int i=0 ; i<s1.length() ; i++)
            cnt[s1.charAt(i)]++;
        for(int i=0 ; i<s2.length() ; i++){
            cnt[s2.charAt(i)]--;
            if(cnt[s2.charAt(i)]<0) return false;
        }
      //  System.out.println("true");
        return true;
    }
    public boolean isScramble(String s1, String s2) {
     //   System.out.println(s1+" "+s2);
        if(isSame(s1,s2) == false) return false;
        if(s1.length() == 1) return true;
        for(int i=0 ; i<s1.length()-1 ; i++){
            if(isScramble(s1.substring(0,i+1) , s2.substring(0,i+1)) && isScramble(s1.substring(i+1,s1.length()) , s2.substring(i+1,s2.length())))
                return true;
            if(isScramble(s1.substring(0,i+1) , s2.substring(s2.length()-i-1,s2.length())) && isScramble(s1.substring(i+1,s1.length()) , s2.substring(0,s2.length()-i-1)))
                return true;
        }
        return false;
    }

Leetcode218 矩形相连求边界点问题

题目链接：https://leetcode.com/problems/the-skyline-problem/description/

问题

给定所有底在x轴上的矩形，底边两个端点对应在x轴上和矩形的高3个值告诉你可以确定一个矩形。

那么多个矩形覆盖在一起的时候画出除x轴之外的轮廓，找到所有轮廓上每一水平线上最左侧的点集

题解：

一般解决矩形的覆盖问题

最通常的情况都是要区分它的左右侧的边，跟以前做线段树上解决Atlantic求矩形覆盖面积的问题一样。

将左侧边标记为-1，右侧边标记为1，那么所有边由左到右排好序后，左侧边进入容器，右侧边到的时候，将和他等高的左侧边从容器里删除，因为之后的边不再受这个矩形影响了。也就是说容器里所有边的高度都是覆盖了当前对应矩形的范围，那么我们只要判断容器里面的最大高度和自己比较即可。

这里边排序进入容器判断的顺序很关键，我们总是保证在等x的时候，越高的边越优先进入，越低的边越优先出去，这样才不会影响当前容器里最大值的判断。

1
2
3
4
5
6
7
8
9
10
struct Side{
        int x , y , op;
        Side(int x=0 , int y=0 , int op=0):x(x),y(y),op(op){}
        bool operator<(const Side a) const {
            return x<a.x || (x==a.x && op*y < a.op*a.y);//横坐标相同，希望添加的顺序一定是左侧的边越大优先入set，右侧的 边越小优先出set才不会影响最大值
        }
        bool operator==(const Side a) const {
            return x==a.x && y==a.y && op==a.op;
        }
    }sides[100005];

且保存这些进入的容器用一个有序的容器可以帮助你最快的找到最大值，我选择的是multiset，因为总是会出现高度一样的边，但我们不能将其相互抵消，所以都应该保存，要注意multiset删除元素一定只删除一个，所以是删除指定的指针，不然相同元素多个，删除值会导致一条右侧边删了多条左侧边。

当然这个问题的解决可以是你自己定义结构体保存在set中，给每一条边定一个id，找到相同id的左侧边删除即可。但这道题目本身不需要这么麻烦就能解决。

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
44
45
46
47
48
class Solution {
public:
    struct Side{
        int x , y , op;
        Side(int x=0 , int y=0 , int op=0):x(x),y(y),op(op){}
        bool operator<(const Side a) const {
            return x<a.x || (x==a.x && op*y < a.op*a.y);//横坐标相同，希望添加的顺序一定是左侧的边越大优先入set，右侧的 边越小优先出set才不会影响最大值
        }
        bool operator==(const Side a) const {
            return x==a.x && y==a.y && op==a.op;
        }
    }sides[100005];
    
    multiset<int> st;
    vector<pair<int, int> > getSkyline(vector<vector<int> >& buildings) {
        
        int n = buildings.size();
        for(int i=0 ; i<n ; i++){
            sides[i*2] = Side(buildings[i][0] , buildings[i][2] , -1);
            sides[i*2+1] = Side(buildings[i][1] , buildings[i][2] , 1);
        }
        sort(sides , sides+(n*2));
        vector<pair<int,int> > ret;
        st.clear();
        int val;
        int last = -1;
        for(int i=0 ; i<n*2 ; i++){
           // cout<<"test: "<<sides[i].x<<" "<<sides[i].y<<" "<<sides[i].op<<endl;
            if(sides[i].op == 1){
                st.erase(st.lower_bound(sides[i].y));
                if(st.size()>0) val = *(--st.end());
                else val = 0;
            }
            else{
                st.insert(sides[i].y);
                val = *(--st.end());
                
            }
         //   cout<<"cur val : "<<val<<endl;
            if(val != last){
                ret.push_back(make_pair(sides[i].x , val));
                last = val;
            }
        }
        return ret;
    }
};
赏

谢谢你请我吃糖果

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

中南大学的本科毕业<br><br>南京大学的研究生在读<br>不断进步中，做更好的自己