LeetCode Weekly Contest 18B

1. 496. Next Greater Element I

暴力的话，复杂度也就1000 * 1000 = 1e6, 在1s的时限内完全可以。

当然，有许多优化方法，利用stack维护递减序列的方法，见这里http://bookshadow.com/weblog/2017/02/05/leetcode-next-greater-element-i/

2. 506. Relative Ranks

这个是水题，直接排序，处理一下边界问题，输出就可以。

 class Solution {

 public:

     vector<string> findRelativeRanks(vector<int>& nums) {

         int n = nums.size();

         vector<int> a(n);

         for (int i = ; i < n; i++) a[i] = i;

         sort(a.begin(), a.end(), [&](int x, int y) {

             return nums[x] > nums[y];

         });

         vector<string> res(n);

         string b[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};

         for (int i = ; i < min(, n); i++) {

             res[a[i] ] = b[i];

         }

         for (int i = ; i < n; i++) {

             //stringstream ss;

             //ss << i + 1;

             res[a[i]] = to_string(i + );

         }

         return res;

     }

 };

3. 503. Next Greater Element II

a. 这题，暴力的话1e4 * 1e4 = 1e8, 卡时限，每次的运算也很简单，在leetcode上面一般能过。

但是，应该寻找更优的方法。

b. 先说一下，我的蠢办法，我居然拿线段树去做了，复杂度nlognlogn,应该是这个吧！我用线段树维护区间的最大值，预先建立好线段树，使得查询任意区间的最大值都是logn，然后，对一个数，对剩下的区间进行二分查找，求满足第一个满足区间的最大值大于该数。可以ac。

我的代码，（写的有点多，有点杀鸡焉用牛刀的感觉，算是复习下线段树的写法，其实rmq，sparse table也可以满足要求）。

 int a[];

 vector<int> f;

 int n;

 void bt(int o, int l, int r) {

     //cout << o << endl;

     if(l == r) {

         a[o] = f[l - ];

         //cout << l - 1 << " " << f[l - 1] << endl;

     } else {

         int mid = (l + r) >> ;

         bt(o * , l, mid);

         bt(o *  + , mid + , r);

         a[o] = max(a[o * ], a[o *  + ]);

     }

     //cout << o << " " << a[o] << endl;

 }

 int dx, dy;

 //int cnt;

 int ask(int o, int l, int r) {

     //cout << o << " " << l << " " << r << endl;

     //cnt++;

     //if(cnt >= 5) return 0;

     if(dx > dy) return INT_MIN;

     if(r < dx || l > dy) return INT_MIN;

     if(dx <= l && r <= dy) {

         return a[o];

     } else {

         int mid = (l + r) >> ;

         bool f1, f2;

         int a1, a2;

         f1 = f2 = ;

 //        if(mid <= dy) {

 //            f1 = 1;

 //            a1 = ask(o * 2, l, mid);

 //        }

 //        if(mid + 1 >= dx) {

 //            f2 = 1;

 //            a2 = ask(o * 2 + 1, mid + 1, r);

 //        }

         a1 = ask(o * , l, mid);

         a2 = ask(o *  + , mid + , r);

         int res = INT_MIN;

         //if(f1) res = max(res, a1);

         //if(f2) res = max(res, a2);

         res = max(a1, a2);

         return res;

     }

 }

 int work(int tar, int left, int right) {

     int p = left;

     while(left < right) {

         int mid = (left + right) / ;

         dx = p, dy = mid;

         int t = ask(, , n);

         if(t > tar) {

             right = mid;

         } else {

             left = mid + ;

         }

     }

     dx = p, dy = left;

     return ask(, , n);

 }

 vector<int> nextGreaterElements(vector<int>& nums) {

     f = nums;

     n = nums.size();

     bt(, , n);

     vector<int> res(n);

     //cout << "asd" << endl;

     for (int i = ; i <= n; i++) {

         int tar = nums[i - ];

         dx = i + , dy = n;

         int x = ask(, , n);

         //cout << x << endl;

         //return res;

         dx = , dy = i - ;

         int y = ask(, , n);

         cout << x << " " << y << endl;

         if(x > tar) {

             res[i - ] = work(tar, i + , n);

         } else if(y > tar) {

             res[i - ] = work(tar, , i - );

         } else {

             res[i - ] = -;

         }

         cout << i << endl;

         //return res;

     }

     return res;

 }

c. 这个题跟第一题差不多，其实还是稍微不同的，一种是利用stack维护单调递减的性质，循环的解决办法，就是创建2倍的原数组长度，这应该算通用的解决办法。见这里：http://bookshadow.com/weblog/2017/02/05/leetcode-next-greater-element-ii/

其实，stack优化的题目，leetcode有一类这样的题目，这种解法不容易想出来，需要仔细分析性质，我不是很熟练，有时间练习学习一下。好像有好几道，反正不是很好做！

d. 还有一种解法，我看的排名第一的解法，利用这样的性质，用res[i]记录最后的结果，a[i]代表原数组，i < j, 我们计算res[i]的时候，如果i < j, a[j] <= a[i], 可以先计算出res[j], 然后怎么考虑使用res[j]进行优化，其实 j 到 res[j] 之间的数字可以直接跳过，我们可以不直接保存res[j], 而是保存res[j]的下标，利用这个下标进行跳转。可以利用这个性质，进行优化。复杂度分析：不会分析。

代码：

 class Solution {

     int n;

     vector<int> a, f;

 public:

     int calc(int x)

     {

         int &ans = f[x];

         if(ans >= -)

             return ans;

         if(ans == -)

             return ans = -;

         ans = -;

         int y;

         for(y = (x + ) % n; y != - && a[x] >= a[y]; y = calc(y));

         return ans = y;

     }

     vector<int> nextGreaterElements(vector<int>& nums) {

         a = nums; n = a.size();

         f.resize(n, -);

         vector<int> aa;

         for(int i = ; i < n; i++)

         {

             calc(i);

             if(f[i] == -) aa.push_back(-);

             else aa.push_back(a[f[i]]);

         }

         return aa;

     }

 };

4. 498. Diagonal Traverse

我的做法是：使用辅助空间记录每一行的起始位置，注意一下方向和边界条件。

更好的做法是：空间复杂度O(1)的，http://bookshadow.com/weblog/2017/02/05/leetcode-diagonal-traverse/ 维护每次转移的坐标，代码速度很快！

巴特西

LeetCode Weekly Contest 18B

最新文章

热门文章