【算法筆記自學】入門篇（2）——算法初步

?4.1排序

自己寫的題解

#include <stdio.h>
#include <stdlib.h>void selectSort(int A[], int n) {for(int i = 0; i < n - 1; i++) { // 修正索引范圍int k = i;for(int j = i + 1; j < n; j++) { // 修正索引范圍if(A[j] < A[k]) {k = j;}}if (k != i) { // 僅在需要時進行交換int temp = A[i];A[i] = A[k];A[k] = temp;}}
}int main() {int n = 0;scanf("%d", &n);int A[n];for(int i = 0; i < n; i++) {scanf("%d", &A[i]);}selectSort(A, n); // 直接傳遞數組名for(int i = 0; i < n; i++) {if(i!=n-1){printf("%d ", A[i]);}else{printf("%d", A[i]);}}system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}

?自己寫的題解

#include <stdio.h>
#include <stdlib.h>
void insertSort(int A[], int n) {for(int i=1;i<=n-1;i++){int temp=A[i],j=i;while(j>0&&temp<A[j-1]){A[j]=A[j-1];j--;}A[j]=temp;}
}int main() {int n = 0;scanf("%d", &n);int A[n];for(int i = 0; i < n; i++) {scanf("%d", &A[i]);}insertSort(A, n); // 直接傳遞數組名for(int i = 0; i < n; i++) {if(i!=n-1){printf("%d ", A[i]);}else{printf("%d", A[i]);}}system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}

4.2散列

#include <stdio.h>
#include <stdlib.h>const int maxn = 100010;
int hashTable[maxn] = {0};int main() {int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);if (x >= 0 && x < maxn) { // 確保x在合法范圍內hashTable[x]++;}}for (int i = 0; i < maxn; i++) { // 修正遍歷范圍if (hashTable[i] != 0) {printf("%d %d\n", i, hashTable[i]); // 修正輸出格式}}system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}

?標答

#include <cstdio>
#include <cstring>const int MAXN = 26;
const int MAXL = 1001;
char str1[MAXL], str2[MAXL];
bool hashTable[MAXN] = {false};int getHashKey(char c) {return c - 'a';
}int main () {scanf("%s%s", str1, str2);int len1 = strlen(str1);int len2 = strlen(str2);for (int i = 0; i < len1; i++) {hashTable[getHashKey(str1[i])] = true;}for (int i = 0; i < len2; i++) {printf("%d", hashTable[getHashKey(str2[i])]);printf(i < len2 - 1 ? " " : "\n");}return 0;
}

#include <cstdio>const int MAXN = 26 * 26 * 26;
const int MAXL = 1001;
char str[MAXL];
int hashTable[MAXN] = {0};int getHashKey(char s[]) {return (s[0] - 'A') * 26 * 26 + (s[1] - 'A') * 26 + (s[2] - 'A');
}int main () {int n, m;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", str);hashTable[getHashKey(str)]++;}scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%s", str);printf("%d", hashTable[getHashKey(str)]);printf(i < m - 1 ? " " : "\n");}return 0;
}

?4.3遞歸

#include <stdio.h>
#include <stdlib.h>void print(int n) {if (n == 0) {printf("講你妹的故事啊！快點去睡覺！！！\n");} else {printf("從前有座山，山上有座廟\n廟里有一個老和尚和一個小和尚\n睡前老和尚給小和尚講故事：\n");print(n - 1);printf("然后老和尚和小和尚就睡覺啦\n");}
}int main() {int n;scanf("%d", &n);print(n);system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}


#include <stdio.h>
#include <stdlib.h>int F(int n) {if(n==1)return 1;if(n==2)return 1;if(n>2)return F(n-1)+F(n-2);
}int main() {int n;scanf("%d", &n);printf("%d",F(n));system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}


#include <stdio.h>
#include <stdlib.h>
const int maxn=11;
int n,P[maxn],hashTable[maxn]={false};
void generateP(int index){if(index==n+1){for(int i=1;i<=n;i++){printf("%d",P[i]);printf(i<n ? " " : "\n");}return;}for(int x=1;x<=n;x++){if(hashTable[x]==false){P[index]=x;hashTable[x]=true;generateP(index+1);hashTable[x]=false;}}
}int main() {n=3;scanf("%d",&n);generateP(1);system("pause"); // 防止運行后自動退出，需頭文件stdlib.hreturn 0;
}

