GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Algorithm_Interview_Notes-Chinese/C-算法 at master · DarLiner/Algorithm_Interview_Notes-Chinese

Expand file tree

/

C-算法

/
Copy path

Directory actions

More options

More options

Directory actions

More options

More options

Latest commit

 

History

History
History
/

C-算法

/
Copy path

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
专题-A-字符串.md
专题-A-字符串.md
 
 
专题-A-数据结构.md
专题-A-数据结构.md
 
 
专题-A-数据结构_Advanced.md
专题-A-数据结构_Advanced.md
 
 
专题-B-动态规划.md
专题-B-动态规划.md
 
 
专题-B-双指针.md
专题-B-双指针.md
 
 
专题-C-区间问题.md
专题-C-区间问题.md
 
 
专题-C-排列组合.md
专题-C-排列组合.md
 
 
专题-C-数学问题.md
专题-C-数学问题.md
 
 
专题-C-洗牌、采样、随机数.md
专题-C-洗牌、采样、随机数.md
 
 
专题-D-大数运算.md
专题-D-大数运算.md
 
 
专题-D-海量数据处理.md
专题-D-海量数据处理.md
 
 
备忘-IO模板.md
备忘-IO模板.md
 
 
备忘-必备算法.md
备忘-必备算法.md
 
 
题解-LeetCode.md
题解-LeetCode.md
 
 
题解-剑指Offer.md
题解-剑指Offer.md
 
 
题解-面试真题.md
题解-面试真题.md
 
 

README.md

Outline

题解

  • 剑指Offer 题解
  • Leetcode 题解

专题

  • A
    • 数据结构
    • 数据结构_Advanced
  • B
    • 双指针
    • 动态规划
  • C
    • 排列组合
    • 洗牌、采样、随机数

备忘

  • IO 模板
  • 必备算法

Reference

  • f-zyj/ACM 模板以及个人平时训练的代码

    ACM 在线模版 - 逐梦者 - CSDN博客

  • OI Wiki

Index

  • 排序
    • 稳定排序与不稳定排序
    • 堆排序-建堆的时间复杂度 O(N)
  • Trick
    • 时间复杂度
    • 敏感空间

排序

稳定排序与不稳定排序

稳定排序

  • 冒泡排序、插入排序、归并排序、基数排序

不稳定排序

  • 选择排序、快速排序、希尔排序、堆排序

堆排序-建堆的时间复杂度 O(N)

  • 堆排序的时间复杂度是 O(NlogN) 没有问题
  • 但是建堆的时间复杂度是 O(N)

    为什么建立一个二叉堆的时间为O(N)而不是O(Nlog(N))? - 知乎

Trick

时间复杂度

百度:ACM trick

  • 暴力枚举永远是第一个考虑的方法,但也有一些前提
    • 如果输入规模 < 1e4,那么可以尝试考虑 O(n^2) 的算法(两次循环暴力枚举);如果 ≥ 1e5,那么可能就需要考虑 O(nlogn) 的算法了——这不是绝对的,也可以通过剪枝等操作加速。
    • [C++] string 拼接的速度依次为:1)使用 stringstream;2)使用 append();3)使用 s += c;4)使用 s = s + c——如果有大量拼接操作,要避免使用最后一种方法。

敏感空间

ACM Trick点&&常用操作记录(持续更新)(敏感空间) - CSDN博客

  • long long 上界:2^63-1 = 9,223,372,036,854,775,807 ≈ 9.223372e+18
    • 阶乘:20! = 2432902008176640000 ≈ 2.432902e+18 OK,21!超
    • Fibnacci 数列:fib[92] = 7540113804746346429 ≈ 7.540114e+18 OK,fib[93] 超
    • Catalan 数:
    • 整数划分:
  • 数组大小:如果内存限制为 2MB,那么最大可开辟的 int 数组为 2*1024*1024/4 = 524288 ≈ 50,0000,char 数组为 2*1024*1024 = 2,097,152 ≈ 200,0000
    • 实际单个数组是远开不了那么大,比如 windows 默认的栈好像只有 1MB
    • 在无法修改栈大小的情况下,可以使用 new 或 malloc 在堆上开辟内存
      int *pa = malloc(sizeof(int)*1024*1024);
      int *pb = new int[1024*1024];
You are visitor 01402605 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.