第6章 函数

笔记

函数概念

一个典型的函数定义包括以下部分：修饰符、返回类型、函数名字、由0个或多个形参组成的列表以及函数体。

private static int fact(int val) {
    int res = 1;
    for (int i = 1; i <= val; i ++ )
        res *= i;
    return res;
}

函数名字是fact，它作用于一个整型参数，返回一个整型值。return语句负责结束fact并返回res的值。
修饰符包括private、static等，它们属于类相关的概念，会在下一章解释。

调用函数

函数的调用完成两项工作：一是用实参初始化函数对应的形参，二是将控制权转移给被调用函数。此时，主调函数的执行被暂时中断，被调函数开始执行。

fact("hello");      // 错误：实参类型不正确
fact();             // 错误：实参数量不足
fact(42, 10, 0);    // 错误：实参数量过多
fact(' ');          // 正确：该实参能自动转换成int类型，' '的ASCII值为32，所以该操作等价于fact(32);

实参是形参的初始值。第一个实参初始化第一个形参，第二个实参初始化第二个形参，依次类推。形参和实参的类型和个数必须匹配。

函数的形参列表可以为空，但是不能省略。

大多数类型都能用作函数的返回类型。一种特殊的返回类型是void，它表示函数不返回任何值。
函数的返回类型也可以是数组、字符串或者其他对象：

变量的作用域

函数内定义的变量为局部变量，只能在函数内部使用。
定义在类中的变量为成员变量，可以在类的所有成员函数中调用。
当局部变量与全局变量重名时，会优先使用局部变量。

ublic class Main {
    private static int x = 4;

    private static void f1() {
        int x = 3;
        System.out.println(x);
    }

    private static void f2() {
        System.out.println(x);
    }

    private static void f3() {
        System.out.println(x + 1);
    }

    public static void main(String[] args) {
        f1();       // 3
        f2();       // 4
        f3();       // 4
    }
}

参数传递

值传递

八大基本数据类型和String类型等采用值传递。

将实参的初始值拷贝给形参。此时，对形参的改动不会影响实参的初始值。

public class Main {
    private static void f(int x) {
        x = 5;
    }

    public static void main(String[] args) {
        int x = 10;
        f(x);
        System.out.println(x);
    }
}

引用传递

除String以外的数据类型的对象，例如数组、StringBuilder等采用引用传递。

将实参的引用（地址）传给形参，通过引用找到变量的真正地址，然后对地址中的值修改。所以此时对形参的修改会影响实参的初始值。

import java.util.Arrays;

public class Main {
    private static void f1(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i ++, j -- ) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    private static void f2(StringBuilder sb) {
        sb.append("Hello World");
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        f1(a);
        System.out.println(Arrays.toString(a));

        StringBuilder sb = new StringBuilder("");
        f2(sb);
        System.out.println(sb);
    }
}

返回类型和return语句

return语句终止当前正在执行的函数并将控制权返回到调用该函数的地方。return语句有两种形式：

return;
return expression;

无返回值函数

没有返回值的return语句只能用在返回类型是void的函数中。返回void的函数不要求非得有return语句，因为在这类函数的最后一句后面会隐式地执行return。

通常情况下，void函数如果想在它的中间位置提前退出，可以使用return语句。return的这种用法有点类似于我们用break语句退出循环。

有返回值的函数

只要函数的返回类型不是void，则该函数内的每个分支都必须有return语句，且每条return语句都必须返回一个值。return语句返回值的类型必须与函数的返回类型相同，或者能隐式地转换函数的返回类型。

private static int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}

函数重载

函数重载是指：在同一个类中存在多个函数，函数名称相同但参数列表不同。编译器会根据实参的类型选择最匹配的函数来执行。

private static int max(int a, int b) {
    System.out.println("int max");
    if (a > b) return a;
    return b;
}

private static double max(double a, double b) {
    System.out.println("double max");
    if (a > b) return a;
    return b;
}

public static void main(String[] args) {
    System.out.println(max(3, 4));
    System.out.println(max(3.0, 4.0));
}

函数递归

在一个函数内部，也可以调用函数本身。