4.4貪心

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;    // 箱子數量上限
int a[MAXN];                // 箱子數組
int main() {int n, maxW;            // 箱子數量、載重scanf("%d%d", &n, &maxW);for (int i = 0; i < n; i++) {    // 輸入各箱子重量scanf("%d", &a[i]);}sort(a, a + n);                  // 將箱子按重量從小到大排序int num = 0, sum = 0;            // 最大箱子數量、最大累計重量for (int i = 0; i < n; i++) {    // 從小到大遍歷箱子if (sum + a[i] <= maxW) {    // 如果加上當前箱子的重量之后沒有超過載重num++;                   // 最大箱子數量加1sum += a[i];             // 最大累計重量加上當前箱子的重量} else {                     // 如果超過載重，那么退出循環break;}}printf("%d %d", num, sum);       // 輸出最大箱子數量和最大累計重量return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
struct Interval {    // 區間結構體定義int l, r;
} interval[MAXN];    // 區間數組bool cmp(Interval a, Interval b) {    // 區間的比較函數if (a.l != b.l) {                 // 如果左端點不同，那么按左端點從大到小return a.l > b.l;} else {                          // 否則，按右端點從小到大return a.r < b.r;}
}int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {         // 輸入n個區間的左右端點scanf("%d%d", &interval[i].l, &interval[i].r);}sort(interval, interval + n, cmp);    // 將區間數組進行排序int num = 1, lastL = interval[0].l;   // 排序后的第一個區間總是被選中for (int i = 1; i < n; i++) {         // 遍歷剩余的區間if (interval[i].r <= lastL) {     // 如果和上一個選中的區間不相交lastL = interval[i].l;        // 那么選中當前區間num++;                        // 并令選中的區間數量加1}}printf("%d", num);                    // 輸出選中的區間數量return 0;
}

4.5二分法

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int binarySearch(int A[],int left,int right,int x)
{int mid;while(left<=right){mid=(left+right)/2;if(A[mid]==x)return mid;else if(A[mid]>x){right=mid-1;}else{left=mid+1;}}return -1;
}
int main() {int n=0,x=0;scanf("%d %d", &n,&x);int a[n];for (int i = 0; i < n; i++) {         // 輸入n個區間的左右端點scanf("%d", &a[i]);}printf("%d", binarySearch(a,0,n-1,x));                    // 輸出選中的區間數量return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int lower_bound(int A[],int left,int right,int x)
{int mid;while(left<right){mid=(left+right)/2;if(A[mid]>=x){right=mid;}else{left=mid+1;}}return left;
}
int main() {int n=0,x=0;scanf("%d %d", &n,&x);int a[n];for (int i = 0; i < n; i++) {         // 輸入n個區間的左右端點scanf("%d", &a[i]);}printf("%d", lower_bound(a,0,n,x));                    // 輸出選中的區間數量return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int upper_bound(int A[],int left,int right,int x)
{int mid;while(left<right){mid=(left+right)/2;if(A[mid]>x){right=mid;}else{left=mid+1;}}return left;
}
int main() {int n=0,x=0;scanf("%d %d", &n,&x);int a[n];for (int i = 0; i < n; i++) {         // 輸入n個區間的左右端點scanf("%d", &a[i]);}printf("%d", upper_bound(a,0,n,x));                    // 輸出選中的區間數量return 0;
}

#include <cstdio>const int MAXN = 100000;
int n, a[MAXN], target;int binarySearch() {int l = 0, r = n;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] >= target) {r = mid;} else {l = mid + 1;}}if (l < n && a[l] == target) {return l;} else {return -1;}
}int main() {scanf("%d%d", &n, &target);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}printf("%d", binarySearch());return 0;
}

#include <cstdio>const int MAXN = 100000;
int n, a[MAXN], target;int binarySearch() {int l = 0, r = n;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] > target) {r = mid;} else {l = mid + 1;}}if (l >0 && a[l-1] == target) {return l-1;} else {return -1;}
}int main() {scanf("%d%d", &n, &target);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}printf("%d", binarySearch());return 0;
}

#include <cstdio>
const int MAXN = 100000;
const double eps=1e-6;
double a;
double f(double x){return x*x*x+x*x+x-a;
}
double calSqrt(){double left=-100,right=100,mid;while(right-left>eps){mid=(left+right)/2;if(f(mid)>0){right=mid;}else{left=mid;}}return mid;
}int main() {scanf("%lf",&a);printf("%.2f",calSqrt());return 0;
}

4.6 two pointers

