欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

知识点积累

程序员文章站 2024-02-25 16:13:15
...

2018.10.8
1.python中字符串也是可以实现  str.pop()操作
2.C++中,对于vector<string> ans {}; 整个vector可以进行 ans.size()
   对于其中的每个元素也可以实现 ans[i].size()

2018.10.9
1.python中没有自增  ++,取而代之的是  +=1
对于字符串问题,考虑到26个字母的问题的 ,可以将26个字母全部表示出来

2018.10.10
1.关于树的问题,特别是二叉树相关的问题,divide and conquer 分而治之是一个很重要的思想,这个解题思路在快速排序中也有体现
2.树的问题一般都会用 递归的方法来解决 ,但是要注意有题目有意让你用iteration迭代的方法来实现,注意基础的实现(利用栈的数据结构)
2018.10.11
1.关于树遍历迭代遍历的总结
2.关于树的问题,判断问题 第一步要先判断结点能否存在,第二步判断结点的值是否相等  这个步骤很重要
2018.10.17
1.关于链表数据结构,对于设计到链表的长度以及中点的问题“双指针的问题”,两个起点相同的指针,一个走一步,一个一次走两步 .还有经典问题 倒数第k个问题也是利用双指针解决
2018.10.18
1.牛客网刷题:
*  main函数中变量不是在整个程序中有用,main函数中定义的变量只能在主函数中使用,只用在所有函数外定义的变量才可以在整个函数中使用.
*  析构函数,是在函数前面加上~,析构函数不能指定返回函数类型
* 运算符的优先级:
      1 () [] . -> 
      2 ! ~ -(负号) ++ -- &(取变量地址)* (type)(强制类型) sizeof  
      3 * / %  4 + -  5 >> <<  6 > >= < <=  7 == !=  
      8 &  9 ^  10 |  11 && 12 || 13 ?: 
     14 = += -= *= /= %= |= ^= &= >>= <<= 15 , 
* 简单的宏定义:
         #define 标识符 替换列表
(替换列表可以是数,字符串字面量,标点符号,运算符,标识符,关键字,字符常量。注意:替换列表是可以为空的)
       对于宏定义的运算,直接将替换列表带入到公式中计算
* 位运算符考察也是挺多的,以及各种位运算符的优先级
2018.10.19
牛客基础知识:
* Switch 语句 在case中如果没有break,会执行满足条件语句以及之后的所有条件语句.
*  函数构造,友元函数,析构函数定义不是很理解
* 名字的作用域:始于初始化,结束于花括号;对象的生命周期-执行过程中该对象存在的一段时间
* 构造函数和名字和类名相同,构造函数没有返回类型
* struct 类定义默认是public公用的 class类定义默认是私有的。
* 友元(friend):类可以允许其他类或者函数访问它的非公有成员
2018.10.20
语言基础知识:
* sizeof 返回的是字节数 :元素个数*元素的字节数  指针的sizeof为8个字节32位
2018.10.22
c++基础知识:
* 字符串常量,字符常量
       字符常量必须是单引号括起来的内容
* 派生类对象可以自动split为基类对象,但一个基类对象不能转换为派生类对象
* 要非常注意⚠️:while(I++)这个判断后i是要自增的。
* p是指针,可以写p->str,但是(*p)只能写(*p).str;
2018.10.23
* Backtracking 回溯算法   
* 关于回溯算法的讲解: https://leetcode.com/problems/combination-sum/discuss/16496/Accepted-16ms-c++-solution-use-backtracking-easy-understand.
* Divide and conquer 分而治之算法
* 一个程序中允许使用任意数量的#Include命令行
2018.10.25
* (start-end)>>1 与(start-end)/2 是一样的效果
* 数组中重复元素的读取可以利用hashtable来使用。
2018.10.31
-  static int a=2  只会进行一次初始化,下次调用就不是这个值了
2018.11.5
-  函数的调用和定义都可以嵌套使用
-  malloc是函数
-   赋值运算符〈逻辑运算符〈关系运算符〈算术运算符
-  系统函数符可以作为自定义标识符
2018.10.24

