LeetCode刷题第一天——1two sum 2 AddTwoList

曾经终败给现在 2021-10-26 15:12 320阅读 0赞

1.Leetcode 1

给定数组和目标，问：数组中的文字哪两个能组成这个目标。且规定只有一种可能（人为简化条件）

注意点：

LeetCode出于简化编程的思路，只让写solution类即可，但是本地调试需要自己写main函数。在main函数中新建一个变量 Solution s

通过s调用相关函数或者变量，这体现了一种封装的思想

进步：

复习了C语言中类的用法

迭代器的用法

容器vector的用法，以及对vector添加数据的操作

代码：

1 //Leetcode #1: twoSum
     2 //题目描述：给定一个数组和另外一个数target，
     3 //若数组中某两个数的和等于target，输出这两个数的下标。
     4 //假设只有一个解，并且同一个数不能重复使用。
     5 
     6 #include<stdio.h>
     7 #include<iostream>
     8 #include<vector>
     9 
    10 using namespace std;
    11 
    12 class Solution {
    13 public:
    14     vector<int> twoSum(vector<int>& nums, int target) {
    15         vector<int> v(2);
    16         for(int i = 0; i<nums.size(); i++)
    17         {
    18             for(int j = i + 1; j<nums.size(); j++)
    19             {
    20                 if(nums[i] + nums[j] == target)
    21                 {
    22                     v[0] = i;
    23                     v[1] = j;
    24                     return v;
    25                 }
    26 
    27             }
    28         }
    29        return v;
    30     }
    31 };
    32 
    33 int main()
    34 {
    35     Solution s;//initializing object s
    36     vector<int> v1;//dynamic array container
    37     vector<int> v2;
    38     vector<int>::iterator ite;//迭代器iterator
    39 
    40     v1.push_back(0);//add to the vector end
    41     v1.push_back(1);
    42     v1.push_back(2);
    43     v1.push_back(3);
    44 
    45     int target = 5;
    46     v2 = s.twoSum(v1, target);
    47 
    48     for(int i = 0; i < v2.size(); i++)
    49     {
    50         cout<<v2[i]<<endl;
    51     }
    52 
    53     return 0;
    54 }

//Leetcode \#1: twoSum//题目描述：给定一个数组和另外一个数target，//若数组中某两个数的和等于target，输出这两个数的下标。//假设只有一个解，并且同一个数不能重复使用。  
\#include<stdio.h>\#include<iostream>\#include<vector>  
using namespace std;  
class Solution \{ public:    vector<int> twoSum(vector<int>& nums, int target) \{         vector<int> v(2);        for(int i = 0; i<nums.size(); i++)        \{             for(int j = i + 1; j<nums.size(); j++)            \{                 if(nums\[i\] + nums\[j\] == target)                \{                     v\[0\] = i;                    v\[1\] = j;                    return v;                \}  
            \}        \}       return v;    \}\};  
int main()\{     Solution s;//initializing object s    vector<int> v1;//dynamic array container    vector<int> v2;    vector<int>::iterator ite;//迭代器iterator  
    v1.push\_back(0);//add to the vector end    v1.push\_back(1);    v1.push\_back(2);    v1.push\_back(3);  
    int target = 5;    v2 = s.twoSum(v1, target);  
    for(int i = 0; i < v2.size(); i++)    \{         cout<<v2\[i\]<<endl;    \}  
    return 0;\}

2.考察链表，两个链表反向输入，进行加和，结果也用链表倒序输出

1 class Solution {
     2 public:
     3     ListNode *addTwoNumbers(ListNode *l1,ListNode *l2) {
     4         if(l1==NULL)
     5             return l2;
     6         if(l2==NULL)
     7             return l1;
     8 
     9         ListNode *result = NULL;
    10         ListNode *sum = NULL;
    11         int val=0,carry=0;
    12         while(l1!=NULL||l2!=NULL)
    13         {
    14             val=carry;
    15             if(l1!=NULL)
    16                 val+=l1->val;
    17             if(l2!=NULL)
    18                 val+=l2->val;
    19 
    20             carry=val/10;
    21             val-=carry*10;
    22 
    23             if(sum==NULL)
    24             {
    25                 sum=new ListNode(val);
    26                 result=sum;
    27             }
    28             else
    29             {
    30                 sum->next=new ListNode(val);
    31                 sum=sum->next;
    32             }
    33 
    34             if(l1!=NULL)
    35                 l1=l1->next;
    36             if(l2!=NULL)
    37                 l2=l2->next;
    38 
    39 
    40         }
    41         if(carry!=0)
    42         {
    43             sum->next=new ListNode(carry);
    44         }
    45         return result;
    46     }
    47 };

