@thousfeet
2018-02-18T21:00:00.000000Z
字数 8743
阅读 1021
LeetCode
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512
【思路】
以第一行、第一列为基准，然后一个个往右下角去遍历，然后...卡边界判断条件卡了快一个小时....我好像以前就老是在边界上自坑....真的是要多训练..orz
【代码】
bool isToeplitzMatrix(int** matrix, int matrixRowSize, int *matrixColSizes) {if(matrixRowSize == 1 || matrixColSizes[0] == 1)return true;for(int i = 0; i < matrixRowSize-1; i++){for(int j = 1; j < matrixRowSize-i && j < matrixColSizes[0]; j++)if(matrix[i][0] != matrix[i+j][j]) return false;}for(int i = 1; i < matrixColSizes[0]-1; i++){for(int j = 1; j < matrixRowSize && j < matrixColSizes[0]-i; j++)if(matrix[0][i] != matrix[j][i+j]) return false;}return true;}
In a given integer array nums, there is always exactly one largest element. Find whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, otherwise return -1.
Example 1:
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the
largest integer, and for every other number in the array x, 6 is more
than twice as big as x. The index of value 6 is 1, so we return 1.Example 2:
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't
at least as big as twice the value of 3, so we return -1.
【思路】
不用看了，三秒签到题。
【代码】
int dominantIndex(int* nums, int numsSize) {int fir = -1;int sec = -1;int index = -1;for(int i = 0; i < numsSize; i++){if(nums[i] > sec)sec = nums[i];if(sec > fir){int tmp = sec;sec = fir;fir = tmp;index = i;}}if(fir >= 2*sec)return index;return -1;}
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost1, pay that cost and go to the top.Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost3.Note:
cost will have a length in the range [2, 1000]. Every cost[i] will be an integer in the range [0, 999].
【思路】
本来在那边兴致勃勃的瞎贪心，贪第一个样例就显然不对了..于是乖乖的开始动规...
偷偷百度了一下小学奥数题走楼梯怎么写的，噢原来就是那个传说中的经典题解，当前方案等于前一节楼梯+前两节楼梯的方案和。搜嘎那我就会了..（一拳就是一个...x）大致思路就是，当到达第 i 节楼梯的总cost值，要不然就是 i-1 那节的总数值加上第 i 节的cost，要不然就是 i-2 那节的总数值加上第 i 节的cost，取一个最小的就好了。（从结果是怎么来的往前想，而不是从第一步往后想这种，也不失为一个好办法）
中间那段代码因为早上被边界坑惨了于是特判了一下边界防RE，如果当前step超过cost数组长度，手动给这个cost值赋值0。
然后写递归写超时了...于是还是老办法，拿了个dp数组来存之前算过的值（以 i 节楼梯为终点的cost），之后就可以直接判断如果dp不为0，算过了的就不用再递归。
LeetCode用全局变量数组会出事，没有手动初始化不会给默认0，所以要手动memset。
【代码】
int dp[1010];int sum(int step,int* cost, int costSize){if(step == 0) return dp[step] = cost[0];if(step == 1) return dp[step] = cost[1];int c;if(step >= costSize) c = 0;else c = cost[step];int a = dp[step-1] == 0 ? sum(step-1,cost,costSize) + c : dp[step-1] + c;int b = dp[step-2] == 0 ? sum(step-2,cost,costSize) + c : dp[step-2] + c;if(a < b) return dp[step] = a;return dp[step] = b;}int minCostClimbingStairs(int* cost, int costSize) {memset(dp,0,sizeof(dp));return sum(costSize+1,cost,costSize);}
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 (nums3 = 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].
【思路】
不用看了，签到题
int pivotIndex(int* nums, int numsSize) {int sum = 0;int mid = 0;for(int i = 0; i < numsSize; i++)sum += nums[i];for(int i = 0; i < numsSize; i++){if(mid*2 + nums[i] == sum) return i;mid += nums[i];}return -1;}
We have some permutation A of [0, 1, ..., N - 1], where N is the length of A. The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j]. The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1]. Return true if and only if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.Example 2:
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.
【思路】
最暴力的做法就是O(n^2)求逆序数对数了，但是显然题目说了会卡时间，虽然也可以O(nlogn)但是还要归并或者树状数组来一通。
开始审题审错浪费了半天orz，后面偷偷看了眼别人的3行代码solution，woc牛逼啊，%%%%
大致思路就是，local一定是global，那也就是只要看非紧挨着的那种逆序数对是不是存在了。因为正常的A数组应该是[0 1 2 3 4...]这样，第i个会在i的位置上，但如果第i个位置上出现的是i+2以及更大的数，说明这2个或更多比它小的数不得不摆在它后面了，即使是紧挨着一个扣掉local，那肯定逃不掉的还有一个是global。同理出现的是i-2以及更小的数，在它前面就会有比它更大的数造成global。
bool isIdealPermutation(int* A, int ASize) {for(int i = 0; i < ASize; i++)if(abs(A[i]-i) > 1) return false;return true;}
Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], 2, 3, 4 is the highest number of chunks possible.Note:
arr will have length in range [1, 10]. arr[i] will be a permutation of [0, 1, ..., arr.length - 1].
【思路】
题目要求切分开之后，各自排序再拼一起，能够等价于直接全部升序排序的结果，问最多能切分为几段。
有点像上午那题。由于数组里的数字一定是 [0, 1, ..., arr.length - 1]，因此思路就是，如果某个很大的数 i 出现在了比较前面的地方，那至少从这开始的一串一直到第 i 位都不得不保留成一整块。所以遍历数组，当遇到一个 arr[i] 大于 i 的数的话，就一路遍历到第 i 个位置看看是不是都比它小，如果在此段内还遇到更大的数 arr[j]，那么这块得继续延长至少到 j 的位置。
（想到就会打，用时20+min）
【代码】
int maxChunksToSorted(int* arr, int arrSize) {int count = 0;int num = arr[0];for(int i = 0; i < arrSize;){while(i <= num){if(arr[i] > num) num = arr[i];i++;}count++;num = arr[i];}return count;}
Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.
Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.
A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)
For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)Example 1:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns trueExplanation:
The first two events can be booked. The third event can be double booked.
The fourth event (5, 15) can't be booked, because it would result in a triple booking.
The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.Note:
The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].
【思路】
很像挑战的那道题...但是没想出来triple要怎么处理...
这个解法看着还基本能懂，但也有点懵逼：C++ O(N) solution
以及一个看起来很厉害但是没看懂的题解，mark以后研究：Simplified winner's solution
This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.
Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], 3, 4, 4 is the highest number of chunks possible.Note:
arr will have length in range [1, 2000]. arr[i] will be an integer in range [0, 10**8].
按照前面一题的想法已经行不通了，因为会出现重复或压根不出现的数字。
想了一会会发现，当前段的最大值一定要小于后面一段的最小值，所以还是可以用一边遍历一边去找某个区段的最右边界的想法。
用一个 max 数组来存每段的最大值，显然这个 max 数组是升序的。遍历 arr，一旦发现某个数大于最后一段的最大值，那就说明可以新开一个段了，否则把它拿去和前面那些段的 max 值比较，如果小于第 j 段的 max 值，那么说明当前这个数应该归入到那一段，于是count = j。
这其实是一个O(n^2)的做法，本来不抱希望的试一试没想到就A了..
int maxChunksToSorted(int* arr, int arrSize) {int max[2007] = {0};max[1] = arr[0];int count = 1;for(int i = 1; i < arrSize; i++){if(arr[i] >= max[count]){max[++count] = arr[i];continue;}for(int j = 1; j < count; j++){if(arr[i] < max[j]){max[j] = max[count];count = j;}}}return count;}