解释性语言&编译性语言
1.解释性语言是不需要编译的,程序运行的时候代码会一行一行翻译成机器能够识别的语言。语言每执行一次就需要逐行翻译一次,效率比较低
2.编译性语言在程序被执行之前,需要一个专门的编译过程,生成机器语言文件,exe文件,运行时候不再需要翻译,执行运行执行后的结果。程序的效率比较高

内联函数
内联函数是编译器优化手段的一种技术。是c++增强特性之一,用来降低程序的运行时间。关键字为:inline

C++合法自定义字符
1、首字符为字母或者下划线;
2、其他字符为字母、数字或下划线的名称;
3、不为特殊字符或C/C++关键字

static变量
程序中定义静态变量
静态变量只会初始化一次,并且具有全局生存期。

计算机网络
感觉很难受,知识点都不知道,需要强化计算机网络和数据库操作


2018.10.25

String&字符串字面值

  • "hello,world" 字符串字面值
  • string s="hello,world" string类型
    字面值不能直接相加
    错误:string str="hello"+"world"
    正确:string str=s+"hello"+"world"
    错误:string str="hello"+world"+s
    需要保证string类型在字面值前面(左侧)

for-下标循环&迭代器循环
泛型编程
一般程序中不考虑其他元素,我们都可以写成迭代器循环
有的容器类型没有提供下标运算符,不能使用下标循环。

二维vector的初始化及运算

  • 初始化的程序步骤
  • 能否使用数组的下标 matrix[0].size()

数组及多维数组
1.数组的大小确定不变,不能随意增添数组。不知道元素的确切个数还是要使用vector
2.数组的特性:在用到数组名字的地方,编译器会自动的将其替换为一个指向数组首元素的指针。
3.c++本质上来说是没有多维数组的,所谓的多维数组只是数组的数组。
4.对于范围for语句,除了最内层的循环外,其他所有循环的控制变量都应该是引用类型。

int cnt=0;
for(auto &row:array)
    for(auto &col:row){
        col=cnt;
        ++cnt;
    }
// 这个也可以实现
for(auto row:array)
    for(auto &col:row){
        col=cnt;
        ++cnt;
    }
// 这个就实现不了
for(auto row:array)
    for(auto col:row){
        col=cnt;
        ++cnt;
    }

初始化row的时候,会自动将这个数组形式的元素转换成指向该数组内首元素的指针。下一个内层循环就不合法了。

有效的预处理命令总是以“#”开头
(1)头文件包含#include
(2)宏定义 #define
(3)条件编译 #ifdef #endif

//统计二进制数中“1”的个数,用如下代码
int fun(int value)
{
    int cnt = 0;
    while(value)
    {
        cnt++;
        //消除所有1,变成0,用二进制的与命令
        value = value & (value - 1);
    }
}
//统计二进制数中“0”的个数,用如下代码
int fun(int value)
{
    int cnt = 0;
    while(!value)
    {
        cnt++;
        //消除所有0,变成1,用二进制的或命令
        value = value | (value + 1);
    }
}

程序中判断条件的短路
while(z-->0 && ++x<5)
当z=0的时候执行while,z>0不成立,z--后z=-1;后面的语句被短路将不再执行。

指针类型占8个字节,char一个字节,int4个字节
结构体struct的总大小sizeof一定是最大字节的整数倍。

2018.10.29

开始学习字符串的相关问题
注意区分vector<string>和其中字符的区别
string相当于一个容器,其中的每个字符是其真正的元素
每个元素vector[index]是一个字符串 string
string[index]则是一个char

2018.10.30

利用vector可以高效率简洁的实现stack
注意vector特有的push_back()和pop_back()对应“进栈”和“出栈”
其实感觉关联容器很简单啊
啪啪打脸!!!!!
关联容器
主要就是两种类型:
map
set
再根据关键字是否可以重复(multimap)
元素是否有序 (unordered_map)进行划分。
无序元素采用哈希函数来组织元素。
实现sort(.begin(),.end()) blogs自己实现功能
map就是一个关联数组 associative array
map中一个就是一个pair类型对象(first-key,second-value)
map提供下标操作 map[key] 返回value值,如果key不存在则新建一个key并将其初始化。
set关键字的简单集合,没有值value

