力扣刷题第1天

1. Two Sum

Description：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Input:
[2,7,11,15]
Output:
[0, 1]

Idea：

采用边哈希边查找的方式来判断是否有相异的2个元素即可！
时间复杂度为$ O(n) $。

Solution：

C++代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;  // 采用无序哈希表，O(1)查询
        vector<int> res;
        int tmp = 0;
        for(int i = 0, siz = nums.size(); i < siz; ++i) {
        	tmp = target - nums[i];
        	if(hash.find(tmp) != hash.end()) {
        		res = vector<int>({hash[tmp], i});
        		break;
        	} 
        	hash[nums[i]] = i;
        }
        return res;
    }
};

Java代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> mp = new HashMap<>(); //一般查询时间复杂度为O(1)
        int[] res = new int[2];
        int dig = 0;
        for(int i = 0, siz = nums.length; i < siz; ++i) {
            dig = target - nums[i];
            if(mp.containsKey(dig)) {
                res[0] = mp.get(dig);
                res[1] = i;
                break;
            }
            mp.put(nums[i], i);
        }
        return res;
    }
}

Python3代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}  # 采用字典，查询速度为O(1)，缺点是占用内存大
        for idx, val in enumerate(nums):  # 枚举字典
            other_idx = hash_map.get(target - val)
            if other_idx is not None:
                return [other_idx, idx]
            hash_map[val] = idx
        return None
        

提交结果	执行用时	内存消耗	语言
Accepted	8 ms	10 MB	Cpp
Accepted	2 ms	37.2 MB	Java
Accepted	56 ms	15.1 MB	Python3

2. Add Two Numbers

Description：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input:
(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:
7 -> 0 -> 8

Idea：

小学数学，只需按位相加，最后的进位单独处理！固定一个头指针指向答案整条链的首地址，通过另一个指针cur创建new下一个next节点，注意：要先new创建当前指针的下一个next节点再移动当前cur到下一个节点的地址处，否则将会断开整条链！

Solution：

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* head = new ListNode(0);
		ListNode* cur = head;
		int carry = 0;
		while(l1 != NULL || l2 != NULL) {
			if(l1 != NULL) {
				carry += l1 -> val;
				l1 = l1 -> next;
			} 	
			if(l2 != NULL) {
				carry += l2 -> val;
				l2 = l2 -> next;
			}
			cur -> next = new ListNode(carry % 10);
			cur = cur -> next;
			carry /= 10; 
		}
		if(carry > 0) {
			cur -> next = new ListNode(carry);
			cur = cur -> next;
		}
		return head -> next;  	   
	}
};

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int carry = 0, sum = 0;
        while(l1 != null || l2 != null) {
            ListNode now = new ListNode(0);
            if(l1 != null && l2 != null) {
                sum = l1.val + l2.val + carry;
                carry = sum / 10;
                now.val = sum % 10;
                l1 = l1.next;
                l2 = l2.next;
            } else if(l1 != null) {
                sum = l1.val + carry;
                carry = sum / 10;
                now.val = sum % 10;
                l1 = l1.next;
            } else {
                sum = l2.val + carry;
                carry = sum / 10;
                now.val = sum % 10;
                l2 = l2.next;
            }
            cur.next = now;
            cur = cur.next;
        }
        if(carry > 0) {
            ListNode now = new ListNode(carry);
            cur.next = now;
            cur = cur.next;
        }
        return head.next;
    }
}

Python3代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        cur = head
        carry = 0
        # 逻辑运算符的优先级：not > and > or
        while l1 is not None or l2 is not None:
            if l1 is not None:
                carry += l1.val
                l1 = l1.next
            if l2 is not None:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry % 10)
            cur = cur.next
            carry //= 10
        if carry > 0:
            cur.next = ListNode(carry)
            cur = cur.next
        return head.next

Submission Detail：

提交结果	执行用时	内存消耗	语言
Accepted	16 ms	44.7 MB	Cpp
Accepted	1 ms	44.7 MB	Java
Accepted	76 ms	14 MB	Python3

3. Longest Substring Without Repeating Characters

Description：

Given a string, find the length of the longest substring without repeating characters.

Example:

Input:
"abcabcbb"
"bbbbb"
"pwwkew"
Output:
3
1
3

Idea：

典型的双指针问题！以右指针为参照点，若当前右指针指向字符出现的次数大于1，则不断地移动左指针（不超过右指针），然后更新一下区间元素不重复出现的最多个数： $ max(res, ed -st + 1) $ 即可 ！时间复杂度为 $ O(n) $。
python中使用字典加优化的解法，即对于当前右指针指向的字符，若有出现相同键的旧下标值，则跳到旧下标的下一个位置！

Solution：

C++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, st = 0, ed = 0, siz = s.size();
        int* num = new int[128](); //初始化一个全为0的int数组
        while(ed < siz) {
            ++num[s[ed]];
            while(st < ed && num[s[ed]] > 1) {
                --num[s[st]];
                ++st;
            }
            res = max(res, ed - st + 1);
            ++ed;
        }
        return res;
    }
};

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, st = 0, ed = 0, siz = s.length();
        int[] nums = new int[128];
        while(ed < siz) {
            ++nums[s.charAt(ed)];
            while(st < ed && nums[s.charAt(ed)] > 1) {
                --nums[s.charAt(st)];
                ++st;
            }
            res = Math.max(res, ed - st + 1);
            ++ed;
        }
        return res;
    }
}

Python3代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res, st, hash_map = 0, 0, {}
        for idx, val in enumerate(s):  # 枚举遍历字符串
            if val in hash_map:  # 自动判断字典中是否存在一个key，存在就跳，否则不移动
                tmp = hash_map[val] + 1  # O(1) 获取值
                if tmp > st:  # 尽量用if-else语句，测试大量数据时可降低时间复杂度
                    st = tmp  # 取左指针的最大值
            num = idx - st + 1
            if num > res:
                res = num
            hash_map[val] = idx
        return res
        

Submission Detail：

提交结果	执行用时	内存消耗	语言
Accepted	8 ms	9.9 MB	Cpp
Accepted	3 ms	35.9 MB	Java
Accepted	56 ms	14.1 MB	Python3