Introduction to Algorithms, Programming, and Compilers

算法、编程与编译器入门

Sequencing means steps execute one at a time, in order. This is the most basic control structure in any program.

顺序执行是指各个步骤按顺序逐条执行。这是任何程序中最基本的控制结构。

The Build Process

构建流程

Three Types of Errors

三种错误类型

Variables and Data Types

变量与数据类型

A data type is a set of values plus operations on those values. Java data types fall into two categories: primitive and reference.

数据类型是一组值以及作用于这些值的运算的集合。Java 的数据类型分为两大类：基本类型（primitive type）和引用类型（reference type）。

The Three Primitive Types (AP CSA)

三种基本类型（AP CSA）

A variable is a named storage location. It has a name, a type, and a value that can change while the program runs.

变量是一个有名字的存储位置。它有一个名字、一个类型，以及一个在程序运行过程中可以改变的值。

int score = 95;         // primitive, holds the value directly// 基本类型，直接保存值
String name = "Alice";  // reference, holds address of String object// 引用类型，保存指向 String 对象的地址

Expressions and Output

表达式与输出

Printing to the Console

打印到控制台

System.out.println("Hello!");  // prints + newline// 打印并换行
System.out.print("Hi ");       // prints, cursor stays// 打印，光标停在原行
System.out.print("there");     // continues on same line// 在同一行继续输出
// Output: Hi there// 输出：Hi there

Literals & Escape Sequences

字面量与转义序列（escape sequence）

A literal is a fixed value in code. A string literal is text in double quotes: "Hello".

字面量（literal）是代码中的固定值。字符串字面量是写在双引号里的文本："Hello"。

Arithmetic Operators

算术运算符（operator）

double avg = 5 / 2 * 2.0;
// Step 1: 5 / 2 evaluates to 2 (both ints, integer division)// 第 1 步：5 / 2 = 2（两边都是 int，整数除法）
// Step 2: 2 * 2.0 evaluates to 4.0 (int gets promoted to double)// 第 2 步：2 * 2.0 = 4.0（int 被提升为 double）
// avg = 4.0, not 5.0// avg = 4.0，而不是 5.0

Assignment Statements and Input

赋值语句与输入

The assignment operator = stores the value on the right into the variable on the left. The expression on the right is evaluated first.

赋值（assignment）运算符 = 把右侧的值存入左侧的变量。右侧的表达式会先被求值。

int x = 5;
x = x + 3;  // x is now 8, right side evaluates first// x 现在是 8，右边先求值

Reading Input

读取输入

import java.util.Scanner;

Scanner input = new Scanner(System.in);
System.out.print("Enter age: ");
int age = input.nextInt();

Casting and Range of Variables

类型转换（casting）与变量取值范围

Casting

类型转换

Explicit casting converts one primitive type to another.

显式类型转换可以把一种基本类型（primitive type）转换成另一种。

double d = 9.7;
int n = (int) d;       // n = 9, truncates (does NOT round)// n = 9，向零截断（不是四舍五入）
double e = (double) 5; // e = 5.0// e = 5.0

Integer Range & Overflow

整数取值范围与溢出

int uses 4 bytes: range is Integer.MIN_VALUE (−2,147,483,648) to Integer.MAX_VALUE (2,147,483,647). Going beyond → integer overflow: result wraps around unpredictably.

int 占 4 字节：取值范围是 Integer.MIN_VALUE（−2,147,483,648）到 Integer.MAX_VALUE（2,147,483,647）。超出该范围会发生整数溢出（integer overflow）：结果会以不可预测的方式回卷。

int a = (int) 9.7;          // 9   (drops the .7)// 9   （丢弃 .7）
int b = (int) -9.7;         // -9  (NOT -10; truncates toward zero)// -9  （不是 -10；向零截断）
double c = (int) 3.9 + 0.5;   // 3.5  (cast hits 3.9 only, then 3 + 0.5)// 3.5  （转换只作用于 3.9，然后 3 + 0.5）
int d = (int) (3.9 + 0.5);    // 4    (parentheses make the cast hit the whole sum)// 4    （括号让转换作用于整个和）

Compound Assignment Operators

复合赋值运算符（operator）

int score = 10;
score += 5;   // 15// 15
score *= 2;   // 30// 30
score--;       // 29// 29

Application Program Interface (API) and Libraries

应用程序接口（API）与库

Libraries are collections of pre-written classes. An API (Application Programming Interface) is documentation that tells you how to use those classes.

库是一组已经写好的类的集合。API（应用程序接口）是一份文档，告诉你如何使用这些类。

Classes in APIs are grouped into packages. You use existing classes to create objects and call their methods.

API 中的类按包来组织。你使用已有的类来创建对象，并调用它们的方法。

Documentation with Comments

使用注释做文档

// Single-line comment// 单行注释

/* Multi-line
   block comment *//* 多行
   块注释 */

/** Javadoc comment, used to
  * generate API documentation *//** Javadoc 注释，用于
  * 生成 API 文档 */

Method Signatures

方法签名

A method is a named block of code that runs only when called. Procedural abstraction: you can use a method knowing what it does without knowing how.

方法（method）是一段有名字的代码块，只有在被调用时才会执行。过程抽象：你只需要知道一个方法做什么就能使用它，而不必知道它怎么做。

