每日刷题记录 (三)

转x33g5p2x  于2022-06-27 转载在 其他  
字(4.0k)|赞(0)|评价(0)|浏览(400)

第一题: 括号

LeetCode: 面试题 08.09. 括号
描述:
括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

解题思路:

这里使用回溯.
left表示左括号数. right 表示右括号数.
构建字符串, 遇到不合格的就停止, 满足要求就加入list中
注意这里的剪枝,

代码实现:

  1. class Solution {
  2.     public List<String> generateParenthesis(int n) {
  3.         List<String> res = new ArrayList<>();
  4.         backstrack(res,"",n,n);
  5.         return res;
  6.     }
  8.     public void backstrack(List<String> res,String str,int left,int right) {
  9.     	// 剪枝1 left 或者 right 小于0的情况
  10.         if(left < 0 || right < 0) return;
  11.         // 剪枝2 left > right的情况
  12.         if(left > right) return;
  13.         // left和right都为0 此时就满足条件
  14.         if(left == 0 && right == 0) {
  15.             res.add(str);
  16.             return;
  17.         }
  18.         backstrack(res,str+"(",left-1,right);
  19.         backstrack(res,str+")",left,right-1);
  20.     }
  21. }

第二题: 硬币

LeetCode: 面试题 08.11. 硬币
描述:
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

解题思路:

动态规划思路:

  • 状态 F(i) : 表示当前凑出i的方式
  • 状态转移方程: F(i) = (F(i) + F(i-coin)) %1000000007
  • 初始状态: F(0) = 1; 因为刚好可以用硬币抽出来.
  • 返回结果: F(n)

这里 coins = { 1, 5, 10, 25 };
如果直接遍历, 会有重复的情况, 例如 5 + 10 和 10 + 5
避免这种情况, 就可以使用小循环, 每次小循环只用一种硬币可以避免重复.

代码实现:

  1. class Solution {
  2.     public int waysToChange(int n) {
  3.     	// 当前硬币的情况
  4.         int[] coins = {1,5,10,25};
  5.         int[] dp = new int[n+1];
  6.         // 例如 dp[1] = dp[1] + dp[0], 这里就表示刚好可以使用当前硬币,初始化就为1
  7.         dp[0] = 1;
  8.         // 外层遍历这个coins数组
  9.         for(int coin : coins) {
  10.         	// 内层 遍历一种硬币
  11.             for(int i = coin;i <= n; i++) {
  12.                 dp[i] = (dp[i] + dp[i-coin]) % 1000000007;
  13.             }
  14.         }
  15.         return dp[n];
  16.     }
  17. }

第三题: 变位词组

LeetCode: 面试题 10.02. 变位词组
描述:
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

解题思路:

  1. 遍历, 让遍历到的字符串进行排序, 添加到HashMap中key为排序后的字符串, value为一个list
  2. 把排序后的字符相同的,加入到同一个list中
  3. 不同的就新添加一个list.
  4. 遍历结束之后, 把所有的list添加到一起

代码实现:

  1. class Solution {
  2.     public List<List<String>> groupAnagrams(String[] strs) {
  3.         List<List<String>> list = new ArrayList<>();
  4.         Map<String,List<String>> map = new HashMap<>();
  5.         for(String str : strs) {
  6.         	// 进行排序
  7.             char[] ch = str.toCharArray();
  8.             Arrays.sort(ch);
  9.             // 排序后的字符数组变成字符串
  10.             String s = new String(ch);
  11.             if(!map.containsKey(s)) {
  12.             //这里是不存在相同key的情况, 需要创建一个新的list
  13.                 List<String> ret = new ArrayList<>();
  14.                 ret.add(str);
  15.                 map.put(s,ret);
  16.             }else{
  17.             //这里是存在相同的key的情况, 需要得到之前的list,然后添加数据
  18.                 map.get(s).add(str);
  19.             }
  20.         }
  21.         // 使用keySet的方法得到key, 然后把所有的value值添加到一起.
  22.         for(String key : map.keySet()) {
  23.             list.add(map.get(key));
  24.         }
  25.         return list;
  26.     }
  27. }

