2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
C++ structures have constructors.
#include can appear in the middle of a program file.
The parameter names can be omitted in a function declaration, but not in a definition.
A non-empty data structure satisfies the following two conditions:
It is called a linear structure, and in data structure it is called a linear list.
The node of a doubly linked list has two pointer fields and is a linear structure.
The pointers of all nodes in the circular linked list are not empty, and it also belongs to a linear structure.
Methods for constructing a hash table include: direct address method and division remainder method.
Methods for resolving conflicts include:
Given two integers left and right, representing the interval [left, right], return the bitwise AND result of all numbers in this interval.
For a series of bits, as long as there is a zero-valued bit, the result of the bitwise AND operation on the series is zero.
In the above example, we can find thatThe result of performing a bitwise AND operation on all the numbers is the common prefix of all corresponding binary strings followed by zero padding of the remaining bits.
Given an integer array nums, except for an element that only appears once, all other elements appear three times. Find and return the element that appears only once.
Design an algorithm that takes linear time and constant space to solve this problem.
Determine each binary bit in turn
Since the elements in the array are within the int range, we can calculate whether each binary bit of the answer is 0 or 1.
Specifically, consider the i-th binary bit of the answer (i starts at 0), which can be either 0 or 1.
The i-th bit of the answer is the remainder of the sum of the i-th bits of all elements in the array divided by 3.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i=0; i<32; i++){
int sum = 0;
for(int num : nums){
sum += ((num >> i) & 1);
}
ret += ((sum%3) << i);
}
return ret;
}
};
Fast exponentiation + recursion
The essence of the fast power algorithm is a divide and conquer algorithm.
Starting from x, just square the previous result each time. Do this 5 times and you will get x64.
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);
}
};
Given an integer n, return n! the number of trailing zeros in the result.
The number of trailing zeros in n! is the number of factors of 10, and 10=2x5, so it is converted to the smaller value of the number of prime factors 2 and the number of prime factors 5 in n!.
Since the number of prime factors 5 is not greater than the number of prime factors 2, only the number of prime factors 5 is considered.
The number of prime factors of 5 in n! is equal to the sum of the number of prime factors of 5 of each number.
class Solution {
public:
int trailingZeroes(int n) {
int res = 0;
for(int i=5; i<=n; i += 5){
for(int j=i; j%5 == 0; j/=5){
res++;
}
}
return res;
}
};
Fast and slow pointer
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr){
return false;
}
ListNode* slow = head->next;
ListNode* fast = head->next->next;
while(fast != nullptr){
if(slow == fast){
return true;
}
if(fast->next == nullptr){
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return false;
}
};
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr){
return list2;
}
if(list2 == nullptr){
return list1;
}
ListNode* newHead;
if(list1->val <= list2->val){
newHead = list1;
list1 = list1->next;
}else{
newHead = list2;
list2 = list2->next;
}
ListNode* p = newHead;
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;
}
}
while(list1){
p->next = list1;
p = p->next;
list1 = list1->next;
}
while(list2){
p->next = list2;
p = p->next;
list2 = list2->next;
}
return newHead;
}
};
A tree is symmetric if its left subtree is a mirror image of its right subtree.
Breadth-first traversal
The search starts from the root node, and each round traverses all nodes in the same layer, calculates the number of nodes in the layer and the sum of the number of nodes in the layer, and then calculates the average value of the layer.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> average;
queue<TreeNode *> que;
que.push(root);
while(!que.empty()){
double sum = 0;
int size = que.size();
for(int i=0; i<size; i++){
TreeNode* node = que.front();
que.pop();
sum += node->val;
TreeNode* left = node->left;
TreeNode* right = node->right;
if(left){
que.push(left);
}
if(right){
que.push(right);
}
}
average.push_back(sum / size);
}
return average;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode* > que;
if(!root){
return res;
}
que.push(root);
while(!que.empty()){
vector<int> temp;
int size = que.size();
for(int i=0; i<size; i++){
TreeNode* node = que.front();
que.pop();
temp.push_back(node->val);
TreeNode* left = node->left;
TreeNode* right = node->right;
if(left){
que.push(left);
}
if(right){
que.push(right);
}
}
res.push_back(temp);
}
return res;
}
};
Take a sorted array nums, delete the duplicate elements in place, so that the elements that appear more than twice appear only twice, and return the new length of the array after deletion.
The input array must be modified in-place and should be done using O(1) additional space.
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0;
int right = 0;
int n = nums.size();
int count = 0;
int sum = 0;
while (right < n) {
if (nums[left] == nums[right]) {
count++;
right++;
} else {
if (count > 1) {
nums[++left] = nums[left];
sum += 2;
} else {
sum += 1;
}
nums[++left] = nums[right++];
count = 1;
}
}
if (count > 1) {
nums[++left] = nums[left];
sum += 2;
} else {
sum += 1;
}
return sum;
}
};
Given an integer array nums, rotate the elements in the array k positions to the right.
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
int price = prices[0];
for(int i=1; i<prices.size(); i++){
if(prices[i] > price){
result = max(result, prices[i] - price);
}else{
price = prices[i];
}
}
return result;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(2)); //dp[i][0]第i天没有股票
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i<n; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
Given a non-negative integer array nums, initially located at the first index of the array, each element in the array represents the maximum length that can be jumped.
Determine whether it is possible to jump to the last subscript.
greedy
For any position y in the array, as long as there is a position x that is reachable by itself and x + nums[x] ≥ y, then y is also reachable.
For each reachable position x, it makes the consecutive positions x+1, x+2, ..., x+nums[x] reachable.
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for(int i=0; i<n; i++){
if(i <= rightmost){
rightmost = max(rightmost, i+nums[i]);
if(rightmost >= n-1){
return true;
}
}
}
return false;
}
};
Given a string s, arrange it in a zigzag pattern from top to bottom and from left to right according to the given number of rows numRows.
Using two-dimensional matrix simulation
Let n be the length of string s, r = numRows, for r = 1 (only one row), or r >= n (only one column), the answer is the same as s and can be returned directly.
For the rest of the cases, consider creating a two-dimensional matrix, then filling in the string s in a zigzag pattern on the matrix, and finally scanning the non-blank characters in the matrix row by row to form the answer.
According to the question, when we fill in the characters on the matrix, we will fill in r characters downwards, then fill in r-2 characters to the upper right, and finally return to the first row, so the zigzag transformation period is t = r + r - 2 = 2r - 2. Each period will occupy 1+r-2 = r-1 columns on the matrix.
There are n/t periods multiplied by the number of columns, which equals the number of columns in the matrix.
Create a matrix of r rows and c columns, then iterate over the string and fill it in in a zigzag pattern.
class Solution {
public:
string convert(string s, int numRows) {
int n = s.length(), r = numRows;
if(r == 1 || r >= n){
return s;
}
//变换周期
int t = 2*r - 2;
int c = (n + t -1) / t * (r - 1);
//创建二维字符串
vector<string> mat(r, string(c, 0));
for(int i = 0, x = 0, y =0; i<n; i++){
mat[x][y] = s[i];
if(i % t < r - 1){
++x; //向下移动
}else{
--x;
++y; //向右上移动
}
}
string ans;
for(auto &row : mat){
for(char ch : row){
if(ch){
ans += ch;
}
}
}
return ans;
}
};
class Solution {
public:
vector<string> splitString(string s){
istringstream iss(s);
vector<string> res;
string word;
while(iss >> word){
res.push_back(word);
}
return res;
}
string reverseWords(string s) {
vector<string> words = splitString(s);
string res;
for(int i=words.size()-1; i>=0; i--){
res += words[i] + " ";
}
res.pop_back();
return res;
}
};
I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.