#include <cstdio>const int MAXN = 100000;
int n, k, a[MAXN];int twoSum() {int counter = 0;int i = 0, j = n - 1;while (i < j) {if (a[i] + a[j] == k) {counter++;i++;j--;} else if (a[i] + a[j] < k) {i++;} else {j--;}}return counter;
}int main() {scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}printf("%d", twoSum());return 0;
}

#include <cstdio>const int MAXN = 100000;
int n, a[MAXN];
int m, b[MAXN];
int merged[MAXN * 2];void merge() {int i = 0, j = 0, cnt = 0;while (i < n && j < m) {if (a[i] < b[j]) {merged[cnt++] = a[i++];} else {merged[cnt++] = b[j++];}}while (i < n) {merged[cnt++] = a[i++];}while (j < m) {merged[cnt++] = b[j++];}
}int main() {scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}for (int i = 0; i < m; i++) {scanf("%d", &b[i]);}merge();for (int i = 0; i < n + m; i++) {printf("%d", merged[i]);if (i < n + m - 1) {printf(" ");}}return 0;
}

#include <cstdio>const int MAXN = 1000;
int n, a[MAXN];
int merged[MAXN];void merge(int l1, int r1, int l2, int r2) {int i = l1, j = l2, cnt = 0;while (i <= r1 && j <= r2) {if (a[i] < a[j]) {merged[cnt++] = a[i++];} else {merged[cnt++] = a[j++];}}while (i <= r1) {merged[cnt++] = a[i++];}while (j <= r2) {merged[cnt++] = a[j++];}for (i = 0; i < cnt; i++) {a[l1 + i] = merged[i];}
}void mergeSort(int l, int r) {if (l < r) {int mid = (l + r) / 2;mergeSort(l, mid);mergeSort(mid + 1, r);merge(l, mid, mid + 1, r);}
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}mergeSort(0, n - 1);for (int i = 0; i < n; i++) {printf("%d", a[i]);if (i < n - 1) {printf(" ");}}return 0;
}

#include <cstdio>const int MAXN = 1000;
int n, a[MAXN];
int mergedNums[MAXN];int partition(int l, int r) {int temp = a[l];while (l < r) {while (l < r && a[r] > temp) {r--;}a[l] = a[r];while (l < r && a[l] <= temp) {l++;}a[r] = a[l];}a[l] = temp;return l;
}void quickSort(int l, int r) {if (l < r) {int pos = partition(l, r);quickSort(l, pos - 1);quickSort(pos + 1, r);}
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}quickSort(0, n - 1);for (int i = 0; i < n; i++) {printf("%d", a[i]);if (i < n - 1) {printf(" ");}}return 0;
}

4.7其他高效技巧與算法

#include <cstdio>int main() {int n, x, numZero = 0;scanf("%d", &n);long long result = 0;for (int i = 0; i < n; i++) {scanf("%d", &x);if (x == 1) {result += numZero;} else {numZero++;}}printf("%lld", result);return 0;
}

