一些简单却精妙的算法

文章目录

• 1.树状数组
• 2.红黑树
• 3.星星打分
• 4.欧几里得算法
• 5.快速幂
• 6.并查集

  在编程的世界里，简洁的代码往往隐藏着深邃的智慧。一起来看看那些看似简单，实则精妙绝伦的代码片段，体会编程语言的优雅与力量。

  1.树状数组

  int lowbit(int x)  
  {    
      return x&-x;    
  }
  

  树状数组里的这个，太精妙了，树状数组使区间求和复杂度降低到了log(n),发明这段代码的人一定是个天才,而这个lowbit恰恰是最精妙的一部分,可以准确的找到我们需要加的部分，巧妙的利用了计算机的位运算。

  
  （图片来源网络，侵删）

  2.红黑树

  defun rbt-balance (tree)  
    "Balance the rbtree list TREE."  
    (pcase tree  
      (`(B (R (R ,a ,x ,b) ,y ,c) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))  
      (`(B (R ,a ,x (R ,b ,y ,c)) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))  
      (`(B ,a ,x (R (R ,b ,y ,c) ,z ,d)) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))  
      (`(B ,a ,x (R ,b ,y (R ,c ,z ,d))) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))  
      (_                                 tree)))  
    
  (defun rbt-insert- (x s)  
    "Auxilary function of rbt-insert."  
    (pcase s  
      (`nil              `(R nil ,x nil))  
      (`(,color ,a ,y ,b) (cond (( x y)  
                                 (rbt-balance `(,color ,a ,y ,(rbt-insert- x b))))  
                                (t  
                                 s)))  
      (_                  (error "Expected tree: %S" s))))  
    
  (defun rbt-insert (x s)  
    "Insert S to rbtree X."  
    (pcase (rbt-insert- x s)  
      (`(,_ ,a ,y ,b) `(B ,a ,y ,b))  
      (_              (error "Internal error: %S" s))))
  

  3.星星打分

  function getRating(rating) {  
      if(rating > 5 || rating  
  这种实现方式之所以精妙，是因为它利用了字符串的固定模式和 substring 方法的灵活性来生成不同数量的星星，而不需要使用循环或额外的逻辑来逐个添加或删除星星。这种方法简洁且高效，特别是在需要频繁生成星级评分表示时。
   
  然而，这段代码也有局限性，它假设评分总是整数，并且只支持0到5的评分范围。如果需要支持小数评分或更广泛的评分范围，这段代码将需要相应的调整。
  （图片来源网络，侵删）
   
  4.欧几里得算法
   
  function gcd(a, b) {  
      return b ? gcd(b, a % b) : a;   
  }
   
  这种递归实现的欧几里得算法非常简洁且高效。它利用了数学上的一个性质：两个整数的最大公约数与它们的余数和较小数的最大公约数相同。即 gcd(a, b) = gcd(b, a % b)。
   
  5.快速幂
   
  function fastPower(b, n) {  
      if (n === 0) return 1;  
      const result = fastPower(b, Math.floor(n / 2));  
      return n % 2 === 0 ? result * result : b * result * result;
   
  用于高效地计算 b 的 n 次方。快速幂算法特别适用于计算大幂次的情况，因为它将幂次的计算复杂度从 O(n) 降低到 O(log n)。
   
  6.并查集
   
  int find(int x){  
    x==parent[x]？:find(parent[x]);  
  }
   
  并查集（Union-Find）数据结构中的 find 函数的简洁实现。
   
  递归查找：find 函数通过递归的方式查找元素 x 的根节点。递归会在元素与其父节点不同时，继续查找父节点的父节点，直到找到一个元素其父节点是它自己的元素，即根节点。
   
  路径压缩：代码中的三元运算符 ?: 实现了路径压缩技术。当 x 不是其根节点时（即 x != parent[x]），find 函数会调用自身并传入 parent[x] 作为参数。在递归返回的过程中，每个节点的父节点指针都被更新为最终的根节点，这样可以减少后续查找操作的深度。