第7章 类与接口

笔记

类与对象

类定义一种全新的数据类型，包含一组变量和函数；对象是类这种类型对应的实例。
例如在一间教室中，可以将Student定义成类，表示“学生”这个抽象的概念。那么每个同学就是Student类的一个对象（实例）。

源文件声明规则

一个源文件中只能有一个public类。
一个源文件可以有多个非public类。
源文件的名称应该和public类的类名保持一致。
每个源文件中，先写package语句，再写import语句，最后定义类。

类的定义

public: 所有对象均可以访问
private: 只有本类内部可以访问
protected：同一个包或者子类中可以访问
不添加修饰符：在同一个包中可以访问

静态（带static修饰符）成员变量/函数与普通成员变量/函数的区别：

• 所有static成员变量/函数在类中只有一份，被所有类的对象共享；
• 所有普通成员变量/函数在类的每个对象中都有独立的一份；
• 静态函数中只能调用静态函数/变量；普通函数中既可以调用普通函数/变量，也可以调用静态函数/变量。

class Point {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void setX(int x) {
        this.x = x;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public String toString() {
        return String.format("(%d, %d)", x, y);
    }
}

类的继承

每个类只能继承一个类。

class ColorPoint extends Point {
    private String color;

    public ColorPoint(int x, int y, String color) {
        super(x, y);
        this.color = color;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public String toString() {
        return String.format("(%d, %d, %s)", super.getX(), super.getY(), this.color);
    }
}

类的多态

public class Main {
    public static void main(String[] args) {
        Point point = new Point(3, 4);
        Point colorPoint = new ColorPoint(1, 2, "red");

        // 多态，同一个类的实例，调用相同的函数，运行结果不同
        System.out.println(point.toString());
        System.out.println(colorPoint.toString());
    }
}

接口

interface与class类似。主要用来定义类中所需包含的函数。

接口也可以继承其他接口，一个类可以实现多个接口。

接口的定义：

// 接口中不添加修饰符时，默认为public
interface Role {
    public void greet();
    public void move();
    public int getSpeed();
}

接口的继承

// 每个接口可以继承多个接口
interface Hero extends Role {
    public void attack();
}

接口的实现

// 每个类可以实现多个接口
class Zeus implements Hero {
    private final String name = "Zeus";
    public void attack() {
        System.out.println(name + ": Attack!");
    }

    public void greet() {
        System.out.println(name + ": Hi!");
    }

    public void move() {
        System.out.println(name + ": Move!");
    }

    public int getSpeed() {
        return 10;
    }
}

接口的多态

class Athena implements Hero {
    private final String name = "Athena";
    public void attack() {
        System.out.println(name + ": Attack!!!");
    }

    public void greet() {
        System.out.println(name + ": Hi!!!");
    }

    public void move() {
        System.out.println(name + ": Move!!!");
    }

    public int getSpeed() {
        return 10;
    }
}

public class Main {
    public static void main(String[] args) {
        Hero[] heros = {new Zeus(), new Athena()};
        for (Hero hero: heros) {
            hero.greet();
        }
    }
}

习题

AcWing 21. 斐波那契数列

class Solution {
    public int Fibonacci(int n) {
         if (n == 0) return 0;
         else if (n == 1) return 1;
         else return Fibonacci(n - 2) + Fibonacci(n - 1);
    }
}

AcWing 16. 替换空格

class Solution {
    public String replaceSpaces(StringBuffer str) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == ' ') stringBuilder.append("%20");
            else stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }
}

AcWing 84. 求1+2+…+n

class Solution {
    public int getSum(int n) {
        int res = n;
        boolean flag = n > 0 && (res += getSum(n - 1)) > 0; 
        return res;
    }
}

笔记

可用&&特性先判断前者是否满足n > 0，然后再用后者计算结果。如果不满足，不会计算res。

AcWing 28. 在O(1)时间删除链表结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        ListNode p = node.next;
        node.val = p.val;
        node.next = p.next;
    }
}

