面试经典150题(85-87)

这篇具有很好参考价值的文章主要介绍了面试经典150题(85-87)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode 150道题 计划花两个月时候刷完,今天(第四十三天)完成了3道(85-87)150:

85.(77. 组合)题目描述:

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
输入:n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

第一版(昨天就是这个卡了好久没弄出来,今天还是没思路啊。。看了解题,感觉都是一个for 然后for里面嵌套。看看解题的代码吧)

class Solution {
    List<List<Integer>> res=new ArrayList();
    public List<List<Integer>> combine(int n, int k) {
        if(n<k){
            return res;
        }
        selectKNum(n,k,1,new ArrayList<Integer>());
        return res;
    }
    public void selectKNum(int n, int k,int start,List<Integer> list) {
        if(list.size()==k){
            res.add(new ArrayList(list));
            return ;
        }
        for(int i=start;i<=n;i++){
            list.add(i);
            selectKNum(n,k,i+1,list);
            list.remove(list.size()-1);
        }
        
    }
}

86.(46. 全排列)题目描述:

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

第一版(还是解题,感觉这个又是另一种回溯的题型)

class Solution {
    List<List<Integer>> res=new ArrayList();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        permuteCore(nums,used,new ArrayList<Integer>());
        return res;
    }
    public void permuteCore(int[] nums,boolean[] used,List<Integer> list){
        if(list.size()==nums.length){
            res.add(new ArrayList(list));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            list.add(nums[i]);
            used[i]=true;
            permuteCore(nums,used,list);
            used[i]=false;
            list.remove(list.size()-1);
        }
    }
}

87.(39. 组合总和)题目描述:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
candidates 全是大于0的整数
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]

第一版(根据之前的两个题的解题,照猫画虎写了一版。。终于自己写了一版了,虽然性能不是很好)

class Solution {
    List<List<Integer>> res=new ArrayList();
    Set<String> set=new HashSet();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinationSumCore(candidates,target,new ArrayList<Integer>());
        return res;
    }
    public void combinationSumCore(int[] candidates,int target,List<Integer> list){
        if(0==target){
            List<Integer> temp=new ArrayList(list);
            temp.sort((i1,i2)->{return i1-i2;});
            if(set.add(temp.toString()))
            {
                res.add(temp);
            }
            return ;
        }
        for(int i=0;i<candidates.length;i++){
            if(target<0){
                break;
            }
            if(target-candidates[i]<0){
                continue;
            }
            list.add(candidates[i]);
            combinationSumCore(candidates,target-candidates[i],list);
            list.remove(list.size()-1);
        }
    }
}

第二版(看了解题,讲的还是理解不了,就照着写了一版,真的是性能从 104ms->5ms 质的飞跃)

class Solution {
    List<List<Integer>> res=new ArrayList();
    Set<String> set=new HashSet();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinationSumCore(candidates,0,target,new ArrayList<Integer>());
        return res;
    }
    public void combinationSumCore(int[] candidates,int start,int target,List<Integer> list){
        if(0==target){
            res.add(new ArrayList(list));
            return ;
        }
        for(int i=start;i<candidates.length;i++){
            if(target<0){
                break;
            }
            if(target-candidates[i]<0){
                continue;
            }
            list.add(candidates[i]);
            combinationSumCore(candidates,i,target-candidates[i],list);
            list.remove(list.size()-1);
        }
    }
}

就这两天回溯我感觉咋都是 for 加递归调用。。但是不好理解。。不行就背下来(笨人做法)

加油,第四十三天了,早日跳槽啊!!!文章来源地址https://www.toymoban.com/news/detail-802206.html

到了这里,关于面试经典150题(85-87)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-面试经典150题-day14】

      目录 19.删除链表的倒数第N个结点  82.删除排序链表中的重复元素Ⅱ  61. 旋转链表  86.分隔链表  146.LRU缓存 19.删除链表的倒数第N个结点 题意: 给你一个链表,删除链表的倒数第  n   个结点,并且返回链表的头结点。 【输入样例】head = [1,2,3,4,5],n=2 【输出样例】[1,2,3,5

    2024年02月11日
    浏览(43)
  • 【LeetCode-面试经典150题-day23】

    目录 108. 将有序数组转换为二叉搜索树  148.排序链表  427.建立四叉树  23.合并K个升序链表   108. 将有序数组转换为二叉搜索树 题意: 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「

    2024年02月09日
    浏览(43)
  • LeetCode面试经典150题(day 1)

    LeetCode是一个免费刷题的一个网站,想要通过笔试的小伙伴可以每天坚持刷两道算法题。 接下来,每天我将更新LeetCode面试经典150题的其中两道算法题,一边巩固自己,一遍希望能帮助到有需要的小伙伴。 88.合并两个有序数组 给你两个按  非递减顺序  排列的整数数组  nu

    2024年02月11日
    浏览(36)
  • LeetCode150道面试经典题-- 快乐数(简单)

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」  定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为  1,那么这个数就是快乐数。 如果

    2024年02月12日
    浏览(39)
  • Leetcod面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年02月03日
    浏览(41)
  • Leetcode面试经典150题刷题记录 —— 数学篇

    Leetcode面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试经典

    2024年01月21日
    浏览(56)
  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(56)
  • leetcode每日一题——189.轮转数组(面试经典150题)

    189. 轮转数组 - 力扣(LeetCode) 给定一个整数数组  nums ,将数组中的元素 向右轮转  k   个位置 ,其中  k   是非负数。 示例1: 示例2: 1 = nums.length = 105 -231 = nums[i] = 231 - 1 0 = k = 105        对题目进行分析可知,我们需要根据轮转量k,将数组后面的k个元素按照原来的顺

    2024年02月12日
    浏览(37)
  • LeetCode150道面试经典题-合并两个有序数组(简单)

    题目: 给你两个按 非递减顺序 排列的整数数组  nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对

    2024年02月14日
    浏览(40)
  • 【leetcode面试经典150题】29.三数之和(C++)

    【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致) 给你一个整数数组 

    2024年04月13日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包