5 problems solved.

lintcoder · lintcoder · commit 1543f0cd9df9 · 2020-03-08T18:14:52.000+08:00
diff --git a/src/1302.cpp b/src/1302.cpp
@@ -0,0 +1,24 @@
+int deepestLeavesSum(TreeNode* root) {
+        deque<TreeNode*> dq;
+        dq.push_back(root);
+        int len = 1;
+        int sum = 0;
+        while (len != 0)
+        {
+            int subsum = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                TreeNode* node = dq[i];
+                subsum += node->val;
+                if (node->left != nullptr)
+                    dq.push_back(node->left);
+                if (node->right != nullptr)
+                    dq.push_back(node->right);
+            }
+            sum = subsum;
+            dq.erase(dq.begin(), dq.begin()+len);
+            len = dq.size();
+        }
+        
+        return sum;
+    }
diff --git a/src/1329.cpp b/src/1329.cpp
@@ -0,0 +1,34 @@
+vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
+        int row = mat.size();
+        int col = mat[0].size();
+        if (row == 1 || col == 1)
+            return mat;
+        
+        int minval = row < col ? row : col;
+        vector<int> vec(minval);
+        for (int i = row-2; i >= 0; --i)
+        {
+            int k = row-i;
+            if (col < k)
+                k = col;
+            for (int j = 0; j < k; ++j)
+                vec[j] = mat[i+j][j];
+            sort(vec.begin(), vec.begin()+k);
+            for (int j = 0; j < k; ++j)
+                mat[i+j][j] = vec[j];
+        }
+        
+        for (int i = 1; i < col-1; ++i)
+        {
+            int k = col-i;
+            if (row < k)
+                k = row;
+            for (int j = 0; j < k; ++j)
+                vec[j] = mat[j][i+j];
+            sort(vec.begin(), vec.begin()+k);
+            for (int j = 0; j < k; ++j)
+                mat[j][i+j] = vec[j];
+        }
+        
+        return mat;
+    }
diff --git a/src/235.cpp b/src/235.cpp
@@ -0,0 +1,33 @@
+TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
+        if (root == p || root == q)
+            return root;
+        vector<TreeNode*> path;
+        TreeNode* node = root;
+        while (node != nullptr)
+        {
+            path.push_back(node);
+            if (node->val > p->val)
+            {
+                node = node->left;
+            }
+            else if (node->val == p->val)
+                break;
+            else
+            {
+                node = node->right;
+            }
+        }
+
+        node = root;
+        int len = path.size();
+        int i = 0;
+        while (i < len && node == path[i])
+        {
+            if (node == p || node == q)
+                return node;
+            node = node->val > q->val ? node->left : node->right;
+            ++i;
+        }
+        
+        return path[i-1];
+    }
diff --git a/src/414.cpp b/src/414.cpp
@@ -0,0 +1,55 @@
+int thirdMax(vector<int>& nums) {
+        int len = nums.size();
+        if (len == 1)
+            return nums[0];
+        if (len == 2)
+            return nums[0] > nums[1] ? nums[0] : nums[1];
+        int arr[3] = {0};
+        arr[0] = nums[0];
+        int ct = 1;
+        int i = 1;
+        while (i < len)
+        {
+            if (ct == 1)
+            {
+                if (nums[i] != arr[0])
+                {
+                    arr[1] = nums[i];
+                    ++ct;
+                }
+            }
+            else if (ct == 2)
+            {
+                if (nums[i] != arr[0] && nums[i] != arr[1])
+                {
+                    arr[2] = nums[i];
+                    ++ct;
+                    sort(arr, arr+3);
+                }
+            }
+            else
+            {
+                if (nums[i] > arr[0] && nums[i] < arr[1])
+                    arr[0] = nums[i];
+                else if (nums[i] > arr[1] && nums[i] < arr[2])
+                {
+                    arr[0] = arr[1];
+                    arr[1] = nums[i];
+                }
+                else if (nums[i] > arr[2])
+                {
+                    arr[0] = arr[1];
+                    arr[1] = arr[2];
+                    arr[2] = nums[i];
+                }
+            }
+            ++i;
+        }
+        
+        if (ct == 1)
+            return arr[0];
+        else if (ct == 2)
+            return arr[0] > arr[1] ? arr[0] : arr[1];
+        else
+            return arr[0];
+    }
diff --git a/src/643.cpp b/src/643.cpp
@@ -0,0 +1,22 @@
+double findMaxAverage(vector<int>& nums, int k) {
+        int maxsum = INT_MIN;
+        int len = nums.size();
+        if (len <= k-1)
+            return 0;
+        int subsum = 0;
+        for (int i = 0; i < k; ++i)
+            subsum += nums[i];
+        if (subsum > maxsum)
+            maxsum = subsum;
+        int i = 0, j = k;
+        while (j < len)
+        {
+            subsum = subsum - nums[i] + nums[j];
+            if (subsum > maxsum)
+                maxsum = subsum;
+            ++i;
+            ++j;
+        }
+        
+        return (double)maxsum/k;
+    }