2018.11.1

对于链表结点删除以及更改问题:
要把头结点进行复制保存,应用于返回。
复制的结点进行删除及更改的操作,这样不会影响原始的链表结点。
新建一个空的结点 ListNode node(0)
以及如何去定义结点指针
this node can't use '->next' but use '.next'

  • 链表的删除存在很大问题
  • 就是如何在修改这个结点同时保留链表的头结点,最后进行返回。这个一直不是很明白!!!

2018.10.2

逻辑logistic regression 中
梯度上升法(下降法)采用的权重更新公式的数学表达式和编程过程中的表达式之间的联系理解不是很好。或则就是没有理解这个编程表达式的具体含义

宏替换不占用程序运行时间:
宏是在预编译期间进行的,将代码中的指定字符转换,转换结束后,再进行编译,所以不占用程序运行时间

2018.10.3

vector<int> 进行(beigin(),end())返回的是一个iterator,这个迭代器该如何使用?
能否直接进行排序,按下标值选取其中的元素
std::sort() 可以直接对vector进行排序。这个算是标准库函数的调用

2018.10.4

关于链表的知识点,一个最基本的知识点一定要烂熟于心
合并两个有序链表
这个基本的知识点,可以应用于很多的程序当中子程序来实现链表的各种功能。
divide and conquer 一般与 recursion 相结合使用
注意分而治之的使用情况及条件(连续的大问题转换成小问题解决,再进行bottom-to-up 递归)
如果能用栈来解决的问题,那么递归也可以实现
递归在本质上就是一个栈结构。
但是递归容易导致调用函数栈的溢出,其代码的鲁棒性不是很好。对于一些层级很深的函数慎用递归来实现。
双向链表的要求不是很高,基本的数据结构也还是要理解记忆一下


2018.10.5

*和&的知识点
| 符号 | * |& |
| --- | --- | --- |
| 定义语句 | 定义一个变量指针 | 定义一个变量引用(别名) |
| 非定义语句 | 取指针变量指向的内容 | 取这个变量的地址 |
专题

1.基本知识点

  • 度:树的度是树内各结点度的最大值
  • 深度(高度):结点的最大层次(level)

  • 二叉树:
    满二叉树,所有分支结点都有左子树和右子树,所有叶子结点都在同一层上面
    完全二叉树,按层序编号,如果编号为i和满二叉树编号为i的结点在同一个位置

2.二叉树的性质
这个在面试基础题中经常考查到

  • 二叉树\(i\)层上至多有\(2^{i-1}\)个结点

  • 深度为\(k\)的二叉树最多有\(2^{k}-1\)个结点

  • 对于任意一棵二叉树,终端结点个数\(n_{0}\)度为2的结点个数\(n_{2}\)\(n_{0}=n_{2}+1\)

  • 具有n个结点的完全二叉树的深度为\([log_{2}n]+1\)

  • n个结点的完全二叉树,结点按层进行编号,对于任一结点 i 结点
    如果i=1,其为根结点无双亲。如果i>1,其双亲结点为[i/2]
    如果2i>n,结点i无左孩子,否则其左孩子是结点2i
    如果2i+1>n,则结点i无右孩子;否则其右孩子结点是2i+1.

3.二叉树的遍历

三种遍历6种方法 都要非常熟悉

在树的递归中,注意如何返回 可以直接返回递归表达式。

November 6, 2018 

一个无返回的函数,其修改的结果是什么类型
迭代器能否使用for循环
可以使用循环

std::vector<int> ints {1,2,4,8};
for (auto it = ints.cbegin(); it != ints.cend(); it++)
  • 函数的调用和定义都可以嵌套使用
  • malloc是函数
  • 各种运算符的优先顺序:
    赋值运算符<逻辑运算符<关系运算符<算术运算符
  • 系统函数符可以作为自定义标识符

