ARTS 028
这是第28篇
ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。
Algorihm 算法题
2. 两数相加
Difficulty: 中等
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
这道题难度是中等，其主要的难点在于考虑到不同的case，我的第一次解答如下：
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;
}
上面的逻辑也很清楚简单，但是在输入为 5 、5的时候结果是错的。因为少考虑了一下情况。
最终结果：
/**
* 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;
}
上面的运行结果是:
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.
下面这个提交记录里面运行时间16ms，目前第一：
/**
* 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;
}
但是我运行了一下结果如下，所以测试环境也是在变化的，同一份代码的运行时间也是在变的。
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. 无重复字符的最长子串Copy for Markdown
Difficulty: 中等
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Solution
Language: C
我的解答如下：
//滑动窗口
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;
}
下面这个是执行用时为 8 ms 的范例，但是我运行了一下，执行时间和我的代码一样(下面是我的代码的执行时间)
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;
}
英文版：sample 8 ms submission，这个实现的思路是
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. 寻找两个有序数组的中位数
Difficulty: 困难
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
Solution
Language: C
先合并数组，然后再计算
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
这篇文章主要讲了创业做产品时什么才是你真正的敌人 https://dandan2009.github.io/2019/03/20/competitors-are-not-the-enemy/
Tips
git提交代码的时候是有作者信息的，比如用户名 、邮箱，但是如果不小心把作者信息搞错了或者不符合规范，该怎么修改呢？ 下面这个脚本可以帮助你修改已提交的作者信息，注意这里是修改的所有的已提交作者信息，使用的时候要注意，不要把别人的提交改成了你的。
#!/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"
'
上面的脚步执行完成后，再把正确历史 push 到 Github：
git push --force --tags origin 'refs/heads/*'
注意：
1 在执行前请备份代码
2 在执行完 git push --force --tags origin 'refs/heads/*' 以后，要把已经存在的本地仓库删除，重新clone。
当你在同一个仓库中再次执行上面的脚本的时候，会提示：
Cannot create a new backup.
A previous backup already exists in refs/original/
Force overwriting the backup with -f
执行以下这个命令即可
git update-ref -d refs/original/refs/heads/master
Share
一下内容来自一位微信群一位网友的分享。
这个案例很简单也很有意思,但需求却是真实存在也很强烈的,原作者的分享给我们带来了很多痛点挖掘和产品开发上面的启发 基本情况 1.产品名称: Salem Software 2.产品功能:圣经西班牙语版本 iOS App 3.安装量:130万以上 4.月收入:$10,000以上 产品从0到1给我们带来的4个启发
1.作者懂西班牙语,于是将圣经做了一份西班牙语言版本的 Jos app,并在一段时间后出了西班牙音频版本的APP 2.他提到快速找到真实需求的一个方法:翻App Store榜单,从上到下找评价不太好的应用,然后将其复制到其他语言模式去,因为这些需求已经确认,模式已经走通,只需要改动一些新的变量,就可以很快的盈利,比如改变语言变量,改变渠道变量等 3.除了做出一份文字版本的西班牙语圣经作者提到他收入增长非常关键的一个操作就是将这些免费内容做了一份语音版的,大幅度提高了他的被动收入。给我们的启示就是除了语言、渠道等变量,媒介形式也是一种变量,文字、图片、音频、视频,任何一种式都有其对应的需求存在,我们需要是去寻找和发现市场上面的空缺 4.从这个案例,我们还可以获取到的一个启发就是:找公用版权领域的作品,进行再加工再制作,使得其更符合大众的需求,比如水浒传、红楼梦,进行再加工再传播
这里提到了自己做APP，如果你想做独立开发，却没有什么想法，可以按照这个试试。
