每周算法（week2）【leetcode11~30】

前言

本该两周完成的30道算法题没想到5天就完成了，接下来继续刷算法，保持手感，对不熟悉的基础算法二分、搜索还得继续练。

leetcode 编号	完成时间	复习时间
11. 盛水最多的容器	2024-07-02
12. 整数转罗马数字	2024-07-02
13. 罗马数字转整数	2024-07-02
14. 最长公共前缀	2024-07-02
15. 三数之和	2024-07-02
16、最接近的三数之和	2024-07-03
17、电话号码的字母组合	2024-07-03
18、四数之和	2024-07-03
19、删除链表倒数第N个节点	2024-07-03
20、有效的括号	2024-07-04
21、合并两个有序的链表	2024-07-04

23、合并K个升序链表	2024-07-05
24、两两交换链表中的节点	2024-07-05
25、K个一组翻转链表	2024-07-05
26、删除有序数组中的重复项	2024-07-05
27、移除元素
28、找出字符串中第一个匹配项的下标	2024-07-05

30、串联所有单词的子串	2024-07-05

11、盛水最多的容器（双指针）

11.1、暴力枚举

思路💡：枚举每种左右高度的组合，直到取到最大值
时间复杂度🕖：O（n2）

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for(int i=0;i<height.length-1;i++){
            for(int j=i+1;j<height.length;j++){
                int high = Math.min(height[i],height[j]);
                int width = j-i;
                max = Math.max(max,high*width);
            }
        }
        return max;
    }
}

11.2、双指针

思路💡：左右指针

虽然指针每移动一次，容器的宽度 -1，但是如果移动得到的"回报"——边界的高度变得更高，那就是值得的

时间复杂度🕖： O（N）

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0,right = height.length - 1;
        while(left < right){
            int area = Math.min(height[left],height[right])*(right-left);
            if(height[left] <= height[right]){
                left++;
            }else{
                right--;
            }
            max = Math.max(max,area);
        }
        return max;
    }
}

12、整数转罗马数字（数学 + 模拟）

12.1、模拟

思路💡：从千位到个位，对每一位进行逻辑模拟
时间复杂度🕖：O（1）

class Solution {
    static Map<Integer,Character> map = new HashMap<>();
    static{
        map.put(1,'I');
        map.put(5,'V');
        map.put(10,'X');
        map.put(50,'L');
        map.put(100,'C');
        map.put(500,'D');
        map.put(1000,'M');
    }
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        if(String.valueOf(num).length()>3){
            int q = num/1000;
            while(q!=0){
                sb.append(map.get(1000));
                q--;
            }
            num %= 1000;
        }
        if(String.valueOf(num).length()>2){
            int b = num/100;
            while(b!=0) {
            	if(b >=5 && b < 9) {
                	sb.append(map.get(500));
                	b-=5;
                }else if(b==4) {
                	sb.append("CD");
                	break;
                }else if(b==9) {
                	sb.append("CM");
                	break;
                }else {
                	while(b!=0){
                        sb.append(map.get(100));
                        b--;
                    }	
                }	
            }  
            num %= 100;
        }
        if(String.valueOf(num).length()>1){
            int s = num/10;
            while(s!=0) {
            	if(s<9 &&  s>=5){
                    sb.append(map.get(50));
                    s-=5;
                }else if(s==4){
                    sb.append("XL");
                    break;
                }else if(s==9){
                    sb.append("XC");
                    break;
                }else{
                    while(s != 0){
	                    sb.append(map.get(10));
	                    s--;
                    }
                }
            }
            num %= 10;
        }
        while(String.valueOf(num).length()>0 && num>0){
            if(num <9 && num >= 5){
                sb.append(map.get(5));
                num-=5;
            }else if(num == 4){
                sb.append("IV");
                break;
            }else if(num == 9){
                sb.append("IX");
                break;
            }else{
                while(num!=0){
                    sb.append("I");
                    num--;
                }
            }
        }
        return sb.toString();
    }
}

13、罗马数字转整数（模拟）

13.1、模拟

思路💡：从高位到低位，在判断当前位对应数值的同时向低一位判断一下，因为罗马数字只有相邻位置可以进行减法表示（比如 49 可以表示为 IX）
时间复杂度🕖：O（1）

class Solution {
    static Map<Character,Integer> map = new HashMap<>();
    static{
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
    }
    public int romanToInt(String s) {
        int res = 0;
        int index = 0;
        while(index+1<s.length()){
            if(map.get(s.charAt(index)) >= map.get(s.charAt(index+1))){
                res += map.get(s.charAt(index));
                index++;
            }else{
                res += (map.get(s.charAt(index+1)) - map.get(s.charAt(index)));
                index+=2;
            }
        }
        if(index < s.length()){
                res += map.get(s.charAt(index));
        }
        return res;
    }
}