// 求斐波那切数列第n项
private static int fib(int n) {  
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

习题

AcWing 804. n的阶乘

import java.util.Scanner;

public class Main {

    public static int fact(int n) {
        if (n == 1) return 1;
        else return n * fact(n - 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        System.out.println(fact(n));
    }
}

AcWing 805. x和y的最大值

import java.util.Scanner;

public class Main {

    public static int max(int x, int y) {
        if (x > y) return x;
        else return y;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.close();

        System.out.println(max(a, b));
    }
}

AcWing 808. 最大公约数

import java.util.Scanner;

public class Main {

    public static int gcd(int a, int b) {
        if (b > 0) return gcd(b, a % b);
        else return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.close();

        System.out.println(gcd(a, b));
    }
}

AcWing 811. 交换数值

import java.util.Scanner;

public class Main {

    public static void swap(int[] a) {
        int tmp = a[0];
        a[0] = a[1];
        a[1] = tmp;
    }

    public static void main(String[] args) {
        int[] a = new int[2];
        Scanner scanner = new Scanner(System.in);
        a[0] = scanner.nextInt();
        a[1] = scanner.nextInt();
        scanner.close();

        swap(a);
        System.out.println(a[0] + " " + a[1]);
    }
}

AcWing 812. 打印数字

import java.util.Scanner;

public class Main {

    public static void print(int a[], int size) {
        for (int i = 0; i < size; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
        scanner.close();

        print(a, k);
    }
}

AcWing 813. 打印矩阵

import java.util.Scanner;

public class Main {

    public static void print2D(int a[][], int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++)
                System.out.printf("%d ", a[i][j]);
            System.out.print('\n');
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] a = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = scanner.nextInt();
        scanner.close();

        print2D(a, m, n);
    }
}

AcWing 819. 递归求阶乘

import java.util.Scanner;

public class Main {

    public static int fact(int n) {
        if (n == 1) return 1;
        else return n * fact(n - 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        System.out.println(fact(n));
    }
}

AcWing 820. 递归求斐波那契数列

import java.util.Scanner;

public class Main {

    public static int fib(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 1;
        else return fib(n - 2) + fib(n - 1);
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        System.out.println(fib(n));
    }
}

AcWing 810. 绝对值

import java.util.Scanner;

public class Main {

    public static int abs(int x) {
        if (x < 0) x = -x;
        return x;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        scanner.close();

        System.out.println(abs(x));
    }
}

AcWing 806. 两个数的和

import java.util.Scanner;

public class Main {

    public static double add(double x, double y) {
        return x + y;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        double x = scanner.nextDouble();
        double y = scanner.nextDouble();
        scanner.close();

        System.out.printf("%.2f\n", add(x, y));
    }
}

AcWing 807. 区间求和

import java.util.Scanner;

public class Main {

    public static int sum(int l, int r) {
        if (l > r) {
            int tmp = l;
            l = r;
            r = tmp;
        }
        return (l + r) * (r - l + 1) / 2;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int r = scanner.nextInt();
        scanner.close();

        System.out.println(sum(l, r));
    }
}

AcWing 809. 最小公倍数

import java.util.Scanner;

public class Main {

    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    public static int gcd(int a, int b) {
        if (b > 0) return gcd(b, a % b);
        else return a;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.close();

        System.out.println(lcm(a, b));
    }
}

AcWing 814. 复制数组

import java.util.Scanner;

public class Main {

    public static void copy(int a[], int b[], int size) {
        for (int i = 0; i < size; i++) b[i] = a[i];
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n1 = scanner.nextInt();
        int[] a = new int[n1];
        int n2 = scanner.nextInt();
        int[] b = new int[n2];
        int k = scanner.nextInt();
        for (int i = 0; i < n1; i++) a[i] = scanner.nextInt();
        for (int i = 0; i < n2; i++) b[i] = scanner.nextInt();
        scanner.close();
        copy(a, b, k);
        for (int i = 0; i < n2; i++) System.out.printf("%d ", b[i]);
        System.out.print("\n");
    }
}

AcWing 815. 打印字符串

import java.util.Scanner;

public class Main {

    public static void print(char[] str) {
        for (char c : str) System.out.print(c);
        System.out.print('\n');
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        char[] str = scanner.nextLine().toCharArray();
        print(str);
    }
}

AcWing 816. 数组翻转

import java.util.Scanner;

public class Main {

    public static void reverse(int a[], int size) {
        for(int i = 0, j = size - 1; i < j; i++, j--) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int size = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
        scanner.close();

        reverse(a, size);

        for (int i = 0; i < n; i++) 
            System.out.printf("%d ", a[i]);
        System.out.print('\n');
    }
}

AcWing 817. 数组去重

import java.util.Scanner;

public class Main {

    public static int size = 1001;
    public static boolean[] h = new boolean[size];

    public static int get_unique_count(int a[], int n) {
        for (int i = 0; i < n; i++) h[a[i]] = true;
        int cnt = 0;
        for (int i = 0; i < size; i++)
            if (h[i]) cnt++;
        return cnt;
    }


    public static void main(String[] args) {


        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
        scanner.close();

        System.out.println(get_unique_count(a, n));
    }
}

AcWing 818. 数组排序

import java.util.Scanner;

public class Main {
    public static void sort(int a[], int l, int r) {
        if (l >= r) return;

        int i = l - 1, j = r + 1, x = a[l + r >> 1];
        while(i < j) {
            do i++; while(a[i] < x);
            do j--; while(a[j] > x);
            if (i < j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }

        sort(a, l, j);
        sort(a, j + 1, r);
    }

    public static void main(String[] args) {


        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int l = scanner.nextInt();
        int r = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
        scanner.close();

        sort(a, l, r);
        for (int i = 0; i < n; i++)
            System.out.printf("%d ", a[i]);
        System.out.print('\n');
    }
}

AcWing 821. 跳台阶

import java.util.Scanner;

public class Main {
    public static int fib(int n) {
        if (n <= 2) return 1;
        else return fib(n - 2) + fib(n - 1);

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        System.out.println(fib(n + 1));
    }
}

AcWing 822. 走方格

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.close();

        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                if (i == 0 || j == 0) f[i][j] = 1;
                else f[i][j] = f[i - 1][j] + f[i][j - 1];

        System.out.println(f[m][n]);
    }
}

AcWing 823. 排列

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {

    private static int n;
    private static int[] path;
    private static boolean[] st;

    private static final BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void f(int k) throws IOException {
        if (k == n) {
            for (int i = 0; i < n; i++)
                bufferedWriter.write(path[i] + " ");
            bufferedWriter.write("\n");
        } else {
            for (int i = 1; i <= n; i++)
                if (!st[i]) {
                    st[i] = true;
                    path[k] = i;
                    f(k + 1);
                    st[i] = false;
                }
        }
    }

    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        scanner.close();

        path = new int[n];
        st = new boolean[n + 1];
        f(0);

        bufferedWriter.flush();
    }
}

笔记

本题需要用BufferedWriter优化输出效率，同时需要调用flush()方法刷新才能输出结果。