IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【力扣hot100】day2 -> 正文阅读

[数据结构与算法]【力扣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();
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-11-05 00:49:40  更:2022-11-05 00:54:02 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 19:49:05-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码