14、最长公共前缀（二分搜索）

14.1、枚举

思路💡：木桶原理，最长公共前缀取决于"最混蛋"的那个字符串（任意一个字符串的第 1 个前缀字符和别的字符串不一样，就算别的 9999 个字符串都完全一样也没用，它们的公共前缀就是 0）。所以我们可以拿任意一个字符串当做模板和别的所有字符串进行对比。

时间复杂度🕖：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        char[] prefix = strs[0].toCharArray();
        StringBuilder sb = new StringBuilder();
        for(char c : prefix){
            sb.append(c);
            for(String str : strs){
                if(!str.startsWith(sb.toString())){
                    return sb.substring(0,sb.length()-1).toString();
                }
            }
        }
        return sb.toString();
    }
}

14.2、二分搜索

思路💡：前缀的长度范围超不出数组中最短的字符串长度，所以使用二分不断寻找可能的 mid 值，也就是最长的前缀长度

时间复杂度🕖：二分查找的迭代执行次数是 O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。

知识点🙉：这里的二分搜索是左闭右闭的，所以 while 条件是 left < right，而不是 left <= right；

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int minLength = Integer.MAX_VALUE;
        for(String str : strs)
            minLength = Math.min(minLength,str.length());
        int left = 0,right = minLength;
        while(left < right){
            // (right - left + 1) 中 +1 的原因是我们mid的意义是长度,而不是索引
            int mid = (right - left + 1) / 2 + left;
            if(isSamePrefix(strs,mid))
                left = mid;
            else
                right = mid - 1;
        }
        return strs[0].substring(0,left);
    }
    public boolean isSamePrefix(String[] strs,int length){
        String suffix = strs[0].substring(0,length);
        for(int i=1;i<strs.length;i++)
            if(!strs[i].startsWith(suffix))
                return false;
        return true;
    }
}

15、三数之和（双指针）

15.1、暴力枚举

思路💡：三层遍历

时间复杂度🕖：O（n3）

知识点🙉：这里唯一收获的东西就是：使用 list.contains() 判断元素相同的集合对象进行去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        for(int i=0;i < nums.length-2;i++){
            for(int j=i+1;j < nums.length-1;j++){
                for(int k=j+1;k < nums.length;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        put(nums[i],nums[j],nums[k]);
                    }
                }
            }
        }
        return res;
    }
    public void put(int v1,int v2,int v3){
        List<Integer> list = new ArrayList<>();
        list.addAll(Arrays.asList(v1,v2,v3));
        Collections.sort(list);
        if(!res.contains(list)) res.add(list);
    }
}

15.2、双指针

思路💡：

首先对数组排序，不然无法判断指针应该如何移动
这道题在使用双指针时有一个特别需要注意的就是：当左指针或右指针对应当前值和下一个值相同时，得到的结果会有重复，所以在每次循环前后都会对重复值进行处理

时间复杂度🕖：O（n2）

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        Arrays.sort(nums);
        //确定第一个数
        for(int i = 0;i < n ;i ++)
        {
            // 当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1,r = n - 1;

            while(l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum > 0) 
                {
                    r --;
                    continue;
                }
                if(sum < 0)
                {
                    l ++;
                    continue;
                }
                //sum == 0时
                ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                //去除重复处理
                do {l ++;} while(l < r && nums[l] == nums[l - 1]);
                do {r --;} while(l < r && nums[r] == nums[r + 1]);
            }

        }
        return ans;
    }
}

16、最接近的三数之和（双指针）

16.1、双指针

思路💡：首先对数组进行排序，然后枚举三数之和中的第一个数字，剩下的两个数字用左右指针寻找，不断逼近和目标值最近的两个数

时间复杂度🕖：O（n2）

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            int l = i+1,r = nums.length-1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                ans = Math.abs(sum-target)<Math.abs(ans-target)?sum:ans;
                if(sum > target)    r--;
                else if (sum < target)  l++;
                else if (sum == target) return target;
            }
        }
        return ans;
    }
}

17、电话号码的字母组合（深搜）

17.1、深度优先搜索

思路💡：组合问题，直接深搜

时间复杂度🕖：O(3^m ×4^n )，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9）

