【算法】三道算法题两道难度中等一道困难

news/2024/4/24 23:04:07/文章来源:https://blog.csdn.net/leng_yong/article/details/129209085

算法目录

只出现一次的数字（中等难度）
- java解答参考
二叉树的层序遍历（难度中等）
- java 解答参考
给表达式添加运算符（比较困难）
- java解答参考

大家好，我是小冷。
上一篇是算法题目
接下来继续看下算法题目吧，用Java解答，可能更能激发一下大脑思考。

只出现一次的数字（中等难度）

题目要求：

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

根据题目要求和实例可分析有哪些步骤，需要几个for循环。

进阶：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

java解答参考

class Solution {public int singleNumber(int[] nums) {int ret = 0;for (int i = 0; i < 32; ++i) {int bitnums = 0;int bit = 1 << i;for (int num : nums) {if ((num & bit) != 0)bitnums++;}if (bitnums % 3 != 0)ret |= bit;}return ret;}
}

二叉树的层序遍历（难度中等）

题目要求：
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

java 解答参考

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> l = new ArrayList<>();Queue<TreeNode> q = new LinkedList<TreeNode>();if (root != null) {q.add(root);}while (!q.isEmpty()) {List<Integer> l2 = new ArrayList<>();int number = q.size();while (number > 0) {TreeNode t = q.poll();l2.add(t.val);if (t.left != null) {q.add(t.left);}if (t.right != null) {q.add(t.right);}number--;}l.add(l2);}return l;}
}

给表达式添加运算符（比较困难）

题目要求：
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]

示例 2:

输入:
num =
“232”, target = 8
输出: [“23+2", "2+32”]

示例 3:

输入:
num =
“105”, target = 5
输出: [“1*0+5”,“10-5”]

示例 4:

输入:
num =
“00”, target = 0
输出: [“0+0”, “0-0”, “0*0”]

示例 5:

输入:
num =
“3456237490”, target = 9191
输出: []

提示：

1 <= num.length <= 10
num 仅含数字
-231 <= target <= 231 - 1

java解答参考

class Solution {int n;String num;List<String> ans;int target;public List<String> addOperators(String num, int target) {this.n = num.length();this.num = num;this.target = target;this.ans = new ArrayList<String>();StringBuffer expr = new StringBuffer();dfs(expr, 0, 0, 0);return ans;}public void dfs(StringBuffer sba, long sum, long prepareMultiply, int index) {StringBuffer sb = new StringBuffer(sba);if (index == n) {if (sum == target) {ans.add(sb.toString());}return;}int sign = sb.length();if (index > 0) {sb.append("0");}long val = 0;for (int i = index; i < n && (i == index || num.charAt(index) != '0'); i++) {val = val * 10 + (num.charAt(i) - '0');sb.append(num.charAt(i));if (index == 0) {dfs(sb, val, val, i + 1);continue;}sb.setCharAt(sign, '+');dfs(sb, sum + val, val, i + 1);sb.setCharAt(sign, '-');dfs(sb, sum - val, -val, i + 1);sb.setCharAt(sign, '*');dfs(sb, sum - prepareMultiply + prepareMultiply * val, prepareMultiply * val, i + 1);}}
}