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是偶数只需对原对应数字取反即可~

 

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

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.

题目大意:给一个数组,找三个数字,使这三个数乘积最大,返回乘积的最大值~

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

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的值~