The original intention of writing this article is to sort out and review the questions you have brushed
1. Sum of two numbers
1. Sum of two numbers
Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot be repeated in the answer.
You can return answers in any order.
Example 1:
Input: num = [2,7,11,15], target = 9
Output: [0,1]
Explanation: because num [0] + num [1] = = 9, return [0, 1].
Solution 1: violence, too slow
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int>a;
for (int i = 0; i < nums.size() - 1; i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target);
{
a.push_back(i);
a.push_back(j);
return a;
}
}
}
return a;
}
};
Solution 2: hash
Note: unordered in this question_ The second value of the map is I, and I may be 0. Therefore, if (target - num [i]) cannot be used when judging target - num [i], and an iterator is required
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int>a;
vector<int>arr;
for (int i = 0; i < nums.size(); ++i)
{
unordered_map<int, int>::iterator it = a.find(target - nums[i]);
if (it != a.end())
{
arr.push_back(it->second);
arr.push_back(i);
break;
}
else
a[nums[i]] = i;
}
return arr;
}
};
Solution 3: hash
In order to solve the problem of determining target - nums[i] in solution 2, an iterator is required, which can make a[nums[i]] = i+1;
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int>a;
vector<int>arr;
for (int i = 0; i < nums.size(); ++i)
{
if (a[target - nums[i]])
{
arr.push_back(a[target - nums[i]]-1);
arr.push_back(i);
break;
}
else
a[nums[i]] = i+1;
}
return arr;
}
};
2. Add two numbers
2. Add two numbers
Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number.
Please add the two numbers and return a linked list representing sum in the same form.
You can assume that neither number starts with 0 except the number 0.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
Refer to the official explanation
As long as L1 or L2 is not equal to NULL, it is always in the loop
Set three variables a, b, now and tmp (carry, initial value is 0)
a: The value of L1. If L1 is NULL, it is 0
b: The value of L2. If L2 is NULL, it is 0
now:a+b+tmp
tmp record carry: now/10
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* head = NULL;
ListNode* tail = NULL;
int tmp = 0;
int a, b, now;
while (l1 || l2)
{
a = l1 ? l1->val : 0;
b = l2 ? l2->val : 0;
now = a + b + tmp;
tmp = now / 10;
if (!head)//head is empty
{
head = tail = new ListNode(now % 10);
}
else
{
tail->next = new ListNode(now % 10);
tail = tail->next;
}
if (l1)
{
l1 = l1->next;
}
if (l2)
{
l2 = l2->next;
}
}
if (tmp)
{
tail->next = new ListNode(tmp);
}
return head;
}
};
I suddenly found that the time and space efficiency written in C were much better
But the C + + program is more concise and readable
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int len1 = 0, len2 = 0;
struct ListNode* p;
struct ListNode* q;
struct ListNode* head;
struct ListNode* r;
for (p = l1; p->next != NULL; p = p->next)
len1++;
for (q = l2; q->next != NULL; q = q->next)
len2++;
if (len1 > len2)
{
p = head = l1;
q = l2;
}
else
{
p = head = l2;
q = l1;
}
int tmp = 0;
int val;
while (p != NULL)
{
if (q != NULL)
{
val=p->val;
p->val = (p->val + q->val + tmp) % 10;
tmp = (val + q->val + tmp) / 10;
if (tmp == 1 && p->next == NULL)
{
r = (struct ListNode*)malloc(sizeof(struct ListNode));
p->next = r;
r->val = tmp;
r->next = NULL;
break;
}
q = q->next;
}
else
{
val=p->val;
p->val=(p->val+tmp)%10;
tmp=(val+tmp)/10;
if (p->next == NULL && tmp == 1)
{
r = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(r != NULL);
r->val = tmp;
r->next = NULL;
p->next = r;
break;
}
}
p = p->next;
}
return head;
}
3. Longest substring without repeated characters
3. Longest substring without repeated characters
Given a string s, please find the length of the longest substring that does not contain duplicate characters.
Example 1:
Enter: s = "abcabcbb"
Output: 3
Explanation: because the longest substring without repeated characters is "abc", its length is 3.
Note: the substring has sequence and the substring has no sequence
Solution 1: hash, very poor efficiency
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
unordered_map<char, int>a;
int max = 0;
int num = 0;
int i = 0, j = 0;
for (i = 0; i < s.length(); i++)
{
num = 0;
a.clear();
for (j = i; j < s.length(); j++)
{
if (a.empty() || a[s[j]] == 0)
{
a[s[j]]++;
num++;
}
else
{
max = fmax(max, num);
break;
}
}
if (j == s.length())
{
max = fmax(max, num);
if (max == s.length())
break;
}
}
return max;
}
};
Solution 2: hash + sliding window
Efficiency has improved a little
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
if (s.size() == 0)
return 0;
unordered_set<char> a;
int max = 0;
int left = 0;
for (int right = 0; right < s.size(); right++)
{
while (a.find(s[right]) != a.end())//Iterator, when not equal to, means found
{
a.erase(s[left]);
left++;
}
max = fmax(max, right - left + 1);
a.insert(s[right]);
}
return max;
}
};
5. Longest palindrome substring
5. Longest palindrome substring
Give you a string s and find the longest palindrome substring in S.
Example 1:
Enter: s = "bad"
Output: "bab"
Explanation: "aba" is also the answer to the question.
Dynamic planning, take a good look at the official solution, and you can understand it several times!!! Then practice more
class Solution
{
public:
string longestPalindrome(string s)
{
int n = s.length();
if (n < 2)
return s;
vector<vector<int>>dp(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
dp[i][i] = true;
}
int begin = 0;
int maxlen = 1;
for (int len = 2; len <= n; len++)
{
for (int left = 0; left < n; left++)
{
int right = len + left - 1;
if (right >= n)
break;
if (s[left] != s[right])
{
dp[left][right] = false;
}
else
{
if (right - left < 3)
{
dp[left][right] = true;
}
else
{
dp[left][right] = dp[left + 1][right - 1];
}
}
if (dp[left][right] && right - left + 1 > maxlen)
{
maxlen = right - left + 1;
begin = left;
}
}
}
return s.substr(begin, maxlen);
}
};
Here is a blogger I like very much: Code Capriccio Solution to the problem
**Define dp[i] [j]: * * whether the substring of the range [i,j] is a palindrome substring. It is true, otherwise it is false
**Initialization: * * false
When s[i] is equal to s[j], there are three cases as follows
Case 1: the subscript i is the same as j, and the same character, such as a, is of course a palindrome substring
Case 2: the difference between subscripts i and j is 1. For example, aa is also a text substring
Case 3: subscript: when the difference between I and j is greater than 1, such as cabac, s[i] and s[j] are the same. We can see whether the interval I and j is a palindrome substring depends on whether aba is a palindrome. Then the interval of aba is i+1 and j-1. Whether this interval is a palindrome depends on whether DP [i+1] [J - 1] is true.
In case 3, dp[i] [j] is assigned true according to whether dp[i + 1] [j - 1] is true.
dp[i + 1] [j - 1] is in the lower left corner of dp[i] [j]
Therefore, we must traverse from bottom to top and from left to right, so as to ensure that dp[i + 1] [j - 1] is calculated.
class Solution
{
public:
string longestPalindrome(string s)
{
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
int maxlenth = 0;
int left = 0;
int right = 0;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] == s[j]) {
if (j - i <= 1) { // Cases I and II
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // Situation III
dp[i][j] = true;
}
}
if (dp[i][j] && j - i + 1 > maxlenth) {
maxlenth = j - i + 1;
left = i;
right = j;
}
}
}
return s.substr(left, right - left + 1);
}
};
6. Z igzag transformation
A given string s is arranged in a zigzag manner from top to bottom and from left to right according to the given number of rows numRows.
For example, when the input string is "paypalishing" and the number of lines is 3, the arrangement is as follows:
P A H N
A P L S I I G
Y I R
After that, your output needs to be read line by line from left to right to produce a new string, such as "PAHNAPLSIIGYIR".
Please implement this function to transform the string to the specified number of lines:
string convert(string s, int numRows);
Example 1:
Enter: s = "paypalishing", numRows = 3
Output: "PAHNAPLSIIGYIR"
There is another story about this question. This is the written test question of the first company I invested in autumn
class Solution
{
public:
string convert(string s, int numRows)
{
if (numRows == 1)
return s;
int tmp = 2 * (numRows - 1);
string s1;
for (int k = 0; k < numRows; k++)
{
for (int j = 0; j < s.length(); j++)
{
if ((j % tmp == k) || (j % tmp == tmp - k))
{
s1.push_back(s[j]);
}
}
}
return s1;
}
};
I feel it is more difficult to sort out the problem solution than before. This time, I found a new idea in the comment area, which comes from Krahets
First create a two-dimensional array of numRows, initialize i=0, flag=-1 (this - 1 is great)
The idea is: first assign values to each row of one-dimensional array in order. The zigzag will change the direction in row 0 and numRows. Therefore, when I0 | inumrows-1, flag=-flag will change the direction. Therefore, the initial value of flag is - 1
eg.1,2,3,4,5,6,7 numRows=3
1 for the first row, 2 for the second row, 3 for the third row, change direction,
i again came to the second row, 4 to the second row, 5 to the first row, change direction,
6 for the second line, 7 for the third line
(the first line corresponds to subscript 0, and the third line corresponds to subscript numRows-1)
class Solution
{
public:
string convert(string s, int numRows)
{
if (numRows == 1)
return s;
vector<vector<char>>a(numRows);
int i=0;
int flag=-1;
for(auto n:s)
{
a[i].push_back(n);
if(i==0||i==numRows-1)flag=-flag;
i+=flag;
}
string s1;
for(auto n:a)
{
for(auto m:n)
{
s1.push_back(m);
}
}
return s1;
}
};
7. Integer inversion
Give you a 32-bit signed integer x and return the result after reversing the number part in X.
If the inverted integer exceeds the range of 32-bit signed integers [− 231, 231 − 1], 0 is returned.
Assume that the environment does not allow the storage of 64 bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Finally came to a simple question
However, my previous code really can't bear to look directly at it. It's smelly and long. It's fun to post it. Ha ha
At that time, reverse, atoi and itoa were addicted to swap and string
class Solution
{
public:
void swap(char& a, char& b)
{
char tmp = a;
a = b;
b = tmp;
}
int reverse(int x)
{
if(x==0)return 0;
int left = 0;
string s = to_string(x);
int right = s.size()-1;
if (x < 0)
{
left++;
}
while (s[right] == '0')
{
right--;
}
string s1(s.begin() + left, s.begin() + right+1);
left=0;
right=s1.length()-1;
while (left <= right)
{
swap(s1[left], s1[right]);
left++;
right--;
}
long long num = 0;
for (int i = 0; i < s1.length(); i++)
{
num = num*10+s1[i] - '0';
}
if (x < 0)
num = -num;
if (num > -1 + pow(2, 31) || num < -pow(2, 31))
return 0;
return num;
}
};
Because it may be out of bounds, the type of x1 is long long. Just judge before return
Clear and pleasing to the eye
class Solution
{
public:
int reverse(int x)
{
long long x1 = 0;
while (x)
{
x1 = 10 * x1 + x % 10;
x /= 10;
}
if (x1 > INT_MAX || x1 < INT_MIN)
return 0;
return x1;
}
};
8. String to integer (atoi)
Please implement a myAtoi(string s) function to convert the string into a 32-bit signed integer (similar to the atoi function in C/C + +).
The algorithm of the function myAtoi(string s) is as follows:
-
Read in the string and discard useless leading spaces
-
Check whether the next character (assuming it is not at the end of the character) is a positive or negative sign, and read the character (if any). Determine whether the final result is a negative or positive number. If neither exists, the result is assumed to be positive.
-
Reads the next character until the next non numeric character is reached or the end of the input is reached. The rest of the string will be ignored.
Convert the numbers read in the previous steps to integers (i.e., "123" - > 123, "0032" - > 32). If no numbers are read in, the integer is 0. Change the symbol if necessary (starting from step 2). -
If the number of integers exceeds the range of 32-bit signed integers [− 231, 231 − 1], you need to truncate the integer to keep it within this range. Specifically, integers less than − 231 should be fixed as − 231, and integers greater than 231 − 1 should be fixed as 231 − 1.
-
Returns an integer as the final result.
be careful:
The blank characters in this question only include the space character ''.
Do not ignore any characters other than the leading space or the rest of the string after the number.
Very obvious string to number:
Condition 1: leading space skip
Condition 2: + - the symbol can be at the front (after the leading space)
Condition 3: return as long as it is not a number, and return int as long as it exceeds the int type range_ Max or INT_MIN
class Solution
{
public:
int myAtoi(string s)
{
int len = s.length();
int i = 0;
while (s[i] == ' ')
{
i++;
}
int flag = 1;
if (s[i] == '-')
{
flag = -flag;
i++;
}
else if (s[i] == '+')
{
i++;
}
long long x = 0;
while (i < len)
{
if (!isdigit(s[i]) || x > INT_MAX)
break;
x = x * 10 + (s[i] - '0');
i++;
}
x = x * flag;
if (x > INT_MAX)
{
return INT_MAX;
}
else if (x < INT_MIN)
{
return INT_MIN;
}
return x;
}
};
9. Number of palindromes
Give you an integer X. if x is a palindrome integer, return true; Otherwise, false is returned.
Palindromes are integers whose positive (left to right) and reverse (right to left) reads are the same. For example, 121 is a palindrome, not 123.
Example 1:
Input: x = 121
Output: true
class Solution
{
public:
bool isPalindrome(int x)
{
if (x < 0)
return false;
int x1 = x;
long long x2 = 0;
while (x1)
{
x2 = x2 * 10 + x1 % 10;
x1 /= 10;
}
if (x2 == x)
return true;
return false;
}
};
11. Container containing the most water
11. Container containing the most water
Give you n nonnegative integers a1, a2,..., an, each representing a point (i, ai) in the coordinate. Draw n vertical lines in the coordinates. The two endpoints of the vertical line i are (i, ai) and (i, 0). Find the two lines so that the container formed by them and the x-axis can hold the most water.
Note: you cannot tilt the container.
Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: the vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum value that the container can hold water (represented by the blue part) is 49.
c + + write two for loop timeout
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0;
int right = height.size() - 1;
int max = INT_MIN;
for (int i = 0; i < right; i++)
{
for (int j = i + 1; j <= right; j++)
{
int min = height[i] > height[j] ? height[j] : height[i];
max = fmax(max, min * (j - i));
}
}
return max;
}
};
Double finger Needling: always move the smaller end
Amount of water contained = the smaller of the numbers pointed to by the two pointers * the distance between the pointers
The core lies in: if the larger end is moved, Y - > Y1, when Y1 > y, the minimum value x at both ends still does not change when calculating the capacity, and the distance between them becomes smaller and the capacity becomes smaller; When Y1 < = y, the capacity must become smaller, so move the smaller end;
That is to say, we have excluded the column with a smaller section, and the capacity bounded by it will only be less than the current one, not more than the current one
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0;
int right = height.size() - 1;
int max = INT_MIN;
while(left<right)
{
if(height[left]<=height[right])
{
max=fmax(max,height[left]*(right-left));
left++;
}
else
{
max=fmax(max,height[right]*(right-left));
right--;
}
}
return max;
}
};
12. Integer to Roman numeral
Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
Character value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, the Roman numeral 2 is written as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.
Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:
- I can be placed to the left of V (5) and X (10) to represent 4 and 9.
- X can be placed to the left of L (50) and C (100) to represent 40 and 90.
- C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Give you an integer and convert it to Roman numerals.
Example 1:
Input: num = 3
Output: "III"
Very simple if... else
Just take special circumstances into account
class Solution
{
public:
string intToRoman(int num)
{
string s;
while (num)
{
if (num >= 1000)
{
s.push_back('M');
num -= 1000;
}
else if (num >= 900)
{
s.append("CM");
num -= 900;
}
else if (num >= 500)
{
s.push_back('D');
num -= 500;
}
else if (num >= 400)
{
s.append("CD");
num -= 400;
}
else if (num >= 100)
{
s.push_back('C');
num -= 100;
}
else if (num >= 90)
{
s.append("XC");
num -= 90;
}
else if (num >= 50)
{
s.push_back('L');
num -= 50;
}
else if (num >= 40)
{
s.append("XL");
num -= 40;
}
else if (num >= 10)
{
s.push_back('X');
num -= 10;
}
else if (num >= 9)
{
s.append("IX");
num -= 9;
}
else if (num >= 5)
{
s.push_back('V');
num -= 5;
}
else if (num >= 4)
{
s.append("IV");
num -= 4;
}
else if (num >= 1)
{
s.push_back('I');
num -= 1;
}
}
return s;
}
};
13. Roman numeral to integer
Write a switch... case... To accumulate, and then judge the special cases in 6. Note that it is - 2, - 20, - 200, not - 1, - 10, - 100, because it was added once more during the previous accumulation!!!
class Solution
{
public:
int num(char s)
{
int a;
switch (s)
{
case 'I':a = 1; break;
case 'V':a = 5; break;
case 'X':a = 10; break;
case 'L':a = 50; break;
case 'C':a = 100; break;
case 'D':a = 500; break;
case 'M':a = 1000; break;
}
return a;
}
int romanToInt(string s)
{
int sum = 0;
for (auto n : s)
{
sum += num(n);
}
for (int i = 0; i < s.size() - 1; i++)
{
if (s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X'))
sum -= 2;
else if (s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C'))
sum -= 20;
else if (s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))
sum -= 200;
}
return sum;
}
};
14. Longest common prefix
Write a function to find the longest common prefix in a string array.
Returns the empty string '' if there is no public prefix.
Example 1:
Input: strs = ["flower", "flow", "flight"]
Output: "fl"
Write a long function with a return value of string type to return the public prefix between two strings
Traverse in the longestCommonPrefix function. S is used to save the current shortest public prefix, s1 saves the public prefix of adjacent strings, and finally returns s
class Solution
{
public:
string longest(string a, string b)
{
string s;
for (int i = 0; i < a.length(); i++)
{
if (a[i] == b[i])
s.push_back(a[i]);
else
break;
}
return s;
}
string longestCommonPrefix(vector<string>& strs)
{
if (strs.size() == 1)
return strs[0];
string s;
string s1;
for (int i = 0; i < strs.size()-1; i++)
{
if(i==0)
s= longest(strs[i], strs[i + 1]);
else
{
s1 = longest(strs[i], strs[i + 1]);
s = s<s1 ? s : s1;
}
}
return s;
}
};
15. Sum of three
Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: the answer cannot contain duplicate triples.
Example 1:
Input: num = [- 1,0,1,2, - 1, - 4]
Output: [- 1, - 1,2], [- 1,0,1]]
What a long code
Sort and fix I. If num [i] > 0, exit the loop and make left=i+1, right = num Size () - 1, traverse and find the array with num [i] + num [left] + num [right] = = 0
Note: repeat the array
- Continue when I > 0 & & num [i] = = num [I - 1]
- When sum == 0, judge the situation of num [left] and num [left + 1], Num [right] and num [right - 1]
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>>arr;
if (nums.size() < 3)
{
return arr;
}
sort(nums.begin(), nums.end());
int left;
int right;
int sum;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
left = i + 1;
right = nums.size() - 1;
while (left < right)
{
sum = nums[i] + nums[left] + nums[right];
if (sum == 0)
{
arr.push_back({ nums[i],nums[left],nums[right] });
while (left < right && nums[left] == nums[left + 1])
{
left++;
}
while (left < right && nums[right] == nums[right - 1])
{
right--;
}
left++;
right--;
}
else if (sum > 0)
{
right--;
}
else
{
left++;
}
}
}
return arr;
}
};
16. Sum of the nearest three
Give you a length of n integer array nums and a target value target. Please select three integers from nums to make their sum closest to target.
Returns the sum of these three numbers.
It is assumed that there is only exactly one solution for each set of inputs.
Example 1:
Input: num = [- 1,2,1, - 4], target = 1
Output: 2
Explanation: the closest sum to target is 2 (- 1 + 2 + 1 = 2).
The idea is basically the same as that in the previous question. In the area closest to the target, mina and minb are newly set to save ABS (sum target) and sum respectively. When ABS (sum target) < mina, the values of mina and minb should be updated synchronously
class Solution
{
public:
int threeSumClosest(vector<int>& nums, int target)
{
if (nums.size() == 3)
{
return nums[0] + nums[1] + nums[2];
}
sort(nums.begin(), nums.end());
int mina= INT_MAX, minb=INT_MAX;
int left, right, sum;
for (int i = 0; i < nums.size(); i++)
{
left = i + 1;
right = nums.size() - 1;
while (left < right)
{
sum = nums[i] + nums[left] + nums[right];
if (sum == target)
{
return target;
}
else if (sum < target)
{
if (target-sum < mina)
{
mina = target - sum;
minb = sum;
}
left++;
}
else
{
if (sum- target < mina)
{
mina = sum - target;
minb = sum;
}
right--;
}
}
}
return minb;
}
};
19. Delete the penultimate node of the linked list
19. Delete the penultimate node of the linked list
Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
When writing exercises such as linked lists and binary trees that give initialization, you must realize the initialization process yourself!! Otherwise, the written interview will suffer
After each linked list problem, I will emphasize it in the problem solution
C implementation of initialization
struct ListNode
{
int val;
struct ListNode* next;
};
C + + implementation of initialization
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
First traverse to find the length of the linked list len, n=len-n, and change n into the order of positive order
There are two cases. When the new n==0, directly make head = head - > next; return head； that will do
The other is that i starts to traverse from 0. When i+1==n, skip the next node of the node
class Solution
{
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
int len = 0;
for (ListNode* p = head; p != NULL; p = p->next)
{
len++;
}
n = len - n;
if (n==0)
{
head = head->next;
return head;
}
int i = 0;
for (ListNode* p = head; p != NULL; p = p->next)
{
if (i + 1 == n)
{
ListNode* q = p->next;
p->next = q->next;
break;
}
i++;
}
return head;
}
};
I have done some linked list problems and found that Official solution Generally, dummy node is set, and its next pointer points to the head node of the linked list. In this way, we don't need to make special judgment on the head node.
Because the linked list is used to writing in C, it is pasted C and C + + official code
C
int getLength(struct ListNode* head)
{
int length = 0;
while (head)
{
++length;
head = head->next;
}
return length;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = 0, dummy->next = head;
int length = getLength(head);
struct ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; ++i)
{
cur = cur->next;
}
cur->next = cur->next->next;
struct ListNode* ans = dummy->next;
free(dummy);
return ans;
}
C++
class Solution
{
public:
int getLength(ListNode* head)
{
int length = 0;
while (head)
{
++length;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode* dummy = new ListNode(0, head);
int length = getLength(head);
ListNode* cur = dummy;
for (int i = 0; i < length - n; ++i)
{
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
//return dummy->next;
}
};
20. Valid brackets
Given a string s that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
- The left parenthesis must be closed with the same type of right parenthesis.
- The left parentheses must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Introductory exercise when learning stack: bracket matching
class Solution
{
public:
bool isValid(string s)
{
if (s.size() % 2)
{
return false;
}
stack<char>a;
for (auto n : s)
{
if (n == '(' || n == '[' || n == '{')
{
a.push(n);
}
else
{
if (a.empty())
{
return false;
}
if (n == ')' && a.top() == '(')
{
a.pop();
}
else if (n == ']' && a.top() == '[')
{
a.pop();
}
else if (n == '}' && a.top() == '{')
{
a.pop();
}
else
{
return false;
}
}
}
if (a.empty())
return true;
else
return false;
}
};
21. Merge two ordered linked lists
21. Merge two ordered linked lists
Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
When writing exercises such as linked lists and binary trees that give initialization, you must realize the initialization process yourself!! Otherwise, the written interview will suffer
After each linked list problem, I will emphasize it in the problem solution
C implementation of initialization
struct ListNode
{
int val;
struct ListNode* next;
};
C + + implementation of initialization
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
It's really only hand familiar!! Today, I wrote it over and over again, and there was no card when I executed it
Finally, if... else... This can be simplified as p - > next = LIST1? list1:list2;
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode* p =new ListNode(0);
ListNode* q = p;
while (list1 && list2)
{
if (list1->val <= list2->val)
{
p->next = list1;
p = p->next;
list1 = list1->next;
}
else
{
p->next = list2;
p = p->next;
list2 = list2->next;
}
}
/*if (list1 != NULL)
{
p->next = list1;
}
else
{
p->next = list2;
}*/
p->next=list1?list1:list2;
return q->next;
}
};
23. Merge K ascending linked lists
23. Merge K ascending linked lists
Give you a linked list array, each linked list has been arranged in ascending order.
Please merge all linked lists into an ascending linked list and return the merged linked list.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: the linked list array is as follows:
[
1->4->5,
1->3->4,
2->6
]
Combine them into an ordered linked list.
1->1->2->3->4->4->5->6
Using the idea of 21 questions, first sort in pairs, and then sort
There are solutions to divide and conquer and priority queue. Then fill the pit
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode* p = new ListNode(0);
ListNode* q = p;
while (list1 && list2)
{
if (list1->val <= list2->val)
{
p->next = list1;
p = p->next;
list1 = list1->next;
}
else
{
p->next = list2;
p = p->next;
list2 = list2->next;
}
}
p->next = list1 ? list1 : list2;
return q->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
if (lists.size() == 0)
{
return NULL;
}
else if (lists.size() == 1)
{
return lists[0];
}
for (int i = 0; i < lists.size()-1; i++)
{
lists[i + 1] = mergeTwoLists(lists[i], lists[i + 1]);
}
return lists[lists.size() - 1];
}
};
29. Divide two numbers
Given two integers, divisor and divisor. To divide two numbers, multiplication, division and mod operators are not required.
Returns the quotient obtained by dividing the dividend by the divisor.
The result of integer division should truncate its decimal part, such as truncate(8.345) = 8 and truncate(-2.7335) = -2
Example 1:
Input: divide = 10, division = 3
Output: 3
Explanation: 10/3 = truncate(3.33333...) = truncate(3) = 3
First attach the timeout code (using long)
technological process:
1. The divisor is 0 and returns 0
2. Judge the positive and negative of divisor and dividend. Only when one of them is negative, will the result change sign after both become absolute values
3. If the divisor is 1 and the dividend is returned, there will be an overflow problem here, INT_MIN/1 will overflow
4. Cycle (divisor > = divisor): the constant subtraction of the divisor
5.return result
class Solution
{
public:
int divide(int dividend, int divisor)
{
if (dividend == 0)
return 0;
long a = dividend;
long b = divisor;
int tmp = 0;
if (dividend < 0 || divisor < 0)
{
if (!(dividend < 0 && divisor < 0))
tmp = 1;
a = abs(a);
b = abs(b);
}
if (b == 1)
{
if (tmp == 1)
{
return -a;
}
return a > INT_MAX ? INT_MAX : a;
}
int num = 0;
while (a >= b)
{
a -= b;
num++;
}
return tmp ? -num : num;
}
};
33. Search rotation sort array
33. Search rotation sort array
The integer array nums is arranged in ascending order, and the values in the array are different from each other.
Before passing to the function, nums rotates on a previously unknown subscript k (0 < = k < nums. Length), so that the array becomes [nums [k], nums [K + 1],..., nums [n-1], nums [0], nums [1],..., nums [k-1]] (the subscript counts from 0). For example, after rotating at subscript 3, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2].
Give you the rotated array num and an integer target. If the target value target exists in num, return its subscript, otherwise return - 1.
Example 1:
Input: num = [4,5,6,7,0,1,2], target = 0
Output: 4
Using dichotomy + rotation to find the properties of sorted arrays
Rotate sort array: large - > maximum - > minimum - > small
Use the if... else... Statement:
Conditional judgment statement 1:
Nums [mid] > = nums [0] means that mid and mid left are ordered, that is, mid is on the left of the maximum number
else, that is, mid, is to the right of the decimal point, that is, the decimal point
Conditional judgment statement 2:
Num [mid] > target & & target > = num [0] divides the range of target between [num [0], Num [mid-1])
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size()-1;
int mid;
while (left <= right)
{
mid = left + (right - left) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[mid] >= nums[0])//mid left order
{
if (nums[mid] > target && target >= nums[0])//In an orderly range
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else//mid right order
{
if (nums[mid] < target && target < nums[0])
//Within the ordered range, target < = num [num.size() - 1] can also be used
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return -1;
}
};
50. Pow(x, n)]
Realize pow(x, n), that is, calculate the N-power function of X (i.e. x^n).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
I think x*myPow(x, n-1), and the result is stack overflow
Method I:
A wonderful idea seen in the comments area
Similar to guanxie II
Each binary digit has a weight. The weight is shown in the figure below. The final result is equal to the product of the weight of all binary bits with 1. For example, the binary (1001101) corresponding to the power of x^77 above and the weight of each binary bit are as follows
1 0 0 1 1 0 1 x^64 x^32 x^16 x^8 x^4 x^2 x^1 The final result is the product of all weights with binary bits of 1: x^1 * x^4 * x^8 * x^64 = x^77
And we don't have to calculate the weight of each binary bit in advance. We can calculate the weight while calculating the result
class Solution
{
public:
double myPow(double x, int n)
{
if (x == 0)
{
return 0;
}
else if (n == 1)
{
return x;
}
long power = n;// To ensure that - n does not overflow - > int_ Min, convert to long type first
if (n < 0)
{ // If n is less than 0, find the - n power of 1/x
power = abs(power);
x = 1 / x;
}
double weight = x; // The initial value of the weight is x, that is, the weight of the first bit of the binary bit is x^1
double res = 1;//Save results
while (power)
{
// If the current binary bit is 1, multiply the result by the weight on this binary bit,
// The bit weight has been calculated in the last iteration
if ((power & 1) == 1)
{
res *= weight;
}
weight *= weight; // Calculate the weight of the next binary bit
power >>= 1;
}
return res;
}
};
Method 2:
Official explanation : fast power + recursion
If we want to calculate x^77, we can follow:
X → x ^2 → x ^4 → x ^9 → x ^19 → x 38 → x 77
In the steps of X → x ^2, x ^2 → x ^4, x ^19 → x ^38, we square the last result directly;
In the steps of x4 → x9, x^9 → x 19, x38 → x77, after squaring the last result, we have to multiply an additional X.
It seems difficult to deduce directly from left to right, because in each step, we don't know whether we need to multiply x after squaring the last result. But if we look from right to left, the idea of partition is very obvious:
-
When we want to calculate x^n, we can recursively calculate y = x^n/2 ⌋, where ⌊ a ⌋ means rounding down a;
-
According to the result of recursive calculation, if n is an even number, then x ^ n = y ^ 2x, n = Y2;
If n is an odd number, then x^n = y^2 * x;
-
The boundary of recursion is n=0, and the power of 0 of any number is 1.
class Solution
{
public:
double quickMul(double x, long long N)
{
if (N == 0)
{
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
double myPow(double x, int n)
{
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
Method 3:
Official solution : fast power + iteration
Since recursion requires additional stack space, we try to translate recursion into iteration. In method 1, we also mentioned that it is not easy to deduce from left to right, because we don't know whether we need to multiply X. But we might as well look for rules to see where we multiply x extra and how they affect the answer.
Let's take x^77 as an example: X → x ^2 → x ^4 → x ^9 → x ^19 → x 38 → x 77, and mark the step requiring additional multiplication of X with + mark.
It can be found that:
When we multiply these contributions, x* x^4* x8*x64 is exactly equal to x^77.
And what is the exponential part of these contributions?
They are all powers of 2, because every extra multiplied x is then squared several times. These indices 1, 4, 8 and 64 correspond to each 1 in the binary representation (1001101) of 77!
Therefore, we can get the iterative calculation method with the help of binary splitting of integer. Generally, if the binary splitting of integer n is
class Solution
{
public:
double quickMul(double x, long long N)
{
double ans = 1.0;
// The initial value of the contribution is x
double x_contribute = x;
// Calculate the answer while binary splitting N
while (N > 0)
{
if (N % 2 == 1)
{
// If the lowest bit of N binary representation is 1, the contribution needs to be included
ans *= x_contribute;
}
// Will contribute continuously
x_contribute *= x_contribute;
// Discard the lowest bit of N binary representation, so that we only need to judge the lowest bit each time
N /= 2;
}
return ans;
}
double myPow(double x, int n)
{
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
69. Sqrt(x)]
Give you a nonnegative integer x, calculate and return the arithmetic square root of X.
Since the return type is an integer, only the integer part will be retained and the decimal part will be rounded off.
**Note: * * it is not allowed to use any built-in exponential functions and operators, such as pow(x, 0.5) or x ** 0.5.
Example 1:
Input: x = 4
Output: 2
The dichotomy finds the value of the maximum m that matches mid ^ 2 < X
Because the maximum mid value of < x is to be returned, use ans to record the current mid value when mid ^ 2 < x, so as to avoid non-compliance after mid increases
class Solution
{
public:
int mySqrt(int x)
{
int left = 1;
int right = x;
int mid;
int ans;
while (left <= right)
{
mid= left + (right - left) / 2;
long tmp = (long)mid * mid;
if (tmp == x)
{
return mid;
}
if (tmp > x)
{
right = mid-1;
}
else
{
ans=mid;
left = mid + 1;
}
}
return ans;
}
};
70. Climb stairs
Suppose you are climbing stairs. You need n steps to reach the roof.
You can climb one or two steps at a time. How many different ways can you climb to the roof?
Note: given n is a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: there are two ways to climb to the roof.
- 1st order + 1st order
- Second order
dp[i]: there are dp[i] ways to climb the i-th stair
Because n is a positive integer, it is unnecessary to consider the case of 0. Initialization: there are one for n=1 and two for n=2
When I > = 3, it can be seen from dp[i] that dp[i] can be pushed out in two directions
(1) dp[i - 1], there are dp[i - 1] ways to go up the i-1 stairs, so jumping another step is dp[i]
(2) dp[i - 2], there are dp[i - 2] ways to go up the i-2 stairs, so jumping two more steps is dp[i]
So dp[i] = dp[i - 1] + dp[i - 2]
class Solution
{
public:
int climbStairs(int n)
{
if(n<3)
return n;
vector<int>dp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
Second writing solution:
The first idea is recursion
climbStairs(int n)=climbStairs(n - 2) + climbStairs(n - 1);
But it timed out
class Solution
{
public:
int climbStairs(int n)
{
if (n <= 0)
return 0;
if (n <= 2)
return n;
return climbStairs(n - 2) + climbStairs(n - 1);
}
};
The above idea is realized by array iteration
class Solution
{
public:
int climbStairs(int n)
{
if (n <= 2)
return n;
vector<int>arr(n);
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < n; ++i)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n - 1];
}
};
81. Search rotation sort array II
81. Search rotation sort array II
It is known that there is an integer array nums arranged in non descending order, and the values in the array do not have to be different from each other.
Before passing to the function, nums rotates on a previously unknown subscript k (0 < = k < nums. Length), so that the array becomes [nums [k], nums [K + 1],..., nums [n-1], nums [0], nums [1],..., nums [k-1]] (the subscript counts from 0). For example, after rotating at subscript 5, [0,1,2,4,4,4,5,6,6,7] may become [4,5,6,7,0,1,2,4,4].
Give you the rotated array num and an integer target. Please write a function to judge whether the given target value exists in the array. If the target value target exists in nums, it returns true; otherwise, it returns false.
Example 1:
Input: num = [2,5,6,0,0,1,2], target = 0
Output: true
FA Yi
The difference between this question and question 33 is that this question is in non descending order - > there are repeated elements, and there may be nums[0]==nums[nums.size()-1], etc
Compared with 33 questions, the conditional sentence is added: num [left] = = num [mid] & & num [mid] = = num [right], to avoid that when an array with the shape of {1,0,1,1,1,1,1} appears, it is not sure whether it is mid left order or mid right order
Difference: judge that the target range is changed from target > = num [0] to target > = num [left]. At this moment, it can be seen that the array range is changed from [num [0], Num [num. Size() - 1]] to [num [left], num [right]], and the boundary data are deleted. It is still to avoid the interval judgment problem when the repetition number of the rotating array exists (you can also do this in question 33)
Compared with law one, I think law two is easier to understand and write
class Solution
{
public:
bool search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1;
int mid;
while (left <= right)
{
mid = left + (right - left) / 2;
if (nums[mid] == target)
{
return true;
}
if (nums[left] == nums[mid] && nums[mid] == nums[right])
{
left++;
right--;
}
else if (nums[mid]>=nums[left])//mid left order
{
if (nums[mid] > target && target >= nums[left])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else
{
if (nums[mid] < target && target <= nums[right])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return false;
}
};
Method II
Simplify: remove the tail repeating element before dichotomy
Note: left < = Right-1 (because right –)
The binary code is the same as question 33
class Solution
{
public:
bool search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1;
int mid;
while (nums[left] == nums[right] && left <= right - 1)
{
right--;
}
while (left <= right)
{
mid = left + (right - left) / 2;
if (nums[mid] == target)
{
return true;
}
if (nums[mid] >= nums[0])//mid left order
{
if (nums[mid] > target && target >= nums[0])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else
{
if (nums[mid] < target && target < nums[0])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return false;
}
};
104. Maximum depth of binary tree
104. Maximum depth of binary tree
Given a binary tree, find its maximum depth.
The depth of the binary tree is the number of nodes on the longest path from the root node to the farthest leaf node.
Note: leaf nodes refer to nodes without child nodes.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Returns its maximum depth 3.
level traversal
class Solution
{
public:
int maxDepth(TreeNode* root)
{
if (root == NULL)
return 0;
queue< TreeNode*>que;
que.push(root);
int k = 0;
while (!que.empty())
{
int len = que.size();
for (int i = 0; i < len; i++)
{
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
}
k++;
}
return k;
}
};
153. Find the minimum value in the rotation sort array
153. Find the minimum value in the rotation sort array
An array of length n is known, which is arranged in ascending order in advance. After 1 to n rotations, the input array is obtained. For example, the original array num = [0,1,2,4,5,6,7] may be obtained after changing:
- If you rotate 4 times, you can get [4,5,6,7,0,1,2]
- If you rotate 7 times, you can get [0,1,2,4,5,6,7]
Note that arrays [a [0], a [1], a [2], The result of a [n-1]] rotation is array [a [n-1], a [0], a [1], a [2], a[n-2]] .
Give you an array nums with different element values. It was originally an array arranged in ascending order and rotated many times according to the above situation. Please find and return the smallest element in the array.
Example 1:
Input: num = [3,4,5,1,2]
Output: 1
Explanation: the original array is [1,2,3,4,5]. Rotate it three times to get the input array.
First write an opportunistic solution
Set a min, and write the others in binary format. Compare the values of num [mid] and min each time, and finally return min;
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;
int mid;
int min = INT_MAX;
while (left <= right)
{
mid = left + (right - left) / 2;
min = fmin(min, nums[mid]);
if (nums[mid] > nums[right])//The left side of mid is orderly, and the minimum value is on the right side of mid
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return min;
}
};
Method II
General solution
I write my own dichotomy. I'm used to using left < = right, left = mid + 1, right = mid-1, so this question is wrong twice
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;
int mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (nums[mid] > nums[right])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return nums[left];
}
};
Finally, post a binary related knowledge point saved in your notes
(I forgot who summarized it. I saw the sentence "the essence of dichotomy is two stages", which is the summary of Miyoshi Sanye)
Binary search
1. Check the value in an orderly queue, with two points.
2. The essence of "dichotomy" is two stages, not monotonicity. As long as one paragraph satisfies a certain property and the other paragraph is not satisfied, you can use "dichotomy".
There are two templates for binary search:
- If (left < right), the reduced range is left = mid + 1 and right = mid
- The right boundary always maintains the semantic num [right] > = target (taking the ordinary binary search as an example). This semantic is realized by detecting if (Num [mid] > = target), so right = mid rather than right = mid - 1
- After the loop exits, it is necessary to check whether the semantics maintained by right is correct, that is, if (Num [right] > = target), because the position of right may not move all the time, and the semantics of this position has never been detected, because the loop condition we set is if (left < right). If it is set to if (left < = right), the last left == right == mid may kill the loop
- If (left < = right), the reduced range is left = mid + 1 and right = mid - 1
- If (Num [mid] = = target) return mid is directly detected in the middle. If the statement is never executed and the loop is pushed out, it means that the target is not searched
- If (left < = right) is used for condition detection, so that the semantics of the right boundary can be detected. Therefore, right = mid- 1 should be used instead of right = mid
164. Maximum spacing
Given an unordered array, find out the maximum difference between adjacent elements of the array after sorting.
If the number of array elements is less than 2, 0 is returned.
Example 1:
Input: [3,6,9,1]
Output: 3
Explanation: the sorted array is [1,3,6,9], in which there is a maximum difference of 3 between adjacent elements (3,6) and (6,9).
Call library function
class Solution
{
public:
int maximumGap(vector<int>& nums)
{
if (nums.size() < 2)
return 0;
sort(nums.begin(), nums.end());
int max = INT_MIN;
for (int i = 0; i < nums.size() - 1; i++)
{
if (abs(nums[i] - nums[i + 1]) > max)
{
max = abs(nums[i] - nums[i + 1]);
}
}
return max;
}
};
Linear time complexity and spatial complexity: Cardinal ordering
I feel like I have lost my memory. I haven't studied for long
Giant slow
class Solution
{
public:
//Get the maximum number of digits
int GetFigur(vector<int>& arr, int len)
{
if (len < 1)
return -1;
int max = arr[0];
for (int i = 1; i < len; i++)
{
max = max > arr[i] ? max : arr[i];
}
int count = 0;
while (max != 0)
{
max /= 10;
count++;
}
return count;
}
//Gets the number of the right digit of the decimal integer, figur e starts from 0
//For example, (123,0) - > 3 (123,1) - > 2 (123,2) - > 1 (123,3) - > 0
int GetNum(int n, int figur)
{
for (int i = 0; i < figur; i++)
{
n /= 10;
}
return n % 10;
}
//Cardinality sort
vector<int>RadixSort(vector<int>& arr, int len)//Time complexity O (d*n), space o (n), stability
{
queue<int>queArr[10];
//Get the number of digits of the maximum number and determine the number of trips in and out of the team
int count = GetFigur(arr, len);
int index;
for (int i = 0; i < count; i++)//Process the ith number of each number from right to left
{
for (int j = 0; j < len; j++)//Traverse the array and join the queue
{
index = GetNum(arr[j], i);
queArr[index].push(arr[j]);//Put the number in the corresponding queue
}
//Get out of the team in turn
int j = 0;
for (int k = 0; k < 10; k++)
{
while (!queArr[k].empty())
{
arr[j++] = queArr[k].front();
queArr[k].pop();
}
}
}
return arr;
}
int maximumGap(vector<int>& nums)
{
if (nums.size() < 2)
return 0;
RadixSort(nums, nums.size());
int max = INT_MIN;
for (int i = 0; i < nums.size() - 1; i++)
{
if (abs(nums[i] - nums[i + 1]) > max)
{
max = abs(nums[i] - nums[i + 1]);
}
}
return max;
}
};
169. Most elements
Given an array of size n, find most of its elements. Most elements refer to elements that appear more than ⌊ n/2 ⌋ in the array.
You can assume that the array is non empty and that there are always many elements in a given array.
Example 1:
Input: [3,2,3]
Output: 3
Hash
"Time complexity O(n), space complexity O(n)"
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
unordered_map<int, int>hash;
for (auto m : nums)
{
hash[m]++;
if (hash[m] > nums.size() / 2)
return m;
}
return -1;
}
};
Boyer Moore voting algorithm (Moore voting algorithm)
"Time complexity O(n), space complexity O(1)"
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
int count = 1;
int tmp;
for (int i=0;i<nums.size();++i)
{
if (i == 0)
tmp = nums[0];
else
{
if (nums[i] == tmp)
{
count++;
}
else
{
count--;
if (count == 0)
{
tmp = nums[i];
count = 1;
}
else if (count > nums.size() / 2)
{
break;
}
}
}
}
return tmp;
}
};
Optimized
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
int count =0;
int tmp=nums[0];
for (auto n:nums)
{
if (n == tmp)
count++;
else
{
if (--count == 0)
{
tmp = n;
count = 1;
}
if (count > nums.size() / 2)
{
break;
}
}
}
return tmp;
}
};
172. Factorial zero
Given an integer n, return n! The number of trailing zeros in the result.
Prompt n= n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
Example 1:
Input: n = 3
Output: 0
Explanation: 3= 6, excluding trailing 0
Personally, I think the most difficult point of this problem is the treatment of large numbers
The first idea to get this question is to save n with sum!
But 0 < = n < = 10000. Obviously, sum of long long type will not work
Read the solution
Finding a multiple of 5 is really absolute. Only when n is a multiple of 5 will the end 0 appear, and 5 * any even number will have the end 0
Split all multiples x of 5 into 5*y (i.e. y 5, y 0 will appear)
At the same time, y may also be a multiple of 5, so the return is n / 5 + trailingZeroes(n / 5)
Recursion until n < 5
class Solution
{
public:
int trailingZeroes(int n)
{
if (n < 5)
return 0;
return n / 5 + trailingZeroes(n / 5);
}
};
Write iterations according to recursion
class Solution
{
public:
int trailingZeroes(int n)
{
int tmp = 0;
while (n)
{
if (n < 5)
break;
tmp += n / 5;
n /= 5;
}
return tmp;
}
};
217. There are duplicate elements
217. There are duplicate elements
Given an integer array, determine whether there are duplicate elements.
If a value exists and appears in the array at least twice, the function returns true. Returns false if each element in the array is different.
Example 1:
Input: [1,2,3,1]
Output: true
Hash
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_map<int, int>hash;
for (auto n : nums)
{
if (++hash[n] == 2)
return true;
}
return false;
}
};
sort
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i++)
{
if (nums[i] == nums[i + 1])
{
return true;
}
}
return false;
}
};
222. Number of nodes of complete binary tree
222. Number of nodes of complete binary tree
Give you the root node of a complete binary tree, root, and find the number of nodes of the tree.
Complete binary tree The definition of is as follows: in a complete binary tree, except that the bottom node may not be filled, the number of nodes in each layer reaches the maximum, and the nodes in the lowest layer are concentrated in several positions on the leftmost side of the layer. If the bottom layer is the h-th layer, the layer contains 1~ 2h nodes.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6
recursion
class Solution
{
public:
int countNodes(TreeNode* root)
{
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
Iterations: sequence traversal
class Solution
{
public:
int countNodes(TreeNode* root)
{
int tmp = 0;
queue<TreeNode*> que;
if (root != NULL)
{
que.push(root);
tmp++;
}
while (!que.empty())
{
int size = que.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if (node->left)
{
que.push(node->left);
tmp++;
}
if (node->right)
{
que.push(node->right);
tmp++;
}
}
}
return tmp;
}
};
226. Flip binary tree
Flip a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Modify recursive order
class Solution
{
public:
TreeNode* invertTree(TreeNode* root)
{
if (root == NULL) return root;
swap(root->left, root->right); // in
invertTree(root->left); // Left
invertTree(root->right); // right
return root;
}
};
231. Power of 2
Give you an integer n, please judge whether the integer is a power of 2. If yes, return true; Otherwise, false is returned.
If there is an integer x such that n == 2^x, n is considered to be a power of 2.
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1
FA Yi
Special judgment n < = 0
The power of 2 has one characteristic: only one bit in binary is 1
class Solution
{
public:
bool isPowerOfTwo(int n)
{
if (n <= 0)
return false;
int sum = 0;
while (n)
{
if (n & 1)
sum++;
n >>= 1;
}
return sum == 1 ? true : false;
}
};
Method II
Characteristics of the power of 2: n & (n-1) = = 0
class Solution
{
public:
bool isPowerOfTwo(int n)
{
return n > 0 && (n & (n - 1)) == 0;
}
};
300. Longest increasing subsequence
300. Longest increasing subsequence
Give you an integer array nums and find the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from an array. The elements in the array are deleted (or not deleted) without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: num = [10,9,2,5,3,7101,18]
Output: 4
Explanation: the longest increasing subsequence is [2,3,7101], so the length is 4.
class Solution
{
public:
int lengthOfLIS(vector<int>& nums)
{
vector<int> dp(nums.size(), 1);
int min;
for (int i = 1; i < nums.size(); i++)
{
for (int j = 0; j < i; j++)
{
if ((nums[i] > nums[j]))
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
324. Swing sort II
Give you an integer array num, rearrange it into num [0] < num [1] > num [2] < num [3] The order of.
You can assume that all input arrays can get results that meet the requirements of the topic.
Example 1:
Input: num = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also the result that meets the requirements of the topic and can be accepted by the problem determination procedure.
Solution to this problem: sort + reverse insertion (0615243 distinguish parity)
I originally learned to sort + distinguish parity insertion (positive order 0415263), and some of the tests can't pass
class Solution
{
public:
void wiggleSort(vector<int>& nums)
{
sort(nums.begin(), nums.end());
if (nums.size() <= 2)
return;
vector<int>arr = nums;
int r = nums.size() - 1;
for (int i = 1; i < nums.size(); i+=2)
{
nums[i] = arr[r--];
}
for (int i = 0; i < nums.size(); i += 2)
{
nums[i] = arr[r--];
}
}
};
Note:
O(n) time complexity and / or in situ O(1) additional space not implemented
326. Power of 3
Given an integer, write a function to determine whether it is a power of 3. If yes, return true; Otherwise, false is returned.
The integer n is to the power of 3, which needs to be satisfied: there is an integer x so that n == 3x
Example 1:
Input: n = 27
Output: true
It is still a recursion
This recursion is special: (n% 3) = = 0? isPowerOfThree(n / 3):false；
When n%3==0, the next step of recursion will be carried out, otherwise false will be returned
Exit conditions are the same as above
class Solution
{
public:
bool isPowerOfThree(int n)
{
if (n <= 0)
return false;
if (n == 1)
return true;
return (n % 3)==0?isPowerOfThree(n / 3):false;
}
};
342. Power of 4
Given an integer, write a function to determine whether it is a power of 4. If yes, return true; Otherwise, false is returned.
The integer n is to the power of 4, which needs to be satisfied: there is an integer x so that n == 4x
Example 1:
Input: n = 16
Output: true
FA Yi
Set the template of the previous question directly
class Solution
{
public:
bool isPowerOfFour(int n)
{
if (n <= 0)
return false;
if (n == 1)
return true;
return (n % 4) == 0 ? isPowerOfFour(n / 4) : false;
}
};
Method II
On the basis of the power of 2 (the power of 4 is also the power of 2), a condition n & 0xaaaa = = 0 is added
0xaaaaaa format is 1010 1010 1010 1010 (right to left: even bit is 1)
The power of 4 is (from right to left: odd bit is 1) eg.1 100 10000
class Solution
{
public:
bool isPowerOfFour(int n)
{
return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}
};
367. Effective complete square
367. Effective complete square
Given a positive integer num, write a function. If num is a complete square number, it returns true, otherwise it returns false.
Advanced: do not use any built-in library functions, such as sqrt.
Example 1:
Input: num = 16
Output: true
Dichotomy to find the complete square
Note: to avoid overflow, tmp takes the long type
class Solution
{
public:
bool isPerfectSquare(int num)
{
int left = 1;
int right = num;
int mid;
long tmp;
while (left <= right)
{
mid = left + (right - left) / 2;
tmp =(long) mid * mid;
if (tmp == num)
return true;
else if (tmp > num)
right = mid - 1;
else
left = mid + 1;
}
return false;
}
};
371. Sum of two integers
Give you two integers a and b, do not use the operator + and -, calculate and return the sum of the two integers.
Example 1:
Input: a = 1, b = 2
Output: 3
Before cycle:
c=a ^ b use c to record the XOR value of a and b (sum without carry)
tmp = A & b use tmp to record the values of a and b (the sum during carry, because there is carry, remember to shift one bit left during calculation)
Enter loop (carry):
Record the value of c with x, and then update the value of c
c = c ^ (TMP < < 1) update c: record the XOR value of c and carry TMP < < 1 (sum without carry)
tmp = x & (tmp < 1) update carry tmp: record the value of X and carry tmp < 1 (sum of carry)
tmp must be set as an unsigned integer: if the highest bit of the number shifted to the left is the sign bit, some compilers will report an error
runtime error: left shift of negative value -2147483648 (solution.cpp)
int getSum(int a, int b)
{
int c = a ^ b;
unsigned int tmp = a & b;
int x = c;
while (tmp)
{
x = c;
c = c ^ (tmp << 1);
tmp = x & (tmp << 1);
}
return c;
}
After understanding the above process, the following results are simplified
int getSum(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
397. Integer substitution
Given a positive integer n, you can do the following:
- If n is an even number, replace n with n / 2.
- If n is an odd number, n can be replaced with n + 1 or n - 1.
What is the minimum number of replacements required for n to become 1?
Example 1:
Input: n = 8
Output: 3
Explanation: 8 - > 4 - > 2 - > 1
After reading a lot of problem solutions, only this can be understood
First, if a number is even, dividing by two is the best solution.
If it is an odd number, there are only two operations: + 1 or - 1.
The correct way is not to judge whether the number is the power of 2 (sadly, my own writing is to judge which of n+1 and n-1 will be the power of 2). It should depend on whether there are at least two consecutive ones at the lowest point of the number.
Because when there are multiple consecutive ones at the lowest position, + 1 can eliminate multiple ones at the same time, and then fill a 1 in front. It is 0 from the lowest position to the filled 1, which can be obtained directly by constantly moving to the right.
In this case, if - 1 is used, these consecutive 1s will be encountered after each bit of right shift. In this way, each bit of right shift will reduce 1 more than before.
If there are only two consecutive ones in the end, the final operands of + 1 and - 1 are the same. When it is greater than 2, there must be less + 1 operands.
The only exception: 3. When there is only 3, it is direct-1 optimal. 3 → 2 → 1 is better than 3 → 4 → 2 → 1.
Also note that when n = = int_ At max, + 1 will explode int.
class Solution
{
public:
int integerReplacement(int n)
{
int tmp = 0;
long num = n;
while (num > 1)
{
if (num&1)
{
if (num != 3 && (num >> 1) & 1)
{
num += 1;
}
else
{
num -= 1;
}
}
else
{
num /= 2;
}
tmp++;
}
return tmp;
}
};
455. Distribution of biscuits
Suppose you are a great parent and want to give your children some cookies. However, each child can only give one biscuit at most.
For each child I, there is an appetite value g[i], which is the minimum size of biscuits that can satisfy the children's appetite; And every cookie j has a size s[j]. If s[j] > = g[i], we can assign this biscuit j to child I, and the child will be satisfied. Your goal is to meet as many children as possible and output this maximum value.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation:
You have three children and two biscuits. The appetite values of the three children are: 1, 2 and 3.
Although you have two small biscuits, because their size is 1, you can only satisfy children with an appetite of 1.
So you should output 1.
Sorting: traversal based on small
class Solution
{
public:
int findContentChildren(vector<int>& g, vector<int>& s)
{
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0;
int tmp = 0;
for (auto n : s)
{
if (g[i] <= n)
{
tmp++;
if (++i >= g.size())
break;
}
}
return tmp;
}
};
463. Perimeter of the island
A two-dimensional grid map grid of row x col is given, where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
The grids in the grid are connected horizontally and vertically (not diagonally). The whole grid is completely surrounded by water, but there is exactly one island (or an island composed of one or more grids representing land).
There is no "Lake" in the island ("Lake" means that the water is inside the island and not connected with the water around the island). The grid is a square with side length of 1. The grid is rectangular and its width and height do not exceed 100. Calculate the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0], [1,1,0], [0,1,0,0], [1,1,0,0]]
Output: 16
Explanation: its circumference is the 16 yellow edges in the picture above
It's a law finding problem. All 1 * 4 - all 1 (right neighbor 1 + lower neighbor 1) * 2
class Solution
{
public:
int islandPerimeter(vector<vector<int>>& grid)
{
int sum = 0;
int tmp = 0;
for (int i = 0; i < grid.size(); ++i)
{
for (int j = 0; j < grid[0].size(); ++j)
{
if (grid[i][j])
{
sum++;
}
if (grid[i][j] && (i + 1 < grid.size() && grid[i + 1][j]))
{
tmp++;
}
if (grid[i][j] && (j + 1 < grid[0].size() && grid[i][j + 1]))
{
tmp++;
}
}
}
return sum * 4 - tmp * 2;
}
};
509. Fibonacci number
Fibonacci numbers are usually represented by F(n), and the sequence formed is called Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent number is the sum of the first two numbers. That is:
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，among n > 1
Here you are n, please calculate F(n).
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1
Recursion: the efficiency is very slow (because the problem 0 < = n < = 30, the compilation can pass)
It can be said that question 70 is a variation of Fibonacci number
class Solution
{
public:
int fib(int n)
{
if (n < 0)
return 0;
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
};
Array iteration
class Solution
{
public:
int fib(int n)
{
if (n <= 1)
return n;
vector<int>arr(n + 1);
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i <= n; i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
};
539. Minimum time difference
Given a time list in 24-hour system (hour: minute "HH:MM"), find the minimum time difference between any two times in the list and express it in minutes.
Example 1:
Input: timePoints = ["23:59", "00:00"]
Output: 1
Convert to minutes + sort
Note: time should be counted as two days
class Solution
{
public:
int findMinDifference(vector<string>& timePoints)
{
vector<int>arr;
int h;
int m;
for (auto n : timePoints)
{
h = 0;
m = 0;
for (int i = 0; i < 5; i++)
{
if (i < 2)
{
h = h * 10 + n[i] - '0';
}
else if (i > 2)
{
m = m * 10 + n[i] - '0';
}
}
arr.push_back(h * 60 + m);
if (h < 12)//Instead of H < 12, it can be regarded as two days, 24 hours a day, < 12 is to calculate the first 12 hours again
{
arr.push_back((h+24) * 60 + m);
}
}
sort(arr.begin(), arr.end());
int min = INT_MAX;
for (int i = 0; i < arr.size() - 1; i++)
{
if (arr[i] == arr[i + 1])
{
return 0;
}
if (min > abs(arr[i] - arr[i + 1]))
{
min = abs(arr[i] - arr[i + 1]);
}
}
return min;
}
};
561. Array splitting I
Given an integer array nums with a length of 2n, your task is to divide these numbers into n pairs, such as (A1, B1), (A2, B2), (an, BN) so that the sum of min(ai, bi) from 1 to n is the largest.
Returns the maximum sum of the.
Example 1:
Input: num = [1,4,3,2]
Output: 4
Explanation: all possible divisions (ignoring element order) are:
- (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
- (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
- (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum sum is 4
Find regular questions:
Rule: sort and accumulate numbers at odd positions (even subscripts)
class Solution
{
public:
int arrayPairSum(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int tmp = 0;
for (int i = 0; i < nums.size(); i += 2)
{
tmp += nums[i];
}
return tmp;
}
};
566. Reshaping the matrix
In MATLAB, there is a very useful function reshape, which can reshape an m x n matrix into another new matrix with different size (r x c), but retain its original data.
Give you an m x n matrix represented by a two-dimensional array mat, and two positive integers r and c, respectively, representing the number of rows and columns of the matrix you want to reconstruct.
The reconstructed matrix needs to fill all elements of the original matrix in the same row traversal order.
If the reshape operation with given parameters is feasible and reasonable, a new reshape matrix is output; Otherwise, the original matrix is output.
Example 1:
After traversing and saving, first judge whether it is legal
class Solution
{
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c)
{
if (r * c != mat.size() * mat[0].size())
return mat;
vector<vector<int>>arr(r, vector<int>(c));
int i = 0;
int j = 0;
for (auto n : mat)
{
for (auto m : n)
{
arr[i][j++] = m;
if (j == c)
{
j = 0;
i++;
}
}
}
return arr;
}
};
611. Number of effective triangles
611. Number of effective triangles
Given an array containing nonnegative integers, your task is to count the number of triples that can form three sides of a triangle.
Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (use the first 2)
2,3,4 (use the second 2)
2,2,3
There is a plain loop timeout
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
if (nums.size() <= 2)
return 0;
sort(nums.begin(), nums.end());
int tmp = 0;
for (int i = 0; i < nums.size() - 2; i++)
{
for (int j = i + 1; j < nums.size() - 1; j++)
{
if (nums[i] + nums[j] <= nums[j + 1])
continue;
else i
for (int k = j + 1; k < nums.size(); k++)
{
if (nums[i] + nums[j] > nums[k])
{
tmp++;
}
else
break;
}
}
}
return tmp;
}
};
Official solution: sorting + dichotomy
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
int n = nums.size();
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int left = j + 1;
int right = n - 1;
int mid;
int k = j;
while (left <= right)
{
mid = left + (right - left) / 2;
if (nums[i] + nums[j]> nums[mid] )
{
k = mid;
left = mid + 1;
}
else
{
right = mid - 1;
}
}
ans += k - j;
}
}
return ans;
}
};
661. Picture smoother
The two-dimensional matrix M containing integers represents the gray level of a picture. You need to design a smoother to make the gray level of each unit become the average gray level (rounding down). The calculation of the average gray level is to average the surrounding 8 units and their own values. If there are less than 8 surrounding cells, use them as much as possible.
Example 1:
Input:
[[1,1,1],
[1,0,1],
[1,1,1]]
Output:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
Explanation:
For points (0,0), (0,2), (2,0), (2,2): Average (3 / 4) = average (0.75) = 0
For points (0,1), (1,0), (1,2), (2,1): Average (5 / 6) = average (0.83333333) = 0
For points (1,1): Average (8 / 9) = average (0.88888889) = 0
Constantly use if... else... To judge the legitimacy of i and j conditions
class Solution
{
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img)
{
vector<vector<int>>arr(img.size(), vector<int>(img[0].size(), 1));
for (int i = 0; i < img.size(); ++i)
{
for (int j = 0; j < img[i].size(); ++j)
{
int sum = 0;
int tmp = 0;
sum += img[i][j];
tmp++;
if (i - 1 >= 0)
{
sum += img[i - 1][j];
tmp++;
}
if (j - 1 >= 0)
{
sum += img[i][j - 1];
tmp++;
}
if (i + 1 < img.size())
{
sum += img[i + 1][j];
tmp++;
}
if (j + 1 < img[i].size())
{
sum += img[i][j + 1];
tmp++;
}
if (i - 1 >= 0 && j - 1 >= 0)
{
sum += img[i - 1][j - 1];
tmp++;
}
if (i - 1 >= 0 && j + 1 < img[i].size())
{
sum += img[i - 1][j + 1];
tmp++;
}
if (i + 1 < img.size() && j - 1 >= 0)
{
sum += img[i + 1][j - 1];
tmp++;
}
if (i + 1 < img.size() && j + 1 < img[i].size())
{
sum += img[i + 1][j + 1];
tmp++;
}
arr[i][j] = sum / tmp;
}
}
return arr;
}
};
766. Toplitz matrix
Give you a matrix of m x n. If the matrix is a toplitz matrix, return true; Otherwise, false is returned.
If the elements on each diagonal from top left to bottom right are the same, then the matrix is a toplitz matrix.
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above matrix, its diagonal is:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
All elements on each diagonal are the same, so the answer is True.
Ergodic judgment
class Solution
{
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix)
{
int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m - 1; ++i)
{
for (int j = 0; j < n - 1; ++j)
{
if (matrix[i][j] != matrix[i + 1][j + 1])
return false;
}
}
return true;
}
};
832. Flip image
Given a binary matrix A, we want to flip the image horizontally first, then reverse the image and return the result.
Flip the picture horizontally is to flip each line of the picture, that is, in reverse order. For example, the result of flipping [1, 1, 0] horizontally is [0, 1, 1].
Reversing the picture means that all 0's in the picture are replaced by 1's, and all 1's are replaced by 0's. For example, the result of reversing [0, 1, 1] is [1, 0, 0].
Example 1:
Input: [[1,1,0], [1,0,1], [0,0,0]]
Output: [[1,0,0], [0,1,0], [1,1,1]]
Explanation: first flip each line: [[0,1,1], [1,0,1], [0,0,0]];
Then reverse the picture: [1,0,0], [0,1,0], [1,1,1]]
Two functions swap and flip are written
class Solution
{
public:
void Swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}
void flip(int& a)
{
if (a)
a = 0;
else
a = 1;
}
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image)
{
int i = 0;
for (auto n : image)
{
int left = 0;
int right = n.size() - 1;
while (left < right)
{
Swap(n[left], n[right]);
flip(n[left++]);
flip(n[right--]);
}
if (n.size() & 1)
{
flip(n[n.size() / 2]);
}
image[i++] = n;
}
return image;
}
};
It is found from this question that auto n:image simply copies the image array, and modifying it on N does not affect the image value
867. Transpose matrix
Give you a two-dimensional integer array matrix and return the transpose matrix of the matrix.
Transpose of a matrix refers to flipping the main diagonal of the matrix and exchanging the row index and column index of the matrix.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7], [2,5,8], [3,6,9]]
New array save
class Solution
{
public:
vector<vector<int>> transpose(vector<vector<int>>& matrix)
{
vector<vector<int>>arr(matrix[0].size(), vector<int>(matrix.size()));
for (int i = 0; i < matrix.size(); ++i)
{
for (int j = 0; j < matrix[i].size(); ++j)
{
arr[j][i] = matrix[i][j];
}
}
return arr;
}
};
881. Lifeboats
The weight of the ith person is people[i], and the maximum weight that each ship can carry is limit.
Each ship can carry up to two people at the same time, provided that the sum of the weight of these people is up to limit.
Returns the minimum number of boats required to carry each person. Ensure that everyone can be carried on board.
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 ship (1, 2)
sort
Because you can only sit two people at most, and the sum of the two people's weights is at most limit
Therefore, set left and right. If the heaviest + lightest not on board > limit, then the heaviest will go on board; Otherwise, the two get on board together
class Solution
{
public:
int numRescueBoats(vector<int>& people, int limit)
{
sort(people.begin(), people.end());
int left = 0;
int right = people.size() - 1;
int num = 0;
while (left <= right)
{
if (people[left] + people[right] <= limit)
{
left++;
}
num++;
right--;
}
return num;
}
};
905. Sort arrays by parity
Given A nonnegative integer array A, returns an array in which all even elements of A are followed by all odd elements.
You can return any array that meets this condition as the answer.
Example:
Input: [3,1,2,4]
Output: [2,4,3,1]
Outputs [4,2,3,1], [2,4,1,3] and [4,2,1,3] are also accepted.
Double pointer
class Solution
{
public:
void Swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}
vector<int> sortArrayByParity(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;
while (left < right)
{
while (nums[left] % 2 == 0)
{
if (++left >= nums.size())
break;
}
while (nums[right] % 2 == 1)
{
if (--right < 0)
break;
}
if (left >= nums.size() || right < 0)
break;
if(left<right)
Swap(nums[left], nums[right]);
left++;
right--;
}
return nums;
}
};
912. Sort array
Give you an integer array nums, please arrange the array in ascending order.
Example 1:
Input: num = [5,2,3,1]
Output: [1,2,3,5]
Call library function
However, it is obvious that the purpose of being divided into medium questions is to make yourself sort
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
sort(nums.begin(), nums.end());
return nums;
}
};
Merge sort
When writing Merge, I wrote less &, and gave the child a mask. It took a long time
By the way, recommend what I sent Eight sorts
class Solution
{
public:
void Merge(vector<int>& arr, int len, int gap)
{
int low1 = 0;
int high1 = low1 + gap - 1;
int low2 = high1 + 1;
int high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;
vector<int>brr(len);
int i = 0;//Subscript of brr
//There are two merging segments
while (low2 < len)
{
//There are still data in the two merging segments, which need to be compared
while (low1 <= high1 && low2 <= high2)
{
if (arr[low1] < arr[low2])
{
brr[i++] = arr[low1++];
}
else
{
brr[i++] = arr[low2++];
}
}
//One merge segment has been completed, and the other has data
while (low1 <= high1)
{
brr[i++] = arr[low1++];
}
while (low2 <= high2)
{
brr[i++] = arr[low2++];
}
//Four variables go back and the next two merge segments
low1 = high2 + 1;
high1 = low1 + gap - 1;
low2 = high1 + 1;
high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;
}
//There is only one merge segment
while (low1 < len)
{
brr[i++] = arr[low1++];
}
//brr data copied to arr
arr = brr;
}
vector<int> sortArray(vector<int>& nums)
{
for (int i = 1; i < nums.size(); i *= 2)
{
Merge(nums, nums.size(), i);
}
return nums;
}
};
938. Scope and of binary search tree
938. Scope and of binary search tree
Given the root node of the binary search tree, root, returns the sum of the values of all nodes with values in the range [low, high].
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
level traversal
class Solution
{
public:
int rangeSumBST(TreeNode* root, int low, int high)
{
queue<TreeNode*>que;
if (root)
{
que.push(root);
}
int tmp=0;
while (!que.empty())
{
int size = que.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if (node->val >= low && node->val <= high)
{
tmp += node->val;
}
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
}
}
return tmp;
}
};
945. Minimum increment to make the array unique
945. Minimum increment to make the array unique
Give you an integer array nums. Each move operation will select any one that satisfies 0 < = I < nums Subscript i of length and increment num [i] by 1.
Returns the minimum number of operations required to make each value in num unique.
Example 1:
Input: num = [1,2,2]
Output: 1
Explanation: after a move operation, the array will become [1, 2, 3].
Naive timeout solution: traversal: < = the previous number++
class Solution
{
public:
int minIncrementForUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int tmp = 0;
for (int i = 1; i < nums.size(); i++)
{
while (nums[i] <= nums[i - 1])
{
nums[i]++;
tmp++;
}
}
return tmp;
}
};
Change the while loop to if (similar to question 1827)
class Solution
{
public:
int minIncrementForUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int tmp = 0;
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] <= nums[i - 1])
{
tmp += nums[i - 1] - nums[i] + 1;
nums[i] = nums[i - 1] + 1;
}
}
return tmp;
}
};
976. Maximum perimeter of triangle
976. Maximum perimeter of triangle
Given an array A composed of some positive numbers (representing length), return the maximum perimeter of A triangle with non-zero area composed of three lengths.
If no triangle with non-zero area can be formed, return 0.
Example 1:
Input: [2,1,2]
Output: 5
3 for loop timeouts
class Solution
{
public:
int largestPerimeter(vector<int>& nums)
{
int max = INT_MIN;
sort(nums.begin(), nums.end());
for (int i = 0; i <nums.size()-2; i++)
{
for (int j = i + 1; j < nums.size() - 1; j++)
{
for (int k = j + 1; k < nums.size() ; k++)
{
if (nums[i] + nums[j] > nums[k]&&nums[i]+nums[j]+nums[k]>max)
{
max = nums[i] + nums[j] + nums[k];
}
}
}
}
return max == INT_MIN ? 0 : max;
}
};
The above code is traversed from back to front
class Solution
{
public:
int largestPerimeter(vector<int>& nums)
{
sort(nums.begin(), nums.end());
for (int i = nums.size() - 1; i >= 2; i--)
{
for (int j = i - 1; j >= 1; j--)
{
for (int k = j - 1; k >= 0; k--)
{
if (nums[j] + nums[k] > nums[i])
{
return nums[i] + nums[j] + nums[k];
}
else
break;
}
}
}
return 0;
}
};
I went to see the solution
So this is called sorting + greed
We must choose the two largest numbers less than c
class Solution
{
public:
int largestPerimeter(vector<int>& nums)
{
sort(nums.begin(), nums.end());
for (int i = nums.size() - 1; i >= 2; i--)
{
if (nums[i] < nums[i - 1] + nums[i - 2])
return nums[i] + nums[i - 1] + nums[i - 2];
}
return 0;
}
};
1030. Arrange matrix cells in distance order
1030. Arrange matrix cells in distance order
Give the matrix of row R and column C, where the integer coordinates of the cells are (r, c), satisfying 0 < = R < R and 0 < = C < C.
In addition, we give a cell with coordinates (r0, c0) in the matrix.
Returns the coordinates of all cells in the matrix and arranges them in the order of minimum to maximum distance to (r0, c0), where the distance between two cells (r1, c1) and (r2, c2) is Manhattan distance, | r1 - r2| + |c1 - c2|. (you can return answers in any order that meets this condition.)
Example 1:
Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0], [0,1]]
Explanation: the distance from (r0, c0) to other cells is: [0,1]
Learned how to customize sort in class
I think it will be easier to write this question with C's qsort
class Solution
{
public:
vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter)
{
vector<vector<int>>arr;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
arr.push_back({ i,j });
}
}
sort(arr.begin(), arr.end(), [=](vector<int>& a, vector<int>& b) {
return abs(a[0] - rCenter) + abs(a[1] - cCenter) < abs(b[0] - rCenter) + abs(b[1] - cCenter);
});
return arr;
}
};
1108. IP address invalidation
Give you an effective IPv4 Address, return the invalid version of this IP address.
The so-called invalid IP address is actually "[.]" Instead of each ".".
Example 1:
Input: address = "1.1.1.1"
Output: "1 [.] 1[.] 1[.] 1”
A more stupid way of writing
class Solution
{
public:
string defangIPaddr(string address)
{
string s = "[.]";
string s1;
for (auto n : address)
{
if (n != '.')
{
s1.push_back(n);
}
else
s1.append(s);
}
return s1;
}
};
1137. N th teponacci number
The teponacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 when n > = 0
Here is the integer n, please return the value of the nth teponacci number Tn.
Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
Iterative walk wave
class Solution
{
public:
int tribonacci(int n)
{
if (n == 0)
return 0;
else if (n <= 2)
return 1;
vector<int>arr(n + 1);
arr[0] = 0;
arr[1] = arr[2] = 1;
for (int i = 3; i <= n; ++i)
{
arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
}
return arr[n];
}
};
1260. 2D mesh migration
Give you a two-dimensional grid with m rows and n columns and an integer k. You need to migrate the grid k times.
Each migration operation will trigger the following activities:
- Elements located in grid[i][j] will be moved to grid[i][j + 1].
- Elements located in grid[i][n - 1] will be moved to grid[i + 1][0].
- Elements located in grid[m - 1][n - 1] will be moved to grid[0][0].
Please return the 2D mesh obtained after k migration operations.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2], [3,4,5], [6,7,8]]
My friends, this problem is too much
The library is closed and there is no time for optimization
class Solution
{
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k)
{
int i = 0;
int lenn = grid[0].size();
int tmp = k;
vector<vector<int>>arr;
while (tmp)
{
i = 0;
arr.clear();
for (auto n : grid)
{
for (int j = 0; j < lenn; j++)
{
n[(j + 1) % lenn] = grid[i][j];
if (i > 0 && j == lenn - 1)
{
n[0] = grid[i - 1][j];
}
}
arr.push_back(n);
arr[0][0] = grid[grid.size() - 1][n.size() - 1];
++i;
}
grid = arr;
tmp--;
}
return grid;
}
};
1314. Matrix areas and
Medium difficulty 119
Give you a matrix mat of m x n and an integer k. please return a matrix answer, where each answer[i][j] is the sum of all elements mat[r][c] that meet the following conditions:
- i - k <= r <= i + k,
- J - K < = C < = j + K and
- (r, c) in the matrix.
Example 1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16], [27,45,33], [24,39,28]]
1342. Number of operations to change the number to 0
1342. Number of operations to change the number to 0
Give you a non negative integer num, please return the number of steps required to turn it into 0. If the current number is even, you need to divide it by 2; Otherwise, subtract 1.
Example 1:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is an even number, divided by 2 to get 7.
Step 2) 7 is an odd number. Subtract 1 to get 6.
Step 3) 6 is an even number. Divide by 2 to get 3.
Step 4) 3 is an odd number. Subtract 1 to get 2.
Step 5) 2 is an even number. Divide by 2 to get 1.
Step 6) 1 is an odd number, and 0 is obtained by subtracting 1.
class Solution
{
public:
int numberOfSteps(int num)
{
int tmp = 0;
while (num)
{
if (num & 1)
{
num -= 1;
}
else
{
num /= 2;
}
++tmp;
}
return tmp;
}
};
1351. Negative numbers in statistically ordered matrices
1351. Negative numbers in statistically ordered matrices
Give you a matrix grid of m * n. The Elements in the matrix are arranged in non increasing order, whether in rows or columns.
Please count and return the number of negative numbers in the grid.
Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: there are 8 negative numbers in the matrix.
Traversal + accumulation
class Solution
{
public:
int countNegatives(vector<vector<int>>& grid)
{
int tmp = 0;
for (auto n:grid)
{
for (auto m : n)
{
if (m < 0)
{
tmp++;
}
}
}
return tmp;
}
};
Dichotomy
class Solution
{
public:
int countNegatives(vector<vector<int>>& grid)
{
int num = 0;
for (auto x : grid)
{
int left = 0;
int right = x.size() - 1;
int mid;
int pos = -1;
while (left <= right)
{
mid = left + (right - left) / 2;
if (x[mid] < 0)
{
pos = mid;
right = mid - 1;
}
else
left = mid + 1;
}
if (pos!=-1)
num += x.size() - pos;// pos=-1 indicates that this line is full of numbers > = 0 and cannot be counted
}
return num;
}
};
Find 1 in reverse order
class Solution
{
public:
int countNegatives(vector<vector<int>>& grid)
{
int num = 0;
int m = grid[0].size();
int pos = grid[0].size() - 1;
for (auto x : grid)
{
int i;
for (i = pos; i >= 0; --i)
{
if (x[i] >= 0)
{
if (i + 1 < m)
{
pos = i + 1;
num += m - pos;
}
break;
}
}
if (i == -1)//This line is all negative
{
num += m;
pos = -1;
}
}
return num;
}
};
Reverse lookup 2
class Solution
{
public:
int countNegatives(vector<vector<int>>& grid)
{
int cnt = 0;
int N = grid[0].size() - 1;
int pos = N;
for (int i = 0; i < grid.size(); ++i)
{
// Find the first number not less than 0 from pos to the left, save it in pos, and find the next line from pos
while (pos >= 0 && grid[i][pos] < 0)
{
--pos;
}
cnt += N - pos;
}
return cnt;
}
};
1365. How many numbers are smaller than the current number
1365. How many numbers are smaller than the current number
Give you an array nums. For each element nums[i], please count the number of all numbers smaller than it in the array.
In other words, for each num [i], you must calculate the number of effective J, where j satisfies J= I and num [J] < num [i].
Returns the answer as an array.
Example 1:
Input: num = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8, there are four smaller numbers: (1, 2, 2 and 3).
There is no smaller number for num [1] = 1.
For nums[2]=2, there is a smaller number: (1).
For nums[3]=2, there is a smaller number: (1).
For nums[4]=3, there are three smaller numbers: (1, 2 and 2).
Simple method: two-layer cycle
class Solution
{
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums)
{
vector<int>ret(nums.size(), 0);
for (int i = 0; i < nums.size(); i++)
{
for (int j = 0; j < nums.size(); j++)
{
if (nums[j] < nums[i])
{
ret[i]++;
}
}
}
return ret;
}
};
1380. Lucky numbers in the matrix
1380. Lucky numbers in the matrix
Give you a matrix of m * n, the numbers in the matrix are different. Please return all lucky numbers in the matrix in any order.
Lucky numbers refer to the elements in the matrix that meet the following two conditions at the same time:
- The smallest of all elements in the same row
- Maximum of all elements in the same column
Example 1:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number because it is the minimum value in the row and the maximum value in the column.
I didn't time out
Traversal
First save the number tmpj of the smallest column in row i, then traverse the number tmpk of the largest row in the column, and judge the relationship between tmpk and i. if it is consistent, it indicates that it is a lucky number
class Solution
{
public:
vector<int> luckyNumbers(vector<vector<int>>& matrix)
{
int min = INT_MAX;
int max = INT_MIN;
int tmpj,tmpk;
vector<int>arr;
for (int i=0;i<matrix.size();++i)
{
min = INT_MAX;
max = INT_MIN;
for (int j = 0; j < matrix[0].size(); ++j)
{
if (matrix[i][j] < min)
{
tmpj = j;
min = matrix[i][j];
}
}
for (int k = 0; k < matrix.size(); ++k)
{
if (matrix[k][tmpj]> max)
{
tmpk = k;
max = matrix[k][tmpj];
}
}
if (tmpk == i)
arr.push_back(min);
}
return arr;
}
};
1389. Create the target array in the established order
1389. Create the target array in the established order
Here are two integer arrays nums and index. You need to create the target array according to the following rules:
- The target array target was initially empty.
- Read num [i] and index[i] from left to right, and insert the value num [i] at the subscript index[i] in the target array.
- Repeat the previous step until there are no elements to read in num and index.
Please return the target array.
The title ensures that the number insertion position always exists.
Example 1:
Input: num = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums index target
0 0 [0]
1 1 [0,1]
2 2 [0,1,2]
3 2 [0,1,3,2]
4 1 [0,4,1,3,2]
Insert function: insert(where, value)
class Solution
{
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index)
{
vector<int>target;
for (int i = 0; i < nums.size(); ++i)
{
target.insert(target.begin() + index[i], nums[i]);
}
return target;
}
};
1470. Rearrange array
Here is an array nums. There are 2n elements in the array, which are arranged in the format of [x1,x2,...,xn,y1,y2,...,yn].
Please rearrange the array in [x1,y1,x2,y2,...,xn,yn] format and return the rearranged array.
Example 1:
Input: num = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
Explanation: because x1=2, x2=5, x3=1, y1=3, y2=4, y3=7, the answer is [2,3,5,4,1,7]
Find rules
class Solution
{
public:
vector<int> shuffle(vector<int>& nums, int n)
{
vector<int>ret(nums.size());
for (int i = 0; i < nums.size(); ++i)
{
if (i & 1)
{
ret[i] = nums[i / 2 + n];
}
else
ret[i] = nums[i / 2];
}
return ret;
}
};
1480. Dynamic sum of one-dimensional arrays
1480. Dynamic sum of one-dimensional arrays
Give you an array nums. The calculation formula of array "dynamic sum" is: runningsum [i] = sum (Num [0]... Num [i]).
Please return the dynamic and of nums.
Example 1:
Input: num = [1,2,3,4]
Output: [1,3,6,10]
Explanation: the dynamic and calculation process is [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4].
nums[i] += nums[i - 1]
class Solution
{
public:
vector<int> runningSum(vector<int>& nums)
{
for (int i = 0; i < nums.size(); ++i)
{
if (i == 0)
continue;
nums[i] += nums[i - 1];
}
return nums;
}
};
1492. Factor k of n
I'll give you two positive integers n and k.
If the positive integer i satisfies n% i = = 0, then we say that the positive integer i is the factor of the integer n.
Consider all factors of integer n and arrange them in ascending order. Please return the k-th factor. If the number of factors of n is less than k, please return - 1.
Example 1:
Input: n = 12, k = 3
Output: 3
Explanation: the factor list includes [1, 2, 3, 4, 6, 12], and the third factor is 3.
For the number of tags K, whenever n%i0, execute K –. When k0, that is, i at this time is the k-th factor
class Solution
{
public:
int kthFactor(int n, int k)
{
for (int i = 1; i <= n; i++)
{
if (n % i == 0)
{
k--;
}
if(k==0)
{
return i;
}
}
return -1;
}
};
1572. Sum of diagonal elements of matrix
1572. Sum of diagonal elements of matrix
Give you a square matrix mat, please return the sum of the diagonal elements of the matrix.
Please return the sum of the elements on the main diagonal and the elements on the sub diagonal and not on the main diagonal of the matrix.
Example 1:
Input: mat = [[1,2,3],
[4,5,6],
[7,8,9]]
Output: 25
Explanation: the sum of diagonal lines is: 1 + 5 + 9 + 3 + 7 = 25
Note that the element mat[1][1] = 5 is calculated only once.
Matrix traversal: find the i and j laws of the diagonal
(after reading the solution, I found that this is line by line data retrieval)
class Solution
{
public:
int diagonalSum(vector<vector<int>>& mat)
{
int tmp = 0;
for (int i = 0, j = 0; i < mat[0].size(); ++i, ++j)
{
tmp += mat[i][i] + mat[j][mat[0].size() - 1 - j];
}
if (mat[0].size() & 1)
{
tmp -= mat[mat[0].size() / 2][mat[0].size() / 2];
}
return tmp;
}
};
1582. Special positions in binary matrix
1582. Special positions in binary matrix
Give you a matrix mat with the size of rows x cols, where mat[i][j] is 0 or 1. Please return the number of special positions in the matrix * mat *.
Special position definition: if mat[i][j] == 1 and all other elements in row I and column j are 0 (the subscripts of rows and columns start from 0), the position (i, j) is called a special position.
Example 1:
Input: mat = [[1,0,0],
[0,0,1],
[1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in the row and column are 0
And 1380 questions
Traversal
First save the number of columns tmpj with unique 1 in row i, then traverse the number of rows tmpk with unique 1 in this column, and judge the relationship between tmpk and i. if it is consistent, it indicates that it is a special position
class Solution
{
public:
int numSpecial(vector<vector<int>>& mat)
{
int sum1 = 0;
int sum2 = 0;
int tmpj,tmpk;
int num = 0;
for (int i = 0; i < mat.size(); ++i)
{
sum1 = 0;
tmpj = -1;
for (int j = 0; j < mat[0].size(); ++j)
{
if (mat[i][j])
{
if (sum1 == 0)
{
tmpj =j;
sum1++;
}
else
{
tmpj = -1;
break;
}
}
}
if (tmpj!=-1)
{
tmpk = -1;
sum2 = 0;
for (int k = 0; k < mat.size(); ++k)
{
if (mat[k][tmpj])
{
if (sum2 == 0)
{
tmpk = k;
sum2++;
}
else
{
tmpk = -1;
break;
}
}
}
if (tmpk ==i)
{
num++;
}
}
}
return num;
}
};
1672. Total assets of the richest customers
1672. Total assets of the richest customers
Give you an integer grid accounts of m x n, where accounts[i][j] is the number of assets hosted by the i-th customer in the j-th bank. Returns the total amount of assets owned by the richest customer.
The total assets of customers are the sum of the assets they hold in each bank. The richest customer is the customer with the largest total assets.
Example 1:
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
Total assets of the first customer = 1 + 2 + 3 = 6
Total assets of the 2nd customer = 3 + 2 + 1 = 6
Both customers are the richest, and the total assets are 6, so 6 is returned.
Ergodic accumulation
It's poisonous. If you change the three eye operator to fmax, the efficiency will be doubled directly
class Solution
{
public:
int maximumWealth(vector<vector<int>>& accounts)
{
int max = INT_MIN;
for (auto n : accounts)
{
int tmp = 0;
for (auto m : n)
{
tmp += m;
}
//max = tmp > max ? tmp : max;
max = fmax(max, tmp);
}
return max;
}
};
1827. Increment array with minimum operation
1827. Increment array with minimum operation
Give you an integer array nums (subscript starts from 0). In each operation, you can select an element in the array and increase it by 1.
- For example, if num = [1,2,3], you can choose to add num [1] to get num = [1, * * 3 * *, 3].
Please return the minimum number of operations to strictly increment num.
We call the array nums strictly incremental when it satisfies for all 0 < = I < nums Length - 1 has num [i] < num [i + 1]. An array of length 1 is a special case of strictly increasing.
Example 1:
Input: num = [1,1,1]
Output: 3
Explanation: you can do the following:
- Add nums[2] and the array becomes [1,1,2].
- Add nums[1], and the array becomes [1,2,2].
- Add nums[2] and the array becomes [1,2,3].
I feel that I have done similar problems before, which are a little more difficult than this one
This is traversal: when not strictly increasing + difference + 1
class Solution
{
public:
int minOperations(vector<int>& nums)
{
int tmp = 0;
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] <= nums[i - 1])
{
tmp += nums[i - 1] - nums[i] + 1;
nums[i] = nums[i - 1] + 1;
}
}
return tmp;
}
};
1913. Maximum product difference between two number pairs
1913. Maximum product difference between two number pairs
The product difference between two number pairs (a, b) and (c, d) is defined as (a * b) - (c * d).
- For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.
Give you an integer array nums. Select four different subscripts W, x, y and z to maximize the product difference between number pairs (nums[w], nums[x]) and (nums[y], nums[z]).
Returns the maximum value of the product difference obtained in this way.
Example 1:
Input: num = [5,6,2,7,4]
Output: 34
Explanation: elements with subscripts 1 and 3 can be selected to form the first number pair (6, 7) and subscripts 2 and 4 to form the second number pair (2, 4)
The product difference is (6 * 7) - (2 * 4) = 34
Sorting, return Max * sub large - min * sub small (true if and only if all array elements are non negative)
class Solution
{
public:
int maxProductDifference(vector<int>& nums)
{
sort(nums.begin(), nums.end());
return nums[nums.size() - 1] * nums[nums.size() - 2] - nums[0] * nums[1];
}
};
Official greed
class Solution
{
public:
int maxProductDifference(vector<int>& nums)
{
int n = nums.size();
// The two largest values in the array
int mx1 = max(nums[0], nums[1]);//maximum
int mx2 = min(nums[0], nums[1]);//Second largest
// The smallest two values in the array
int mn1 = min(nums[0], nums[1]);//minimum
int mn2 = max(nums[0], nums[1]);//Second small
for (int i = 2; i < n; ++i)
{
int tmp = nums[i];
if (tmp > mx1)
{
mx2 = mx1;
mx1 = tmp;
}
else if (tmp > mx2)
{
mx2 = tmp;
}
if (tmp < mn1)
{
mn2 = mn1;
mn1 = tmp;
}
else if (tmp < mn2)
{
mn2 = tmp;
}
}
return (mx1 * mx2) - (mn1 * mn2);
}
};
1920. Building arrays based on permutations
1920. Building arrays based on permutations
Give you an array num starting from 0 (subscript also starts from 0). Please build an array ans of the same length, where ans [i] = num [num [i]] is satisfied for each I (0 < = I < num.length). Return the constructed array ANS.
The permutation nums starting from 0 is from 0 to nums An array of different integers of length - 1 (0 and num.length - 1 are also included).
Example 1:
Input: num = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: the ans array is constructed as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
= [0,1,2,4,5,3]
Write according to the meaning of the title
class Solution
{
public:
vector<int> buildArray(vector<int>& nums)
{
vector<int>ret(nums.size());
for (int i = 0; i < nums.size(); ++i)
{
ret[i] = nums[nums[i]];
}
return ret;
}
};
1929. Array concatenation
Give you an integer array num of length n. Please construct an answer array ans with a length of 2n. The array subscript counts from 0. For all i with 0 < = i < n, all the following requirements are met:
- ans[i] == nums[i]
- ans[i + n] == nums[i]
Specifically, ans is formed by concatenating two nums arrays.
Returns the array ans.
Example 1:
Input: num = [1,2,1]
Output: [1,2,1,1,2,1]
Explanation: the array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]
Method 1: create a new array
class Solution
{
public:
vector<int> getConcatenation(vector<int>& nums)
{
vector<int>ret(nums.size() * 2);
for (int i = 0; i < nums.size(); i++)
{
ret[i] = ret[i + nums.size()] = nums[i];
}
return ret;
}
};
Found that the efficiency was very slow, he ran to glance at the problem solution
Method 2: just push directly behind nums
class Solution
{
public:
vector<int> getConcatenation(vector<int>& nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
{
nums.push_back(nums[i]);
}
return nums;
}
};
2006. Number of pairs whose absolute value of difference is K
2006. Number of pairs whose absolute value of difference is K
Give you an integer array nums and an integer k. please return the number of pairs (i, j) that satisfy I < J and | nums[i] - nums[j]| == k.
|The value of x | is defined as:
- If x > = 0, the value is X.
- If x < 0, the value is - X.
Example 1:
Input: num = [1,2,2,1], k = 1
Output: 4
Explanation: the number pair with absolute value of difference of 1 is:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
Write according to the meaning of the title
class Solution
{
public:
int countKDifference(vector<int>& nums, int k)
{
int tmp = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (abs(nums[i] - nums[j]) == k)
{
tmp++;
}
}
}
return tmp;
}
};
2022. Convert one-dimensional array to two-dimensional array
2022. Convert one-dimensional array to two-dimensional array
Give you an array of one-dimensional integers with subscripts starting from 0, original and two integers m and n. You need to use all the elements in original to create a two-dimensional array of M rows and N columns.
In original, elements with subscripts from 0 to N - 1 (both included) constitute the first row of the two-dimensional array, elements with subscripts from n to 2 * n - 1 (both included) constitute the second row of the two-dimensional array, and so on.
Please return a two-dimensional array of m x n according to the above process. If such a two-dimensional array cannot be formed, please return an empty two-dimensional array.
Example 1:
Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2], [3,4]]
Explanation:
The constructed two-dimensional array should contain 2 rows and 2 columns.
The first n=2 part of the original is [1,2], which constitutes the first row of the two-dimensional array.
The second n=2 part in the original is [3,4], which forms the second row of the two-dimensional array.
New array save
class Solution
{
public:
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n)
{
vector<vector<int>>arr(m, vector<int>(n));
if (m * n != original.size())
{
arr.clear();
return arr;
}
int i = 0, j = 0;
for (auto k : original)
{
arr[i][j] = k;
if (++j == n)
{
j = 0;
++i;
}
}
return arr;
}
};
Optimized a little
class Solution
{
public:
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n)
{
if (m * n != original.size())
{
return vector<vector<int>>{};
}
vector<vector<int>>arr(m, vector<int>(n));
int i = 0, j = 0;
for (auto k : original)
{
arr[i][j] = k;
if (++j == n)
{
j = 0;
++i;
}
}
return arr;
}
};
Sword finger Offer 05 Replace spaces
Sword finger Offer 05 Replace spaces
Please implement a function to replace each space in the string s with "% 20".
Example 1:
Enter: s = "We are happy."
Output: "We%20are%20happy."
Same as question 1108
class Solution
{
public:
string replaceSpace(string s)
{
string s1 = "%20";
string s2;
for (auto n : s)
{
if (n == ' ')
{
s2.append(s1);
}
else
s2.push_back(n);
}
return s2;
}
};
Sword finger Offer 17 Print from 1 to maximum n digits
Sword finger Offer 17 Print from 1 to maximum n digits
Enter the number N and print out the decimal number from 1 to the maximum n digits in order. For example, if you enter 3, 1, 2 and 3 will be printed up to the maximum 3 digits 999.
Example 1:
Input: n = 1
Output: [1,2,3,4,5,6,7,8,9]
Note: n digits + start from 1
class Solution
{
public:
vector<int> printNumbers(int n)
{
vector<int>ret;
for (int i = 0; i < pow(10,n)-1; i++)
{
ret.push_back(i + 1);
}
return ret;
}
};
Sword finger Offer 55 - I. depth of binary tree
Sword finger Offer 55 - I. depth of binary tree
Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) passing from root node to leaf node form a path of the tree, and the length of the longest path is the depth of the tree.
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
Returns its maximum depth 3.
level traversal
class Solution
{
public:
int maxDepth(TreeNode* root)
{
queue<TreeNode*>que;
if (root)
que.push(root);
int tmp = 0;
while (!que.empty())
{
tmp++;
int size = que.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
{
que.push(node->right);
}
}
}
return tmp;
}
};
Sword finger Offer 58 - II Left rotation string
Sword finger Offer 58 - II Left rotation string
The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to realize the function of string left rotation operation. For example, if you enter the string "abcdefg" and the number 2, the function will return the result "cdefgab" obtained by rotating two bits left.
Example 1:
Input: s = "abcdefg", k = 2
Output: "cdefgab"
Just call the function directly in C + +
class Solution
{
public:
string reverseLeftWords(string s, int n)
{
string s1;
s1.append(s.begin() + n, s.end());
s1.append(s.begin(), s.begin() + n);
return s1;
}
};
Sword finger Offer 64 Find 1 + 2 +... + n
Sword finger Offer 64 Find 1 + 2 +... + n
For 1 + 2 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.
Example 1:
Input: n = 3
Output: 6
Wrote a recursive
Recursion precautions: exit conditions shall be provided
class Solution
{
public:
int sumNums(int n)
{
if (n == 1)
return 1;
return n + sumNums(n - 1);
}
};
Sword finger Offer 65 No addition, subtraction, multiplication and division
Sword finger Offer 65 No addition, subtraction, multiplication and division
Write a function and find the sum of two integers. It is required that four operation symbols "+", "-", "*", "/" shall not be used in the function body.
Example:
Input: a = 1, b = 1
Output: 2
Same as 371
int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
Interview question 08.05 Recursive multiplication
Interview question 08.05 Recursive multiplication
Recursive multiplication. Write a recursive function that multiplies two positive integers without using the * operator. You can use plus sign, minus sign and displacement, but be stingy.
Example 1:
Input: A = 1, B = 10
Output: 10
A. The essence of the multiplication of two numbers B (both non-zero) is that a is added B times
Recursive implementation
class Solution
{
public:
int multiply(int A, int B)
{
if (A == 0 || B == 0)
return 0;
return A + multiply(A, B - 1);
}
};
Interview question 17.01 Addition without plus sign
Interview question 17.01 Addition without plus sign
Design a function to add two numbers. Do not use + or other arithmetic operators.
Example:
Input: a = 1, b = 1
Output: 2
Sword finger offer65
int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
LCP 01. Guess the number
Little A and little B are playing guessing numbers. Little B randomly selects one from 1, 2 and 3 every time, and little A also selects one from 1, 2 and 3 every time. They played this game three times. Please go back to little A and guess how many times?
The guess array entered is the guess of small A every time, and the answer array is the selection of small B every time. The length of guess and answer is equal to 3.
Example 1:
Input: guess = [1,2,3], answer = [1,2,3]
Output: 3
Explanation: Xiao A guessed right every time.
A problem of excessive water
class Solution
{
public:
int game(vector<int>& guess, vector<int>& answer)
{
int tmp = 0;
for (int i = 0; i < 3; i++)
{
if (guess[i] == answer[i])
{
tmp++;
}
}
return tmp;
}
};
LCP 06. Take the coin
There are n piles of coins on the table, and the quantity of each pile is saved in the array coins. We can choose any pile at a time, take one or two of them, and find the minimum number of times to take all force deduction coins.
Example 1:
Input: [4,2,1]
Output: 4
Explanation: the first pile of force deduction coins needs to be taken at least twice, the second pile needs to be taken at least once, and the third pile needs to be taken at least once, a total of 4 times.
FA Yi
In short, try to take two at a time, and only get one at a time when the original number of each pile is odd
Therefore, you can directly use the property of int (number + 1) / 2
class Solution
{
public:
int minCount(vector<int>& coins)
{
int tmp = 0;
for (int i = 0; i < coins.size(); i++)
{
tmp += (coins[i] + 1) / 2;
}
return tmp;
}
};
However, the efficiency of method 1 is a little low. It can be optimized by using the premise of odd binary & 1 = = 1
Method II
Note: note the priority of & and add parentheses to coins [i] & 1
class Solution
{
public:
int minCount(vector<int>& coins)
{
int tmp = 0;
for (int i = 0; i < coins.size(); i++)
{
tmp += coins[i] / 2 + (coins[i] & 1);
}
return tmp;
}
};
LCP 44. Opening ceremony fireworks
Adjustable dfs
LCP 44. Opening ceremony fireworks
The opening ceremony of the "Li Kou challenge" began, and a huge fireworks in the shape of a binary tree bloomed in the air.
Given a binary tree, root represents fireworks, and the node value represents the color type of giant fireworks. Please help Xiaokou calculate how many different colors the giant fireworks have.
Example 1:
Input: root = [1,3,2,1,null,2]
Output: 3
Explanation: there are three different colors in fireworks, with values of 1, 2 and 3 respectively
level traversal
I have to say, I still like to use sequence traversal in the topic of binary tree class
class Solution
{
public:
int numColor(TreeNode* root)
{
unordered_set<int>set;
queue<TreeNode*>que;
if (root != NULL)
{
que.push(root);
}
while (!que.empty())
{
int size = que.size();
for (int i = 0; i < size; ++i)
{
TreeNode* node = que.front();
set.insert(que.front()->val);
que.pop();
if (node->left)
{
que.push(node->left);
}
if (node->right)
{
que.push(node->right);
}
}
}
return set.size();
}
};
dfs seen in comment area
I don't understand this algorithm at present
class Solution
{
public:
unordered_set<int>set;
void dfs(TreeNode* root)
{
if (root)
set.insert(root->val);
if (root->left)
dfs(root->left);
if (root->right)
dfs(root->right);
}
int numColor(TreeNode* root)
{
dfs(root);
return set.size();
}
};
Fork tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
Returns its maximum depth 3.
level traversal
class Solution
{
public:
int maxDepth(TreeNode* root)
{
queue<TreeNode*>que;
if (root)
que.push(root);
int tmp = 0;
while (!que.empty())
{
tmp++;
int size = que.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if (node->left)
que.push(node->left);
if (node->right)
{
que.push(node->right);
}
}
}
return tmp;
}
};
Sword finger Offer 58 - II Left rotation string
Sword finger Offer 58 - II Left rotation string
The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to realize the function of string left rotation operation. For example, if you enter the string "abcdefg" and the number 2, the function will return the result "cdefgab" obtained by rotating two bits left.
Example 1:
Input: s = "abcdefg", k = 2
Output: "cdefgab"
Just call the function directly in C + +
class Solution
{
public:
string reverseLeftWords(string s, int n)
{
string s1;
s1.append(s.begin() + n, s.end());
s1.append(s.begin(), s.begin() + n);
return s1;
}
};
Sword finger Offer 64 Find 1 + 2 +... + n
Sword finger Offer 64 Find 1 + 2 +... + n
For 1 + 2 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.
Example 1:
Input: n = 3
Output: 6
Wrote a recursive
Recursion precautions: exit conditions shall be provided
class Solution
{
public:
int sumNums(int n)
{
if (n == 1)
return 1;
return n + sumNums(n - 1);
}
};
Sword finger Offer 65 No addition, subtraction, multiplication and division
Sword finger Offer 65 No addition, subtraction, multiplication and division
Write a function and find the sum of two integers. It is required that four operation symbols "+", "-", "*", "/" shall not be used in the function body.
Example:
Input: a = 1, b = 1
Output: 2
Same as 371
int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
Interview question 08.05 Recursive multiplication
Interview question 08.05 Recursive multiplication
Recursive multiplication. Write a recursive function that multiplies two positive integers without using the * operator. You can use plus sign, minus sign and displacement, but be stingy.
Example 1:
Input: A = 1, B = 10
Output: 10
A. The essence of the multiplication of two numbers B (both non-zero) is that a is added B times
Recursive implementation
class Solution
{
public:
int multiply(int A, int B)
{
if (A == 0 || B == 0)
return 0;
return A + multiply(A, B - 1);
}
};
Interview question 17.01 Addition without plus sign
Interview question 17.01 Addition without plus sign
Design a function to add two numbers. Do not use + or other arithmetic operators.
Example:
Input: a = 1, b = 1
Output: 2
Sword finger offer65
int add(int a, int b)
{
while (b)
{
unsigned int carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
LCP 01. Guess the number
Little A and little B are playing guessing numbers. Little B randomly selects one from 1, 2 and 3 every time, and little A also selects one from 1, 2 and 3 every time. They played this game three times. Please go back to little A and guess how many times?
The guess array entered is the guess of small A every time, and the answer array is the selection of small B every time. The length of guess and answer is equal to 3.
Example 1:
Input: guess = [1,2,3], answer = [1,2,3]
Output: 3
Explanation: Xiao A guessed right every time.
A problem of excessive water
class Solution
{
public:
int game(vector<int>& guess, vector<int>& answer)
{
int tmp = 0;
for (int i = 0; i < 3; i++)
{
if (guess[i] == answer[i])
{
tmp++;
}
}
return tmp;
}
};
LCP 06. Take the coin
There are n piles of coins on the table, and the quantity of each pile is saved in the array coins. We can choose any pile at a time, take one or two of them, and find the minimum number of times to take all force deduction coins.
Example 1:
Input: [4,2,1]
Output: 4
Explanation: the first pile of force deduction coins needs to be taken at least twice, the second pile needs to be taken at least once, and the third pile needs to be taken at least once, a total of 4 times.
FA Yi
In short, try to take two at a time, and only get one at a time when the original number of each pile is odd
Therefore, you can directly use the property of int (number + 1) / 2
class Solution
{
public:
int minCount(vector<int>& coins)
{
int tmp = 0;
for (int i = 0; i < coins.size(); i++)
{
tmp += (coins[i] + 1) / 2;
}
return tmp;
}
};
However, the efficiency of method 1 is a little low. It can be optimized by using the premise of odd binary & 1 = = 1
Method II
Note: note the priority of & and add parentheses to coins [i] & 1
class Solution
{
public:
int minCount(vector<int>& coins)
{
int tmp = 0;
for (int i = 0; i < coins.size(); i++)
{
tmp += coins[i] / 2 + (coins[i] & 1);
}
return tmp;
}
};
LCP 44. Opening ceremony fireworks
Adjustable dfs
LCP 44. Opening ceremony fireworks
The opening ceremony of the "Li Kou challenge" began, and a huge fireworks in the shape of a binary tree bloomed in the air.
Given a binary tree, root represents fireworks, and the node value represents the color type of giant fireworks. Please help Xiaokou calculate how many different colors the giant fireworks have.
Example 1:
Input: root = [1,3,2,1,null,2]
Output: 3
Explanation: there are three different colors in fireworks, with values of 1, 2 and 3 respectively
level traversal
I have to say, I still like to use sequence traversal in the topic of binary tree class
class Solution
{
public:
int numColor(TreeNode* root)
{
unordered_set<int>set;
queue<TreeNode*>que;
if (root != NULL)
{
que.push(root);
}
while (!que.empty())
{
int size = que.size();
for (int i = 0; i < size; ++i)
{
TreeNode* node = que.front();
set.insert(que.front()->val);
que.pop();
if (node->left)
{
que.push(node->left);
}
if (node->right)
{
que.push(node->right);
}
}
}
return set.size();
}
};
dfs seen in comment area
I don't understand this algorithm at present
class Solution
{
public:
unordered_set<int>set;
void dfs(TreeNode* root)
{
if (root)
set.insert(root->val);
if (root->left)
dfs(root->left);
if (root->right)
dfs(root->right);
}
int numColor(TreeNode* root)
{
dfs(root);
return set.size();
}
};