LeetCode OJ – 第3页 – 柳婼の blog

LeetCode 779. K-th Symbol in Grammar

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
Note:

N will be an integer in the range [1, 30].
K will be an integer in the range [1, 2^(N-1)].

题目大意：在第一行，我们写一个0.现在在后面的每一行中，我们看前一行，用01代替0出现的每一个，每一次出现1代表10。现在问第N行第K数字是什么数字

分析：用递归，已知N == 1的时候返回0，为了知道第N行第K个数字的值，只要知道它在第N-1行的第(K+1)/2个数字对应的值即可，因为0对应01，1对应10，那么如果K是奇数只需和原数字相同即可，如果K是偶数只需对原对应数字取反即可～

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        return (K % 2 == 0) ? !kthGrammar(N-1, (K+1)/2) : kthGrammar(N-1, (K+1)/2);
    }
};

class Solution {

public:

int kthGrammar(int N, int K) {

if (N == 1) return 0;

return (K % 2 == 0) ? !kthGrammar(N-1, (K+1)/2) : kthGrammar(N-1, (K+1)/2);

}

};

LeetCode 643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

题目大意：给定一个由n个整数组成的数组，找到具有最大平均值的给定长度k的连续子数组。你需要输出最大的平均值～

分析：sum[i]保存0～i个数字的和，每次将(sum[i]-sum[i-k])的最大值保存在ans中，然后返回ans*1.0/k

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        if (nums.size() == 0) return 0.0;
        vector<int> sum(nums.size());
        sum[0] = nums[0];
        for (int i = 1; i < k; i++) sum[i] = sum[i-1] + nums[i];
        int ans = sum[k-1];
        for (int i = k; i < nums.size(); i++) {
            sum[i] = sum[i-1] + nums[i];
            ans = max(ans, sum[i] - sum[i-k]);
        }
        return ans * 1.0 / k;       
    }
};

class Solution {

public:

double findMaxAverage(vector<int>& nums, int k) {

if (nums.size() == 0) return 0.0;

vector<int> sum(nums.size());

sum[0] = nums[0];

for (int i = 1; i < k; i++) sum[i] = sum[i-1] + nums[i];

int ans = sum[k-1];

for (int i = k; i < nums.size(); i++) {

sum[i] = sum[i-1] + nums[i];

ans = max(ans, sum[i] - sum[i-k]);

}

return ans * 1.0 / k;

}

};

LeetCode 628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

题目大意：给一个数组，找三个数字，使这三个数乘积最大，返回乘积的最大值～

分析：先对数组排序，要么是最后三个数字乘积，要么可能会有负数，则是前两个数的乘积*最后一个数字的乘积，取这个两个乘积结果的最大值即可～

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[0] * nums[1] * nums[n-1], nums[n-3] * nums[n-2] * nums[n-1]);
    }
};

class Solution {

public:

int maximumProduct(vector<int>& nums) {

sort(nums.begin(), nums.end());

int n = nums.size();

return max(nums[0] * nums[1] * nums[n-1], nums[n-3] * nums[n-2] * nums[n-1]);

}

};

LeetCode 674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it is not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
Note: Length of the array will not exceed 10,000.

题目大意：给一个乱序数组，返回这个数组中递增连续子序列中最长的长度～

分析：遍历从i = 1到结尾，每次比较nums[i-1]和nums[i]，如果是递增的就将temp++，否则temp=1，每次将temp最大值保存在ans中，最后返回ans的值～

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int temp = 1, ans = 1;
        for (int i = 1; i < nums.size(); i++) {
            temp = (nums[i-1] < nums[i]) ? temp + 1 : 1;
            ans = max(ans, temp);
        }
        return nums.size() == 0 ? 0 : ans;
    }
};

class Solution {

public:

int findLengthOfLCIS(vector<int>& nums) {

int temp = 1, ans = 1;

for (int i = 1; i < nums.size(); i++) {

temp = (nums[i-1] < nums[i]) ? temp + 1 : 1;

ans = max(ans, temp);

}

return nums.size() == 0 ? 0 : ans;

}

};

LeetCode 633. Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False

题目大意：给一个数c，判断是否存在两个数字a b满足a*a+b*b=c，存在就返回true，否则返回false

分析：i和j分别从根号c开始到0，如果找到了i * i + j * j == c就return true，如果i * i + j * j < c就break第二层for循环，最后如果都没有找到就返回false～

class Solution {
public:
    bool judgeSquareSum(int c) {
        int t = sqrt(c);
        for (int i = t; i >= 0; i--) {
            for (int j = t; j >= 0; j--) {
                if (i * i + j * j == c) return true;
                if (i * i + j * j < c) break;
            }
        }
        return false;
    }
};

class Solution {

public:

bool judgeSquareSum(int c) {

int t = sqrt(c);

for (int i = t; i >= 0; i--) {

for (int j = t; j >= 0; j--) {

if (i * i + j * j == c) return true;

if (i * i + j * j < c) break;

}

return false;

}

};

LeetCode 724. Find Pivot Index

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

题目大意：在一个数组中找到一个数字的下标，要求这个数字左边的数字和等于右边的数字和，如果不存在就返回-1

分析：计算数组所有元素和sum，然后遍历数组，每次将前i-1个数字的和累加在t中，每次从sum中减去nums[i]，这样sum就是nums[i]后面所有数字的和，如果sum == t就返回i，否则就返回-1

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size(), sum = 0, t = 0;
        if (n == 0) return -1;
        if (n == 1) return 0;
        for (int i : nums) sum += i;
        for (int i = 0; i < n; i++) {
            sum -= nums[i];
            if (sum == t) return i;
            t += nums[i];
        }
        return -1;
    }
};

class Solution {

public:

int pivotIndex(vector<int>& nums) {

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

if (n == 0) return -1;

if (n == 1) return 0;

for (int i : nums) sum += i;

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

sum -= nums[i];

if (sum == t) return i;

t += nums[i];

}

return -1;

}

};