#include <cstdio>
const int MAXN = 100000;
int n,k,a[MAXN];
int mergedNums[MAXN];int partition(int l, int r) {int temp = a[l];while (l < r) {while (l < r && a[r] > temp) {r--;}a[l] = a[r];while (l < r && a[l] <= temp) {l++;}a[r] = a[l];}a[l] = temp;return l;
}void quickSort(int l, int r) {if (l < r) {int pos = partition(l, r);quickSort(l, pos - 1);quickSort(pos + 1, r);}
}
int main() {scanf("%d %d", &n,&k);for(int i=0;i<n;i++){scanf("%d",&a[i]);}quickSort(0, n - 1);for(int i=0;i<n;i++){if(i==k-1)printf("%d",a[i]);}return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/41298.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/41298.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/41298.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

跨境人最怕的封店要怎么規避?

跨境人最怕的封店要怎么規避?

跨境人最怕的是什么&#xff1f;——封店 造成封店的原因很多&#xff0c;IP關聯、無版權售賣、虛假發貨等等&#xff0c;其中IP關聯這個問題導致店鋪被封在跨境商家中簡直是屢見不鮮 IP關聯&#xff0c;是指被海外平臺檢測到多家店鋪開設在同一個站點上的情況。我們知道有些…
閱讀更多...
賣家必讀：阿里巴巴國際站登錄與入駐全流程

賣家必讀：阿里巴巴國際站登錄與入駐全流程

阿里巴巴國際站作為全球最大的B2B電子商務平臺之一&#xff0c;為品牌建立和業務拓展提供了可能。那么跨境賣家如何才能成功登錄和入駐阿里巴巴國際站&#xff1f;本文將講解如何用阿里巴巴國際站網頁版進行登錄&#xff0c;以及阿里巴巴國際站賣家的入駐條件、流程和費用。此外…
閱讀更多...
統計信號處理基礎 習題解答11-12

統計信號處理基礎 習題解答11-12

題目 證明 的MAP估計量為 其中是一個的矢量, 是一個可逆的p*p的矩陣。也就是說&#xff0c;MAP估計量對可逆的線性變換是可以變換的。 解答 已知的聯合概率密度 且&#xff1a; 現在知道&#xff1a; 那么為了獲得變換后的MAP&#xff0c;首先需要根據求出 根據概率密度變換…
閱讀更多...
2024年軟件測試面試題，精選100+，附答案+文檔

2024年軟件測試面試題，精選100+，附答案+文檔

&#x1f345; 視頻學習&#xff1a;文末有免費的配套視頻可觀看 &#x1f345; 點擊文末小卡片 &#xff0c;免費獲取軟件測試全套資料&#xff0c;資料在手&#xff0c;漲薪更快 Part1 1、你的測試職業發展是什么&#xff1f; 測試經驗越多&#xff0c;測試能力越高。所以我…
閱讀更多...
C++入門 容器適配器 / stack queue模擬實現

C++入門 容器適配器 / stack queue模擬實現

目錄 容器適配器 deque的原理介紹 stack模擬實現 queue模擬實現 priority_queue模擬實現 仿函數 容器適配器 適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總 結)&#xff0c;該種模式是將一個類的接口轉換成客戶希望…
閱讀更多...
深度學習Week19——學習殘差網絡和ResNet50V2算法

深度學習Week19——學習殘差網絡和ResNet50V2算法

文章目錄 深度學習Week18——學習殘差網絡和ResNet50V2算法 一、前言 二、我的環境 三、論文解讀 3.1 預激活設計 3.2 殘差單元結構 四、模型復現 4.1 Residual Block 4.2 堆疊Residual Block 4.3. ResNet50V2架構復現 一、前言 &#x1f368; 本文為&#x1f517;365天深度學…
閱讀更多...
Kubernetes k8s 命名空間 namespace 介紹以及應用 資源限額配置

Kubernetes k8s 命名空間 namespace 介紹以及應用 資源限額配置

目錄 命名空間 什么是命名空間&#xff1f; namespace應用場景 namespacs使用案例分享 namespace資源限額 文檔中的YAML文件配置直接復制粘貼可能存在格式錯誤&#xff0c;故實驗中所需要的YAML文件以及本地包均打包至網盤 鏈接&#xff1a;https://pan.baidu.com/s/1qv8Tc…
閱讀更多...
Python中異步事件觸發

Python中異步事件觸發

1、問題背景 在Python中&#xff0c;我想創建一個由事件生成控制流程的類結構。為此&#xff0c;我做了以下工作&#xff1a; class MyEvent: EventName_FunctionName {}classmethoddef setup(cls, notificationname, functionname):if notificationname in MyEvent.EventN…
閱讀更多...
ONLYOFFICE 8.1版本震撼來襲，讓辦公更高效、更智能

ONLYOFFICE 8.1版本震撼來襲，讓辦公更高效、更智能

官網鏈接&#xff1a; 在線PDF查看器和轉換器 | ONLYOFFICE 在線辦公套件 | ONLYOFFICE 隨著科技的不斷發展&#xff0c;辦公軟件已經成為現代企業提高工作效率、實現信息共享的重要工具。在我國&#xff0c;一款名為ONLYOFFICE的在線辦公套件受到了越來越多企業的青睞。今天…
閱讀更多...
golang中的類型轉換那些事

golang中的類型轉換那些事

由于golang是一門強類型的語言&#xff0c; 所以我們在golang的開發中不可避免的會對一些數據類型進行手動轉換&#xff0c;以適應我們的業務需求。 golang中類型轉換的途徑大致有4種&#xff0c;強制轉換&#xff0c;類型斷言&#xff0c;類型匹配 還有使用strconv包中提供的…
閱讀更多...
[TensorFlow-Lite][深度學習]【快速簡介-1】

[TensorFlow-Lite][深度學習]【快速簡介-1】

