ARTS #008
ARTS #008
ARTS is an activity initiated by
由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.
ARTS 008
This is article 8
Algorihm algorithm question
leetcode algorithm question 18 4Sum: Difficulty: Moderate
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
Since I just solved the 3Sum problem last time, the first solution I thought of was to convert it into a 3Sum problem. The implementation is as follows:
//插入排序
int* insertionSort(int nums[],int numsSize) {
for (int j = 1; j < numsSize; j++) {
int sortingNum = nums[j];
for (int i = j-1; i >=0; i--) {
if (sortingNum < nums[i] ) {
int temp = nums[i+1];
nums[i+1] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
// 二分查找
int binary_search(int arr[],int left,int right,int element){
while(left<=right) {
int mid = (left+right)/2;
if(arr[mid]>element){
right = mid - 1;
}
else if(arr[mid]<element){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
int** threeSumtarget(int* nums, int numsSize, int* returnSize,int target) {
int *sortedNums = insertionSort(nums,numsSize);
int min = sortedNums[0] ;
int max = sortedNums[numsSize-1];
int count = 0;
int **result= NULL;
int mixLimit = 0;
int maxLimit = 0;
if (target > 0) {
mixLimit = target;
maxLimit = 0;
}
else if (target < 0){
mixLimit = 0;
maxLimit = target;
}
else{
mixLimit = 0;
maxLimit = 0;
}
if(min > mixLimit)//最小数
return NULL;
if(max < maxLimit)//最大数
return NULL;
for (int i = 0; i < numsSize-2 && sortedNums[i] <=mixLimit; i++) {
if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
continue;
}
for (int j =numsSize-1; j >i && sortedNums[j] >= maxLimit; j--) {
if (j < numsSize-1 && sortedNums[j] == sortedNums[j+1]) {
continue;
}
int first = sortedNums[i];
int second = sortedNums[j];
int third = target - first - second;
int dfsd =binary_search(sortedNums, i+1, j-1, third);
if (dfsd == -1) {
continue;
}
third = sortedNums[dfsd];
int* sums = (int*)malloc(sizeof(int) * (3));
sums[0] = first;
sums[1] = second;
sums[2] = third;
if (count ==0) {
count++;
result=(int**)malloc(sizeof(sums)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = sums;
}
}
*returnSize = count;
return result;
}
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
*/
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
int *sortedNums = insertionSort(nums,numsSize);
int **result= NULL;
int count =0;
for (int i=0; i < numsSize- 3; i++) {
if (target >0 ) {
if (sortedNums[i] >= target) {
break;
}
}
else if ( target < 0){
if (sortedNums[i] >= 0) {
break;
}
}else{
if (sortedNums[i] > 0) {
break;
}
}
if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
continue;
}
int left = target - sortedNums[i];
int returnSize1 = 0;
int **aa = threeSumtarget(nums + i +1, numsSize - i-1, &returnSize1,left);
for (int j =0; j< returnSize1; j++) {
int *t = aa[j];
t=(int*)realloc(t,sizeof(int)*4);
t[3] = sortedNums[i];
if (count ==0) {
count++;
result=(int**)malloc(sizeof(t)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = t;
}
}
*returnSize = count;
return result;
}
The running time of the above algorithm on LeetCode is 44ms. The following shows that the running time on LeetCode is 4ms. The code is simpler than what I wrote, and the running time is 10 times faster than mine. The difference is not a little bit.
void Qsort(int*s,int left,int right){
if(left >= right) return ; //这一句必不可少，后面递归的终止条件
int tem = s[left];
int i = left;
int j = right;
while(i < j){
while((s[j] >= tem) && (i < j)) //从后往前比较
j--;
if(i < j) s[i] = s[j];
while((s[i] <= tem) && (i < j)) //从前往后比较
i++;
if(i < j) s[j] = s[i];
}
s[i] = tem; //把基准放到位置上
Qsort(s,left,i-1);
Qsort(s,j+1,right);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
Qsort(nums,0,numsSize-1);
int **res = NULL;
*returnSize = 0;
if ((nums == NULL) || (numsSize < 4))
return NULL;
res = malloc(sizeof(int *) * numsSize * (numsSize - 1) * (numsSize - 2) * (numsSize - 3) / 24);
int i,j,m = 0;
for(i = 0;i < numsSize - 3;i++){
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)
break;
// check [a,x,x,x] maxinum
if(nums[i]+nums[numsSize-3]+nums[numsSize-2]+nums[numsSize-1] < target)
continue;
for(j = i + 1;j < numsSize - 2;j++){
// check [a,b,x,x] mininu
if(nums[i]+nums[j]+nums[j+1]+nums[j+2] > target)
break;
// check [a,b,x,x] maxinum
if(nums[i]+nums[j]+nums[numsSize-2]+nums[numsSize-1] < target)
continue;
int left = j + 1;
int right = numsSize - 1;
while(left < right){
if((nums[i] + nums[j] + nums[left] + nums[right]) == target){
res[*returnSize] = (int*)malloc(sizeof(int)*4);
res[*returnSize][0] = nums[i];
res[*returnSize][1] = nums[j];
res[*returnSize][2] = nums[left];
res[*returnSize][3] = nums[right];
(*returnSize)++;
while(left<right && nums[left] == nums[left+1])
left++;
while(left<right && nums[right] == nums[right-1])
right--;
left++;
right--;
}
else if((nums[i] + nums[j] + nums[left] + nums[right]) > target) //右指针左移
right--;
else
left++; //左指针右移
}
while(j < numsSize-2 && nums[j+1] == nums[j])
j++;
}
while(i < numsSize - 3 && nums[i+1] == nums[i])
i++;
}
//*returnSize = m;
return res;
}
Review
SEC Sues Elon Musk for Fraud, Seeks Removal From TeslaSEC
U.S. securities regulators on Thursday sought to force Tesla Inc Chief Executive Elon Musk out of the company he helped get off the ground about 15 years ago, alleging he misled shareholders when he tweeted he had funding for what would have been the largest-ever corporate buyout.
U.S. securities regulators on Thursday sought to force Tesla Inc. TSLA Chief Executive Elon Musk out of the company he co-founded almost 15 years ago, accusing him of misleading shareholders when he tweeted that he had secured financing for a going-private deal. The deal was expected to be the largest going private deal in history.
The filing by the SEC in federal court in Manhattan threatens to deal a severe blow to the Palo Alto, Calif., electric car maker. Its brand and Mr. Musk are closely intertwined, and analysts have said the company’s roughly $50 billion market value is driven by Wall Street’s appreciation for Mr. Musk’s vision and skill as an innovator.
The U.S. Securities and Exchange Commission (SEC) filed the lawsuit in Manhattan federal court. The case is likely to be a heavy blow to the Palo Alto, California-based electric car maker. The Tesla brand is inseparable from Musk’s name. Analysts have said that behind the company’s market value of approximately US$50 billion is Wall Street’s appreciation of Musk’s vision and technology as an innovator.
Tesla wasn’t named in the suit as a defendant, but the SEC is seeking to bar Mr. Musk, Tesla’s largest shareholder and its top executive, from serving as an officer or director of any U.S. public company. Tesla shares, which have been under intense pressure amid questions about the firm’s financial strength and Mr. Musk’s behavior, tumbled 9.9% to $277 in after-hours trading Thursday on Nasdaq.
Tesla is not named as a defendant in the case, but the SEC is seeking to bar Musk from serving as an officer or director of any U.S. public company. Musk is currently Tesla’s largest shareholder and CEO. Faced with questions about Tesla’s financial strength and Musk’s personal behavior, the company’s stock price has been under tremendous pressure. The stock fell 9.9% to $277 in after-hours trading on the Nasdaq market on Thursday.
“This unjustified action by the SEC leaves me deeply saddened and disappointed,” Mr. Musk said in a statement. “I have always taken action in the best interests of truth, transparency and investors. Integrity is the most important value in my life and the facts will show I never compromised this in any way.”
Musk said in a statement: “This unreasonable action by the SEC makes me very sad and disappointed. I always try my best to uphold the principles of truth and transparency and safeguard the interests of shareholders. Integrity is the value I value most, and facts will prove that I have never done anything that violates integrity.”
“I am deeply saddened and disappointed by this improper conduct by the SEC,” Musk said in a statement. “I have always acted in the best interests of truth, transparency, and investors. Integrity is the most important value in my life, and facts will prove that I have never compromised it in any way.”
TIPS:
The previous article introduced the method of using CAGradientLayer to implement gradient colors. In addition to using CAGradientLayer to implement gradient colors, you can also use CGGradientRef and Core Image. However, when using CGGradientRef and Core Image to implement gradient colors, you need to call it in the drawRect: method. There is a very good explanation on the use of Core Graphics and Core Image: http://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image CGGradientRef: The following code should be written in drawRect:
UIColor *_inputColor0 = [UIColor yellowColor];
UIColor *_inputColor1 = [UIColor blueColor];
CGPoint _inputPoint0 = CGPointMake(0, 0);
CGPoint _inputPoint1 = CGPointMake(0, 1);
//方法1
CGContextRef context = UIGraphicsGetCurrentContext();
UIGraphicsPushContext(context);
CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
CGFloat locations[] = {0,1};
NSArray *colors = @[(__bridge id)_inputColor0.CGColor, (__bridge id)_inputColor1.CGColor];
CGGradientRef gradient = CGGradientCreateWithColors(colorSpace, (CFArrayRef) colors, locations);
CGColorSpaceRelease(colorSpace);
CGPoint startPoint = (CGPoint){rect.size.width * _inputPoint0.x, rect.size.height * _inputPoint0.y};
CGPoint endPoint = (CGPoint){rect.size.width * _inputPoint1.x, rect.size.height * _inputPoint1.y};
CGContextDrawLinearGradient(context, gradient, startPoint, endPoint, 0);
CGGradientRelease(gradient);
UIGraphicsPopContext();
UIColor *_inputColor0 = [UIColor yellowColor];
UIColor *_inputColor1 = [UIColor blueColor];
CGPoint _inputPoint0 = CGPointMake(0, 0);
CGPoint _inputPoint1 = CGPointMake(0, 1);
CIFilter *ciFilter = [CIFilter filterWithName:@"CILinearGradient"];
CIVector *vector0 = [CIVector vectorWithX:rect.size.width * _inputPoint0.x Y:rect.size.height * (1 - _inputPoint0.y)];
CIVector *vector1 = [CIVector vectorWithX:rect.size.width * _inputPoint1.x Y:rect.size.height * (1 - _inputPoint1.y)];
[ciFilter setValue:vector0 forKey:@"inputPoint0"];
[ciFilter setValue:vector1 forKey:@"inputPoint1"];
[ciFilter setValue:[CIColor colorWithCGColor:_inputColor0.CGColor] forKey:@"inputColor0"];
[ciFilter setValue:[CIColor colorWithCGColor:_inputColor1.CGColor] forKey:@"inputColor1"];
CIImage *ciImage = ciFilter.outputImage;
CIContext *con = [CIContext contextWithOptions:nil];
CGImageRef resultCGImage = [con createCGImage:ciImage fromRect:rect];
UIImage *resultUIImage = [UIImage imageWithCGImage:resultCGImage];
CGImageRelease(resultCGImage);
[resultUIImage drawInRect:rect];
效果如下图
UIColor *_inputColor0 = [UIColor yellowColor];
UIColor *_inputColor1 = [UIColor blueColor];
CGPoint _inputPoint0 = CGPointMake(0, 0);
CGPoint _inputPoint1 = CGPointMake(0, 1);
CAGradientLayer *layer = [CAGradientLayer new];
layer.colors = @[(__bridge id)_inputColor0.CGColor, (__bridge id)_inputColor1.CGColor];
layer.startPoint = _inputPoint0;
layer.endPoint = _inputPoint1;
layer.frame = view.bounds;
[view.layer addSublayer:layer];
It can be seen that the implementation methods are different, but the effects are still different. It is also worth mentioning that UIBezierPath and CAShapeLayer can be combined to do some animations.
Reference article: http://www.cnblogs.com/YouXianMing/p/3793913.html https://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image
Share:
There is a question that I have never understood. Most of the electricity we use now (70%) comes from thermal power generation. The fuel for thermal power generation comes from oil and coal. There are a lot of losses in the thermal power generation process.
For example: 1kg of oil, if used directly to boil water, can boil 20kg of water. If you first use 1kg of oil to generate electricity and then use electricity to boil water, you may only be able to boil 10kg of water.
In this case, why do we use electric cars? For the same distance of 1km, the actual fuel consumption of electric vehicles is actually higher. The use of electric vehicles actually increases pollution, but the pollution occurs in power plants and is transferred.
So why do we use electric cars or other devices that use electricity when they could use oil?
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。