关于刷 Coding 题的总结

• Data Structures 数据结构
• Algorithms 算法
• Basic Java Structure - How to code in ACM mode 框架在ACM模式下
• Relationship between data range and algorithms selection 数据规模与算法选择
• My Coding Solutions in LeetCode
• Others
• Notice when soloving LeetCode problems
• Notice when solving codeforces problems

Data Structures 数据结构

Algorithms 算法

Basic Java Structure - How to code in ACM mode 框架在ACM模式下

1. Basic skeleton: psvm String[] args - Scanner - nextLine/nextInt
2. How to read string or int, and how to change type from string: Integer.parseInt(str) - Double.parseDouble(str) - str.toCharArray() - str.toLowerCase() - str.split(” ”)
3. How to handle unlimited numbers: while(in.hasNextInt()){}
4. How to convert output format:

// 基本框架，以HJ1字符串最后一个单词的长度为例
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] strs = str.split(" ");
        System.out.print(strs[strs.length-1].length());
    }
}

// 读取一行字符串的操作
Scanner in = new Scanner(System.in);
String str = in.nextLine().toLowerCase();
int num = in.nextInt();
// String -> char[]
char[] chars = str.toCharArray();
// String -> byte[]
byte[] bytes = str.getBytes();
// String -> int
int num1 = Integer.parseInt(str);
int num2 = Integer.valueOf(str).intValue();
int num3 = (new Integer(str)).intValue();
// String -> double
double double_num1 = Double.parseDouble(str);
double double_num2 = Double.valueOf(str).doubleValue();
double double_num3 = (new Double(str)).doubleValue();

// 华为指南，如何处理无限数字
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }
    }
}

Relationship between data range and algorithms selection 数据规模与算法选择

1. O(n^2) 解决 n<1e4 的问题
2. O(nlogn) 解决 n<1e6 的问题
3. O(n) 解决 n <1e8 的问题
4. O(logn) 解决 n>1e8 的问题

My Coding Solutions in LeetCode

Others

Notice when soloving LeetCode problems

• while循环里面的变量不要忘了某个变量要更新（如，有prev curr不要只更新curr）
• 返回List<List<Integer>>则不能写ArrayList<List<Integer>>，但返回List<Integer>则可以用LinkedList<Integer> result = new LinkedList<>();，其中有addFirst功能的是LinkedList。
• 二分相关的考虑left==right包含与否，以及防止溢出使用left+(right-left)/2（74. Search a 2D Matrix）。
• 链表题目：可视化节点。如：反转链表的recursion：1→2→3时，head最后到1，情况是1→2←3，注意node是3，那么要做什么呢？更改为1←2，并且null←1即可；反转链表的iteration：curr 1->2->3，要变成 null<-1 2->3，即每次iteration要修改一个符号，那么如何写prev curr next都会很清楚（206. Reverse Linked List）。
• 如果你修改了一句代码的一部分，请检查是否这句话别的部分也要修改！易错！
• 又错一次，这种情况直接重想重写
• 语法：new int[]{1,2,3,4};
• 看清题，不要想当然；如最后一句话说：如果不满足则xxx
• 正难反易，比如有时候你会从最后开始填充（88. Merge Sorted Array），或者你会倒着加入元素（145. Binary Tree Postorder Traversal）。
• 每次push offer的时候都要判断一下是不是null！尤其是树节点相关的题目。如果不在push offer的时候判断，pop poll的时候也应该判断。
• 树的题目先想清楚遍历结构，是dfs用stack，是bfs用queue；level遍历时候用queue，每次for q.size()次，即清理一层。（这点又错了一次，因为清理的时候没用for q.size()次，在哥大作业中）
• 处理那种类型是对象的，如TreeNode之类的，一定要判断null。
• 如果是tree，跟H有关的复杂度就用H写。因为平均一般是logn，最差是n。
• 有时候要看数据范围，如果是≥≤这种，则需要注意别溢出（98. Validate Binary Search Tree），比如Integer.MAX_VALUE如果还小，则要用Long.MAX_VALUE。
• 记一道异或标准题目（136. Single Number），异或（^）的核心是a^a = 0, 0^a = a。
• 如果if了就直接想清楚else，不要只想一半或者非要省略写法而导致出错（203. Remove Linked List Elements）。
• 记得快慢指针的这个方法，经常想不到用= =快的指针走的多，看得多，所以它负责查；慢的指针走的少，遇到要移动的就停下来，等快的找到了不同的再替换（27. Remove Element）。
• 滑动窗口的题目要思考三个问题：窗口内是什么？如何移动窗口的起始位置？如何移动窗口的结束位置？想清楚如果有双重循环，是哪个作为内部循环，因为这个变量变化更多？（209. Minimum Size Subarray Sum）

Notice when solving codeforces problems

• 竞赛的题目一定要在草稿本上先画一画样例。
• 有的题目会迷惑你，说一堆无关信息（如：2-3 Moves，+-2和+-3都是无关信息），请注意甄别，分析出最重要的。

private static int get_ceil(int a, int b) {
    return (a + b - 1) / b;
}
private static int get_mod(int a, int b) {
    return (a % b + b) % b;
}