November 7, 2018 

在二叉树中函数利用递归recursion深度优先遍历DFS 的优缺点分析
| | recursion |DFS |
|---|----|----|
|优点| ||
|缺点| | |

今天见到的最漂亮的代码,可以记下来

// 实现二叉树转换成右二叉树
// 有点和树的旋转变换类似
class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode*now = root;
        while (now)
        {
            if(now->left)
            {
                //Find current node's prenode that links to current node's right subtree
                TreeNode* pre = now->left;
                while(pre->right)
                {
                    pre = pre->right;
                }
                pre->right = now->right;
                //Use current node's left subtree to replace its right subtree(original right 
                //subtree is already linked by current node's prenode
                now->right = now->left;
                now->left = NULL;
            }
            now = now->right;
        }
    }
};

fork()函数
1.fork()函数会把它所在语句以后的语句复制到一个子进程里,单独执行。
2.如果printf函数最后没有"\n",则输出缓冲区不会被立即清空,而fork函数会把输出缓冲区里的内容也都复制到子进程里。
所以,父进程和子进程各输出2个Hello,共4个。
如果第一个printf("Hello");写成printf("Hello\n");,则只会输出3个Hello,父进程2个,子进程1个。

类型 位数(bit) 字节(2字节=1字)
char 8 1
short 16 2
int 16 2
long 32 4
long long 64 8
float 32 4
double 64 8

malloc 和 new
都是从堆上分配内存
malloc 删除内存使用free
new新建的内存删除 需要使用 delete

November 8, 2018 

程序运行的必要条件:
头文件的路径(utilities)这是个公用的工程文件夹 以及头文件的获取
文件路径(\path windows-vs 以及 /path -xcode)

在程序中注意,return语句和要print内容的顺序
如果print语句在return语句后运行,则print的内容无法输出--这是在解释性语言python运行结果
编译性语言有待检测

November 10, 2018 

还是关于树的知识点
关于树的深度遍历的理解
深度遍历在程序中的使用!!!

November 11, 2018 

下午看一看深度优先遍历
和分而治之在深度优先遍历中的应用
问题可以想明白,但是就是不会做。

November 12, 2018 

C++循环的应用
for(int i=0;i<s.size();i++)
要替换为
for(auto i:s) 更加的简洁明了

树的遍历问题:知识盲区
树应该是从下面叶子结点向上根结点进行修改
怎么从下往上
这个就要实时的进行返回。

November 13, 2018 

在非二叉树中,对于孩子结点集,通常是vector
需要遍历循环来讲结点集进行push_back()
和广度优先遍历结合实现非二叉树的层序遍历
两个栈来实现队列
主要是两个栈的来回pop(),push()实现队列性质
也可以用一个栈来实现,时间复杂度要高点?
构造函数(constructor):
每个类都分别定义它的对象被初始化的方式,类通过一个或几个特殊的成员函数来控制其对象的初始化过程,这些函数叫做构造函数

构造函数的任务是初始化类对象的数据成员,无论何时,只要类的对象被创建,就会执行构造函数。
构造函数没有返回类型

x++只能作为右值,++x可为右值,可为左值

x++,将x自增1,返回x原来的值,这个值是一个临时值,不能向其赋值。

November 14, 2018 

template
template <typename T>
模版的定义以关键字 template 开始,后面跟着一个模板参数列表 template parameter list
注意:在模版定义中,模版参数列表不能为空。
T是一个模版实参,一般编译器complier会根据调用函数实参来初始化模版实参

编译器生成改变模版实参生成的版本一般称为模版的实例 instantiation

头文件中的:
#pragma once
防止宏定义被编译器多次编译

#ifndef ...
#define ...

#endif
是一样的效果

当然也可以一起使用,先使用
# pragma once
再使用传统的 if语句来实现(这个一般用的比较多,也是程序员经常用的可以实现跨平台的使用)

