Berbagi teknologi

C soal tes tertulis

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Solusi manajemen partisi variabel

  • Adaptasi terbaik: area bebas bertambah sesuai kapasitas
  • Adaptasi terburuk: area bebas berkurang sesuai kapasitas
  • Adaptasi dulu: area bebas bertambah berdasarkan alamat

Ada konstruktor dalam struktur C++.

Buat pengguna atau grup baru di Linux

  • useradd: perintah digunakan untuk membuat akun pengguna
  • usermod: mengubah akun pengguna
  • groupadd: Membuat grup kerja baru
  • userdel: menghapus akun pengguna

#include dapat muncul di tengah file program.

Nama parameter formal dapat dihilangkan dalam deklarasi fungsi, tetapi tidak dalam definisi.

tabel linier

Struktur data tidak kosong jika memenuhi dua kondisi berikut:

  1. Hanya ada satu simpul akar
  2. Setiap node mempunyai paling banyak satu node sebelumnya dan paling banyak satu node berikutnya.

Ini disebut struktur linier dan disebut tabel linier dalam struktur data.
Node daftar tertaut ganda memiliki dua bidang penunjuk dan merupakan struktur linier.
Pointer dari semua node dalam daftar tertaut melingkar adalah bukan nol dan juga merupakan struktur linier.

Temukan tabel hash

Metode untuk membuat tabel hash meliputi: metode alamat langsung, metode pembagian dan sisa.

Metode penyelesaian konflik meliputi:

  • Metode alamat rantai: Hubungkan elemen dengan nilai hash yang sama menggunakan daftar tertaut.
  • Deteksi linier dan kemudian metode hashing: setelah konflik, putar ke bawah untuk menemukan lokasi kosong untuk penempatan.

Bitwise DAN rentang numerik

Diberikan dua bilangan bulat kiri dan kanan, yang mewakili interval [kiri, kanan], kembalikan hasil bitwise AND dari semua angka dalam interval ini.

Untuk rangkaian bit, selama masih ada bit yang bernilai nol, maka hasil operasi bitwise AND rangkaian ini adalah nol.

Masukkan deskripsi gambar di sini
Dalam contoh di atas, kita dapat menemukannyaHasil dari melakukan operasi AND bitwise pada semua bilangan adalah awalan umum dari semua string biner yang bersesuaian dengan bit sisanya diisi dengan nol.

Angka yang hanya muncul satu kali (2)

Mengingat jumlah array bilangan bulat, setiap elemen muncul tiga kali kecuali elemen yang hanya muncul satu kali.

Rancang algoritma dengan kompleksitas waktu linier dan gunakan ruang konstan untuk menyelesaikan masalah.

Tentukan setiap bit biner secara bergantian
Karena elemen dalam array berada dalam kisaran int, Anda dapat menghitung apakah setiap bit biner dari jawabannya adalah 0 atau 1 secara bergantian.

Secara khusus, pertimbangkan digit biner ke-i dari jawabannya (i diberi nomor mulai dari 0), yang bisa berupa 0 atau 1.

Digit jawaban ke-i adalah sisa penjumlahan digit biner ke-i seluruh elemen array dibagi 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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

Daya(x, n)

Kekuatan cepat + rekursi
Inti dari algoritma fast power adalah algoritma membagi dan menaklukkan.
Mulai dari x, langsung kuadratkan hasil sebelumnya setiap kali. Hitung 5 kali untuk mendapatkan kekuatan 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); 
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

nol setelah faktorial

Diberikan bilangan bulat n, kembalikan n! Jumlah angka nol di akhir hasilnya.

Banyaknya angka nol ekor pada n! adalah mencari banyaknya faktor 10, dan 10=2x5, sehingga diubah menjadi mencari nilai yang lebih kecil dari banyaknya faktor prima 2 dan banyaknya faktor prima 5 pada n!.

Karena banyaknya faktor prima 5 tidak akan lebih besar dari banyaknya faktor prima 2, maka yang dihitung hanya banyaknya faktor prima 5.

Banyaknya faktor prima 5 pada n! sama dengan jumlah banyaknya faktor prima 5 pada setiap bilangan.

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

