@thousfeet
2018-02-20T23:18:06.000000Z
字数 7965
阅读 902
LeetCode
We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).
Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.
Example 1:
Input:
bits = [1, 0, 0]
Output: True
Explanation:
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.Example 2:
Input:
bits = [1, 1, 1, 0]
Output: False
Explanation:
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.Note:
1 <= len(bits) <= 1000.
bits[i] is always 0 or 1.
【思路】
三秒签到题。
因为如果有 1 就一定要凑 10、11，也即不管 1 后面是啥，只要逢 1 都必须要带走后面一个，如果能顺利遍历到最末尾（不会被前面的数带走），就OK
【代码】
bool isOneBitCharacter(int* bits, int bitsSize) {bool flag = false;for(int i = 0; i < bitsSize;){if(i == bitsSize-1) flag = true;if(bits[i] == 1) i+=2;else i++;}return flag;}
Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6Note:
nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.
【思路】
一开始想的用 map 去存一个 < int, < int,pair > > 这样的（前一个 int 存 num，第二个是计数， pair 存 num 出现的最起始位置和终止位置），可以直接丢进map最终遍历拿到计数最大的。但是 map 太久没用生疏了- -，于是手动用数组模拟，开三个数组count、minIndex、maxIndex，去存每个数的计数、出现的最起始位置和终止位置。然后遍历取count最大的。当count相同的时候，取 终止-起始 最小的。
int findShortestSubArray(int* nums, int numsSize) {int count[50010];int minIndex[50010];int maxIndex[50010];memset(count,0,sizeof(count));memset(minIndex,-1,sizeof(minIndex));memset(maxIndex,-1,sizeof(maxIndex));for(int i = 0; i < numsSize; i++){int j = nums[i];count[j]++;if(minIndex[j] < 0) minIndex[j] = i;else maxIndex[j] = i;}for(int i = 0; i < 50000; i++)if(maxIndex[i] < 0) maxIndex[i] = minIndex[i];int tmp = 50010;int maxCnt = -1;for(int i = 0; i < 50000; i++){if(count[i] > maxCnt || (count[i] == maxCnt && tmp > maxIndex[i] - minIndex[i] + 1) ){maxCnt = count[i];tmp = maxIndex[i] - minIndex[i] + 1;}}return tmp;}
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].Note:
1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
【思路】
一开始的暴力代码如下，从最大长度 len 逐渐缩小去找，先比较头尾，如果不一致直接跳过。复杂度会小于 O(n^3)，运气好的话基本就是O(n^2)， 但是遇到测试点是1000个一毛一样的数，妥妥的O(10^9)就炸了...
int findLength(int* A, int ASize, int* B, int BSize) {int len = min(ASize,BSize);while(len > 0){int As = 0, Ae = len-1;int Bs = 0, Be = len-1;for(int i = 0; Ae+i < ASize; i++){for(int j = 0; Be+j < BSize; j++){bool flag = true;if(A[As+i]!=B[Bs+j] || A[Ae+i]!=B[Be+j]) continue;for(int k = 0; k < len; k++){if(A[As+i+k]!=B[Bs+j+k]){flag = false;break;}}if(flag) return len;}}len--;}return 0;}
偷偷看了别人的discuss，woc牛逼啊，其实关键就是两行代码：
if(A[i] == B[j]) dp[j] = dp[j+1]+1;
else dp[j] = 0;
也即动规表达式。
思路大致就是，A 从后往前遍历，只看 A 中从 i 位置到最后的这串（A[ i : ASize-1 ]），然后去找 B 中有没有可以匹配上这串的东西。
dp[j]是： B 中以 j 位置为开头，能够匹配上 A 那串的最长长度。显然如果我知道了前一次中以 j+1 位置开头匹配上的最长长度，只要 j 位置是匹配的，那就有 dp[j] = dp[j+1]+1，如果 j 位置不匹配，那说明以 j 位置开头的串已经打出GG了，dp[j] = 0。
时间复杂度是O(n^2)
【代码】
int findLength(int* A, int ASize, int* B, int BSize) {int dp[BSize+1];memset(dp,0,sizeof(dp));int max = -1;for(int i = ASize - 1; i >= 0; i--){for(int j = 0; j < BSize; j++){if(A[i] == B[j]) dp[j] = dp[j+1]+1;else dp[j] = 0;if(max < dp[j]) max = dp[j];}}return max;}
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note:
The length of each dimension in the given grid does not exceed 50.
【思路】
就是个深搜练习，又在边界上踩坑坑惨了自己，也是没谁了。
【代码】
int dfs(int i, int j, int** grid, int gridRowSize, int gridColSize){if(i < 0 || i >= gridRowSize || j < 0 || j >= gridColSize || grid[i][j] == 0) return 0;grid[i][j] = 0;return dfs(i, j-1, grid, gridRowSize, gridColSize) + dfs(i, j+1, grid, gridRowSize, gridColSize) + dfs(i-1, j, grid, gridRowSize, gridColSize) + dfs(i+1, j, grid, gridRowSize, gridColSize) + 1;}int maxAreaOfIsland(int** grid, int gridRowSize, int gridColSize) {int max = 0;for(int i = 0; i < gridRowSize; i++)for(int j = 0; j < gridColSize; j++){int res = dfs(i, j, grid, gridRowSize, gridColSize);if(res > max) max = res;}return max;}
Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices3 = 8
Buying at prices4 = 4
Selling at prices5 = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.Note:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
感觉是动规，但是规了半天没规出来，想着划分成一个一个的上升段，每次卖出只可能在某一段的最高点，买入只可能在最低点。先把总的最低点和总的最高点拿来做一波，然后找次高点，如果在最低最高之间，且次高点卖出的差值超过 fee，就分两个波段做。
打来打去打了一坨而且发现无论如何逃不掉的O(n^2)....弃疗去看了discuss，然后发现了一篇超级无敌厉害的详解帖：Most consistent ways of dealing with the series of stock problems，里面分析了好多个同类题目不同条件的情况，而我果断的只看了这一题蛤蛤蛤（...以后回来看时候补吧orz
【思路】
当前只有可能是两种情况：我现在有一只股票、我现在没有股票。
有股票可能是因为：昨天就有，我拿着没卖；或昨天没有，我今天买了。（s1 = max(s1, s0-prices[i]-fee)）
没股票可能是因为：昨天没有，今天也没买；或昨天是有的，我今天卖了。（s0 = max(s0, s1+prices[i])）
（-fee放在s1、s0都行）
时间复杂度O(n)。（这代码是真的美炸了好吗（（....
【代码】
int maxProfit(int* prices, int pricesSize, int fee) {int s0 = 0, s1 = -100010;for(int i = 0; i < pricesSize; i++){int tmp = s1;s1 = max(s1,s0-prices[i]-fee);s0 = max(s0, tmp+prices[i]);}return s0;}
In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.
Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
Example:
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.Note:
nums.length will be between 1 and 20000.
nums[i] will be between 1 and 65535.
k will be between 1 and floor(nums.length / 3).
找到 3 个、不相交、和最大的子序列，每个子序列长度为 k。
最暴力就是滑动窗口那样的，前后两个窗口滑，扔掉一个捡一个，直到滑到某个局部最大的地方，然后遍历中部去找中间那段的和最大子序列，是个 < O(n^3) 很可能会炸的解...
【偷学来的思路】
dp，维护头尾两个数组：
L[i]： 从头开始到以 i 结尾的这串里（区间[1, i]）， k 长度子序列和的最大值
R[i]： 从 i 开始到末尾的这串里（区间[i, end]）， k 长度子序列和的最大值
开始都是0，维护的时候：
L[i]从头往后更新：对于某个 i 位置的数，要么不取（L[i] = L[i-1]），要么取（L[i] = sum[i] - sum[i - k]）
R[i]从后往前更新：对于某个 i 位置的数，要么不取（R[i] = R[i+1]），要么取（R[i] = sum[i + k] - sum[i]）
然后就枚举中间那段的起始位置p。中间段的位置是 [p, p+k-1]，然后在[1, p-1]中取一个长度为k的最大值，就是L[p-1]，再在[p+k, n] 中取一个长度为k的最大值，就是 R[p+k]，遍历取max(sum[p+k-1] - sum[p-1] + L[p-1] + R[p+k])。
【代码】
int* maxSumOfThreeSubarrays(int* nums, int numsSize, int k, int* returnSize) {int L[20010];int R[20010];int sum[20010];memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(sum,0,sizeof(sum));int l = -1, m = -1, r = -1;//--initsum[0] = nums[0];for(int i = 1; i < numsSize; i++)sum[i] = sum[i-1]+nums[i];//--维护L、RL[k-1] = sum[k-1];for(int i = k; i < numsSize; i++)L[i] = max(L[i-1],sum[i]-sum[i-k]);R[0] = max(R[1],sum[k-1]);for(int i = numsSize-k; i > 0; i--)R[i] = max(R[i+1],sum[i+k-1]-sum[i-1]);//--遍历寻找中间段 mint res = -1;for(int p = k; p <= numsSize-2*k; p++){int tmp = sum[p+k-1] - sum[p-1] + L[p-1] + R[p+k];if(res < tmp){res = tmp;m = p;}}//--寻找开头段、末尾段的起始位置 l、rint tmp = -1;for(int i = 0; i < m; i++){if(tmp < L[i]){tmp = L[i];l = i-k+1;}}tmp = -1;for(int i = m+k; i < numsSize; i++){if(tmp < R[i]){tmp = R[i];r = i;}}//--returnint *a = (int*)malloc((*returnSize) * sizeof(int));a[0] = l, a[1] = m, a[2] = r;return a;}