[数据结构与算法]【力扣hot100】day2

11. 盛最多水的容器【中】

11.盛最多水的容器
一：双指针

• 时间复杂度 O(N)；
• 空间复杂度 O(1)： 变量 i ，j，S，temp使用常数额外空间。

//执行用时: 3 ms
//内存消耗: 50.9 MB
// S = (j - i) * h[j] 或者 S = (j - i) * h[i]
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int S = 0, temp = 0;;
        while(left < right) {
            if(height[left] < height[right]) {
                temp = height[left]*(right - left);
                left++;
            } else {
                temp = height[right]*(right - left);
                right--;
            }
            S = Math.max(S, temp);
        }
        return S;
    }
}

15. 三数之和【中】

15.三数之和
方法一：双指针

• 时间复杂度：O(n^2)，n 为数组长度

//执行用时: 19 ms
//内存消耗: 45.6 MB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 1; i++) {
            int left = i + 1, right = nums.length - 1;
         // int sum = nums[i] + nums[left] + nums[right]; 写在这里的话就错了
            if(nums[i] > 0) {
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue; //去重
            }

            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right]; 
                if(sum == 0) {
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++; //去重
                    }
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--; //去重
                    }
                    left++;
                    right--;
                }
                else if(sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return list;
    }
}

17. 电话号码的字母组合【中】

17.电话号码的字母组合
方法一：回溯

//执行用时: 0 ms
//内存消耗: 39.9 MB
class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder res = new StringBuilder();
    String[] ss = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return result;
        backTracking(digits, 0);
        return result;
    }

    public void backTracking(String digits, int index) {
        if(index == digits.length()) {
            result.add(res.toString());
            return ;
        }
        String tmp = ss[digits.charAt(index) - '0'];
        for(int i = 0; i < tmp.length(); i++) { 
        //这里真的要注意，i < tmp.length()，而不是 i < digits.length()
            res.append(tmp.charAt(i));
            backTracking(digits, index + 1);
            res.deleteCharAt(res.length() - 1);
        }
    }
}

19. 删除链表的倒数第N个结点【中】

19.删除链表的倒数第N个结点
方法一：遍历
先统计总的结点数count，删除倒数第N个结点也就是删除第(count - n + 1)个结点

//执行用时: 0 ms
//内存消耗: 39.9 MB
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        pre.next = head;
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        for(int i = 0; i < count - n; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
}

方法二：双指针

//执行用时: 0 ms
//内存消耗: 39.5 MB
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {    
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy,slow = dummy;
        while(n != 0) {
            fast = fast.next;
            n--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

20. 有效的括号【易】

20.有效的括号
方法一：辅助栈

//执行用时: 1 ms
//内存消耗: 39.2 MB
class Solution {
    public boolean isValid(String s) {
        if(s.isEmpty()) 
            return true;
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c == '('){
                stack.push(')');
            }else if(c == '['){
                stack.push(']');
            }else if(c == '{'){
                stack.push('}');
            }else if(stack.isEmpty() || c != stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();
    }
}