二刷：

BONUS：

1.python \[::-1\] means reverse order

\[::-1\] use in string list and so on.int cann't use this conversion

use str()

2.nullptr-->C11 NULL-->c/c++ None-->python distinguish between different expression

3.Use of quotation marks

(1)"" '' all can represent string,The idea is for easier to use

if string contain's ' or " we use another represent way to avoid the use of escape character(转义字符)

""" three quotations means annotation&multi-line sentence needn't line seperator(换行符)

eg:

str1="""
    I 
    am the king
    of the world
    """
    
    print(str1)

tmp=[1,2,3,4,5,6]
    print (tmp[::-1])[::-1]

# Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
            """initial means when we use ListNode(x) refer to
             this function,in parentheses has variable x so
             each time we initial this need add x"""
            self.val = x
            self.next = None
    
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            # pay attention to the type illustration
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            # initial string
            num1=""
            num2=""
            while l1:
                # be sensitive to variable types val->int num1->string,use str type conversion
                num1+=str(l1.val)
                l1=l1.next
            while l2:
                # be sensitive to variable types val->int num1->string,use str type conversion
                num2+=str(l2.val)
                l2=l2.next
            # only string can use [::-1]
            num=str(int(num1[::-1])+int(num2[::-1]))[::-1]
            # initial need x
            res=ListNode(num[0])
            # one to loop other refer head
            head=res
            for i in range(1,len(num)):
                node=ListNode(num[i])
                head.next=node
                head=head.next
            return res
    
    solu=Solution()
    l1=ListNode(2)
    
    l2=ListNode(4)
    l1.next=l2
    
    l3=ListNode(3)
    l2.next=l3
    l4=ListNode(5)
    
    l5=ListNode(6)
    l4.next=l5
    
    l6=ListNode(4)
    l5.next=l6
    l=solu.addTwoNumbers(l1,l4)
    while l:
        print(l.val)
        l=l.next

good website:

[https://blog.csdn.net/fuxuemingzhu/article/details/79379626][https_blog.csdn.net_fuxuemingzhu_article_details_79379626]

use carry store carry bit

# Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
            """initial means when we use ListNode(x) refer to
             this function,in parentheses has variable x so
             each time we initial this need add x"""
            self.val = x
            self.next = None
    
    
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            # first begin with 0,end return head.next escape the 0
            res=ListNode(0)
            head=res
            carry=0
            while l1 and l2:
                """not only add two value,carry 
                need to be handle together,must add together 
                firstly,seperate will cause problem"""
                ans=l1.val+l2.val+carry
                carry = 1 if ans>=10 else 0
                # res.next is also ListCode type need use ListCode initialize
                res.next=ListNode(ans%10)
                # update
                res=res.next
                l1,l2=l1.next,l2.next
            l=l1 if l1 else l2
            while l:
                ans=l.val+carry
                carry=1 if ans>=10 else 0
                res.next=ListNode(ans%10)
                res=res.next
                l=l.next
            # consider the situation still need carry bit,as said before add only carry bit 1
            if carry:
                res.next=ListNode(1)
            return head.next
    
    
    solu=Solution()
    l1=ListNode(2)
    
    l2=ListNode(4)
    l1.next=l2
    
    l3=ListNode(3)
    l2.next=l3
    l4=ListNode(5)
    
    l5=ListNode(6)
    l4.next=l5
    
    l6=ListNode(4)
    l5.next=l6
    l=solu.addTwoNumbers(l1,l4)
    while l:
        print(l.val)
        l=l.next

转载于:https://www.cnblogs.com/Marigolci/p/10986670.html

[https_blog.csdn.net_fuxuemingzhu_article_details_79379626]: https://blog.csdn.net/fuxuemingzhu/article/details/79379626