私の連絡先情報
郵便メール:
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
C++ 構造にはコンストラクターがあります。
#include はプログラム ファイルの途中に記述できます。
仮パラメータ名は関数宣言では省略できますが、定義では省略できません。
次の 2 つの条件を満たす場合、空ではないデータ構造。
これは線形構造と呼ばれ、データ構造では線形テーブルと呼ばれます。
二重リンク リスト ノードには 2 つのポインター フィールドがあり、線形構造です。
循環リンク リスト内のすべてのノードのポインタは null ではなく、線形構造でもあります。
ハッシュテーブルの構築方法には、直接アドレス法、除算剰余法などがあります。
競合解決方法には次のようなものがあります。
区間 [left, right] を表す左と右の 2 つの整数を指定すると、この区間内のすべての数値のビット単位の AND の結果を返します。
一連のビットの場合、値が 0 のビットが存在する限り、この一連のビットごとの AND 演算の結果は 0 になります。
上の例では、次のことがわかります。すべての数値に対してビット単位の AND 演算を実行した結果は、対応するすべてのバイナリ文字列の共通プレフィックスとなり、残りのビットにはゼロが埋め込まれます。
整数配列 nums を指定すると、1 回だけ出現する要素を除き、各要素が 3 回出現します。1 回だけ出現する要素を検索して返します。
線形時間計算量を備えたアルゴリズムを設計し、一定空間を使用して問題を解決します。
各バイナリビットを順番に決定します
配列内の要素は int の範囲内にあるため、答えの各バイナリ ビットが 0 か 1 かを順番に計算できます。
具体的には、答えの i 番目の 2 進数 (i は 0 から始まる番号が付けられます) を考慮します。これは 0 または 1 です。
答えの i 番目の桁は、配列内のすべての要素の i 番目の 2 進数の合計を 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 から開始して、毎回前の結果を直接 2 乗します。 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! の末尾ゼロの数は約数 10 を求めることであり、10=2x5 なので、n! の素因数 2 と素因数 5 の小さい方の値を求めることに変換されます。
素因数 5 の数は素因数 2 の数より大きくならないため、素因数 5 の数のみが考慮されます。
n! 内の素因数 5 の数は、各数値の素因数 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 は、繰り返される要素をその場で削除し、2 回以上出現する要素が 2 回のみ出現するようにし、削除後の配列の新しい長さを返します。
入力配列はインプレースで変更する必要があり、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 を指定すると、指定された行数 numRows に従って、上から下、左から右に Z 字型に配置します。
2D マトリックスを使用してシミュレーションする
n を文字列 s の長さ、r = numRows とします。r=1 (1 行のみ)、または r >= n (1 列のみ) の場合、答えは s と同じであり、直接返すことができます。
他の場合には、2 次元行列を作成し、その行列上でジグザグ パターンで文字列 s を埋め、最後に行列内の空でない文字を 1 行ずつスキャンして答えを形成することを検討してください。
質問の意味からすると、マトリックス上に文字を埋めるときは、下にr文字埋めてから、右上にr-2文字埋めて、最後に最初の行に戻ることになるので、Z字型の変形周期はt = r + r - 2 = 2r - 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 などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。
郵便メール: