Lec4.

• Decomposition(分解)
• Abstraction(抽象)

Function

• block up into modules
• suppress detail
• create “new primitive”(原语)

抽象和规格化在模块化和构造函数时的重要性

作用域和值绑定

Interpretes: -> golbal binding
call function-> local table

穷举算法(brute force algorithm)

遍历每一种情况找到答案

Recursion(递归)

-> base case: -simplest possible solution
-> induction step: break problem into a simple version

Lec5 & Lec6.

• 大数
• 浮点数精度
• 浮点数的’==’
• 牛顿法求根号
• 逐次逼近法(guess, check, improve)
• 二分法(Bisection method)
• 回归测试
• 牛顿法和二分法对于求解sqrt问题的复杂度对比: 二分的迭代次数随着x的增加明显增加
• 浮点数的上溢和下溢问题

计算机科学及编程导论 Lec1.

什么是计算思维(computation)

知识：

• 陈述性知识(declarative):描述事实 Ex: 若sqrt(x)=y则y^2=x
• 程序性知识(imperative):对推论过程的描述 Ex:GCD求法

计算机:

fixed-program computer: 固定程序用来做特定的运算

• calculator(计算器)
• Atanasoff(解线性方程组)
• Turing bombe(破译代码-图灵)

stored-program computer: 提供一系列的指令,计算机来执行这些指令(现代计算机模型)

program is a recipe: given a fixed set of primitives -> can program anything

讨论语言的三个维度:

• High vs Low: 离计算机核心有多接近
• General vs targetted: 被设计为通用还是面向目标群体(领域语言)
• interpreted vs compiled: 编译型语言还是解释型语言

Python: High,General,Interpreted

Syntax(语法): 什么是这种语言中的合法表达

Semantics(语义):

• Static: 那些程序是有意义的
• Full:程序有什么意义(运行时意义)

Lec2.

程序运行2种方式:

• Interpret(直接解释)->eval&print

• script(存储脚本)-> no print unless explict

  类型检查:

• weak vs strong typing

  Typediscipline(代码规范)

• A:检查运算符或程序来看他们在不同条件下做的操作是什么

• B:约束参数的类型

  赋值

1 2	x = 3 + 5 y = 15

• 类型
• 类型转换
• 类型绑定(动态绑定)
  建议:Don’t change types arbitrary

Variable used any place it’s legal to required

Statements(声明):

legal commands that Python can Interpret

直线式(顺序)程序:

按照顺序一条条代码执行

分支式(条件)程序:

改变程序执行的顺序通过一些条件Test(一般是变量的值)

Lec3.

流程图

防卫性程序

程序要覆盖所有的可能路径

Tuple: 一系列有序的元素的集合

foo=(1, 2, 3, 4)

题目及理解

题目连接557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:

1
2

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

理解

水题,就是按照每个单词进行翻转.我的方法是遇到空格之前都压入栈中,然后遇到空格全部pop出来,结果自己僵化,最后没有空格的时候没有把最后一个单词pop出来,这里需要注意一下.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public:    
        string reverseWords(string s) {        
            string news;        
            stack<char> stack;        
            for (int i=0; i<s.size(); i++){            
                stack.push(s[i]);            
                if (stack.top() == ' '){                
                    stack.pop();                
                    while(!stack.empty()){                    
                        news += (char)stack.top();                    
                        stack.pop();                
                    }                
                    news += ' ';            
                }        
            }        
            while(!stack.empty()){                    
                news += (char)stack.top();                    
                stack.pop();                
            }        
        return news;    
    }
};

其他解法

看了别人dalao写的代码,用的是找空格然后整体翻转的思路,但是我这样写比较偷懒吧= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public:    
        string reverseWords(string s) {        
            for (int i = 0; i < s.length(); i++) {            
                if (s[i] != ' ') {   // when i is a non-space
                    int j = i;                
                    for (; j < s.length() && s[j] != ' '; j++) { }  // move j to the next space                
                    reverse(s.begin() + i, s.begin() + j);                
                    i = j - 1;            
                }        
            }                
        return s;    
    }
};