一个几乎不可能用到的知识点,switch case 语句
如果case语句后面有没有break语句结束,有则跳出switch语句,没有则执行下一个case语句。

sizeof new delete 都不是函数,都是关键字keywords
类的静态成员?

November 15, 2018 

模板 template:C++范型编程的基础
顾名思义,其是创建类或者函数的公式

ping: packet internet groper
英特网包探索器

November 16, 2018 

malloc()函数如何分配新空间地址
当函数是一个无返回函数的时候,如果需要进行递归需要返回值的时候 return;
散列函数的实现,hashtable 是一个非常重要的数据结构。
处理hash冲突方法有:
开放定址法(线性探测法、线性补偿探测法、随机探测法),拉链法,建立公共溢出区,再散列法
稀疏矩阵压缩:

三元组表示稀疏矩阵可大大节省空间,但是当涉及到矩阵运算时,要大量移动元素。
十字链表表示法可以避免大量移动元素。

November 17, 2018 

python

heapq:
heap queue algorithm =priority queue
堆列和优先队列

C++

两个知识点
一个是关联容器
当我们从map中提取一个元素的时候,我们得到的是一个pair类型的对象
pair是一个生成特性类型的模版
priority_queue 优先队列
priority_queue
explaination:A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
专门是为了找到最大k个元素而实现的数据结构
其插入的元素不再队列尾部,而是根据特定的优先级排列。
也就是元素插入即排序

November 19, 2018 

Include<cassert>

assert 又叫断言,假设
assert 是一个宏,不是函数,bool类型

前置条件断言:代码执行之前必须具备的特性
后置条件断言:代码执行之后必须具备的特性
前后不变断言:代码执行前后不能变化的特性

对于递归的实现,能用自底向上的方法,就用自底向上递归的方法。

指针:
char *p1="123"
指针指向常量字符串,在常量区不能对其修改
在常量区,并没有在拷贝到栈中,所以不能修改

char p[]="hello world";和char *p="hello world"的区别;前者存放在栈里,后者存放在静态区
字符串初始化数组时要记得将数组长度加1,因为字符串默认的末尾有一个‘\0’

数组作为函数参数时,当作普通指针来记

static 全局静态变量,其值作用于全局作用域

November 20, 2018 

哈希表,关联容器
map,set 什么时候使用,如何使用
不是很熟悉
bucket 桶变量,不是很了解
下面这段代码包含的知识点非常多
1.哈希的元素的遍历
2.map可以进行逆序输出
3.mao的默认排序,是按第一个元素进行排序

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> m;
        string result;
        map<int,vector<char>> m_freq;
        for(auto c:s){//1
            m[c]++;
        }
        for(auto x:m){
            m_freq[x.second].push_back(x.first);//3
        }
        for(auto it=m_freq.rbegin();it!=m_freq.rend();it++){ // 2 rbegin() 进行逆序输出
            // map有的操作,但是unordered_map没有
            for(auto c:it->second)// 遍历vector中所有的字符串
                result.append(it->first,c);
        }
        return result;  
    }
};

November 21, 2018 

数据结构,不管什么时候能用 vector就用vector

字符串的问题,记得使用长数组来实现哈希表的功能。

遇到字符串的问题就歇菜,字符串还是需要加强

November 22, 2018 

python中math.log()不能对矩阵直接操作
可以直接使用 np.log()

November 23, 2018 

很重要的一个知识点:
istringstream ss;
while(ss>string)
字符串流,等同于cin

如果直接对string直接使用for(it=string.begin())这样得到的是 char

哈希表和二叉排序树的重点考察都是数据结构而不是算法

快速排序的c++代码要尽快理解
结合java版本的也写个c++版本的快排

November 24, 2018 

binary search :
能使用 lo+(hi-lo)/2 就尽量使用,不要使用
(lo+hi)/2 这个很容易溢出。

找到旋转数组中最小值的下标,这个很关键。
二分查找中,lo及hi的赋值很重要
以及判断条件的选取都是关乎整体代码运行的