class Solution {
    Map<Integer, Character[]> map = new HashMap<Integer, Character[]>();
	{
		int index = 'a';
		for (int i = 2; i < 7; i++) {
			Character[] arr = new Character[3];
			for (int j = 0; j < arr.length; j++) arr[j] = (char)index++;
			map.put(i, arr);
		}
        map.put(7, new Character[]{'p','q','r','s'});
        map.put(8, new Character[]{'t','u','v'});
		map.put(9, new Character[]{'w','x','y','z'});
	}
	List<String> res = new ArrayList<>();
	List<String> letterCombinations(String digits) {
        if(digits.length()==0) return res;

        backtrack(digits,0,"");
		return res;
    }
	public void backtrack(String digits,int index,String str){
        if(index == digits.length()){
            res.add(str);
            return;
        }
        for(char s : map.get(Integer.parseInt(""+digits.charAt(index)))){
            backtrack(digits,index + 1,str + s);
        }
    }
}

18、四数之和（双指针）

18.1、双指针

思路💡：同样对数组先排序，前两个数使用枚举，后两个数用双指针优化

时间复杂度🕖：O（n3）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums.length == 0) return new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        // 定下nums[i]
        for(int i = 0;i < n;i++){
            // 去重
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            // 定下nums[j]
            for(int j = i + 1;j < n - 2;j++){
                // 去重
                if(j != i+1 && nums[j] == nums[j-1]) continue;
                int k = j + 1,m = n-1;
                // 双指针
                while(k < m){
                    int sum = nums[i] + nums[j] + nums[k] + nums[m];
                    if(sum > target){
                        m--;
                        continue;
                    }
                    if(sum < target){
                        k++;
                        continue;
                    }else if(sum == target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[k],nums[m]));
                    }
                    // 去重
                    do{k++;}while(k < m && nums[k] == nums[k - 1]);
                    do{m--;}while(k < m && nums[m] == nums[m + 1]);
                }
            }
        }
        return list;
    }
}

19、删除链表最后一个节点

思路💡：删除倒数第 N 个节点就是删除正数第 L - N +1 个节点

时间复杂度🕖：O（L），L 是链表的长度

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 如果链表只有一个元素还要删除就直接返回空
        if(head.next == null && n==1) return null;
        // 计算链表的长度
        ListNode t1 = head;
        int len = 1;
        while(t1.next != null){
            len++;
            t1 = t1.next;
        }
        int target = len - n + 1; // 倒数第n个就是正数第(len-n+1)个元素
        int cur = 1; // 当前节点位置
        if(cur == target) return head.next; // 如果当前位置就是要删除的元素就直接返回下一个节点
        t1 = head; // 重新初始化
        while(cur != target-1){ // 找到要删除的目标节点的前一个节点
            t1 = t1.next;
            cur++;
        }
        // 如果目标节点的下一个节点为空就置当前节点的下一个节点为空 否则连接下下一个节点
        if(t1.next.next != null) t1.next = t1.next.next; else t1.next = null;
        return head;
    }
}

20、有效的括号

20.1、栈

思路💡：右括号总是出现在第偶数次的，否则说明括号不合法

时间复杂度🕖：O（N）

class Solution {
    public boolean isValid(String s) {
        if(s.length() %2 != 0) return false;
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Deque<Character> stack = new ArrayDeque<>(); 
        for(int i=0;i<s.length();i++){
            if(i!=0 && stack.peek()!=null && stack.peek() == map.get(s.charAt(i))){
                stack.pop();
                continue;
            }
            stack.push(s.charAt(i));
        }
        return stack.size() == 0;
    }
}

21、合并两个有序链表

思路💡：借助一个中间指针，穿针引线

时间复杂度🕖：O（L），L 是链表的长度

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;

        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(list1 != null && list2!=null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1==null?list2:list1;
        return dummy.next;
    }
}

23、合并K个有序链表

思路💡：把链表问题转为数组问题

时间复杂度🕖：O（n2）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists ==null || lists.length==0) return null;
        List<Integer> list = new ArrayList<>();
        for(ListNode node : lists){
            while(node != null){
                list.add(node.val);
                node = node.next;
            }
        }
        Collections.sort(list);
        ListNode res = new ListNode();
        if(list.size()==0) return null;
        ListNode t = new ListNode(list.get(0));
        res.next = t;
        for(int n: list){
            t.next = new ListNode(n);
            t = t.next;
        }
        return res.next.next;
    }
}

24、两两交换链表中的节点

思路💡：把链表问题转为数组问题

