Algorithm
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int charset[256] = {0};
int left = 0, right = -1;
int length = 0;
while(left < s.size()){
if(right+1 < s.size() && charset[s[right+1]] == 0){
right++;
charset[s[right]]++;
} else {
charset[s[left]]--;
left++;
}
length = max(length, right-left+1);
}
return length;
}
};
Review
Clang provides infrastructure to write tools that need syntactic and semantic information about a program. This document will give a short introduction of the different ways to write clang tools, and their pros and cons.
Clang提供了需要程序语法语义信息的编写工具的基础设施。本文将会简述编写clang工具的基本方法。
LibClang is a stable high level C interface to clang. When in doubt LibClang is probably the interface you want to use. Consider the other interfaces only when you have a good reason not to use LibClang.
LibClang是Clang的一个稳定的高级C接口。当你对是否使用LibClang有疑虑时，只有当您有充分的理由不使用LibClang时，再考虑其他接口。
Canonical examples of when to use LibClang:
- Xcode
- Clang Python Bindings
使用LibClang的典型案例：
- Xcode
- Clang Python Bindings
Use LibClang when you…:
- want to interface with clang from other languages than C++
- need a stable interface that takes care to be backwards compatible
- want powerful high-level abstractions, like iterating through an AST with a cursor, and don’t want to learn all the nitty gritty details of Clang’s AST.
使用LibClang当你：
- 想要除C++以外的其他语言与Clang进行交流时
- 需要一个负责向后兼容的稳定的接口时
- 需要强大高级的抽象，就像使用游标遍历抽象语法树。并且你不想要了解Clang抽象语法树所有繁杂的细节。
Do not use LibClang when you…:
- want full control over the Clang AST
不要使用LibClang当你：
- 想要完全控制Clang的抽象语法树。
Clang Plugins allow you to run additional actions on the AST as part of a compilation. Plugins are dynamic libraries that are loaded at runtime by the compiler, and they’re easy to integrate into your build environment.
Clang插件允许你作为编译的一部分运行其他的操作。插件是被编译器在运行时动态加载的动态库，它们很容易集成到构建环境。
Canonical examples of when to use Clang Plugins:
- special lint-style warnings or errors for your project
- creating additional build
artifactsfrom a single compile step
使用Clang插件的典型案例：
- 为你的工程提供特殊样式的警告和错误提示信息
- 从单一的编译阶段创建其他的构建工件。
Use Clang Plugins when you…:
- need your tool to rerun if any of the dependencies change
- want your tool to make or break a build
- need full control over the Clang AST
使用Clang 插件当你：
- 需要重新运行，如果有任何依赖发生变化
- 想要你的工具建立或打破一次构建
- 需要完全控制Clang的抽象语法树
Do not use Clang Plugins when you…:
- want to run tools outside of your build environment
- want full control on how Clang is set up, including mapping of in-memory virtual files
- need to run over a specific subset of files in your project which is not necessarily related to any changes which would trigger rebuilds
不要使用Clang插件当你：
- 想要在构建环境之外去运行工具
- 想要完全控制Clang是怎么被设置的，包括虚拟文件在内存中的映射
- 需要在项目中运行特定的文件子集，这些文件不涉及任何会触发重构的变化
LibTooling is a C++ interface aimed at writing standalone tools, as well as integrating into services that run clang tools. Canonical examples of when to use LibTooling:
- a simple syntax checker
- refactoring tools
LibTooling是一个C++接口，旨在编写独立的工具，并集成到运行clang工具的服务中去。使用LibTooling的典型案例：
- 简单的语法检查器
- 重构工具
Use LibTooling when you…:
- want to run tools over a single file, or a specific subset of files, independently of the build system
- want full control over the Clang AST
- want to share code with Clang Plugins
使用LibTooling当你：
- 想要在独立于构建系统的单个文件或指定文件集上运行工具
- 想要完全控制Clang抽象语法树
- 想用Clang插件共享代码
Do not use LibTooling when you…:
- want to run as part of the build triggered by dependency changes
- want a stable interface so you don’t need to change your code when the AST API changes
- want high level abstractions like cursors and code completion out of the box
- do not want to write your tools in C++
不要使用LibTooling当你：
- 想要作为构建系统的一部分，依赖变化触发去运行。
- 希望有一个稳定的接口，这样当AST API发生变化时，您就不需要更改代码了
- 想要使用高级的抽象就像游标和开箱即用的代码
- 不想使用C++编写你的工具
重点词汇
infrastructure ['ɪnfrə'strʌktʃɚ]
n. 基础设施
例句：Clang provides infrastructure to write tools .
canonical [kə'nɑnɪkl]
adj. 依教规的；权威的;
例句：Canonical examples of when to use LibClang.
** artifact** ['ɑrtə,fækt]
n. 人工制品；手工艺品；工件
例句：creating additional buildartifactsfrom a single compile step.
** standalone** ['stændə,lon]
adj. 单独的
例句：writing standalone tools.
Tips
设计原则相关：
- 找出应用中可能需要变化之处，把它们独立出来，不要和那些不需要变化的代码混在一起。
- 针对接口编程，而不是针对实现编程。
Share
- GCC将C语言的程序转化为用机器语言描述的程序。将机器语言的程序按照ELF这种特定的文件格式注入文件，得到的就是可执行文件。
- 编程语言的运行方式：编程语言可以被编译成机器语言然后被执行，也可以不进行编译，直接运行编程语言的方法，例如解释器，Ruby和Perl的语言处理器就是用解释器来实现的。C语言也可以用解释器来执行，Ruby也可以被编译成机器语言。总之，运行语言的手段不止一种，编程语言与其运行方式可以自由搭配。但是根据语言的特点，其运行方式有适合与不适合该语言之说。一般来讲，有静态类型检查的，要求较高可靠性的情况下使用编译的方式；相反，没有静态类型检查，对灵活性要求高于严密性的情况下则使用解释的方式。
- Build分为四个阶段：预处理-编译-汇编-链接
- 编译分为四个阶段：语法分析-语义分析-生成中间代码-代码生成-（优化）
- 语法分析syntax analyzing：解析器parser（或语法分析器syntax analyzer）转换成计算机易于理解的形式，即语法分析树。语法分析又分为两个阶段：
- 词法分析lexical analyze。将代码分割为一个个的单词，也可以称为扫描。在分隔的同时还会推算出单词的种类，并为单词添加语义值。将“单词”和“单词的种类（语义值）”统称为token。所以词法分析器的作用可以简述为解析字符行，并生成token。下图为打印helloword程序的token序列：
tokens.png
- 语法分析。
-
语义分析semantic analysis：获得语法树之后，就要解析语法树，除去多余的内容，添加必要的信息，生成抽象语法树（Abstract Syntax Tree，AST）。上述处理就是语义分析。语义分析具体做了如下工作：
- 区分变量为局部变量还是全局变量。
- 解析变量的声明和引用。（在变量的声明和引用之间添加链接）
- 变量和表达式的类型检查。
- 检查在引用变量之前是否进行了初始化。
- 检查函数是否按照定义返回了结果。
-
生成中间代码：将抽象语法树转化为只在编译器内部使用的中间代码（Intermediate Representation，IR）。之所以特地转为中间代码是为了支持多种编程语言或者机器语言。
-
解析代码转化为中间代码的这部分内容称为编译器的前端。
-
代码生成：最后把中间代码转化为汇编语言的阶段称为代码生成。由代码生成器Code Generator负责。
-
优化optimization：优化可以在编译器的各个环节进行。
-
字符串能够作为扫描器中的一个token被识别。而‘语句’，‘函数调用’则对应多个单词，即对应多个token，这样的语法 扫描器是无法是别的。将上述多个token构成的语法单位识别出来是解析器的工作。
-
像‘函数调用’，‘表达式’，‘语句’等非token的语法单位成为
非终端符，并将非终端符像java函数调用一样在后面加上括号写成stmt()或expr()。终端符可以被归纳为token。 -
解释为什么会称为终端符和非终端符：因为在画语法树的图时，终端符位于树的末端，非终端符位于分叉处。
-
定义definition包含语句statement，语句statement包含表达式expression，表达式expression包含项term。
网友评论