AcWing 17. 从尾到头打印链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] printListReversingly(ListNode head) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) n++;

        int[] a = new int[n];
        for (ListNode p = head; p != null; p = p.next)
            a[--n] = p.val;

        return a;
    }
}

AcWing 36. 合并两个排序的链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1), p = null, r = res;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p = l1;
                l1 = l1.next;
            } else {
                p = l2;
                l2 = l2.next;
            }

            r.next = p;
            r = p;
        }

        if (l1 != null) r.next = l1;
        if (l2 != null) r.next = l2;

        return res.next;
    }
}

AcWing 78. 左旋转字符串

class Solution {
    public String leftRotateString(String str, int n) {
        StringBuilder sb = new StringBuilder();
        int len = str.length();
        for (int i = 0; i < len; i++)
            sb.append(str.charAt((i + n) % len));

        return sb.toString();
    }
}

AcWing 87. 把字符串转换成整数

class Solution {
    public int strToInt(String str) {
        str = str.trim();
        if (str.length() == 0) return 0;

        boolean positive = true;
        if (str.charAt(0) == '+') str = str.substring(1);
        else if (str.charAt(0) == '-') {
            positive = false;
            str = str.substring(1);
        }

        if (str.length() > 10) {
            if (positive) return Integer.MAX_VALUE;
            else return Integer.MIN_VALUE;
        }

        long res = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c >= '0' && c <= '9') res = res * 10 + c - '0';
            else break;
        }

        if (!positive) res = -res;

        if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        else if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        else return (int)res;
    }
}

AcWing 35. 反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode res = new ListNode(0), p = null;
        while(head != null) {
            p = head;
            head = head.next;
            p.next = res.next;
            res.next = p;
        }
        return res.next;
    }
}

AcWing 66. 两个链表的第一个公共结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        while(p != q) {
            if (p != null) p = p.next;
            else p = headB;
            if (q != null) q = q.next;
            else q = headA;
        }
        return p;
    }
}

笔记

假设不同部分为a 和b，公共部分为c，则有a+ c + b = b + c+ a

因此可让两个指针p和q分别从两个链表的头结点开始走，指针p从a走到链表末尾就从另一个链表头结点b开始走，指针q 从b走到链表末尾就从另一个链表的头结点a开始走，这样两个指针会在公共部分相遇。

注意，相遇不是指两个结点的值相等，而是指两个结点的存储地址相同。

AcWing 29. 删除链表中重复的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplication(ListNode head) {
        ListNode a = new ListNode(0);
        a.next = head;
        ListNode p = a, q = null;
        while (p.next != null) {
            for (q = p.next; q != null && q.val == p.next.val; q = q.next);
            if (q == p.next.next) p = p.next;
            else p.next = q;
        }
        return a.next;
    }
}

笔记

• 前一个指针为p，当前指针为p.next，指针q从当前指针p.next开始遍历，直到走到末尾或结点的值与当前结点的值p.next.val不同停下
• 如果指针q停下的位置恰好为当前指针的下一个，则说明无重复元素或已经走到末尾，直接让指针p指向下一个即可
• 否则从p.next开始到指针q指向的上一个结点元素，都是重复的元素，应该把它们全部删除，即让p.next指向q

AcWing 862. 三元组排序

import java.util.Arrays;
import java.util.Scanner;

class Data implements Comparable<Data> {

    int x;
    double y;
    String z;

    public Data(int x, double y, String z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    @Override
    public int compareTo(Data a) {
        return x - a.x;
    }
}

public class Main {

    public static void main(String[] args)  {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Data[] data = new Data[n];
        for (int i = 0; i < n; i++)
            data[i] = new Data(scanner.nextInt(), scanner.nextDouble(), scanner.next());

        Arrays.sort(data);

        for (Data elem : data)
            System.out.printf("%d %.2f %s\n", elem.x, elem.y, elem.z);

        scanner.close();

    }
}