моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
В структурах C++ есть конструкторы.
#include может появиться в середине программного файла.
Формальные имена параметров могут быть опущены в объявлениях функций, но не в определениях.
Непустая структура данных, если она удовлетворяет следующим двум условиям:
Она называется линейной структурой и в структурах данных называется линейной таблицей.
Узел двусвязного списка имеет два поля указателей и представляет собой линейную структуру.
Указатели всех узлов в циклическом связанном списке не являются нулевыми и также представляют собой линейные структуры.
Методы построения хеш-таблицы включают в себя: метод прямого адреса, метод деления и остатка.
К методам разрешения конфликтов относятся:
Учитывая два целых числа слева и справа, представляющие интервал [лево, право], верните результат побитового И всех чисел в этом интервале.
Для серии битов, пока существует бит с нулевым значением, результат побитовой операции И этой серии равен нулю.
В приведенном выше примере мы можем найти, чтоРезультатом выполнения побитовой операции И над всеми числами является общий префикс всех соответствующих двоичных строк, а остальные биты дополнены нулями.
Учитывая целочисленный массив nums, каждый элемент появляется три раза, за исключением элемента, который появляется только один раз. Найдите и верните элемент, который появляется только один раз.
Разработайте алгоритм с линейной временной сложностью и используйте постоянное пространство для решения проблемы.
Определите каждый двоичный бит по очереди
Поскольку элементы массива находятся в диапазоне int, вы можете по очереди вычислить, равен ли каждый двоичный бит ответа 0 или 1.
В частности, рассмотрим i-ю двоичную цифру ответа (i нумеруется с 0), которая может быть 0 или 1.
i-я цифра ответа — это остаток от суммы i-х двоичных цифр всех элементов массива, разделенной на 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;
}
};
Быстрая мощность + рекурсия
Суть алгоритма быстрой мощности заключается в алгоритме «разделяй и властвуй».
Начиная с x, каждый раз возводите в квадрат предыдущий результат. Рассчитайте 5 раз, чтобы получить мощность 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);
}
};
Учитывая целое число n, верните n Количество конечных нулей в результате.
Число хвостовых нулей в n! предназначено для нахождения количества множителей 10, а 10 = 2x5, поэтому оно преобразуется в нахождение меньшего значения количества простых множителей 2 и количества простых множителей 5 в n!.
Поскольку количество простых делителей 5 не будет больше количества простых делителей 2, учитывается только количество простых делителей 5.
Количество простых делителей 5 в n! равно сумме количества простых делителей 5 каждого числа.
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;
}
};
указатель скорости
/**
* 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;
}
};
Дерево называется симметричным, если его левое и правое поддеревья являются зеркальными отображениями друг друга.
обход в ширину
Поиск начинается с корневого узла, проходит все узлы в одном слое в каждом раунде, вычисляет количество узлов в слое и сумму количества узлов в слое, а затем вычисляет среднее значение слоя.
/**
* 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;
}
};
Упорядоченный массив nums удаляет повторяющиеся элементы на месте, так что элементы, которые появляются более двух раз, появляются только дважды, и возвращает новую длину массива после удаления.
Входной массив должен быть изменен на месте и с использованием дополнительного пространства O(1).
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;
}
};
Учитывая целочисленный массив nums, поверните элементы массива на k позиций вправо.
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];
}
};
Учитывая неотрицательный целочисленный массив nums, первоначально расположенный по первому индексу массива, каждый элемент массива представляет максимальную длину, на которую можно перейти.
Определите, может ли он перейти к последнему индексу.
жадный
Для любой позиции y в массиве, если существует позиция x, которая может быть достигнута сама по себе, и x + nums[x] ≥ y, то y также может быть достигнута.
Для каждой достижимой позиции x он делает достижимыми последовательные позиции x+1, x+2, ..., x+nums[x].
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;
}
};
Дана строка s, расположите ее в виде буквы Z сверху вниз и слева направо в соответствии с заданным количеством строк numRows.
Симулируйте использование 2D-матриц
Пусть n — длина строки s, r = numRows. Для r=1 (только одна строка) или r >= n (только один столбец) ответ такой же, как s, и может быть возвращен напрямую.
В других случаях рассмотрите возможность создания двумерной матрицы, затем заполнения строки s зигзагообразным узором в матрице и, наконец, сканирования непустых символов в матрице построчно, чтобы сформировать ответ.
Согласно смыслу вопроса, когда мы заполняем символы в матрице, мы заполняем r символов вниз, затем r-2 символов вверх вправо и, наконец, возвращаемся в первую строку, поэтому период Z-образного преобразования т = г + г - 2 = 2р - 2. Каждый цикл будет занимать 1+r-2 = r-1 столбца матрицы.
Существует n/t периодов, умноженных на количество столбцов, что равно количеству столбцов матрицы.
Создайте матрицу с r строками и c столбцами, затем выполните итерацию по строкам и заполните их зигзагообразным узором.
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;
}
};
Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.
Почтамезофия@protonmail.com