代码编织梦想

1.全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

我的解法(回溯)

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // 记录已经被选过的元素
        boolean[] used = new boolean[nums.length];
        backtracing(nums, used, res, new ArrayDeque<Integer>());
        return res;
    }
    public void backtracing(int[] nums, boolean[] used, List<List<Integer>> res, Deque<Integer> path){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; ++i){
            if(used[i] == true) continue;
            used[i] = true;
            path.add(nums[i]);
            backtracing(nums, used, res, path);
            path.removeLast();
            used[i] = false;
        }
    }
}

2.子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

我的解法(回溯)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(nums, 0, res, new ArrayDeque<Integer>());
        return res;
    }

    public void backtracking(int[] nums, int startIndex, List<List<Integer>> res, Deque<Integer> path){
        res.add(new ArrayList<>(path));
        for(int i = startIndex; i < nums.length; ++i){
            path.add(nums[i]);
            backtracking(nums, i + 1, res, path);
            path.removeLast();
        }
    }
}

3.根据身高重建队列

假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

示例 1:

输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

解释:
编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 01 的人。
编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0123 的人。
编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2:

输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

我的解法(贪心)

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        LinkedList<int[]> res = new LinkedList<>();
        for(int[] p : people){
            res.add(p[1], p);
        }
        return res.toArray(new int[people.length][]);
    }
}

4.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:
在这里插入图片描述

输入:[1,8,6,2,5,4,8,3,7]
输出:49 

解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

我的解法(暴力破解)

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

一做算法题脑子就跟浆糊一样,两眼一瞪,啥也不会,暴力破解还超时,没有天理啊。

官方解法(双指针)

class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while(i < j){
            res = height[i] < height[j] ? 
                  Math.max(res, (j - i) * height[i++]):
                  Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }
}

没有思路时,一定要仔细分析,如果实在想不出来就动笔画画图。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_51431003/article/details/129829003

练习题随记_白酒蒿的博客-爱代码爱编程

动态区间第k小 之前已经写过题解了,链接动态区间第k小,总结:代码要细心一点啊qwq 秀肌肉 莫队裸题,然后没有开longlong又wa又tqwq 小z的袜子 莫队裸题(因为莫队写起来很简单所以就没有用分块),对于

计算机视觉(1)随记_weixin_34220834的博客-爱代码爱编程

书籍推荐:计算机视觉--算法与应用 What is Computer vision? 对图像处理来说:输入的是图像,输出的还是图像。 而Computer Vision输入的是图像,输出的是它对图像的理解 Why computer vision matters 自动驾驶汽车目前技术已经非常成熟,只是

小白在Idea上配置《算法》第四版的环境(随记)-爱代码爱编程

小白在Idea上配置《算法》第四版的环境(随记) 前言一、官方jar包和文件的准备二、小白操作1.在Idea里创建新项目2.直接解压官方jar包(algs4.jar)和文件(algs4-data.zip)三、使用方法运行总结 前言 本算法小白艰难的入门历程,特此记下,或许对其他人有帮助 一、官方jar包和文件的准备 相信您在打开我的文章时

数组练习1_红绳会太子妃的博客-爱代码爱编程

  #include<stdio.h> int main() { int i=0,c,j; int a[100]; for(i=0;;i++) { scanf("%d",&a[i]); if(a[i]==0) break; // c=i;这里如果使用c,

算法练习随记(一)-爱代码爱编程

1.只出现一次的数字 给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

c语言 第四周知识点随记_c语言 4

c语言 c语言知识点

逻辑类型 布尔运算 #include <stdbool.h> int main() { } bool a = 6>5; //由于6>5为真值,a的结果应该为1 bool b = ture; //由于true在布尔运算中是1,所以b的结果为1 bool b = 3; //这条语句

18-爱代码爱编程

题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据保证整个链式结构中不存在环。 注意,函数返回结果后,链表必须 保持其原始结构 。 自定义评测: 评测系统的输入如下(你设计的程序不适用此输入):

算法练习随记(二)-爱代码爱编程

1.汉明距离 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y,计算并返回它们之间的汉明距离。 示例 1: 输入:x = 1, y = 4 输出:2 解释: 1

java语法随记_constructor-爱代码爱编程

java 1 字符 (1)判断字符大小及相等 a.equals(b); // 判断相等 a.equalsIgnoreCase(b);// 忽略大小写相等 a.compareTo(b);// i>0 a>b;