daftar tertaut melingkar

penunjuk kecepatan

/**
 * 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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

Gabungkan dua daftar tertaut yang diurutkan

/**
 * 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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

Pohon biner simetris

Masukkan deskripsi gambar di sini
Sebuah pohon dikatakan simetris jika subpohon kiri dan kanannya merupakan bayangan cermin satu sama lain.

  • Kedua simpul akarnya memiliki nilai yang sama
  • Subpohon kanan dari setiap pohon merupakan bayangan cermin dari subpohon kiri dari pohon lainnya

Tingkat rata-rata pohon biner

traversal luas-pertama
Pencarian dimulai dari node akar, melintasi semua node pada lapisan yang sama pada setiap putaran, menghitung jumlah node pada lapisan dan jumlah jumlah node pada lapisan, kemudian menghitung nilai rata-rata lapisan tersebut.

  • Awalnya, simpul akar diantrekan.
  • Selama setiap putaran traversal, semua node dalam antrian dikeluarkan, jumlah dan jumlah node ini dihitung, dan kemudian nilai rata-rata dihitung, dan kemudian semua node anak yang kosong dari node tersebut ditambahkan ke antrian.
/**
 * 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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

Penjelajahan urutan tingkat pohon biner

/**
 * 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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

Hapus duplikat dalam array yang dipesan

Array yang diurutkan berjumlah, menghapus elemen berulang di tempatnya, sehingga elemen yang muncul lebih dari dua kali hanya muncul dua kali, dan mengembalikan panjang array yang baru setelah dihapus.

Array masukan harus dimodifikasi di tempatnya dan dilakukan menggunakan O(1) ruang ekstra.

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

Putar susunan

Mengingat jumlah array bilangan bulat, putar elemen dalam posisi k array ke kanan.

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());
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

Waktu terbaik untuk membeli dan menjual saham

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

Waktu terbaik untuk membeli saham 2

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];
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

permainan melompat

Diberikan nomor array bilangan bulat non-negatif, awalnya terletak di indeks pertama array, setiap elemen dalam array mewakili panjang maksimum yang dapat dilompati.
Tentukan apakah dapat melompat ke indeks terakhir.

tamak
Untuk setiap posisi y dalam array, selama ada posisi x yang dapat dicapai dengan sendirinya, dan x + angka[x] ≥ y, maka y juga dapat dicapai.

Untuk setiap posisi x yang dapat dijangkau, maka posisi berturut-turut x+1, x+2, ..., x+nums[x] dapat dijangkau.

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

Transformasi zigzag

Diberikan sebuah string s, susunlah dalam bentuk z dari atas ke bawah dan dari kiri ke kanan sesuai dengan banyaknya baris numRows yang ditentukan.

Masukkan deskripsi gambar di sini
Simulasikan menggunakan matriks 2D
Misalkan n adalah panjang string s, r = numRows. Untuk r=1 (hanya satu baris), atau r &gt;= n (hanya satu kolom), jawabannya sama dengan s dan dapat dikembalikan secara langsung.

Dalam kasus lain, pertimbangkan untuk membuat matriks dua dimensi, kemudian mengisi string s dengan pola zigzag pada matriks, dan terakhir memindai karakter tak kosong dalam matriks baris demi baris untuk membentuk jawabannya.

Sesuai dengan maksud pertanyaannya, ketika kita mengisi karakter pada matriks, kita akan mengisi r karakter ke bawah, kemudian r-2 karakter ke atas ke kanan, dan terakhir kembali ke baris pertama, sehingga periode transformasi berbentuk Z t = r + r - 2 = 2r - 2. Setiap siklus akan menempati 1+r-2 = r-1 kolom pada matriks.

Ada n/t periode dikalikan dengan jumlah kolom, yang sama dengan jumlah kolom matriks.

Buat matriks dengan r baris dan c kolom, lalu ulangi string dan isi dalam pola zigzag.

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

Membalikkan kata-kata dalam sebuah string

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;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. Ia telah memberikan banyak kontribusi di bidang open source stasiun dokumentasi pengembang untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya

informasi kontak saya

Surat