本文最后更新于:2024年9月1日 晚上
语法 分割分号
stringstream ss(s);
while(getline(ss,t,’;’))
正则
string temp = t.substr(1);
if(regex_match(temp, regex(“[0-9]*”))){
}
cout输出格式
cout << setiosflags(ios::fixed);
cout.precision(2);
算法 二分查找 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int Binary (vector<int > ary, int target) { int n = ary.size (); if (n==0 ) return -1 ; int left = 0 , right = n - 1 ; int mid; while (left<=right){ mid = (left + right) / 2 ; int m = ary[mid]; if (m==target) return mid; else if (m<target) left = mid + 1 ; else right = mid - 1 ; } return -1 ; }
快排 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 #include <iostream> using namespace std;int n,a[1000001 ];void qsort (int l,int r) { int mid=a[(l+r)/2 ]; int i=l,j=r; do { while (a[i]<mid) i++; while (a[j]>mid) j--; if (i<=j) { swap (a[i],a[j]); i++; j--; } }while (i<=j); if (l<j) qsort (l,j); if (i<r) qsort (i,r); }int main () { cin>>n; for (int i=1 ;i<=n;i++) cin>>a[i]; qsort (1 ,n); for (int i=1 ;i<=n;i++) cout<<a[i]<<" " ; }
椭球公式 x2 / a2+y2 / b2+z2 / c2=1。
当x^2/a^2+y^2/b^2+z^2/c^2<1时 则点(x,y,z)在内部
反转链表 删除导数第N个数 总体很简单,有两个特殊的需要注意,第一是只有一个数或者零个数,第二个是需要删除的是第一个数
1 2 3 4 5 if (!head || !head -> next) return NULL ; ListNode* first = head; ListNode* second = head;for (int i = 0 ;i<n;i++) second = second->next;if (!second) return head->next;
高精度加法 一个很妙的不用判断进位并且前面0的处理方法
1 2 3 while (n1>=0 || n2>=0 || jw){ int x = n1 >= 0 ? num1[n1] - '0' : 0 ; int y = n2 >= 0 ? num2[n2] - '0' : 0 ;
n变成1 n如果是奇数就变成n-1或者n+1,如果是偶数就变成n/2
用动态规划
1 2 3 4 5 6 7 8 vector<int > dp; dp[0 ] = 0 ; dp[1 ] = 0 ;for (int i = 2 ;i<n;i++){ if (i%2 ==0 ) dp[i] = dp[i/2 ] +1 ; else dp[i] = min (dp[i-1 ],dp[i+1 ]) + 1 ; }return dp[n];
寻找第k大 (1)基于快排,每轮划分选择一个基准值,把比它小的数放在左边,大的放在右边,函数返回基准值的位置,如果该位置恰好是K,就说明了这是第K小的数,所以从0-基准值位置的数是序列中的前K小数。若返回基准值的位置小于或者大于K,再进行相应调整:如果返回的基准值大于k,在基准值左边序列查找,如果小于,在基准值右边进行查找。递归地进行快排,直到返回的结果=K;时间复杂度为O(n)。
(2)基于堆排序,求前K个最小的数用最大顶堆,求前K个最大的数用最小顶堆。以最大顶堆为例,要维护一个大小为K的顶堆,就是先将K个数插入堆中,随后,对每一个数,与堆顶的最大元素比较,若该数比堆顶元素小,则替换掉堆顶元素,然后调整堆,若大于堆顶元素,则不管,那么将所有元素比较和插入后,该堆维护的就是最小的K个数。求前k小的数用最大顶堆的目的(原理):这是一种局部淘汰的思想,尽量的把小的数都放在堆中,最后使得即使堆中最大的数,也比外界的所有数都小,就达到了目的。
洗牌算法 遍历1到n,生成一个随机数,然后把当前位置的和生成位置的交换,复杂度O(n)