Parameters vs Arguments

形参（parameter） vs 实参（argument）

Parameter: variable declared in the method header. Argument: the actual value passed in when calling the method. Java uses call by value, parameters get copies of the arguments.

形参：方法头中声明的变量。实参：调用方法时实际传入的值。Java 采用按值调用，形参拿到的是实参的副本。

Void vs Non-Void Methods

void 方法 vs 非 void 方法

When a method is called, execution jumps into that method. After the method finishes (or hits a return), control returns to the calling point.

方法被调用时，执行会跳转到该方法中。方法执行完毕（或遇到 return）后，控制权再回到调用点。

Calling Class Methods

调用类（class）方法

Class methods (also called static methods) belong to the class itself, not to any particular object. They have static in the header.

类方法（也称为静态方法）属于类本身，而不属于某个具体的对象。它们的方法头中带有 static。

// Called using ClassName.methodName()// 通过 ClassName.methodName() 调用
int absVal = Math.abs(-42);  // 42// 42

If you call a static method from within the same class, the class name is optional.

如果在同一个类内部调用静态方法，类名可以省略。

Math Class

Math 类

Part of java.lang (automatically available). Contains only static methods, no objects needed.

属于 java.lang（自动可用）。只包含静态方法，不需要创建对象就能使用。

Generating Random Integers

生成随机整数

// Random int from min to max (inclusive)// 从 min 到 max（含端点）的随机整数
int roll = (int) (Math.random() * 6) + 1;  // 1–6// 1–6

// General formula: (int)(Math.random() * range) + min// 通用公式：(int)(Math.random() * range) + min
// where range = max - min + 1// 其中 range = max - min + 1

// Random integer in [min, max] inclusive:// [min, max] 闭区间内的随机整数：
int r = (int)(Math.random() * (max - min + 1)) + min;

Objects: Instances of Classes

对象（object）：类的实例（instance）

Key ideas about class hierarchies (for awareness, not implementation on the AP exam):

关于类层级结构的几个关键概念（AP 考试只要求了解，不要求自己实现）：

A reference variable stores an object reference (essentially the memory address of the object).

引用变量存储的是对象引用（本质上是该对象的内存地址）。

Object Creation and Storage (Instantiation)

对象的创建与存储（实例化 instantiation）

Objects are created using the new keyword followed by a constructor call.

使用 new 关键字加上一次构造方法（constructor）调用来创建对象。

// ClassName variableName = new ClassName(arguments);// 类名 变量名 = new 类名(参数列表);
Scanner sc = new Scanner(System.in);
String greeting = new String("Hello");

Like method calls, constructor calls use call by value, parameters get copies of arguments. A constructor call interrupts sequential flow: statements in the constructor execute first, then control returns.

与普通方法调用一样，构造方法调用也使用按值调用，形参拿到的是实参的副本。构造方法的调用会打断顺序执行：构造方法内的语句先执行，然后控制权再返回。

Reference variables hold either an object reference or null.

引用变量保存的要么是对象引用，要么是 null。

Calling Instance Methods

调用实例方法

Instance methods are called on an object using the dot operator.

实例方法（instance method）通过点运算符在某个对象上调用。

String name = "Alice";
int len = name.length();  // instance method call → 5// 实例方法调用 → 5

String Manipulation

字符串（String）操作

String is in java.lang (auto-imported). Strings are immutable, once created, they cannot be changed. Methods return new strings.

String 位于 java.lang（自动导入）。字符串是不可变的（immutable）：一旦创建就无法被修改。相关方法返回的都是新的字符串。

Creating Strings

创建字符串

String a = "hello";                      // string literal// 字符串字面量
String b = new String("hello");         // constructor// 构造方法

Concatenation

字符串拼接（concatenation）

String full = "AP" + " CSA";   // "AP CSA"// "AP CSA"
int num = 5;
String msg = "Unit " + num;    // "Unit 5", int auto-converts// "Unit 5"，int 自动转换

Worked Example

例题

String s = "computer";
s.length()              // 8// 8
s.substring(0, 3)       // "com"// "com"
s.substring(3)          // "puter"// "puter"
s.indexOf("put")        // 3// 3
s.indexOf("xyz")        // -1// -1
s.substring(2, 3)       // "m", single char at index 2// "m"，索引 2 处的单个字符

String a = "hi";
String b = "hi";
String c = new String("hi");

a == b           // true   (string-pool sharing, both point to the same literal)// true   （字符串池共享，两者指向同一个字面量）
a == c           // false  (c is a fresh object on the heap)// false  （c 是堆上新建的对象）
a.equals(c)      // true   (same characters)// true   （字符序列相同）

Unit 1 MCQ Patterns That Show Up Every Year

单元 1 每年都会出现的选择题套路

Unit 1 is mostly tested on the MCQ section. The same handful of patterns reappear in different costumes. If you can spot which pattern a question is testing, you can usually answer it in under 30 seconds.

单元 1 主要在选择题部分被考察。同样的几种套路会换着包装反复出现。只要能认出题目在考哪一种套路，通常 30 秒之内就能作答。

Flashcards, Click to Flip

闪卡（点击翻面）

Unit 1, Practice Quiz

单元 1：练习小测

AP-Style Practice Problems

AP 风格练习题