This is the 12th 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
61. Rotate linked lists
Given a linked list, rotate the list by moving each node of the list k positions to the right, where k is non-negative.
Example 1:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: k = 2, 4 – > 5 – > 1 – > 2 – > 3 – > NULL explanation: spin to the right step 1:1 – > 5 – > 4 – > 2 – > 3 – > NULL spin to the right step 2: 4 – > 5 – > 1 – > 2 – > 3 – > NULL example 2:
Input: 0 – > 1 – > 2 – > NULL, k = 4 output: 1 – > 2 – > 0 – > NULL explanation: spin to the right step 1:1 – > 2 – > 0 – > NULL spin to the right step 2:1 – > 2 – > 0 – > NULL spin to the right step 3: 0->1->2->NULL Rotate 4 steps to the right: 2->0->1->NULL
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null||k==0) {return head;
}
ListNode cursor=head;
ListNode tail=null;/ / the tail pointer
int length=1;
while(cursor.next! =null)// Loop to get the total length
{
cursor=cursor.next;
length++;
}
int loop=length-(k%length);// Get the number of cycles
tail=cursor;// point to the endpoint
cursor.next=head;// Change to a circular list
cursor=head;// point to the header
for(int i=0; i<loop; i++){// Start the loop
cursor=cursor.next;
tail=tail.next;
}
tail.next=null;// Change to singly linked list
return cursor;// return the current header}}Copy the code62. Different paths
A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).
The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).
How many different paths are there?
For example, the image above shows a 7 x 3 grid. How many possible paths are there?
Note: The values of m and n are less than 100.
Example 1:
Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.
- Right -> right -> down
- Right -> down -> right
- Down -> right -> right
Example 2:
Input: m = 7, n = 3 Output: 28
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// If it's row 1 or column 1, the way to get there is 1
if (i == 0 || j == 0)
dp[i][j] = 1;
else {
// Each step can only be the row or column above the current position.
// Add those two methods together to get to the current position
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}}return dp[m - 1][n - 1]; }}Copy the code63. Different paths II
A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).
The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).
Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?
Obstacles and empty positions in the grid are represented by 1 and 0 respectively.
Note: The values of m and n are less than 100.
Example 1:
Input: [[0, 0], [0, 0] to [0, 0]] output: 2:3 x3 grid right in the middle there is a barrier. There are two different paths from the top left to the bottom right:
- Right -> right -> down -> down
- Down -> down -> right -> right
Source: LeetCode link: leetcode-cn.com/problems/un… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
class Solution {
public int uniquePathsWithObstacles(int[][] arr) {
if (arr == null || arr.length <= 0) {
return 0;
}
int rows = arr.length;
int cols = arr[0].length;
int[][] dp = new int[rows][cols];
for (int i = 0; i < cols; i++)
if (arr[0][i] == 1) {
dp[0][i] = 0;
break; // The default value is 0
}
else dp[0][i] = 1;
for (int i = 0; i < rows; i++)
if (arr[i][0] = =1) {
dp[i][0] = 0;
break; // The default value is 0
}
else dp[i][0] = 1;
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (arr[i][j] == 1) dp[i][j] = 0; // If there is an obstacle, it is 0
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // dpdpdp}}return dp[rows - 1][cols - 1]; }}Copy the code64. Minimum path sum
Given an M x N grid of non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.
Note: you can only move one step down or right at a time.
Example:
,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum.
The first row and the first column are the corresponding values in the gridCopy the codeclass Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length < 1 || grid[0] = =null || grid[0].length < 1) {
return 0;
}
int row = grid.length;
int col = grid[row - 1].length;
int dp[][] = new int[row][col];
dp[0] [0] = grid[0] [0];
for (int i = 1; i < row; i++) { dp[i][0] = dp[i - 1] [0] + grid[i][0];
}
for (int i = 1; i < col; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {// The path value is the smallest of the two methods
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; }}return dp[row - 1][col - 1]; }}Copy the code65. Significant figures
Verifies that a given string can be interpreted as a decimal number.
Such as:
"0" => true "0.1" => true "ABC" => False "1 A "=> false" 2E10 "=> true" -90e3 "=> true" 1e" => False "e3" => False "6E-1" => true "99E2.5" => false "53.5E93" => true "--6" => false "-+3" => false "95A54E53" => FalseCopy the codeNote: We intentionally stated the problem in a vague way. Before you implement code, you should think about all possible scenarios beforehand. Here’s a list of characters that might exist in a valid decimal number:
The numbers 0-9 exponent -” e” positive/negative sign -” +”/”-” decimal point -“.” Of course, in the input, the context of these characters is also important.
Updated on February 10, 2015: the form of C++ functions has been updated. If you still see your function accepting const char *, click the reload button to reset your code.
Source: LeetCode link: leetcode-cn.com/problems/va… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
class Solution {
char[] chars;
boolean point = false;// Does it have a decimal part
boolean exponent = false;// Whether there is an exponential part
public boolean isNumber(String s) {
s = s.trim();/ / to space
int length = s.length();
if(length == 0) {return false;
}
chars = s.toCharArray();// Transpose array
String[] ss = s.split("e");// The e delimited array is in two parts
if(ss.length == 0) {// Only e error
return false;
}
if(ss[0].length() == 0) return false;// If the part before e is empty error
if(ss[0].length() < length) exponent = true;// If the first part of the character length is less than the string length, there is an exponential part
if(ss[0].length() == length -1) {return false;
}
String[] pre = ss[0].split("\ \.");// Separate with decimal points
if(pre.length == 0) {// If only the decimal point error
return false;
}
if(pre[0].length() < ss[0].length()) point = true;
// If the first part is smaller than the original length, there is a decimal part
boolean result = pre(0, pre[0].length());
// The integer part is correct
result = result && middle(pre[0].length()+1, ss[0].length());
// The middle part is correct
if(exponent){// If there is an exponential part
result = result && is(ss[0].length() +1, length);
// The index part is correct
}
return result;
}
public boolean pre(int i, int length){// Check whether the integer part is correct
if(i >= length){
// If the integer part is empty, since.1 is also true, return true first
return true;
}
// The first character is a plus or minus sign, I +1
if(chars[i] == '+' || chars[i] == The '-') {
i++;
}
if(i == length && ! point){// If there is no decimal part, but only positive and negative, an error is returned
return false;
}
for(; i < length; i++){
// Iterate over the integer part
if(chars[i] < '0' || chars[i] > '9') {// return an error if it is not 0-9
return false; }}// At this point, the integer part is correct
return true;
}
public boolean middle(int i, int length){// The decimal part
if(i >= length && point ){
// If there is a decimal point, but the decimal part is empty
if(chars[i - 2] > ='0' && chars[i - 2] < ='9') {
// Return correct if there are numbers before the decimal point
return true;
}
// No error is returned
return false;
}
for(; i < length; i++){// Walk through the middle section
if(chars[i] < '0' || chars[i] > '9') {// return an error if it is not 0-9
return false; }}return true;
}
public boolean is(int i, int length){// Index part
if(i == 1) {If e is empty, an error is returned
return false;
}
// The exponent can also be positive or negative
if(chars[i] == '+' || chars[i] == The '-') {
i++;
}
// Return an error
if( i == length){
return false;
}
for(; i < length; i++){
// Iterate over the index section
if(chars[i] < '0' || chars[i] > '9') {// No 0-9 return error
return false; }}return true; }}Copy the code66. Plus one
Given a non-negative integer represented by a non-empty array of integers, add one to that number.
The highest digit is stored at the beginning of an array, where each element stores only a single digit.
You can assume that this integer does not start with zero, except for the integer 0.
Example 1:
Input: [1,2,3] output: [1,2,4] explanation: the input array represents the number 123. Example 2:
Input: [4,3,2,1] output: [4,3,2,2] explanation: the input array represents the number 4321.
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if(digits[i] ! =9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
// Jump out of the for loop, indicating that all numbers are 9
int[] temp = new int[digits.length + 1];
temp[0] = 1;
returntemp; }}Copy the code67. Binary summation
Given two binary strings, return their sum (in binary).
The input is a non-empty string containing only the digits 1 and 0.
Example 1:
Input: a = “11”, b = “1” Output: “100” Example 2:
Input: a = “1010”, b = “1011” output: “10101”
class Solution {
public String addBinary(String a, String b) {
if(a == null || a.length() == 0) return b;
if(b == null || b.length() == 0) return a;
StringBuilder stb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int c = 0; / / carry
while(i >= 0 || j >= 0) {
if(i >= 0) c += a.charAt(i --) - '0';
if(j >= 0) c += b.charAt(j --) - '0';
stb.append(c % 2);
c >>= 1;
}
String res = stb.reverse().toString();
return c > 0 ? '1'+ res : res; }}Copy the code68. Align text left and right
Given an array of words and a maxWidth of length, retype the words so that each line has exactly maxWidth characters and is aligned right and left.
You should use a “greedy algorithm” to place a given word; That is, put as many words in each line as possible. Padding with Spaces “if necessary, so that each line has exactly maxWidth characters.
The number of Spaces between words should be distributed as evenly as possible. If the space between words on a line is not evenly distributed, more space is placed on the left than on the right.
The last line of text should be left aligned and no extra Spaces inserted between words.
Description:
A word is a sequence of characters that is not a space character. The length of each word is greater than 0 and less than or equal to maxWidth. The input word array words contains at least one word. Example:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 ["justification ", "justification ", "justification. "] Words = ["What","must","be"," Acknowledgment ","shall","be"] maxWidth = 16 ["What must be", "Acknowledgment ", "shall be"] Explanation: Note that the format of the last line should be" shall be" instead of "shall be", because the last line should be aligned left, not left. The second line is also left justified because it contains only one word. Example 3: Enter: words = ["Science","is","what","we","understand","well","enough","to","explain", "To", "a", "computer.", "Art", "is", "everything", "else" and "we", "do"] maxWidth = 20 output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]Copy the codeclass Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ret = new ArrayList<>();
int index = 0;
while(index < words.length){
int cur = index, len = 0;
// len + words[cur].length() + cur-index is the length of a space between words
while(cur < words.length && len + words[cur].length() + cur - index <= maxWidth){
// Calculate the pure word length
len = len + words[cur++].length();
}
cur--;
// System.out.println(cur + " " + len);
StringBuilder sb = new StringBuilder();
// Differentiate the last line
if(cur == words.length - 1) {for(int i = index; i <= cur; i++){
sb.append(words[i]);
if(i < cur){
sb.append(' '); }}}else{
int base = cur > index ? (maxWidth - len) / (cur - index) : (maxWidth - len);
String baseStr = genSpace(base);
int left = cur > index ? (maxWidth - len) % (cur - index) : 0;
String leftStr = genSpace(base + 1);
for(int i = index; i <= cur; i++){
sb.append(words[i]);
if(i < cur){
sb.append(left > 0? leftStr : baseStr); left--; }}}if(sb.length() < maxWidth){
sb.append(genSpace(maxWidth - sb.length()));
}
ret.add(sb.toString());
index = cur + 1;
}
return ret;
}
private String genSpace(int n){
char[] cs = new char[n];
Arrays.fill(cs, ' ');
return newString(cs); }}Copy the code69. Square root of x
Implement the int SQRT (int x) function.
Calculates and returns the square root of x, where x is a non-negative integer.
Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.
Example 1:
Input: 4 Output: 2 Example 2:
Input: 8 Output: 2 Description: The square root of 8 is 2.82842… Because the return type is an integer, the decimal part will be omitted.
0x5F3759df is the inverse square rootCopy the codeclass Solution {
public int mySqrt(int x) {
long t = x;
t = 0x5f3759df - (t >> 1);
while(! (t*t <= x && (t+1)*(t+1) > x))
t = (x/t + t)/2;
return (int)t; }}Copy the code70. Climb the stairs
Suppose you’re climbing stairs. It takes n steps to get to the top.
You can climb one or two steps at a time. How many different ways can you climb to the top?
Note: given n is a positive integer.
Example 1: Input: 2 Output: 2 Description: There are two ways to climb to the top of the building. 1. Level 1 + Level 2. Level 2 Example 2: Input: 3 Output: 3 Description: There are three ways to climb to the top of the building. 3. 1 + 1 + 1 4. 1 + 2 5. 2 + 1Copy the codeclass Solution {
// Sort of like Fibonacci numbers
public int climbStairs(int n) {
if (n <= 1)
return 1;
else if (n == 2)
return 2;
else {
int res = 0;
int i = 1, j = 2;
int k = 3;
while (k <= n) {
// The current method comes from the sum of the previous two staircase methods
// The number of steps in the previous step is the current number of steps
// Take the first two steps
res = i + j;
i = j;
j = res;
k++;
}
returnres; }}}Copy the code