算法常用小技巧

1.判断素数

用 i*i<n 取代 i<sqrt(n)减少了开方带来的开销

public boolean isPrime(int n){ 

    if(n <= 3 ){      
        return true;
    }

    if(n % 2 == 0){    //过滤掉偶数
        return false;
    }

    for(int i = 3; i * i < n; i += 2){  //省去开方，并且步长要为2
        if(n % i == 0){
            return false;
        }
    }

    return true;
}

2.小数比较大小

因为浮点数不能进行精确比较，所以尽量不要用小数进行比较大小等

• 例1

  int a = 1.0;
  int b = 2.0;
  if(a + b == 3.0)  //这里执行 return 2; 因为a + b 不等于 3.0
      return 1;
  else
      return 2;

• 例2

  //判断 1/a + 1/b 是否等于 1   （a, b为整数）
  //普通写法
  if((1.0 / a + 1.0 / b) == 1.0)   //这样写是不对的
  
  //保险写法 ------> 想办法去除分式 
  if(a + b == ab)
  
  //解析
  1/a + 1/b = 1
  => (a + b) / ab = 1  //通分
  =>  a + b = ab

  3.奇偶判断

  //偶数最低位为0，奇数最低为为1，&1 用来取出某一位
  x & 1 == 0  //x为偶数
  x & 1 == 1  //x为奇数

  4.取数

• 例1.取出数中的每一位

  int a = 12345;
  int i = 0;
  while(a > 0){
      book[i] = a % 10;  //取出末位
      a = a / 10;        //删除末位
      i++;
  }

• 例2.求数n各个位 之和

  int sum = 0;
  while(n > 0){
      sum = sum + n % 10;  //取个位 + 累加
      n = n / 10;          //删除个位
  }

• 例3.求数n的倒叙。 如123 倒叙 321

  int inverse(int n){
  
      int k = 0;
  
      while( n > 0){
          k = k * 10 + n % 10;
          n = n / 10;
      }
  
      return k;
  }

5.细节

for(int i = 0; i < strlen(str); i++)
和
int len = strlen(str);
for(int i = 0; i < len; i++)

时间复杂度一个是O(n^2),一个是O(n);

6. 有空更新

赏

失败是成功之母

支付宝

微信