算法刷题-四数之和、缺失的第一个正数、N 皇后
算法刷题-四数之和、缺失的第一个正数、N 皇后
共饮一杯无
发布于 2023-02-10 09:55:00
发布于 2023-02-10 09:55:00
文章目录
四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 **注意：**答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [], target = 0
输出：[]提示：
- 0 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
long l_target = target;
Arrays.sort(nums);
List<List<Integer>> results = new ArrayList<>();
int N = nums.length;
for (int i = 0; i < N - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < N - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
for (int k = j + 1, l = N - 1; k < l; k++) {
if (k > j + 1 && nums[k] == nums[k - 1])
continue;
while (k < l && (l_target - nums[i] - nums[j] - nums[k] - nums[l]) < 0) {
l--;
}
if (k >= l) {
break;
}
if ((target - nums[i] - nums[j] - nums[k] - nums[l]) == 0) {
List<Integer> item = new ArrayList<>();
item.add(nums[i]);
item.add(nums[j]);
item.add(nums[k]);
item.add(nums[l]);
results.add(item);
}
}
}
}
return results;
}
}缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
**进阶：**你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1：
输入：nums = [1,2,0]
输出：3示例 2：
输入：nums = [3,4,-1,1]
输出：2示例 3：
输入：nums = [7,8,9,11,12]
输出：1提示：
- 0 <= nums.length <= 300
- -231 <= nums[i] <= 231 - 1
以下程序实现了这一功能，请你填补空白处内容：
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int contains = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
contains++;
break;
}
}
if (contains == 0) {
return 1;
}
for (int i = 0; i < n; i++) {
_________________;
}
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
nums[a - 1] = -Math.abs(nums[a - 1]);
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}答案：
if ((nums[i] <= 0) || (nums[i] > n)) {
nums[i] = 1;
}N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n_ _皇后问题 的解决方案。
在这里插入图片描述
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
提示：
- 1 <= n <= 9
- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
以下程序实现了这一功能，请你填补空白处内容：
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
int[] queenList = new int[n];
placeQueen(queenList, 0, n, res);
return res;
}
private void placeQueen(int[] queenList, int row, int n, List<List<String>> res) {
if (row == n) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 0; i < n; i++) {
String str = "";
for (int col = 0; col < n; col++) {
if (queenList[i] == col) {
str += "Q";
} else {
str += ".";
}
}
list.add(str);
}
res.add(list);
}
for (int col = 0; col < n; col++) {
if (isValid(queenList, row, col)) {
queenList[row] = col;
________________________;
}
}
}
private boolean isValid(int[] queenList, int row, int col) {
for (int i = 0; i < row; i++) {
int pos = queenList[i];
if (pos == col) {
return false;
}
if (pos + row - i == col) {
return false;
}
if (pos - row + i == col) {
return false;
}
}
return true;
}
}答案：
placeQueen(queenList, row + 1, n, res);本文内容到此结束了， 如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问💬欢迎各位指出。 主页：共饮一杯无的博客汇总👨💻 保持热爱，奔赴下一场山海。🏃🏃🏃
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录