2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
C++-rakenteissa on konstruktoreita.
#include voi näkyä ohjelmatiedoston keskellä.
Muodolliset parametrien nimet voidaan jättää pois funktiomäärittelyistä, mutta ei määritelmistä.
Ei-tyhjä tietorakenne, jos se täyttää seuraavat kaksi ehtoa:
Sitä kutsutaan lineaariseksi rakenteeksi ja sitä kutsutaan lineaariseksi taulukoksi tietorakenteissa.
Kaksoislinkitetyssä luettelosolmussa on kaksi osoitinkenttää ja se on lineaarinen rakenne.
Kaikkien pyöreän linkitetyn luettelon solmujen osoittimet eivät ole nolla-arvoja, ja ne ovat myös lineaarisia rakenteita.
Hajautustaulukon rakentamismenetelmiä ovat: suoraosoitemenetelmä, jako- ja jakojäännösmenetelmä.
Konfliktinratkaisumenetelmiä ovat:
Kun annetaan kaksi kokonaislukua vasemmalle ja oikealle, jotka edustavat väliä [vasen, oikea], palauta kaikkien tämän välin lukujen bittikohtaisen JA-arvon tulos.
Bittisarjalle, niin kauan kuin on bitti, jonka arvo on nolla, tämän sarjan bittikohtaisen JA-operaation tulos on nolla.
Yllä olevasta esimerkistä voimme löytää senKaikille numeroille suoritetun bittikohtaisen JA-operaation tulos on kaikkien vastaavien binäärijonojen yhteinen etuliite ja loput bitit on täytetty nolilla.
Kun annetaan kokonaislukutaulukon numerot, jokainen elementti näkyy kolme kertaa paitsi elementti, joka esiintyy vain kerran. Etsi ja palauta elementti, joka esiintyy vain kerran.
Suunnittele algoritmi, jolla on lineaarinen aikamonimutkaisuus ja käytä vakiotilaa ongelman ratkaisemiseen.
Määritä jokainen binääribitti vuorotellen
Koska taulukon elementit ovat alueella int, voit laskea, onko vastauksen jokainen binääribitti vuorotellen 0 vai 1.
Tarkastellaan erityisesti vastauksen i:ttä binaarilukua (i on numeroitu 0:sta alkaen), joka voi olla 0 tai 1.
Vastauksen i:s numero on taulukon kaikkien elementtien i:nnen binääriluvun summan jäännös jaettuna kolmella.
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;
}
};
Nopea teho + rekursio
Nopean tehon algoritmin ydin on hajota ja hallitse -algoritmi.
Alkaen x:stä, neliöi edellisen tuloksen joka kerta suoraan. Laske 5 kertaa saadaksesi x64 teho.
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);
}
};
Kun on annettu kokonaisluku n, palauttaa tuloksen lopussa olevien nollien lukumäärä.
Häntänollien lukumäärä n:ssä on löytää kertoimien lukumäärä 10, ja 10=2x5, joten se muunnetaan alkutekijöiden lukumäärän 2 ja alkutekijöiden lukumäärän 5 pienemmäksi arvoksi n:ssä!.
Koska alkutekijöiden 5 lukumäärä ei ole suurempi kuin alkutekijöiden 2 lukumäärä, huomioidaan vain alkutekijöiden 5 lukumäärä.
Alkutekijöiden 5 määrä n:ssä on yhtä suuri kuin kunkin luvun alkutekijöiden 5 summa.
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;
}
};
nopeusosoitin
/**
* 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;
}
};
Puu on symmetrinen, jos sen vasen ja oikea alipuu ovat toistensa peilikuvia.
leveys ensimmäinen läpikulku
Haku alkaa juurisolmusta, kulkee jokaisen kierroksen kaikkien saman kerroksen solmujen läpi, laskee kerroksen solmujen lukumäärän ja kerroksen solmujen lukumäärän summan ja laskee sitten kerroksen keskiarvon.
/**
* 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;
}
};
Järjestetyn taulukon numerot, poista toistuvat elementit paikoista, jotta elementit, jotka esiintyvät useammin kuin kahdesti, näkyvät vain kahdesti, ja palauta taulukon uusi pituus poistamisen jälkeen.
Syöttötaulukkoa on muokattava paikan päällä ja käytettävä O(1) lisätilaa.
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;
}
};
Kun on annettu kokonaislukutaulukon numerot, käännä taulukon k-kohdassa olevia elementtejä oikealle.
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];
}
};
Kun otetaan huomioon ei-negatiivinen kokonaislukutaulukko, joka sijaitsee alun perin taulukon ensimmäisessä indeksissä, jokainen taulukon elementti edustaa maksimipituutta, joka voidaan hypätä.
Selvitä, voiko se hypätä viimeiseen indeksiin.
ahne
Jos taulukon missä tahansa paikassa y on paikka x, joka voidaan saavuttaa itsestään, ja x + num[x] ≥ y, niin y voidaan myös saavuttaa.
Jokaisen saavutettavan sijainnin x kohdalla se tekee peräkkäisistä paikoista x+1, x+2, ..., x+nums[x] saavutettavissa.
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;
}
};
Kun merkkijono s on annettu, järjestä se z-muotoon ylhäältä alas ja vasemmalta oikealle annetun rivimäärän numRows mukaan.
Simuloi käyttämällä 2D-matriiseja
Olkoon n merkkijonon s pituus, r = numRows Jos r=1 (vain yksi rivi) tai r >= n (vain yksi sarake), vastaus on sama kuin s ja se voidaan palauttaa suoraan.
Muissa tapauksissa harkitse kaksiulotteisen matriisin luomista, sitten merkkijonon s täyttämistä matriisiin siksak-kuviolla ja lopuksi matriisin ei-tyhjien merkkien skannaamista rivi riviltä vastauksen muodostamiseksi.
Kysymyksen tarkoituksen mukaan, kun täytämme merkkejä matriisiin, täytämme r merkkiä alaspäin, sitten r-2 merkkiä ylöspäin oikealle ja lopuksi palaamme ensimmäiselle riville, joten Z-muotoinen muunnosjakso t = r + r - 2 = 2r - 2. Jokainen sykli vie matriisissa 1+r-2 = r-1 saraketta.
On n/t jaksoa kertaa sarakkeiden lukumäärä, mikä on yhtä suuri kuin matriisin sarakkeiden lukumäärä.
Luo matriisi, jossa on r riviä ja c saraketta, iteroi sitten merkkijonojen läpi ja täytä ne siksak-kuviolla.
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;
}
};
Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema, jossa voit jakaa joitakin teknologian kehittämisen ongelmia myöhempää käyttöä varten
