算法刷题-四数之和、缺失的第一个正数、N 皇后

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 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);

本文内容到此结束了
如有收获欢迎点赞👍收藏💖关注✔️您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位指出。
主页共饮一杯无的博客汇总👨‍💻

保持热爱奔赴下一场山海。🏃🏃🏃