第四题: 最小差

LeetCode: 面试题 16.06. 最小差
描述:
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

解题思路:

  1. 定义两个指针, left right, 对两个数组进行排序.
  2. 用 ret 记录当前 a[left] - b[right] 的差值
    如果ret > 0, a[left]>b[right], 就让right++, 为了让b的值更接近a的值
    如果ret < 0, a[left]<b[right], 就让left++, 为了让a的值更接近b的值
    记录 最小的ret

代码实现:

  1. class Solution {
  2.     public int smallestDifference(int[] a, int[] b) {
  3.        	// 先排序
  4.         Arrays.sort(a);
  5.         Arrays.sort(b);
  6.         // 注意这里的溢出
  7.         long min = Integer.MAX_VALUE;
  8.         int left = 0;
  9.         int right = 0;
  10.         while(left < a.length && right < b.length) {
  11.             // long 防止溢出
  12.             long ret = a[left] - b[right];
  13.             // 记录最小值
  14.             min = Math.min(Math.abs(ret),min);
  15.             // 让更接近的值相减
  16.             if(ret < 0) left++;
  17.             else right++;
  18.         }
  19.         return (int)min;
  20.     }
  21. }

第五题: 首个共同祖先

LeetCode: 面试题 04.08. 首个共同祖先
描述:
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

解题思路:

  1. 可能出现的情况:
    ①p 和 q有一个为根节点, 那么该根节点就是最近公共祖先
    ②p 和 q不在同一颗子树下, 那么他们的父亲就是公共祖先
    ③p 和 q在同一颗子树下
  2. 递归左右子树
    ① 左右子树都不为空, 那么root就是公共祖先
    ② 左子树为空, 右子树不为空, 那么右树找到的节点就是公共祖先
    ③ 左子树不为空, 右子树为空, 那么左树找到的节点就是公共祖先

代码实现:

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.     	// 情况一: 根节点为空
  4.         if (root == null) return null;
  5.         // 情况二: p或q为根节点
  6.         if (p == root || q == root) return root;
  7.         // 遍历左右子树
  8.         TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
  9.         TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
  10.         // 都不为空, 那么root就是公共祖先
  11.         if(leftNode != null && rightNode != null) {
  12.             return root;
  13.         }
  14.         // 左子树为空, 右树的节点就是公共祖先
  15.         if(leftNode == null){
  16.             return rightNode;
  17.         }
  18.         // 右子树为空, 左树的节点就是公共祖先
  19.         if(rightNode == null) {
  20.             return leftNode;
  21.         }
  22.         return null;
  23.     }
  24. }

第六题: 最小高度树

LeetCode: 面试题 04.02. 最小高度树
描述:
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

解题思路:

  1. 这里就使用二分方法来分割, 每次取得中间点, 然后构造一个节点.
  2. 然后在左边取得一个中间点, 构造左节点, 再右边取得一个中间点, 构造右节点.

代码实现:

  1. class Solution {
  2.     public TreeNode sortedArrayToBST(int[] nums) {
  3.         return makeBST(nums,0,nums.length-1);
  4.     }
  5.     public TreeNode makeBST(int[] nums, int left, int right) {
  6.         // 如果left>right就不合法了
  7.         if (left > right) {
  8.             return null;
  9.         }
  10.         // 这里防止溢出, 使用left+(right-left)/2
  11.         int mid = left + (right - left) / 2;
  12.         // 构造一个节点
  13.         TreeNode node = new TreeNode(nums[mid]);
  14.         // 构造左右子树
  15.         node.left = makeBST(nums, left, mid - 1);
  16.         node.right = makeBST(nums, mid+1, right);
  17.         return node;
  18.     }
  19. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125427786

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法动态规划

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com