时间复杂度🕖：O（n2）

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        // 1.把链表转为数组
        // 1.1求出链表的深度
        ListNode t = head;
        int len = 0;
        while(t != null){
            len++;
            t = t.next;
        }
        // 1.2 创建数组并赋值
        int[] arr = new int[len];
        int index = 0;
        t = head;
        while(t != null){
            arr[index++] = t.val;
            t = t.next;
        }
        // 2.交换数组(链表)中的节点
        for(int i=0;i+1<len;i+=2){
            swap(arr,i,i+1);
        }
        // 3. 把数组转为链表返回
        ListNode res =  new ListNode();
        ListNode a =  new ListNode(arr[0]);
        res.next = a;
        for(int i=1;i<len;i++){
            a.next = new ListNode(arr[i]);
            a = a.next;
        }
        return res.next;
    }
    void swap(int[] arr,int i, int j){
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
}

25、K个一组翻转链表

思路💡：把链表问题转为数组问题，使用双指针翻转元素

时间复杂度🕖：O（N）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 将链表转为数组
        ListNode t = head;
        int len = 0;
        while(t != null){
            len++;
            t = t.next;
        } 
        int[] nums = new int[len];
        t = head; // 重新初始化
        int index = 0;
        while(t!=null){
            nums[index++] = t.val;
            t = t.next;
        }
        // 比如3个一组，但是数组长度是5，我们只需要翻转前3个，因为剩下的凑不够一组
        int range = len/k*k;
        for(int i=0;i<range;i+=k){
            int l = i,r = i+k-1;
            while(l < r){ // 双指针翻转元素
                nums[l] ^= nums[r];
                nums[r] ^= nums[l];
                nums[l] ^= nums[r];
                l++;
                r--;
            }
        }
        ListNode res = new ListNode();
        ListNode a = new ListNode(nums[0]);
        res.next = a;
        // 把数组组合成链表
        for(int i=1;i<nums.length;i++){
            a.next = new ListNode(nums[i]);
            a = a.next;
        }
        return res.next;
    }

}

26、删除有序数组中的重复项

思路💡：快慢指针

时间复杂度🕖：O（N）

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 1) return 1;
        int l = 0,r = 0;
        while(r < nums.length){
            // 直到找到和左指针指向不同的值
            while(r<nums.length && nums[r]==nums[l])    r++;
            // 防止越界
            if(r >= nums.length) break;
            // 判断是否重复,把不重复的数据前移
            if(r - l > 1)   nums[l+1] = nums[r];
            l++;
            r++;
        }
        return l+1; // 返回去重后原数组的长度
    }
}

27、移除元素（快慢指针）

思路💡：使用两个指针，慢指针负责从索引 0 重新给数组赋值，快指针负责找非目标值

时间复杂度🕖：O（N）

class Solution {
    public int removeElement(int[] nums, int val) {
        int l = 0;
        for (int r = 0; r < nums.length; r++)
            if (nums[r] != val)
                nums[l++] = nums[r];
        return l;
    }
}

28、找出字符串中第一个匹配项的下标（字符串）

思路💡：substring 遍历

时间复杂度🕖：O（n * m），其中 n 是 haystack 的长度，m 是neddle 的长度

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i=0;i<=haystack.length()-needle.length();i++){
            if(haystack.substring(i,i+needle.length()).equals(needle)){
                    return i;
            }
        }
        return -1;
    }
}

30、串联所有单词的子串

思路💡：使用回溯法得到数组元素的全排列，然后遍历字符串的子串查看是否能够匹配

时间复杂度🕖：

class Solution {
    boolean[] visits;
    HashSet<Integer> set = new HashSet<>(); // 因为数组中可能包含重复，所以全排列中可能有重复值
    List<Integer> ans;
    List<List<String>> tracks = new ArrayList<List<String>>();
    public List<Integer> findSubstring(String s, String[] words) {
        visits = new boolean[words.length];
        LinkedList<String> track = new LinkedList<>();
        backtrack(track,words);
        for (List<String> list : tracks) {
			StringBuilder sb = new StringBuilder();
			for(String word : list) {
				sb.append(word);
			}
			check(s,sb.toString());
		}
        ans = new ArrayList<Integer>(set);
        return ans;
    }
    public void check(String s,String ch) {
		for(int i=0;i<s.length();i++) {
			if(i+ch.length()<=s.length() && ch.charAt(0) == s.charAt(i) && s.substring(i,i+ch.length()).equals(ch)) {
				set.add(i);
			}
		}
	}
    public void backtrack(LinkedList<String> track,String[] words) {
		if(track.size()==words.length) {
			LinkedList<String> res = new LinkedList<>(track);
			tracks.add(res);
			return;
		}
		for (int i = 0; i < words.length; i++) {
			// if(track.contains(words[i])) continue; // 这里不能这么用，因为包含重复元素
			if(visits[i]) continue;
			track.add(words[i]);
			visits[i] = true;
			backtrack(track, words);
			track.removeLast();
			visits[i] = false;
		}
	}
}