2020-09-13-数据结构与算法

Record

Posted by Jocelyn on September 13, 2020

2020-09-13 recording.

[TOC]

两数之和

解题思路: 题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

作者:chenlele 链接:https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-gpe3dbjds1/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

//
//  两数之和.cpp
//  leetCode
//
//  Created by ShangYueying on 2020/9/13.
//  Copyright © 2020 ShangYueying. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <map>
using namespace std;
namespace twoSum
{
//暴力
//时间复杂度为O(N^2),空间复杂度为O(1)
class Solution{
public:
    vector<int> twoSum(vector<int> &nums,int target){
        vector<int> result(2);
        for (int i=0; i<nums.size()-1; i++) {
            for (int j=i+1; j<nums.size(); j++) {
                if(nums[i]+nums[j]==target)
                {
                    result[0]=i;
                    result[1]=j;
                    break;
                }
            }
        }
        return result;
    }
};

//两遍哈希表
//时间复杂度O(N),空间复杂度O(N)
class Solution1{
public:
    vector<int> twoSum(vector<int>& nums,int target){
        map<int,int> hashTable;//hash表存放数组
        vector<int> result(2,-1);//存放结果
        for (int i=0; i<nums.size(); i++)
            hashTable.insert(map<int,int>::value_type(nums[i],i));//key就是num中的元素
        for (int i =0 ; i<nums.size(); i++) {
            if(hashTable.count(target-nums[i])>0 && (hashTable[target-nums[i]]!=i)){
                result[0]=i;
                result[1]=hashTable[target-nums[i]];
                break;
            }
        }
        return result;
    }
};


//一遍哈希表
//时间复杂度O(N),空间复杂度O(N)
class Solution2{
public:
    vector<int> twoSum(vector<int>& nums,int target){
        map<int,int>hashTable;
        vector<int> result(2,-1);
        for (int i=0; i<nums.size(); i++) {
            if(hashTable.count(target-nums[i])>0){
                result[0]=hashTable[target-nums[i]] ;
                result[1]=i;
                //这两个的顺序,因为先出现的是target-nums[i],而且应该是 hashTable[target-nums[i]]
                break;
            }
            hashTable[nums[i]]=i;//map中如果没有,会自己添加key-value
        }
        return result;
    }
};

//排序+双指针
//时间复杂度为O(NlogN),空间复杂度为O(N)
//排序时间复杂度为O(NlogN)
class Solution3{
    vector<int> twoSum(vector<int>& nums,int target){
        vector<int>result;
        vector<int> tempNums(nums);
        sort(tempNums.begin(),tempNums.end());
        int n = nums.size();
        int i=0,j=n-1;
        while(i<j){
            if(tempNums[i]+tempNums[j]>target) j--;
            else if(tempNums[i]+tempNums[j]<target) i++;
            else break;
        }
        if(i<j){//为了找到 已经定位的 i,j对应的index 在 nums中的index是什么
            for (int k =0 ; k<n; k++) {
                if(i<n&&nums[k]==tempNums[i]){
                    result.push_back(k);
                    i = n;
                }
                else if(j<n&&nums[k]==tempNums[j]){
                    result.push_back(k);
                    j = n;
                }
                if(i == n && j == n) return result;//等到两个都找到,可以返回了
            }
        }
        return result;
    }
};

}


两数相加

//
//  两数相加.cpp
//  leetCode
//
//  Created by ShangYueying on 2020/9/13.
//  Copyright © 2020 ShangYueying. All rights reserved.
//

//思路:链表
//将两个链表看成是相同长度进行遍历,如果一个链表较短,则在前面补0
//对于链表问题,返回值为头结点,需要先初始化一个预先指针pre,该指针的下一个节点,指向真正的头结点head
#include <stdio.h>
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

namespace addTwo{
class Solution{
public:
    ListNode* addTwoNumbers(ListNode* l1,ListNode* l2){
        ListNode pre(-1);
        ListNode* cur = &pre;
        int sum = 0;
        int carry = false;//表示进位
        while(l1 || l2 || carry){
            sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = sum / 10;
            
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
        }
        return pre.next;
    }
};
}


无重复字符的最长子串

//
//  无重复字符的最长子串.cpp
//  leetCode
//
//  Created by ShangYueying on 2020/9/13.
//  Copyright © 2020 ShangYueying. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

namespace longestString{
//滑动窗口
//时间复杂度为O(N^2),空间复杂度为O(1)
class Solution1{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end)
        int start = 0, end = 0, length = 0, result = 0;
        int stringSize = s.size();
        while(end < stringSize)//右侧指针向右移动
        {
            char currChar = s[end];
            for (int i = start;i < end ; i++)//从start到end 查看s[end]是否出现过,如果有,更新start
            {
                if(currChar == s[i])//s[end]出现过
                {
                    start = i + 1;
                    length = end - start;
                }
            }
            end++;
            length++;
            result = max(result,length);
        }
        return result;
    }
};

//hashmap优化
//时间复杂度O(N),空间复杂度O(N)
class Solution2{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end)
        int start = 0, end = 0, length = 0,result = 0;
        int stringSize = s.size();
        unordered_map<char,int> hash;//存放的是 字符-id
        while(end < stringSize)
        {
            char currChar = s[end];
            if(hash.find(currChar) != hash.end() && hash[currChar] >= start)
            {
                start = hash[currChar] + 1;
                length = end - start;
            }
            hash[currChar] = end;//如果没有这个键值对,会创建并放进去
            end++;
            length++;
            result = max(result,length);
        }
        return result;
    }
};

//利用数组(桶)来代替hash
//时间复杂度O(N),空间复杂度O(N)
//int [26]用于表示字母 ‘A’-'Z'或者 ‘a’-'z'
//int [128]用于ASCII码
//int [256]用于扩展ASCII码
class Solution3{
    public:
    int lengthOfLongestSubstring(string s)
    {
        int start = 0, end = 0, length = 0, result = 0;
        int stringSize = s.size();
        vector<int> vec(128,-1);//桶里面 存放的是 元素的 index
        while(end < stringSize)
        {
            char currChar = s[end];
            if(vec[int(currChar)] >= start)//currChar已经在桶里面,并且index >= start,如果没有出现过,对应的为-1
            {
                start = vec[int(currChar)] + 1;
                length = end - start;
            }
            vec[int(currChar)] = end;//存在更新的情况;出现过,就被更新为end
            
            end++;
            length++;
            result = max(result,length);
        }
        return result;
    }
};
}