5 problems solved.

lintcoder · lintcoder · commit f9094095c767 · 2020-02-13T21:00:52.000+08:00
diff --git a/src/1260.cpp b/src/1260.cpp
@@ -0,0 +1,20 @@
+vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
+        int row = grid.size();
+        int col = grid[0].size();
+        int sz = row*col;
+        k %= sz;
+        if (k == 0)
+            return grid;
+        vector<vector<int>> res(row, vector<int>(col, 0));
+        for (int i = 0; i < row; ++i)
+        {
+            for (int j = 0; j < col; ++j)
+            {
+                int t = (i*col+j+k)%sz;
+                int r = t/col, c = t%col;
+                res[r][c] = grid[i][j];
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/1331.cpp b/src/1331.cpp
@@ -0,0 +1,42 @@
+vector<int> arrayRankTransform(vector<int>& arr) {
+        int len = arr.size();
+        if (len == 0)
+            return {};
+        if (len == 1)
+            return {1};
+        
+        struct Elem
+        {
+            int val;
+            int pos;
+            int rank;
+            Elem(int v = 0, int p = -1, int r = 1):val(v), pos(p), rank(r){}
+        };
+        
+        vector<Elem> vec(len);
+        for (int i = 0; i < len; ++i)
+        {
+            vec[i].val = arr[i];
+            vec[i].pos = i;
+        }
+        
+        auto cmp = [](const Elem& a, const Elem& b) {
+            return a.val < b.val;
+        };
+        
+        sort(vec.begin(), vec.end(), cmp);
+        vector<int> res(len, 1);
+        int rank = 1;
+        for (int i = 1; i < len; ++i)
+        {
+            if (vec[i].val > vec[i-1].val)
+            {
+                ++rank;
+            }
+            vec[i].rank = rank;
+        }
+        for (int i = 0; i < len; ++i)
+            res[vec[i].pos] = vec[i].rank;
+        
+        return res;
+    }
diff --git a/src/341.cpp b/src/341.cpp
@@ -0,0 +1,65 @@
+class NestedIterator {
+public:
+    NestedIterator(vector<NestedInteger> &nestedList) {
+        skF.push(nestedList.begin());
+        skL.push(nestedList.end());
+    }
+
+    int next() {
+        nit iter = skF.top();
+        int res = iter->getInteger();
+        ++iter;
+        skF.pop();
+        skF.push(iter);
+        return res;
+    }
+
+    bool hasNext() {
+        int sz = skF.size();
+        while (sz != 0)
+        {
+            if (skF.top() == skL.top())
+            {
+                skF.pop();
+                skL.pop();
+                sz--;
+                if (sz > 0)
+                {
+                    nit iter = skF.top();
+                    iter++;
+                    skF.pop();
+                    skF.push(iter);
+                }
+                else
+                    break;
+            }
+            else
+            {
+                nit iter = skF.top();
+                if (iter->isInteger())
+                    return true;
+                else
+                {
+                    auto& t = iter->getList();
+                    if (t.size() == 0)
+                    {
+                        iter++;
+                        skF.pop();
+                        skF.push(iter);
+                    }
+                    else
+                    {
+                        skF.push(t.begin());
+                        skL.push(t.end());
+                        ++sz;
+                    }
+                }
+            }
+        }
+        
+        return false;
+    }
+    
+    using nit = vector<NestedInteger>::iterator;
+    stack<nit> skF, skL;
+};
diff --git a/src/454.cpp b/src/454.cpp
@@ -0,0 +1,25 @@
+int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
+        vector<int> sum;
+        int len = A.size();
+        for (int i = 0; i < len; ++i)
+        {
+            for (int j = 0; j < len; ++j)
+                sum.push_back(A[i]+B[j]);
+        }
+        sort(sum.begin(), sum.end());
+        
+        int res = 0;
+        for (int i = 0; i < len; ++i)
+        {
+            for (int j = 0; j < len; ++j)
+            {
+                int t = -(C[i]+D[j]);
+                if (binary_search(sum.begin(), sum.end(), t))
+                {
+                    res += upper_bound(sum.begin(), sum.end(), t) - lower_bound(sum.begin(), sum.end(), t);
+                }
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/944.cpp b/src/944.cpp
@@ -0,0 +1,16 @@
+int minDeletionSize(vector<string>& A) {
+        int len = A.size();
+        int sz = A[0].size();
+        int ct = 0;
+        for (int i = 0; i < sz; ++i)
+        {
+            for (int j = 0; j < len-1; ++j)
+                if (A[j][i] > A[j+1][i])
+                {
+                    ++ct;
+                    break;
+                }   
+        }
+        
+        return ct;
+    }
