This is the 11th day of my participation in the Novembermore Challenge.The final text challenge in 2021
Some of the problems in the LeetCode problem set may have been skipped directly, so clean up the previous brush with LeetCode
51. The N queens
The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.
The figure above shows one solution to the eight Queens problem.
Given an integer n, return all the different solutions to the n-queen problem.
Each solution contains an explicit chess placement scheme for the n-queen problem, in which ‘Q’ and ‘.’ represent queens and slots, respectively.
Example:
Input: 4 output: [[. “q..”, / / solution 1… “Q”, “Q…”, “.. Q. “].
[“..Q.”, // Solution 2 “Q…”, “…Q”, “.q..”] There are two different solutions to the queen problem.
class Solution {
public static List<List<String>> output;
public List<List<String>> solveNQueens(int n) {
output = new ArrayList<>();
// Declare an array of length N to represent that the NTH row pieces are in the result[n] column
int[] result = new int [n];
calnQueens(0, n, result);
return output;
}
// n queen row represents the row computed to the first row
private static void calnQueens(int row, int n, int[] result){
if (row == n){
// Line NTH means you've got a solution
// Add the result to the output list based on the result array
getPrint(result);
return;
}
// If it is not the NTH row, it is necessary to continue to determine which row the chessman should be in
for (int column = 0; column < n; column++){
// Check whether row 1 is placed in the column
if (isOK(row, column, result)){
result[row] = column;
// Determine the next row recursively
calnQueens(row + 1, n, result);
}
// the operation corresponding to the next column is column++}}Row indicates the number of rows. Column indicates the number of columns. Result indicates the position of the pawn in the NTH row that meets the rule
private static boolean isOK(int row, int column, int[] result){
// Check whether the position of the piece is correct
for (int i = 0; i < row; i++){
// The first condition excludes problems in the same column
// The second condition excludes the lower left corner of the diagonal column
// The third condition excludes the lower right corner of the diagonal column
if (column == result[i] || column == result[i] - row + i || column == result[i] + row - i){
return false; }}return true;
}
private static void getPrint(int[] result){
List<String> one = new ArrayList<>();
for (int row = 0; row < result.length; row++){
// A StringBuilder in one line
StringBuilder str = new StringBuilder();
for (int column = 0; column < result.length; column++){
if (column == result[row]){
str.append("Q");
}else{
str.append("."); } } one.add(str.toString()); } output.add(one); }}Copy the code52. Queen II
The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.
The figure above shows one solution to the eight Queens problem.
Given an integer n, return the number of different solutions for n queens.
Example:
Input: 4 Output: 2 Explanation: 4 Queen problem has the following two different solutions. [[“.q.”, // Solution 1 “…Q”, “Q…”, “..Q.”],
[“..Q.”, // Solution 2 “Q…”, “…Q”, “.q..”] ]
class Solution {
/** * Records whether a column has a queen */
private boolean col[];
/** * Records whether a certain diagonal (upper left and lower right) has been placed by the queen (the corresponding position of a diagonal is X-y + n-1) */
private boolean dia1[];
/** * Records whether a diagonal line (lower left and upper right) has been placed by a queen (the corresponding position of a diagonal line is X + Y) */
private boolean dia2[];
public int totalNQueens(int n) {
// The solution to problem 51 can still be used, but the question is whether there is a better way
col = new boolean[n];
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
return putQueen(n, 0);
}
/** * recursive backtracking is placed in queen **@paramN Number of queens to be placed *@paramIndex Number of queens */
private int putQueen(int n, int index) {
int res = 0;
if (index == n) {
return 1;
}
// Attempts to place the queen in column I of the index row
for (int i = 0; i < n; i++) {
if(! col[i] && ! dia1[i - index + n -1] && !dia2[i + index]) {
/ / recursion
col[i] = true;
dia1[i - index + n - 1] = true;
dia2[i + index] = true;
res += putQueen(n, index + 1);
/ / back
col[i] = false;
dia1[i - index + n - 1] = false;
dia2[i + index] = false; }}returnres; }}Copy the code53. Maximum suborder sum
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
Example:
Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4], output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6. Advanced:
If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.
Each time the loop adds the current value, it keeps track of the maximum value and if it's less than 0, it starts at 0Copy the codeclass Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0)
sum += num;
else
sum = num;
res = Math.max(res, sum);
}
returnres; }}Copy the code54. Spiral matrix
Given a matrix containing m x n elements (m rows, n columns), return all elements in the matrix in a clockwise spiral order.
Example 1:
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] output:,2,3,6,9,8,7,4,5 [1] example 2:
Input: [[1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]] output:,2,3,4,8,12,11,10,9,5,6,7 [1]
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new LinkedList<>();
if(matrix.length==0) return result;
int upBound = 0;
int rightBound = matrix[0].length-1;
int leftBound = 0;
int downBound = matrix.length-1;
while(true) {// Top row, left to right
for(int i=leftBound; i<=rightBound; ++i)
result.add(matrix[upBound][i]);
if(++upBound>downBound) break; // If the top row is lower than the bottom row, the loop is finished, and the corresponding row is moved down here
// Right column, from top to bottom
for(int i=upBound; i<=downBound; ++i)
result.add(matrix[i][rightBound]);
if(--rightBound<leftBound) break; // If the right row is closer to the right than the left row, the loop is over,
// Bottom row, right to left
for(int i=rightBound; i>=leftBound; --i)
result.add(matrix[downBound][i]);
if(--downBound<upBound) break; // If the bottom row is higher than the top row, the loop is finished.
// Left column, from bottom to top
for(int i=downBound; i>=upBound; --i)
result.add(matrix[i][leftBound]);
if(++leftBound>rightBound) break; // If the left row is closer to the right than the right row, the loop is over,
}
returnresult; }}Copy the code55. Jump games
Given an array of non-negative integers, you start at the first position in the array.
Each element in the array represents the maximum length you can jump at that location.
Determine if you can reach the last position.
Example 1:
Input: [2,3,1,1,4] output: true explanation: we can jump 1 step from position 0 to position 1, and then jump 3 steps from position 1 to the last position. Example 2:
Input: [3,2,1,0,4] Output: false Explanation: No matter what, you will arrive at index 3. But that position has a maximum jump length of 0, so you’ll never get to the last position.
Iterate through the array from back to front, truncating the following elements if they reach the last line. Otherwise, if you go ahead and have more than one element left at the end of the weak element, it can be judged to be false. Otherwise it's trueCopy the codeclass Solution {
public boolean canJump(int[] nums) {
int n=1;
for(int i=nums.length-2; i>=0; i--){if(nums[i]>=n)
{
n=1;
}
else
{
n++;
}
if(i==0&&n>1)
{
return false; }}return true; }}Copy the code56. Consolidated intervals
Given a set of intervals, merge all overlapping intervals.
Example 1:
Input: [[1, 3], [2, 6], [8, 10], [15, 17]] output: [[1, 6], [8, 10], [15, 17]] : interval [1, 3] and [2, 6] overlap, merge them into [1, 6]. Example 2:
Input: [[1, 4], [4, 5]] output: [[1, 5]] : interval [1, 4] and [4, 5] can be seen as overlapping range.
class Solution {
public int[][] merge(int[][] arr) {
if(arr == null || arr.length<=1)
return arr;
List<int[]> list = new ArrayList<>();
//Arrays.sort(arr,(a,b)->a[0]-b[0]);
// Compare the numbers on the left of the two groups
//[1,3] [2,4] compare 1 and 2
Arrays.sort(arr,new Comparator<int[] > () {@Override
public int compare(int[] a,int[] b){
return a[0]-b[0]; }});int i=0;
int n = arr.length;
while(i<n){
int left = arr[i][0];
int right = arr[i][1];
// If the right side of the current interval is in contact with the left side of the next interval, the right side of the current interval is selected as the largest of the two intervals.
// Merge the two ranges
while(i<n-1 && right>=arr[i+1] [0]){
right = Math.max(right,arr[i+1] [1]);
i++;
}
list.add(new int[] {left,right});
i++;
}
return list.toArray(new int[list.size()][2]); }}Copy the code57. Insert interval
Give an unoverlapped list of intervals sorted by their starting endpoint.
To insert a new range in a list, you need to make sure that the range in the list is still ordered and does not overlap (you can merge the range if necessary).
Example 1:
Input: intervals = [[1, 3], [6, 9]], newInterval = (2, 5) output: [[1, 5], [6, 9]] example 2:
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12 dec]], newInterval = [4, 8] output: [[1, 2], [3, 10], [12 dec]] : This is because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
In fact, it's the same as the previous problem, but instead of merging multiple intervals into a single interval, it's almost the same as the previous problem, but in this problem, it's only going to pass through one interval, using a stackCopy the codeclass Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// Create a new range array, add the new range to the array,
int[][] newIntervals = new int[intervals.length + 1] []; System.arraycopy(intervals,0, newIntervals, 0, intervals.length);
newIntervals[intervals.length] = newInterval;
// Select * from the Comparator's compare method.
Lambda expressions are used for custom sorting
Arrays.sort(newIntervals, (a, b) -> a[0] - b[0]);
Stack<int[]> stack = new Stack<>();
for (int[] num : newIntervals) {
if (stack.isEmpty()) { // If the stack is empty, push the data
stack.push(num);
continue;
}
int[] arr = stack.peek(); // Pop up a range
if (arr[1] >= num[0]) { // If the right side of the previous interval is larger than the left side of the current interval, we can merge and put the newly merged interval on the stack
int[] combine = {arr[0], Math.max(arr[1], num[1])};
stack.pop();
stack.push(combine);
} else { // If not, press the current onestack.push(num); }}return stack.toArray(new int[0][]);
}
}
Copy the code58. Length of the last word
Given a string s containing only uppercase and lowercase letters and Spaces’ ‘, return the length of its last word.
If the string scrolls from left to right, the last word is the last word to appear.
If the last word does not exist, return 0.
Note: A word is the largest substring that consists of only letters and does not contain any Spaces.
Example:
Input: “Hello World” Output: 5
Word length +1 If a space is found, it indicates that the current word has been countedCopy the codeclass Solution {
public int lengthOfLastWord(String s) {
int count=0;
for(int i=s.length()-1; i>=0; i--) {if(s.charAt(i)! =' ') {
count++;
}else if(count>0) {returncount; }}returncount; }}Copy the code59. Spiral matrix II
Given a positive integer n, generate a square matrix containing all elements from 1 to n2 in a clockwise spiral order.
Example:
Input: 3 output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
And this is similar to the spiral matrix, except that the problem is to return a one-dimensional matrix by the matrix and this problem is to create a matrix by the number of rowsCopy the codeclass Solution {
public int[][] generateMatrix(int n) {
int[][] arr = new int[n][n];
int c = 1, j = 0;
while (c <= n * n) {
for (int i = j; i < n - j; i++)
arr[j][i] = c++;
for (int i = j + 1; i < n - j; i++)
arr[i][n - j - 1] = c++;
for (int i = n - j - 2; i >= j; i--)
arr[n - j - 1][i] = c++;
for (int i = n -j - 2; i > j; i--)
arr[i][j] = c++;
j++;
}
returnarr; }}Copy the code60. Permutation K
Give the set [1,2,3… n] in which all elements have n! Kind of arrangement.
All permutations are listed in order of size and marked one by one. When n = 3, all permutations are as follows:
“123” “132” “213” “231” “312” “321” Given n and k, return the KTH permutation.
Description:
Given the range of n is [1, 9]. Given the range of k is [1, n!]. . Example 1:
Input: n = 3, k = 3 Output: “213”
Input: n = 4, k = 9
However, the efficiency is still touching. It can be solved by mathematical method, because the numbers are all continuous natural numbers starting from 1, and the order of the permutation can be deduced. For n=4, k=15, find the process of k=15: 1 + all permutations of 2,3, and 4 (3! 2 + all permutations of 1,3, and 4 (3! 3, 1 + the full permutation of 2,4 (2! 3 + all permutations of 1,2, and 4 (3! -------> 3, 2 + the full permutation of 1,4 (2! -------> 3, 2, 1 + the full permutation of 4 (1! -------> 3214 4 + full permutation of 1,2,3 (3! 3, 4 + the full permutation of 1,2 (2! 3, 2, 4 + the full permutation of 1 (1! Index = k/(n-1)! K is equal to k minus index times n minus 1 factorial. Index = k/(n-2)! K = k - index (n-2) factorial Index = k/(n-3)! = 0, so the third digit of the 15th digit is 1 update k, k is equal to k minus index times n minus 3 factorial. Index = k/(n-4)! Theta is equal to 0, which means that the fourth digit of the 15th digit is 4 and finally the 15th digit is 3214 when n is 4Copy the codeclass Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
// Candidate number
List<Integer> candidates = new ArrayList<>();
// The factorial of the denominator
int[] factorials = new int[n+1];
factorials[0] = 1;
int fact = 1;
for(int i = 1; i <= n; ++i) {
candidates.add(i);
fact *= i;
factorials[i] = fact;
}
k -= 1;
for(int i = n-1; i >= 0; --i) {
// Calculate the index of the candidate number
int index = k / factorials[i];
sb.append(candidates.remove(index));
k -= index*factorials[i];
}
returnsb.toString(); }}Copy the code