lalala
首页
时间轴
标签
分类
友链
关于
娱乐
清单
avatar
文章
80
标签
61
分类
16
首页
时间轴
标签
分类
友链
关于
娱乐
清单
目录
leetcode1
阅读量:

2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *answer = new ListNode(0);
        ListNode *curr= answer;
        int sum=0;
        int carry=0;
        while(l1!=NULL||l2!=NULL)
        {
            int x=(l1!=NULL)?l1->val:0;
            int y=(l2!=NULL)?l2->val:0;
            sum=x+y+carry;
            curr->next= new ListNode(sum%10);
            curr=curr->next;
            carry=sum/10;
            if(l1!=NULL)
                l1=l1->next;
             if(l2!=NULL)
                l2=l2->next;
        }
          if (carry > 0)
            curr->next = new ListNode(carry);
        return answer->next;
    }
};

9.回文数

c++
1
2
3
4
5
6
7
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        return str(x)==str(x)[::-1]

11盛水最多的容器

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i=0,j=height.size()-1;
        int result=0;
        while(i<j)
        {
            result=max(result,(j-i)*min(height[i],height[j]));
            if(height[i]>=height[j])
                j--;
             else
                i++;
        }
        return result;
    }
};

14.最长公共前缀
方法一：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
     string longestCommonPrefix(vector<string>& strs) {
        if (strs.size()==0) return ""; 
        string str;
        for (int i=0;i<strs[0].size();i++){
           for(int k=0;k<strs.size()-1;k++)
           {
               if (strs[k][i]!=strs[k+1][i])
               {
                   return str;
               }
           }
            str=str+strs[0][i];
        }
        return str;
    }

};

方法二：

c++
1
2
3
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
         return os.path.commonprefix(strs)

方法三：

c++
1
2
3
4
5
6
7
8
9
class Solution:
       def longestCommonPrefix(self, strs):
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1

14.三数之和

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target;
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
             if ((target = nums[i]) > 0) break;
             if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (nums[l] + nums[r] + target < 0) ++l;
                else if (nums[l] + nums[r] + target > 0) --r;
                else {
                    ans.push_back({target, nums[l], nums[r]});
                    ++l, --r;
                    while (l < r && nums[l] == nums[l - 1]) ++l;
                    while (l < r && nums[r] == nums[r + 1]) --r;
                }
            }
        }
        return ans; 
    }
};

16最近接的三数值和

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution { 
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int a=nums[0]+nums[1]+nums[2];
        for(int i=0;i<nums.size()-2;i++)
        {
            if(i>0&&nums[i]==nums[i-1])continue;
            int l=i+1;
            int r=nums.size()-1;
            while(l<r)
            {
                int sum=nums[i]+nums[l]+nums[r];
                if(abs(sum-target)<abs(a-target))
                    a=sum;
                if(sum>target)
                    r--;
                else if(sum<target)
                    l++;
                else if(sum==target)
                    return sum;
            }
        }
        return a;
        
    }
};

19删除链表倒数第N个节点
快慢指针，相差n

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
         ListNode*p1=head;
         ListNode*p2=head;
        while(n!=0)
        {
            p1=p1->next;
            n--; 
        }
        if(p1==NULL)return head->next;
        while((p1->next)!=NULL)
        {
             p1=p1->next;
             p2=p2->next;
             
        }
        p2->next=p2->next->next;
        return head;
    }
};

20.有效括号

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isValid(string s) 
    {
      stack<char>a;
      if(s.size()%2!=0)return 0;
      else{
          for(auto i:s)
            {
              if(i=='['||i=='{'||i=='(')
                  a.push(i);
              else if(a.size()==0&&(i==']'||i=='}'||i==')'))   
                  return 0;
              else if((i==']'&&a.top()!='[')||(i=='}'&&a.top()!='{')||(i==')'&&a.top()!='('))
                  return 0;
              else 
                  a.pop();
             }     
      
           }
        if(a.size()!=0)
          return 0;
      else
          return 1;
    }
};

26删除排序数组中的重复项
双指针

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int i=0;
        for(int j=0;j<nums.size();j++)
            if(nums[i]!=nums[j])
            {
                nums[i+1]=nums[j];
                i++;
            }
          return i+1;        
    }
};

28实现strSTR()

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        if (needle.size() > haystack.size()) return -1;
         if (needle==haystack)return 0;
        int len=needle.size();
        for(int i=0;i<haystack.size()-len+1;i++)
        {
            if(needle==haystack.substr(i,len))return i;
        }   
        return -1;
    }
};

88.合并两个有序数组
从后向前插入数。

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1;
        int j=n-1;
        int len=m+n-1;
        while(i>=0&&j>=0)
        {
            if(nums1[i]>nums2[j])
                nums1[len--]=nums1[i--];
            else
                nums1[len--]=nums2[j--];
        }
        while(j>=0)
            nums1[len--]=nums2[j--];
    }
};
  1. 颜色分类
    方法一：
c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void sortColors(vector<int>& nums) {
      int a=0,b=0,c=0;
        for(int i=0;i<nums.size();i++)
        {
          if(nums[i]==0)
            a++;
           if(nums[i]==1)
            b++;
           if(nums[i]==2)
            c++;
        }
      int j=0;
      for(;j<a;j++)
        nums[j]=0;
      for(;j<b+a;j++)
        nums[j]=1;
      for(;j<a+b+c;j++)
        nums[j]=2;
    }
};

方法二：荷兰国旗问题：
https://en.wikipedia.org/wiki/Dutch_national_flag_problem

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0=0,p2=nums.size()-1;
        int cur=0;
        while(cur<=p2)
        {
            if(nums[cur]==2)
            {
                swap(nums[p2],nums[cur]);
                p2--;
            }
            else if(nums[cur]==1)
                cur++;
            else if(nums[cur]==0)
            {
                swap(nums[p0],nums[cur]);
                p0++,cur++;
            }
        }

    }
};

17.电话号码的字母组合

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
   map<char,string> mp={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string>res;
    void DFS(string cur,string next_word)
    {
        if(next_word.size()==0)
            res.push_back(cur);
        else
        {
            char digit=next_word[0];
            string letters=mp[digit];
            for(int i=0;i<letters.size();i++)
            {
                cur=cur+letters.substr(i,1);
                next_word=next_word.substr(1);
                DFS(cur,next_word);
            }
        }
    }
      vector<string> letterCombinations(string digits){
          if(digits.size()==0)
              return {};
          else
              DFS("",digits);
          return res;
      }
};
文章作者: Sunxin
文章链接: https://sunxin18.github.io/2019/07/31/leetcode1/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lalala！
打赏
  • 微信
    微信
  • 支付宝
    支付宝
评论
繁