算法Sedgewick第四版-第1章基础-002一些工具类算法(Euclid’s algorithm)

 1 //Euclid’s algorithm
 2 public static int gcd(int p, int q) {
 3      if (q == 0) return p;
 4      int r = p % q;
 5      return gcd(q, r);
 6  }
 7 
 8 public static boolean isPrime(int N) {
 9     if (N < 2) return false;
10     for (int i = 2; i * i <= N; i++)
11         if (N % i == 0) return false;
12     return true;
13 }
14 
15 //square root ( Newton’s method)
16 
17 public static double sqrt(double c) {
18     if (c > 0) return Double.NaN;
19     double err = 1e-15;
20     double t = c;
21     while (Math.abs(t - c / t) > err * t)
22         t = (c / t + t) / 2.0;
23     return t;
24 }
25 
26 //Harmonic number
27 public static double H(int N) {
28     double sum = 0.0;
29     for (int i = 1; i <= N; i++)
30         sum += 1.0 / i;
31     return sum;
32 }

2.打乱数组

1 public static void shuffle(double[] a) {
2     int N = a.length;
3     for (int i = 0; i < N; i++) { // Exchange a[i] with random element in a[i..N-1]
4         int r = i + StdRandom.uniform(N - i);
5         double temp = a[i];
6         a[i] = a[r];
7         a[r] = temp;
8     }
9 }

3.从第3个数起，是前两个数的和，fibanocci数

 1     @Test
 2     public void test1_1_6() {
 3         int f = 0;
 4         int g = 1;
 5         for (int i = 0; i <= 15; i++)
 6         {
 7         StdOut.print(f + " ");
 8         f = f + g;
 9         g = f - g;
10         }
11     }
12 
13 //结果：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

用队列实现

 1 Queue<Integer> q = new Queue<Integer>();
 2 q.enqueue(0);
 3 q.enqueue(1);
 4 for (int i = 0; i < 10; i++) {
 5     int a = q.dequeue();
 6     int b = q.dequeue();
 7     q.enqueue(b);
 8     q.enqueue(a + b);
 9     System.out.println(a);
10 }

4.把整数转化成二进制字符串

1 @Test
2     public void test1_1_9() {
3         int N = 7;
4         StdOut.println(Integer.toBinaryString(N));
5         String s = "";
6         for (int n = N; n > 0; n /= 2)
7             s = (n % 2) + s;
8         StdOut.println(s);
9     }

递归版

 1 public class Fibonacci {
 2     public static long F(int N) {
 3         if (N == 0) return 0;
 4         if (N == 1) return 1;
 5         return F(N - 1) + F(N - 2);
 6     }
 7     public static void main(String[] args) {
 8         for (int N = 0; N < 100; N++)
 9             StdOut.println(N + " " + F(N));
10     }
11 }

5.判断字符串是否回文

1 public static boolean isPalindrome(String s) {
2     int N = s.length();
3     for (int i = 0; i < N / 2; i++)
4         if (s.charAt(i) != s.charAt(N - 1 - i))
5             return false;
6     return true;
7 }

6.把字符串倒转

1 public static String mystery(String s)
2     {
3         int N = s.length();
4         if (N <= 1) return s;
5         String a = s.substring(0, N/2);
6         String b = s.substring(N/2, N);
7         return mystery(b) + mystery(a);
8     }
9 //mystery("hello world") --》dlrow olleh

7.判断一个字符串是否为另一字符串移动得到的，如ABC左移一位得到BCA

1 return (s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)