- 1. ACM Basic
struct LNode{
int Data[MAXSIZE];
int Last;
};- 建立空表 MakeEmpty
- 查找元素 Find
- 插入元素 Insert
- 删除元素 Delete
typedef struct LNode *PtrToLNode;
struct LNode {
int Data;
PtrToLNode Next;
}class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def create_linklist(list_elems):
node = ListNode(0)
node_ret = node
for i in list_elems:
tmp = ListNode(i)
node.next = tmp
node = node.next
return node_ret.next
def create_cycle_linklist(list_elems,pos):
node = ListNode(0)
node_ret = node
# 先构建链表从头到尾
for i in list_elems:
tmp = ListNode(i)
node.next = tmp
node = node.next
# 再来连接环的节点
start = node_ret.next
if pos != -1:
for i in range(0,len(list_elems)):
node_ret = node_ret.next
if i == pos:
break
node.next = node_ret
return start
def transverse(node):
node_list = []
while node != None:
node_list.append(node.val)
node = node.next
print(node_list)
Stack： 一种输入输出受限的线性表 FILO(First In Last Out)
一定要先在草稿纸上画出具体的操作，想好每一个该怎么做。然后写代码就好写了。
stack.push(val) stack.pop() stack.empty()
//---------------------------------------
// Stack structure,
// | |
// | |
// |________|
// |___4____|<--- Top
// |___3____|
// |___2____|
// |___1____|
//--------------------------------------stack_array.c
typedef int ElementType;
typedef int Position;
struct StackNode {
ElementType *Data; /* 存储元素的数组 */
Position Top; /* 栈顶指针 */
int MaxSize; /* 堆栈最大容量 */
};
typedef struct StackNode *Stack;stack_linked.c
typedef int ElementType;
typedef struct StackNode *PtrToStackNode;
struct StackNode {
ElementType Data;
PtrToStackNode Next; //Point to Next Node
};
typedef PtrToStackNode Stack;用链表实现的Stack，Push元素时，即插入时，插入到链表的头。删除时，删除链表的头元素
- 插入操作
//------------------------------
//链表头节点插入元素
//------------------------------
//1. 先建立一个插入元素的临时节点tmpCell
//2. 该临时节点插入到链表的末尾
// ____________ ___________ ___________
// | s | next |----> | 0 | next |----> | 1 | next |
// |___|________| |___|_______| |___|_______|
// S -> [S->Next]
// [Insert] tmpCell
// S -> tmpCell -> [S->Next]
PtrToStackNode tmpCell = (PtrToStackNode) malloc(sizeof(struct StackNode));
tmpCell->Data = X;
tmpCell->Next = S->Next;
S->Next = tmpCell;
- 删除操作
//------------------------------
//链表头节点删除元素
//------------------------------
// ____________ ___________ ___________
// | s | next |----> | 0 | next |----> | 1 | next |
// |___|________| |___|_______| |___|_______|
// S -> [S->Next] -> S->Next->Next
// Delete
// S -> S->Next->Next
PtrToStackNode tmpCell = S->Next;
ElementType tmpData = tmpCell->Data;
S->Next = tmpCell->Next;
free(tmpCell);
class MyStack(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.topindex = -1
self.element = []
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: None
"""
self.topindex += 1
self.element.append(x)
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if self.topindex != -1:
elem = self.element.pop()
self.topindex -= 1
return elem
else:
return None
def top(self):
"""
Get the top element.
:rtype: int
"""
if self.topindex == -1:
return None
else:
return self.element[self.topindex]
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
if self.topindex == -1:
return True
else:
return False
push() 压入队列
pop() 弹出队列
查看队首元素 front()
两个stack实现queue. stk1用于push操作，stk2用于pop操作。
#include <stack>
#include <iostream>
class MyQueue {
private:
std::stack<int> stk1;
std::stack<int> stk2;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stk1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int front = peek();
stk2.pop();
return front;
}
/** Get the front element. */
int peek() {
int value;
while(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
value = stk2.top();
return value;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk1.empty() && stk2.empty();
}
};
- 树的建立
- 插入节点
- 删除节点
- 遍历节点
- 二叉树的前序遍历 [lc144]
- 二叉树的中序遍历 [lc94]
- 二叉树的后序遍历 [lc145]
- 二叉树的层次遍历,自顶向下 [lc102]
- 二叉树的层次遍历,自底向上 [lc107]
- 从前序和中序遍历序列构造树 [lc105]
- 从后序和中序遍历序列构造树 [lc106]
- 对称树 [lc101]
- 相同树 [lc100]
堆: 是优先队列(Priority Queue),特殊的队列。不是先入先出，而是按照元素的优先权（关键字）大小取出元素。
堆: 可以用优先队列的完全二叉树表示
最大堆(MaxHeap)，最小堆(MinHeap)
- MaxHeap Create(int MaxSize) 创建一个空的最大堆
- IsFull(MaxHeap H) 最大堆是否已满
- IsEmpty(MaxHeap H) 最大堆是否已空
- Insert(MaxHeap H, ElementType item) 插入元素
- Delete(MaxHeap H, ElementType item) 删除元素
#include <queue>
#include <vector>
#include <iostream>
#include <memory> //shared_ptr, make_shared
using namespace std;
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
bx = grid.size();
by = grid[0].size();
queue<shared_ptr<Node>> que;
if(grid[0][0] || grid[bx-1][by-1]) return -1;
que.push(make_shared<Node>(0,0,1));
while(que.size()){
auto now = que.front();
que.pop();
if(now->x == bx-1 && now->y == by-1) return now->step;
for(int i = 0;i < 8; ++i){
int nx = now->x + dir[i][0];
int ny = now->y + dir[i][1];
if(nx < 0 || nx >= bx || ny < 0 || ny >= by || grid[nx][ny])
continue;
que.push(make_shared<Node>(nx, ny, now->step+1));
grid[nx][ny] = 1;
}
}
return -1;
}
private:
struct Node{
int x, y;
int step;
Node(int _x, int _y, int _s):x(_x),y(_y),step(_s){}
};
int bx, by;
int dir[8][2] = {
{0,1}, // 下
{0,-1}, // 上
{1,1}, // 右下角
{1,0}, // 右
{1,-1}, // 右上角
{-1,0}, // 左
{-1,-1},// 左上角
{-1,1} // 左下角
};
};
Dijkstra 思路是维护一个集合 s ，集合内的点是已经确定最短路的点，可以视为一个大整体，每次操作找出距离这个集合最近的点加入集合中，并确定它的最短路为它的上家的最短路+该边权值，存在 dis 中
动态规划可以认为是剪枝的递归算法
问题描述
n = 6
m = 6
s = "abcdec"
t = "becdce"
最长公共子子序列为: bcde求和等于A值问题
从一堆数字中选择几个，使得能够拼出和为SUM的数
arr = [3,34,4,12,5,2]
Sum = 9
选择arr[i]相邻数字求和最大问题描述
一堆数字中，任选几个不能相邻的数字，使得求和最大。
arr = [1,2,4,1,7,8,3]
求 max(Sum(arr[i])),i不相邻动态规划与递归时间比较
$cd step1/2.3_dynamic_programming
$python interval_sum_max.py
('recursive time:', 0.32363200187683105)
31
('dynamic time:', 0.0053958892822265625)
31.0
('times', 59.97750972074938)背包问题描述
n = 4
w = 2, 1, 3, 2
v = 3, 2, 4, 2
W = 5
n个包裹，每个包裹的重量为w[i],价值为v[i],选择几个包裹，使得总重量为W，价值总和最高的方案数组 链表 二叉树 二叉搜索树 二叉平衡树 堆 栈 图 hash table
各种排序算法 动态规划 贪心算法 递归算法
从键盘输入一行以空格为分割符的数字，传给arr_数组. Python
arr_ = map(int,input().split())
arr_list = []
for i in arr_:
arr_list.append(i)C++
vector<int> arr_list;
string str_;
int n;
getline(cin,str_);
stringstream ss(str_);
while(ss>>n){
arr_list.push_back(n);
}
Python
list_.append(a)c++
list_.push_back(a)Python
list_[a:b]c++
vector<int> list_;
vector<int> list_sub(list_.begin()+a,list_.begin()+b);Python
max(list_)
min(list_)c++
*max_element(vector_.begin(),vector_.end());
*min_element(vector_.begin(),vector_.end());共享内存指针
＃include<memory>
queue<shared_ptr<Node>> que;
que.push(make_shared<Node>(0,0,1));
struct Node{
int x,y;
int step;
Node(int _x,int _y,int _s):x(_x),y(_y),step(_s){
}
}
-
string to int stoi(a string)
-
int to string to_string(a int )
-
判断一个string 是否是数字 比如 "9","-10","+" string s; s[0] >= '0' && s[0] <= '9' || s[0] == '-' && s.size() > 1
queue deque que; que.push_back() que.pop_back() que.push_front() que.pop_front()
stack stack stk; stk.push(int); stk.pop(); stk.top();