- C++：STL 好用但是不熟练啊Java：数据结构丰富但是不常用Python：很灵活但是不会用Go：没什么数据结构，只有map和list，只是很常用
Scanner scan = new Scanner(System.in); scan.hasNext(); scan.next(); scan.hasNextLine(); scan.nextLine(); scan.hasNextInt(); scan.nextInt(); scan.hasNextFloat(); scan.nextFloat(); scan.hasNextDouble(); scan.nextDouble(); scan.close();
StringBuilder buf = new StringBuilder();
buf.append(n);
buf.append(m);
buf.append(String.format("%.2f", n));
return buf.toString();
System.out.printf("%010.6fn", 1.31);
System.out.println(String.format("%1.1f", 1.31));
使用数据结构
列表 List
containsaddremovegetsetindexOflastIndexOf
ArrayList
addpollpeek
Deque
getFirstgetLast
linkedList
containsKeycontainsValuegetputremovekeySetvaluesgetOrDefaultreplace
HashMap
firstKeylastKey
集合 Set
subSetheadSettailSet
栈 Stack
pushpoppeek
使用字符串
Arrays.sort(); Collections.sort();数组转 List
// 1. List list = Arrays.asList(strArray); // 2. ArrayList切片：Arrays.copyOfRange()list = new ArrayList (Arrays.asList(strArray)); // 3. ArrayList< String> arrayList = new ArrayList (strArray.length); Collections.addAll(arrayList, strArray);
int a[] = new int[] { 10, 5, 3, 2, 6, 8, 7, 9, 1, 4 };
int b[] = Arrays.copyOfRange(a, 2, 6); // 截取索引2（包括）到索引6（不包括）的元素
备选语言 C++
使用 STL
vector
push_backpop_back
String
push_backpop_backsubstr
unordered_map
counterase
unordered_set
countinserterase
queue
pushfrontpop
stack
pushtoppop
二、题型笔记 搜索 广度优先搜索
package 广度优先搜索;
import java.util.linkedList;
import java.util.Queue;
public class Template {
public static void main(String[] args) {
Queue queue = new linkedList<>(); // Key：广度优先遍历当前层的队列
queue.add(root); // Key：第一层只有根节点
boolean[] marked = new boolean[tree.size()]; // 当前节点是否已经遍历过
int layer = 1; // 当前层的深度
while (!queue.isEmpty()) { // Key：当前层存在
layer++; // 层深度加一
int size = queue.size(); // Key：当前层的大小
while (size-- > 0) { // Key：遍历当前层
String cur = queue.poll(); // 从当前层取出一个元素
for (String next : tree) { // 遍历所有元素
if (!marked[next]) { // 并且当前元素未被访问
if (connect(cur)) { // 并且是当前层的下一层元素
if (find(cur)) { // 已找到目标元素
return;
}
queue.add(next); // Key：添加到下一层，下一层和当前层在同一队列中，当前层在队首，下一层在队尾
marked[next] = true; // 已访问
}
}
}
} // Key：遍历完毕当前层，此时队列全为下一层元素
}
}
}
深度优先搜索
package 深度优先搜索;
public class Template {
public void dfs(TreeNode node, int depth) { // Key：递归遍历各个子树
if (node == null) { // Key：在遍历前判断子树是否为空
return;
}
visit(node); // Key：执行你的操作
// Key：使用函数调用的函数栈，代替dfs的栈操作，调用函数即为入栈，函数返回即为出栈
dfs(node.left, depth + 1); // Key：优先遍历左子树，层数加一
dfs(node.right, depth + 1); // Key：遍历右子树，层数加一
}
public static void main(String[] args) {
dfs(root, 0); // Key：从树的根节点，层数为0开始遍历
}
}
滑动窗口搜索
固定窗口搜索最小窗口搜索最大窗口搜索
void slidingWindow(string s, string t) {
unordered_map need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
...
printf("window: [%d, %d)n", left, right);
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
package 滑动窗口;
import java.util.HashMap;
public class Template {
public String minWindow(String s, String t) {
HashMap window = new HashMap<>(); // 当前窗口
HashMap need = new HashMap<>(); // 目标字符串
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0; // 左右指针
int minLen = Integer.MAX_VALUE, ansLeft = -1, ansRight = -1; // 最小长度和对应的左右指针
for (; right < s.length(); right++) { // 移动右指针，扩大窗口
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1); // 扩大当前窗口
while (窗口满足条件，可以收缩){ // 判断窗口满足条件
if (right - left + 1 < minLen) { // 重写最优解
minLen = right - left + 1;
ansLeft = left;
ansRight = right + 1;
}
left++; // 移动左指针，缩小窗口
char cc = s.charAt(left);
window.put(cc, window.getOrDefault(cc, 0) - 1); // 缩小当前窗口
}
}
return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight); // 返回子串
}
}
二分查找搜索
package 二分查找;
public class Template {
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while (left <= right) {
int mid = left + (right - left) / 2;
// int mid = (left + right) >>> 1;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return right - 1; // 注意
}
}
回溯剪枝搜索
package 回溯;
import java.util.*;
public class Template {
List ans = new ArrayList<>(); // 存储所有满足条件的结果
Stack path = new Stack<>(); // 存储当前遍历的路径
List choiceList = new ArrayList<>(); // 存储所有选择
public List main() {
backtrack(path, choiceList);
return ans;
}
public void backtrack(Stack path, List choiceList) {
if (success(path)) { // 当前路径成功
ans.add(path);
return;
}
for (String choice : choiceList) {
if (fail(path, choice)) { // 当前路径已被剪枝
continue;
}
path.push(choice); // 作出选择
backtrack(path, choiceList); // 进入下一层决策树
path.pop(); // 取消选择
}
}
}
动态规划 迭代框架
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
暴力递归算法
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
存储递归算法
int fib(int N) {
// 备忘录全初始化为 0
int[] memo = new int[N + 1];
// 进行带备忘录的递归
return helper(memo, N);
}
int helper(int[] memo, int n) {
// base case
if (n == 0 || n == 1) return n;
// 已经计算过，不用再计算了
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
DP 迭代算法
int fib(int N) {
if (N == 0) return 0;
int[] dp = new int[N + 1];
// base case
dp[0] = 0; dp[1] = 1;
// 状态转移
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
状态压缩算法
int fib(int n) {
if (n == 0 || n == 1) {
// base case
return n;
}
// 分别代表 dp[i - 1] 和 dp[i - 2]
int dp_i_1 = 1, dp_i_2 = 0;
for (int i = 2; i <= n; i++) {
// dp[i] = dp[i - 1] + dp[i - 2];
int dp_i = dp_i_1 + dp_i_2;
// 滚动更新
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i_1;
}
三、代码框架 解题代码框架
package Hulu;
import java.util.Scanner;
public class Hulu_template {
public static void main(String[] args) {
// 处理输入
Scanner sc = new Scanner(System.in);
// 解析输入
int n = sc.nextInt();
int m = sc.nextInt();
// 主要逻辑 + 输出返回
System.out.println(new Hulu_template().solve(n, m));
// 关闭输入
sc.close();
}
// 处理逻辑 + 构造输出
public String solve(int n, int m) {
StringBuilder buf = new StringBuilder();
// TODO
buf.append(n);
buf.append(m);
buf.append(String.format("%.2f", n));
return buf.toString();
}
}
四、参考链接
● 《labuladong的算法小抄》
