算法部分

#include <cstring>
#include <iostream>
#include <string>

// 计算最长公共前后缀
void prefix_table(char pattern[], int prefix[], int n) {
     prefix[0] = 0;
     int len = 0;
     int i = 1;
     while (i < n) {
         if (pattern[i] == pattern[len]) {
             len++;
             prefix[i] = len;
             i++;
         } else {
             if (len > 0) {
                 len = prefix[len - 1];
             } else {
                 prefix[i] = len;
                 i++;
             }
         }
     }
}

// 计算next数组
void move_prefix_table(int table[], int n) {
    for (int i = n - 1; i > 0; --i) {
        table[i] = table[i - 1];
    }
    table[0] = -1;
}

// kmp算法
void kmp_search(char text[], char pattern[]) {
    int n = strlen(pattern);
    int m = strlen(text);
    int *prefix = new int[n];
 
    prefix_table(pattern, prefix, n);
    move_prefix_table(prefix, n);
  
    int i = 0;
    int j = 0;
    while (i < m) {
        if (j == n - 1 && text[i] == pattern[j]) {
            std::cout << "Found pattern at " << i - j << '\n';
            j = prefix[j];
        }
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = prefix[j];
            if (j == -1) {
                i++;
                j++;
            }
        }
    }
 
    delete[] prefix;
}

int main(void) {

    char pattern[] = "ABABCABAA";
 
    char text[] = "ABABABCABAABABABAAB";
    kmp_search(text, pattern);
    return 0;
}

class Solution {
public:
    /**
     * @param circles: The value of 6 points on n rings
     * @return: Whether there are two same circles
     */
    bool samecircle(Node head) {
        // write your code here
        Node ptr2 = head;
        Node ptr2 = head;
        while (p1 != nullptr && p2 != nullptr)
        {
            ptr1 = p1.next;
            ptr2 = p2.next.next;
            if (ptr1 == ptr2) // 结点相遇
                return true;
        }
        return false;
    }
};

class Solution {
public:
    /**
     * @param circles: The value of 6 points on n rings
     * @return: Whether there are two same circles
     */
    Node find_node(Node head)
    {
        // write your code here
        Node ptr1 = head;
        Node ptr2 = head;
        Node ptr3 = nullptr;
        Node ptr4 = nullptr;
        while (p1 != nullptr && p2 != nullptr)
        {
            ptr1 = p1.next;
            ptr2 = p2.next.next;
            if (ptr1 == ptr2) // 结点相遇
                ptr3 = head;
            	ptr4 = ptr1;
            	break;
        }
        if (ptr3 != nullptr && != ptr4 != nullptr)
        {
            while(ptr3 != ptr4)
            {
                ptr3 = ptr3.next;
                ptr4 = ptr4.next;
            }
            return ptr4;
        }
        return nullptr;
    }
};

template<class T>
int binary_search(vector<T> &A, T K)
{
    int low = 0;
    int high = A.size() - 1;
    
    while( low < high )
    {
        int mid = (low + high)/2;

        if( A[mid]  < K )
            low = mid + 1;
        else if( A[mid] > k )
            high = mid - 1;
        else
            return mid;
    }  

    return -1;      /*返回-1表示数组不存在K的值*/
 }

private Map<String, Boolean> status = new HashMap<String, Boolean>();
    private Queue<String> queue = new LinkedList<String>();
    public void BFSSearch(String startPoint) {
        //1.把起始点放入queue；
        queue.add(startPoint);
        status.put(startPoint, false);
        bfsLoop();
    }
    
    private void bfsLoop() {
        while(!queue.isEmpty()) {
            //  1) 从queue中取出队列头的点；更新状态为已经遍历。
            String currentQueueHeader = queue.poll(); //出队
            status.put(currentQueueHeader, true);
            System.out.println(currentQueueHeader);
            //  2) 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入queue中。
            List<String> neighborPoints = graph.get(currentQueueHeader);
            for (String poinit : neighborPoints) {
                if (!status.getOrDefault(poinit, false)) { //未被遍历
                    if (queue.contains(poinit)) continue;
                    queue.add(poinit);
                    status.put(poinit, false);
                }
            }
        }
    }

/**
 * DFS核心伪代码
 * 前置条件是visit数组全部设置成false
 * @param n 当前开始搜索的节点
 * @param d 当前到达的深度，也即是路径长度
 * @return 是否有解
 */
bool DFS(Node n, int d){
    if (isEnd(n, d)){//路径长度为返回true，表示此次搜索有解
        return true;
    }
 
    for (Node nextNode in n){//遍历跟节点n相邻的节点nextNode，
        if (!visit[nextNode]){//未访问过的节点才能继续搜索
 
            //例如搜索到V1了，那么V1要设置成已访问
            visit[nextNode] = true;
 
            //接下来要从V1开始继续访问了，路径长度当然要加
 
            if (DFS(nextNode, d+1)){//如果搜索出有解
                //例如到了V6，找到解了，你必须一层一层递归的告诉上层已经找到解
                return true;
            }
 
            //重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中
            visit[nextNode] = false;
 
        }
        //到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。
    }
    return false;//本次搜索无解
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null||obstacleGrid.length==0){
            return 0;
        }
        int [] [] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for(int i=0;i<obstacleGrid.length;i++){
            for(int j=0;j<obstacleGrid[i].length;j++){
                if(obstacleGrid[i][j]==1){//有障碍
                    dp[i][j]=0;
                    continue;
                }else{
                    if(i == 0 && j == 0) dp[i][j]=1;//没有障碍起点
                    else if(i==0) dp[i][j]=dp[i][j-1];//在第一行,上一题在没有障碍情况下默认是1,但是有障碍就取决于该行前面是否有障碍了
                    else if(j==0) dp[i][j]=dp[i-1][j];//第一列,没有障碍默认是1,有障碍就取决于该列前面是否有障碍了
                    else{
                         dp[i][j]=dp[i-1][j]+dp[i][j-1];
                    }
                }
                
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

1. 给定长度为N的序列或字符串，要求划分成若干段
   - 段数不限，或指定K段
   - 每一段满足一定的性质
2. 做法
   - 类似于序列型动态规划，但是通常要加上段数信息
   - 一般用`f[i][j]`记录前i个元素（元素0~i-1）分成 j 段的性质，如最小代价