Category Archives

51 Articles

编程

WA 到死原因总结

Posted by 小小泥娃 on
  1. 警惕使用 n = -n; 进行数值正负转换

数值在内存中是以补码的形式进行存储的,因此 int 的数据范围为 [-2147483648, 2147483647],左右边界不对称。
当题目中声明所有数据均在 int 范围内时,应当警惕使用 n = -n;:如果值恰好为下界 -2147483648[......]

Read more

编程/算法

QuickSort Dijkstra 3-Way Partitioning

Posted by 小小泥娃 on

思想

原始的 2-Way 快排在遇到大量重复数据时会退化为 O(n^2),为了解决这个问题,3-Way 快排被提出了。通过将区间分割为“小于”、“等于”和“大于”(基准数)三个部分,获得了趋近 O(nlogn) 的复杂度。不同于 2-Way 快排的是,我们在此选取一个基准数的值,而非一个基准元素。[……]

Read more