leetcode hot 100(刷题篇1)(1/3/2/206/20/19/5/21/34/53)_leetcode hot100刷题顺序

目录

1、leetcode1两数之和

2、leetcode3无重复字符的最长子串

3、leetcode2两数相加

4、leetcode206反转链表

5、leetcode20有效的括号

6、leetcode19删除链表的倒数第 N 个结点

7、leetcode5最长回文子串

8、leetcode21合并两个有序链表

9、leetcode34在排序数组中查找元素的第一个和最后一个位置

10、leetcode53最大子数组和

---

1、leetcode1两数之和

/**
    时间复杂度 O(N²)
    实现思路：我通过俩个for循环，去枚举
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}
 
/**
    哈希表的时间复杂度O(1)
    整体的时间复杂度是O(N)
    实现思路： hashtable.containsKey(target - nums[i])
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

2、leetcode3无重复字符的最长子串

/**
    1）当前字符上次的位置
    2）i-1位置往左推的距离
 */
class Solution {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] str = s.toCharArray();
        // ASCII 只有 0~255
        // map[i] = v  i这个ascii码的字符，上次出现在V位置
        int[] map = new int[256];
        for (int i = 0; i < 256; i++) {
            map[i] = -1;
        }
        map[str[0]] = 0;
        int N = str.length;
        int ans = 1;       // 最少长度 1
        int pre = 1;       // 上一个位置，向左推了多长
        for (int i = 1; i < N; i++) {
            pre = Math.min(i - map[str[i]], pre + 1);
            ans = Math.max(ans, pre);
            map[str[i]] = i;
        }
        return ans;
    }
}

3、leetcode2两数相加

 /**
    时间复杂度：O(max(m,n))
  */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;  //初始化
        ListNode tail = null;