前言&#xff1a; 很多場景下面我們需要需要把我們的深度學習模型部署到Android,IOS 手機上面. Google 通過TensorFlow Lite 提供了對應的解決方案. 目錄&#xff1a; 端側部署優點 硬件支持 性能 應用案例 一 端側部署優點 1; 很多場景下面&#xff1a; 無網絡,數據無法…
閱讀更多...
Hadoop 遠程 debug

Hadoop 遠程 debug

Hadoop 命令行 在執行 hadoop fs 命令行之前&#xff0c;先執行以下命令&#xff1a; export HADOOP_CLIENT_OPTS"-Xdebug -Xrunjdwp:transportdt_socket,servery,suspendy,address8000"
閱讀更多...
昇思25天學習打卡營第10天|基于MindSpore實現BERT對話情緒識別

昇思25天學習打卡營第10天|基于MindSpore實現BERT對話情緒識別

基于MindSpore實現BERT對話情緒識別 模型簡介數據集模型構建模型驗證模型推理自定義推理數據集 模型簡介 BERT全稱是來自變換器的雙向編碼器表征量&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;&#xff0c;它是Google于2018年末開發并發…
閱讀更多...
HTML超鏈接和錨鏈接

HTML超鏈接和錨鏈接

HTML超鏈接和錨鏈接 一、定義 HTML的超鏈接&#xff08;Hyperlink&#xff09;用于在網頁之間創建鏈接&#xff0c;使用戶可以點擊這些鏈接來導航到其他頁面或資源。 二、基本語法 1、語法 HTML中的超鏈接使用a標簽來定義 <a href"URL">鏈接文本</a&g…
閱讀更多...
yolov8實戰——yolov8TensorRT部署（python推理）（保姆教學）

yolov8實戰——yolov8TensorRT部署（python推理）（保姆教學）

yolov8實戰——yolov8TensorRT部署&#xff08;python推理&#xff09;&#xff08;保姆教學&#xff09; 一 、準備好代碼和環境安裝TensorRt下載代碼和安裝環境 部署和推理構建ONNX構建engine無torch推理torch推理 最近用到yolov8&#xff0c;但是尋找了一圈才找到了yolov8最…
閱讀更多...
[SAP ABAP] 版本管理

[SAP ABAP] 版本管理

版本管理是指軟件開發過程中各種程序代碼、配置文件以及說明文檔等文件變更的管理 生成版本 版本管理 對比版本 點擊上述版本管理即可進行版本對比操作 補充擴展 我們可以使用事務碼SE10對傳輸請求進行創建、修改、刪除、合并以及更改所有者等操作 使用事務碼SCC1進行不同cl…
閱讀更多...
3D生成模型TripoSR完美搭建流程，包含所有問題解決方案！

3D生成模型TripoSR完美搭建流程，包含所有問題解決方案！

最近需要使用3D生成模型，無意中看到了TripoSR，覺得效果還行，于是打算在Linux系統上部署一下，結果遇到很多坑，在這里寫一下詳細的部署流程和部署過程中遇到的問題。 下面是TripoSR的源碼地址。 GitHub - VAST-AI-Research/TripoSRContribute to VAST-AI-Research/TripoSR…
閱讀更多...
java-Linkedlist源碼分析

java-Linkedlist源碼分析

## 深入分析 Java 中的 LinkedList 源碼 LinkedList 是 Java 集合框架中的一個重要類&#xff0c;它基于雙向鏈表實現&#xff0c;提供了高效的插入和刪除操作。與 ArrayList 不同&#xff0c;LinkedList 的結構使其在特定操作上有更優的性能表現。本文將詳細分析 LinkedList …
閱讀更多...
android 進程，線程調度的區別

android 進程，線程調度的區別

一 分析&#xff1a; 進程和線程在調度上有什么不同呢&#xff1f;當有一個task去占用指定的資源時候叫進程&#xff0c;當有多個task去共享使用這些資源時候&#xff0c;這個task和之后的task都叫線程&#xff08;最初這個task叫主線程&#xff09;而linux調度主要調的就是cp…
閱讀更多...
【Portswigger 學院】文件上傳

【Portswigger 學院】文件上傳

教程和靶場來源于 Burpsuite 的官網 Portswigger&#xff1a;File upload vulnerabilities - PortSwigger 原理與危害 很多網站都有文件上傳的功能&#xff0c;比如在個人信息頁面允許用戶上傳圖片作為頭像。如果網站應用程序對用戶上傳的文件沒有針對文件名、文件類型、文件內…
閱讀更多...
最新文章

Copyright @ 2022~2023