ARTS #028
ARTS #028
ARTS 028
This is article 28
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.
Algorihm algorithm question
2. Add two numbers
Difficulty: Medium
Given two non-empty linked lists to represent two non-negative integers. Among them, their respective digits are stored in reverse order, and each of their nodes can only store one digit.
If, we add these two numbers, a new linked list will be returned representing their sum.
You can assume that neither number will start with 0 except for the number 0.
Example:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
The difficulty of this question is medium. The main difficulty lies in considering different cases. My first answer is as follows:
Solution
Language: C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* root = NULL;//(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p = NULL;
int sum = 0;
while (l1 != NULL || l2 != NULL ) {
if (l1 != NULL && l2 != NULL ) {
sum = l1->val + l2->val + sum / 10;
l1 = l1->next;
l2 = l2->next;
}
else if (l1 != NULL){
sum = l1->val+ sum / 10;
l1 = l1->next;
}
else if (l2 != NULL){
sum = l2->val + sum / 10;
l2 = l2->next;
}
if (p == NULL) {
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = sum % 10;
p->next = NULL;
root = p;
}
else{
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = sum % 10;
temp->next = NULL;
p->next = temp;
p=temp;
}
}
return root;
}
The above logic is also very clear and simple, but when the input is 5 or 5, the result is wrong. Because I gave the situation less thought.
Final result:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* root = NULL;//(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p = NULL;
int sum = 0;
while (l1 != NULL || l2 != NULL ) {
int flag = 0;
if (l1 != NULL && l2 != NULL ) {
sum = l1->val + l2->val + sum / 10;
l1 = l1->next;
l2 = l2->next;
if (l1 == NULL && l2 == NULL) {
flag = 1;
}
}
else if (l1 != NULL){
sum = l1->val+ sum / 10;
l1 = l1->next;
if (l1 == NULL) {
flag = 1;
}
}
else if (l2 != NULL){
sum = l2->val + sum / 10;
l2 = l2->next;
if (l2 == NULL) {
flag = 1;
}
}
if (p == NULL) {
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = sum % 10;
p->next = NULL;
root = p;
}
else{
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = sum % 10;
temp->next = NULL;
p->next = temp;
p=temp;
}
if (flag ==1 && sum >=10) {
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = sum / 10;
temp->next = NULL;
p->next = temp;
p=temp;
}
}
return root;
}
The result of the above operation is:
Runtime: 40 ms, faster than 10.93% of C online submissions for Add Two Numbers.
Memory Usage: 17.7 MB, less than 55.74% of C online submissions for Add Two Numbers.
The following submission record has a running time of 16ms, currently ranked first:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* recursiveAddTwoNumbers(struct ListNode* l1, struct ListNode* l2, int carry);
struct ListNode* recursiveFinishAdd(struct ListNode* l, int carry);
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
return recursiveAddTwoNumbers(l1, l2, 0);
}
struct ListNode* recursiveAddTwoNumbers(struct ListNode* l1, struct ListNode* l2, int carry) {
if(l1 == NULL) return recursiveFinishAdd(l2, carry);
if(l2 == NULL) return recursiveFinishAdd(l1, carry);
int val = l1->val + l2->val + carry;
struct ListNode *next = recursiveAddTwoNumbers(l1->next, l2->next, val/10);
struct ListNode *node = malloc(sizeof(struct ListNode));
node->val = val%10;
node->next = next;
return node;
}
struct ListNode* recursiveFinishAdd(struct ListNode* l, int carry) {
if(l == NULL) {
if(carry == 0) return NULL;
struct ListNode *node = malloc(sizeof(struct ListNode));
node->val = carry;
node->next = NULL;
return node;
}
int val = l->val + carry;
struct ListNode *next = recursiveFinishAdd(l->next, val/10);
struct ListNode *node = malloc(sizeof(struct ListNode));
node->val = val%10;
node->next = next;
return node;
}
But I ran it and the results are as follows, so the test environment is also changing, and the running time of the same code is also changing.
Runtime: 32 ms, faster than 46.07% of C online submissions for Add Two Numbers.
Memory Usage: 18.2 MB, less than 5.07% of C online submissions for Add Two Numbers.
3. The longest substring without repeated characters Copy for Markdown
Difficulty: Medium
Given a string, please find the length of the longest substring that does not contain repeated characters.
Example 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
Example 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
Example 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Solution
Language: C
My answer is as follows:
//滑动窗口
int lengthOfLongestSubstring(char* s) {
int maxLength = 0;
int strLength = strlen(s);
int leftP = 0;
int sublength = 0;
for(int i = 0; i < strLength; i++){
int flag = 0;
for(int j = leftP; j < i; j++){
if (s[j]== s[i]) {
flag =1;
leftP = j+1;
sublength = i - j;
break;
}
}
if (flag ==0){
sublength++;
}
if(sublength > maxLength) {
maxLength = sublength;
}
}
if(sublength > maxLength) {
maxLength = sublength;
}
return maxLength;
}
The following is an example that takes 8 ms to execute, but I ran it and the execution time is the same as my code (the following is the execution time of my code)
int lengthOfLongestSubstring(char* s) {
int maxlen = 0,currlen = 0;
int table[128], i, j, start = 0;
memset(table, 0, sizeof(table));
for (i = 0; s[i] != '\0'; ++i){
int num = ++table[s[i]];
if( num == 2 ){
if (currlen > maxlen){
maxlen = currlen;
}
for(j = start; j < i; ++j){
if (s[j] == s[i]){
table[s[j]] = 1;
start = j+1;
break;
}else{
--currlen;
table[s[j]] = 0;
}
}
}else{
++currlen;
}
}
if (currlen > maxlen){
maxlen = currlen;
}
return maxlen;
}
English version: sample 8 ms submission, the idea of this implementation is
int lengthOfLongestSubstring(char* s)
{
int len=0;
char *end=s,*temp;
char* addressTable[128]={NULL};
while(*end){
temp = addressTable[*end];
addressTable[*end]=end;
if(temp>=s){
len=end-s>len?end-s:len;
s = temp+1;
}
end++;
}
len=end-s>len?end-s:len;
return len;
}
4. Find the median of two ordered arrays
Difficulty: Difficulty
Given two ordered arrays nums1 and nums2 of size m and n.
Please find the median of these two ordered arrays, and the time complexity of the algorithm is required to be O(log(m + n)).
You can assume that nums1 and nums2 will not be empty at the same time.
Example 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
Solution
Language: C
Merge arrays first, then calculate
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int sumSize = nums1Size + nums2Size;
int *sum = (int*)malloc(sizeof(int) * sumSize);
int loop1 = 0;
int loop2 = 0;
for (int i =0; i< sumSize; i++) {//合并数组
if (loop1>=nums1Size) {
for (int j = i; j < sumSize; j++) {
sum[j] = nums2[loop2++];
}
break;
}
if (loop2>=nums2Size) {
for (int j = i; j < sumSize; j++) {
sum[j] = nums1[loop1++];
}
break;
}
int r1 = nums1[loop1];
int r2 = nums2[loop2];
if (r1 < r2) {
sum[i] = r1;
loop1++;
}
else{
sum[i] = r2;
loop2++;
}
}
//计算最终结果
double r = 0;
if (sumSize % 2 == 0 ) {
int l1 = sumSize / 2;
int l2 = l1 - 1;
r = ((double)(sum[l1] + sum[l2]))/2;
}
else{
int l = sumSize / 2;
r = sum[l];
}
return r;
}
Review
This article mainly talks about what is your real enemy when starting a business and making products. https://dandan2009.github.io/2019/03/20/competitors-are-not-the-enemy/
Tips
When git submits code, there is author information, such as user name and email address. However, if the author information is accidentally mistaken or does not comply with the specifications, how should I modify it? The following script can help you modify the submitted author information. Note that here is all the submitted author information that has been modified. When using it, be careful not to change other people’s submissions to yours.
#!/bin/sh
git filter-branch --env-filter '
an="$GIT_AUTHOR_NAME"
am="$GIT_AUTHOR_EMAIL"
cn="$GIT_COMMITTER_NAME"
cm="$GIT_COMMITTER_EMAIL"
if [ "$GIT_COMMITTER_EMAIL" = "要修改的@邮箱地址.com" ]
then
cn="想要改成的用户名"
cm="想要改成的邮箱"
fi
if [ "$GIT_AUTHOR_EMAIL" = "要修改的@邮箱地址.com" ]
then
an="想要改成的用户名"
am="想要改成的邮箱"
fi
export GIT_AUTHOR_NAME="$an"
export GIT_AUTHOR_EMAIL="$am"
export GIT_COMMITTER_NAME="$cn"
export GIT_COMMITTER_EMAIL="$cm"
'
After the above steps are executed, push the correct history to Github:
git push --force --tags origin 'refs/heads/*'
Note:
1 Please back up the code before executing
2 After executing git push --force --tags origin 'refs/heads/*', delete the existing local warehouse and clone it again.
When you execute the above script again in the same warehouse, you will be prompted:
Cannot create a new backup.
A previous backup already exists in refs/original/
Force overwriting the backup with -f
Just execute the following command
git update-ref -d refs/original/refs/heads/master
Share
The following content is shared by a netizen in a WeChat group.
This case is very simple and interesting, but the demand is real and strong. The original author’s sharing has brought us a lot of inspiration for pain point discovery and product development. Basic situation
- Product name: Salem Software
- Product features: Spanish version of the Bible iOS App
- Installation volume: more than 1.3 million
- Monthly income: more than $10,000 4 inspirations brought to us by the product from 0 to 1
- The author understands Spanish, so he made a Spanish version of the Bible as a Jos app, and a Spanish audio version of the app was released after a period of time.
- He mentioned a way to quickly find real needs: flip through the App Store list, look for apps with poor reviews from top to bottom, and then copy them to other language models. Because these needs have been confirmed and the model has been successful, you only need to change some new variables to make profits quickly, such as changing language variables, changing channel variables, etc.
- In addition to making a text version of the Spanish Bible, the author mentioned that a very key operation for his income growth was to make an audio version of these free contents, which greatly increased his passive income. The inspiration for us is that in addition to variables such as language and channels, media form is also a variable. Text, pictures, audio, and video. Each type has its corresponding demand. We need to look for and discover gaps in the market.
- From this case, we can also get an inspiration: find works in the public copyright field, reprocess and re-produce them to make them more in line with the needs of the public, such as Water Margin and Dream of Red Mansions, re-process and re-distribute them
It is mentioned here to make your own APP. If you want to develop independently but have no idea, you can try this.
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。