/acm

Data structure and Algorithm

Primary LanguageC++

1. ACM Basic

1.1. Reference

  1. 浙大DSA

1.2. List

1.2.1. 数组存储线性表

struct LNode{
    int Data[MAXSIZE];
    int Last;
};
  • 建立空表 MakeEmpty
  • 查找元素 Find
  • 插入元素 Insert
  • 删除元素 Delete

1.2.2. 链式存储线性表

1.2.2.1. 链表数据结构(c)

typedef struct LNode *PtrToLNode;
struct LNode {
    int Data;
    PtrToLNode Next;
}

1.2.2.2. 节点(python)

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

1.2.2.3. 从数组中创建单向链表(lc83)

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

1.2.2.4. 从数组中创建单项环链表(lc141)

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

1.2.2.5. 遍历链表的所有节点并打印

def transverse(node):
 node_list = []
 while node != None:
     node_list.append(node.val)
     node = node.next
 print(node_list)

1.3. Stack

Stack: 一种输入输出受限的线性表 FILO(First In Last Out)

1.3.1. 做stack相关leetcode 题目的一个心得

一定要先在草稿纸上画出具体的操作,想好每一个该怎么做。然后写代码就好写了。

1.3.2. c++ 中stack的一些常用操作

stack.push(val) stack.pop() stack.empty()

//---------------------------------------
// Stack structure,
//   |        |
//   |        |
//   |________|
//   |___4____|<--- Top
//   |___3____|
//   |___2____|
//   |___1____|
//--------------------------------------

1.3.3. 用数组实现stack

stack_array.c

typedef int ElementType;
typedef int Position;
struct StackNode {
        ElementType *Data; /* 存储元素的数组 */
        Position Top;      /* 栈顶指针 */
        int MaxSize;       /* 堆栈最大容量 */
};
typedef struct StackNode *Stack;

1.3.4. 用链表实现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);

1.3.5. 用队列实现stack(lc225)

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      

1.4. Queue

push() 压入队列
pop() 弹出队列 查看队首元素 front()

1.4.1. 用stack 实现queue(lc232)

两个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();
    }
};

1.5. Tree

1.5.1. 二叉树

  • 树的建立
  • 插入节点
  • 删除节点
  • 遍历节点
    • 二叉树的前序遍历 [lc144]
    • 二叉树的中序遍历 [lc94]
    • 二叉树的后序遍历 [lc145]
    • 二叉树的层次遍历,自顶向下 [lc102]
    • 二叉树的层次遍历,自底向上 [lc107]
    • 从前序和中序遍历序列构造树 [lc105]
    • 从后序和中序遍历序列构造树 [lc106]
    • 对称树 [lc101]
    • 相同树 [lc100]

1.5.2. 平衡二叉树

1.5.3. 堆 heap

堆: 是优先队列(Priority Queue),特殊的队列。不是先入先出,而是按照元素的优先权(关键字)大小取出元素。

堆: 可以用优先队列的完全二叉树表示

最大堆(MaxHeap),最小堆(MinHeap)

1.5.3.1. 堆的抽象数据类型描述

  • MaxHeap Create(int MaxSize) 创建一个空的最大堆
  • IsFull(MaxHeap H) 最大堆是否已满
  • IsEmpty(MaxHeap H) 最大堆是否已空
  • Insert(MaxHeap H, ElementType item) 插入元素
  • Delete(MaxHeap H, ElementType item) 删除元素

BFS

#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 算法

Dijkstra 思路是维护一个集合 s ,集合内的点是已经确定最短路的点,可以视为一个大整体,每次操作找出距离这个集合最近的点加入集合中,并确定它的最短路为它的上家的最短路+该边权值,存在 dis 中

1.6. Dynamic Programming

动态规划可以认为是剪枝的递归算法

1.6.1. longest_common_sequence 最长公共子序列问题

问题描述

n = 6
m = 6
s = "abcdec"
t = "becdce"
最长公共子子序列为: bcde

1.6.2. sum_equal_n 从一堆数字中,选择几个,使得能够拼出和为sum的个数。

求和等于A值问题

从一堆数字中选择几个,使得能够拼出和为SUM的数
arr = [3,34,4,12,5,2]
Sum = 9
选择arr[i]

1.6.3. interval_sum_max 从一堆数字中,任选几个不相邻的数字,使得求和最大。

相邻数字求和最大问题描述

一堆数字中,任选几个不能相邻的数字,使得求和最大。
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)

1.6.4. package_problem 背包问题.

背包问题描述

n = 4
w = 2, 1, 3, 2
v = 3, 2, 4, 2
W = 5
n个包裹,每个包裹的重量为w[i],价值为v[i],选择几个包裹,使得总重量为W,价值总和最高的方案

1.7. leetcode

数据结构

数组 链表 二叉树 二叉搜索树 二叉平衡树 堆 栈 图 hash table

算法

各种排序算法 动态规划 贪心算法 递归算法

1.8. python 函数与 c++ 函数功能对应

从键盘输入一行以空格为分割符的数字,传给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);
} 

1.8.1. list后加入元素a

Python

list_.append(a)

c++

list_.push_back(a)

1.8.2. list子串[a:b)

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());

c++ 数据结构常用api

共享内存指针

#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 与int的互相转换

  1. string to int stoi(a string)

  2. int to string to_string(a int )

  3. 判断一个string 是否是数字 比如 "9","-10","+" string s; s[0] >= '0' && s[0] <= '9' || s[0] == '-' && s.size() > 1

queue,stack

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();