Saturday, October 8, 2016

LeetCode OJ - Rotate Function

Problem:

Please find the problem here.

Analysis:

The key idea for this problem is that once we evaluated $ F(0) $, we can quickly evaluate $ F(1) $ as follow:

$ F(0) = 0 a[0] + 1 a[1] + 2 a[2] + 3 a[3] $

$ F(1) = 0 a[1] + 1 a[2] + 2 a[3] + 3 a[0] $

Rearranging, we get:

$ F(0) = 0 a[0] + 1 a[1] + 2 a[2] + 3 a[3] $
$ F(1) = 3 a[0] + 0 a[1] + 1 a[2] + 2 a[3] $

$ F(1) - F(0) = 3 a[0] - a[1] - a[2] - a[3] $

Or equivalently $ F(1) - F(0) = 4 a[0] - a[0] - a[1] - a[2] - a[3] $

Solution:

With the equations above, we know rotating once means adding 4 times the first element minus the sum of all elements, this is easy to rotate through and find the maximum!

Code:

#include "stdafx.h"

// https://leetcode.com/contest/4/problems/rotate-function/

#include "LEET_ROTATE_FUNCTION.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_ROTATE_FUNCTION
{
    class Solution {
    public:
        int maxRotateFunction(vector<int>& A) {
            vector<int>& nums = A;

            int n = (int)nums.size();
            int sum = 0;

            for (int i = 0; i < n; i++)
            {
                sum += nums[i];
            }

            int r = 0;
            for (int i = 0; i < n; i++)
            {
                r += i * nums[i];
            }

            int max_r = r;

            for (int move = 0; move < n - 1; move++)
            {
                r = r - sum + nums[move] * nums.size();
                if (r > max_r)
                {
                    max_r = r;
                }
            }

            return max_r;
        }
    };
};

using namespace _LEET_ROTATE_FUNCTION;

int LEET_ROTATE_FUNCTION()
{
    Solution solution;
    vector<int> v;
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(6);
    cout << solution.maxRotateFunction(v) << endl;
    return 0;
}

No comments :

Post a Comment