数据结构与算法（中）

// 树的深度优先搜索
function Node(value) {
    this.value = value
    this.childs = []
}
var a = new Node('A')
var b = new Node('B')
var c = new Node('C')
var d = new Node('D')
var e = new Node('E')
var f = new Node('F')
a.childs.push(b)
a.childs.push(c)
a.childs.push(d)
c.childs.push(e)
c.childs.push(f)
function deepSearch(root, target) {
    if (root == null) return false
    if (root.value == target) return true
    var result = 0
    for (var i = 0; i < root.childs.length; i++) {
        result |= deepSearch(root.childs[i], target)
    }
    return result ? true : false
}
console.log(deepSearch(a, 'C')) //true
console.log(deepSearch(a, 'n')) //false
<!--树的深度遍历-->
function deepSearchBianli(root) {
    if (root == null) return
    console.log(root.value)
    for (var i = 0; i < root.childs.length; i++) {
        deepSearchBianli(root.childs[i])
    }
}
deepSearchBianli(a) // A B C E F D 深搜
console.log(a)
输出：
Node {
  value: 'A',
  childs:
   [ Node { value: 'B', childs: [] },
     Node { value: 'C', childs: [Array] },
     Node { value: 'D', childs: [] } ] }

function Node(value) {
    this.value = value
    this.childs = []
}
var a = new Node('A')
var b = new Node('B')
var c = new Node('C')
var d = new Node('D')
var e = new Node('E')
var f = new Node('F')
a.childs.push(b)
a.childs.push(c)
a.childs.push(d)
c.childs.push(e)
c.childs.push(f)
function bfc(roots, target) {
    if (roots == null || roots.length == 0) return false
    var childs = []
    for (var i = 0; i < roots.length; i++) {
        if (roots[i].value == target) {
            return true
        } else {
            childs = childs.concat(roots[i].childs)
        }
    }
    return bfc(childs, target)
}
console.log(bfc([a], 'C')) //true
console.log(bfc([a], 'n')) //false
// 实现广度优先遍历
function bfcBianli(roots) {
    if (roots == null) return
    console.log(roots.value)
    var childs = []
    for (var i = 0; i < roots.childs.length; i++) {
        console.log(roots.childs[i].value)
        childs = childs.concat(roots.childs[i].childs)
    }
    for (var j = 0; j < childs.length; j++) {
        console.log(childs[j].value)
    }
}
bfcBianli(a)// A B C D E F

function Node(value) {
    this.value = value
    this.neighbor = []
}
var a = new Node('A')
var b = new Node('B')
var c = new Node('C')
var d = new Node('D')
var e = new Node('E')
a.neighbor.push(b)
a.neighbor.push(c)
b.neighbor.push(a)
b.neighbor.push(c)
b.neighbor.push(d)
c.neighbor.push(a)
c.neighbor.push(b)
c.neighbor.push(d)
d.neighbor.push(b)
d.neighbor.push(c)
d.neighbor.push(e)
e.neighbor.push(d)
// 图的深度优先搜索
function deepSearch(node, target, path) {
    if (node == null) return false
    <!--比较新插入的点是否比较过-->
    if (path.indexOf(node) > -1) return false
    if (node.value == target) return true
    path.push(node)
    var result = false
    for (var i = 0; i < node.neighbor.length; i++) {
        result |= deepSearch(node.neighbor[i], target, path)
    }
    return result ? true : false
}
console.log(deepSearch(a, 'E', []))//true
console.log(deepSearch(a, 'n', []))//false

function Node(value) {
    this.value = value
    this.neighbor = []
}
var a = new Node('A')
var b = new Node('B')
var c = new Node('C')
var d = new Node('D')
var e = new Node('E')
a.neighbor.push(b)
a.neighbor.push(c)
b.neighbor.push(a)
b.neighbor.push(c)
b.neighbor.push(d)
c.neighbor.push(a)
c.neighbor.push(b)
c.neighbor.push(d)
d.neighbor.push(b)
d.neighbor.push(c)
d.neighbor.push(e)
e.neighbor.push(d)
// 图的广度优先搜索
function bfs(nodes, target, path) {
    if (nodes == null || nodes.length == 0) return false
    var nextNodes = []
    for (var i = 0; i < nodes.length; i++) {
        <!--比较新插入的点是否比较过-->
        if (path.indexOf(nodes[i]) > -1) continue;
        path.push(nodes[i])
        if (nodes[i].value == target) return true
        else nextNodes = nextNodes.concat(nodes[i].neighbor)
    }
    return bfs(nextNodes, target, path)
}
console.log(bfs([a], 'A', []))//true
console.log(bfs([a], 'n', []))//false

// 动态规划，笔试遇到动态规划是后面的大题
// 0 ， 1 ， 1 ， 2 ， 3 ， 5 ， 8 ， 13...
// 给出第n 位，问第n位值是多少？
function fibo1(n) {
    if (n <= 0) return -1
    if (n == 1) return 0
    if (n == 2) return 1
    let first = 0,
        seconds = 1,
        third;
    for (let i = 3; i <= n; i++) {
        third = first + seconds
        first = seconds
        seconds = third
    }
    return third
}
console.log(fibo1(8))//13
// f(n) = f(n - 1) + f(n -2)
function fibo2(n) {
    if (n <= 0) return -1
    if (n == 1) return 0
    if (n == 2) return 1
    return fibo2(n - 1) + fibo2(n - 2)
}
console.log(fibo2(8))//13

. . . 即： f(n) = f(n - 1) + f(n - 2)
function jump(n) {
    if (n <= 0) return -1
    if (n == 1) return 1
    if (n == 2) return 2
    return jump(n - 1) + jump(n - 2)
}
console.log(jump(5)) //8
// 1 2 2
// 2 2 1
// 2 1 2
// 1 1 1 1 1
// 2 1 1 1
// 1 2 1 1
// 1 1 2 1
// 1 1 1 2 有8种跳法

f(n) = f( n- 1) + f(n -2) + f(n -3) +......+f(2) + f(1) + f(0)
function jump(n) {
    if (n <= 0) return -1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    let result = 0
    for (let i = 1; i < n; i++) {
        result += jump(n - i)
    }
    return result + 1; //加上1代表从0级台阶直接跳上去的场景
}
console.log(jump(5))//16
//  1 1 1 1 1 
//  1 1 1 2
// 1  1 2 1
// 1 2 1 1
// 2 1 1 1
// 1 2 2
// 2 1 2
// 2 2 1
// 1 1 3 
// 3 1 1
// 1 3 1
// 2 3 
// 3 2
// 1 4
// 4 1
// 5
// 有16种跳法

    function insert(arr, index, data) {
      for (let i = arr.length; i >index; i--) {
        arr[i] = arr[i - 1];
      }
      arr[index] = data;
    }

    class Node {
        constructor(key) {
            this.next = null;
            this.key = key;
        }
    }

    class List {
        constructor() {
            this.head = null;
        }
    }

    static createNode(key) {
        return new createNode(key);
    }

    insert(node) {
        // 如果head有指向的节点
        if(this.head){
           node.next = this.head;
        }else {
           node.next = null;
        }
        this.head = node;
    }

    find(key) {
        let node = this.head;
        while(node !== null && node.key !== key){
            node = node.next;
        }
        return node;
    }

    delete(node) {
        // 第一种情况
        if(node === this.head){
            this.head = node.next;
            return;
        }
        // 查找所要删除节点的上一个节点
        let prevNode = this.head;
        while (prevNode.next !== node) {
            prevNode = prevNode.next;
        }
        // 第二种情况
        if(node.next === null) {
            prevNode.next = null;
        }
        // 第三种情况
        if(node.next) {
            prevNode.next = node.next;
        }
    }

class ListNode {
  constructor(key) {
    this.next = null;
    this.key = key;
  }
}
class List {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  static createNode(key) {
    return new ListNode(key);
  }
  // 往头部插入数据
  insert(node) {
    // 如果head后面有指向的节点
    if (this.head) {
      node.next = this.head;
    } else {
      node.next = null;
    }
    this.head = node;
    this.length++;
  }
  find(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }
  delete(node) {
    if (this.length === 0) {
      throw 'node is undefined';
    }
    if (node === this.head) {
      this.head = node.next;
      this.length--;
      return;
    }
    let prevNode = this.head;
    while (prevNode.next !== node) {
      prevNode = prevNode.next;
    }
    if (node.next === null) {
      prevNode.next = null;
    }
    if (node.next) {
      prevNode.next = node.next;
    }
    this.length--;
  }
}

    class ListNode {
        this.prev = null;
        this.next = null;
        this.key = key;
    }

    class List {
        constructor(){
            this.head = null;
        }
    }

    static createNode(key){
        return new ListNode(key);
    }

    insert(node) {
        node.prev = null;
        node.next = this.head;
        if(this.head){
            this.head.prev = node;
        }
        this.head = node;
    }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

    delete(node) {
        const {prev,next} = node;
        delete node.prev;
        delete node.next;
        if(node === this.head){
            this.head = next;
        }
        if(next){
            next.prev = prev;
        }
        if(prev){
            prev.next = next;
        }
    }

    class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }
  static createNode(key) {
    return new ListNode(key);
  }
  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }
  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }
  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;
    if (node === this.head) {
      this.head = next;
    }
    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}

#include <stdio.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
 bool Duplicate(int numbers[],int length,int *duplicate)
{
  int i = 0;
  int swap =0;
  if(numbers == NULL || length<=0)
  {
    return false;
  }
  for (i = 0;i < length; i++)
  {
    if(numbers[i]<0 || numbers[i]>=length)
      return false;
  }
  for(i = 0;i<length ; i++)
  {
    while(numbers[i]!=i)
    {
      if(numbers[i] == numbers[numbers[i]])
      {
        *duplicate = numbers[i];
        return true;
      }
      swap = numbers[i];
      numbers[i] = numbers[numbers[i]];
      numbers[numbers[i]] = swap;
    }
  }
  return none;
}
int main()
{
  int numbers[6] = {1,0,2,3,4,4};
  int length = sizeof(numbers)/4;
  int duplicate = -1;
  bool state = Duplicate(numbers,length, &duplicate);
  printf("%d,%d",state,duplicate);
}

#include <stdio.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int GetCount(int start,int end,int length,const int *numbers)
{
  int i = 0;
  int count = 0;
  for(i = 0;i<length ; i++)
  {
    if(numbers[i]>=start && numbers[i]<=end)
      count ++ ;
  }
  return count;
}
bool Duplicate(const int* numbers,int length,int *deplicate)
{
  int start = 1;
  int end = length - 1;
  int middle;
  int count;
  int i;
  if(numbers ==0 || length == 0)
    return false;
  for(i=0;i<length;i++)
  {
    if(numbers[i]>length-1 || numbers[i]<=0 )
      return false;
  }
  while(1)
  {
    middle = (start + end)/2;
    count = GetCount(start,middle,length,numbers);
    /*
    if(count>(middle - start + 1))
      end = middle;
    else
      start = middle+1;*/
    if(end <= start)
    {
      if(count>1)
      {
        *deplicate = start;
        return true;
      }
      else
        return false;
    }
    if(count>(middle - start + 1))
      end = middle;
    else
      start = middle+1;
  }
}
int main()
{
  int numbers[] = { 3, 2, 1, 4, 4, 5, 6, 7 };
  int length = sizeof(numbers)/4;
  int duplicate = 0;
  bool state = Duplicate(numbers,length, &duplicate);
  printf("%d,%d",state,duplicate);
}

#include <stdio.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool Find(int* matrix, int rows, int columns, int number)
{
  int i = 0;
  int j = columns-1;
  while(i<rows && j>=0)
  {
    if(matrix[i*columns+j] == number)
    {
      return true;
    }
    else if(matrix[i*columns+j]>number)
      j--;
    else
      i++;
  }
  return false;
}
int main()
{
  int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
  int number = 4;
  bool  result = Find((int*)matrix, 4, 4, number);
  printf("%d",result);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool ReplaceSpace(char* str,int length)
{
  char* p1,*p2;
  int originalLength = 0;
  int newLength = 0;
  int spaceNum = 0;
  int i = 0;
  if(str == 0)
    return false;
  while(str[i]!= '\0')
  {
    originalLength ++;
    if(str[i] == ' ')
      spaceNum++;
    i++;
  }
  newLength = originalLength + spaceNum*2 ;
  if(newLength > length)
    return false;
  p1 = &str[originalLength];
  p2 = &str[newLength ];
  //while(p1>=&str[0] && p2>p1)
  while (p2>p1)
  {
    if(*p1 == ' ')
    {
      *p2-- = '0';
      *p2-- = '2';
      *p2-- = '%';
    }
    else
      *p2-- = *p1;
    p1 --;
  }
  return true;
}
int main()
{
  const int length = 100;
    char str[100] = " We are happy ";
  //char *str = " We are happy ";
    bool state = ReplaceSpace(str, length);
  if(state)
  {
    printf("%s",str);
  }
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
bool NodePush(listNode* L,int data)
{
  listNode* p;
  listNode* node = (listNode*)malloc(sizeof(listNode));
  if(!node)return false;
  node->data = data;
  node->next = NULL;
  p = L;
  while(p->next!=NULL)
    p = p->next;
  p->next = node;
  return true;
}
listNode HeadCreat(int data)
{
  listNode head ;
  head.data = data;
  head.next = NULL;
  return head;
}
void PrintListReverse(listNode* head)
{
  int stack[40];
  int i = 0;
  listNode* p = head;
  if(head == NULL)return;
  while(p->next!=NULL)
  {
    stack[i++] = p->data;
    p = p->next;
  }
  stack[i] = p->data;
  for(;i>=0;i--)
  {
    printf("%d ",stack[i]);
  }
  printf("\n");
}
void PrintListReverse1(listNode* head)
{
  if(head == NULL)return;
  if(head->next!=NULL)
    PrintListReverse1(head->next);
  printf("%d ",head->data);
}
int main()
{
  int i;
  listNode node = HeadCreat(4);
  listNode* head = &node;
  for(i=5;i<20;i++)
  {
    NodePush(head ,i);
  }
  PrintListReverse(head);
  PrintListReverse1(head);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct binaryTreeNode
{
  int value;
  struct binaryTreeNode* left;
  struct binaryTreeNode* right;
}binaryTree;
binaryTree* ConstructCore(int *inorderStart,int* inorderEnd,int *preorderStart,int* preorderEnd)
{
  int *p;
  int *preorderEndLeft;
  binaryTree* root = (binaryTree*)malloc(sizeof(binaryTree));
  if(inorderStart == inorderEnd)//结束条件
  {
     if(*inorderEnd != *preorderEnd)return false;
     else
     {
       root->left = NULL;
       root->right = NULL;
       root->value = *preorderStart;
       return root;
     }
  }
  root->value = *preorderStart++;
  for(p = inorderStart;p<=inorderEnd && *p!=root->value;p++);
  if(p>inorderEnd)return false;//中序遍历中没找到根节点
  preorderEndLeft = preorderStart+(p-1-inorderStart);
  root->left = ConstructCore(inorderStart,p-1,preorderStart,preorderEndLeft);
  root->right = ConstructCore(p+1,inorderEnd,preorderEndLeft+1,preorderEnd);
  return root;
}
binaryTree* Construct(int preorder[],int inorder[],int length1,int length2)
{
  if(length1!=length2 || !length1)
    return false;
  return ConstructCore(inorder,inorder+length1-1,preorder,preorder+length2-1);
}
int main()
{
  int preorder[] = {1,2,4,7,3,5,6,8};
  int inorder[] = {4,7,2,1,5,3,8,6};
  binaryTree* root = Construct(preorder,inorder,sizeof(preorder)/sizeof(int),sizeof(inorder)/sizeof(int));
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct binaryTreeNode
{
  int value;
  struct binaryTreeNode* left;
  struct binaryTreeNode* right;
  struct binaryTreeNode* parent;
}binaryTree;
binaryTree* GetNext(binaryTree* node)
{
  binaryTree* parent;
  binaryTree* current;
  if(node==NULL)return NULL;
  if(node->right!=NULL)
  {
    node = node->right;
    while(node->left!=NULL)
      node = node->left;
    return node;
  }
  else if(node->parent!=NULL)
  {
    parent = node->parent;
    current = node;
    while( parent!=NULL && current!=parent->left)//反过来会出BUG，因为parent是NULL是就访问不到left了
    {
      current = parent;
      parent = parent->parent;
    }
    if(parent!=NULL)
      return parent;
    else 
      return NULL;
  }
}
/*构建二叉树*/
binaryTree* ContructBinaryTree(int value)
{
  binaryTree* node = (binaryTree*)malloc(sizeof(binaryTree));
  node->left = NULL;
  node->right = NULL;
  node->parent = NULL;
  node->value = value;
  return node;
}
void ConnectTreeNodes(binaryTree* parent, binaryTree* left, binaryTree* right)
{
    if(parent != NULL)
    {
        parent->left = left;
        parent->right = right;
        if(left != NULL)
            left->parent = parent;
        if(right != NULL)
            right->parent = parent;
    }
}
/*打印二叉树*/
void PrintTree(binaryTree* root)
{
  if(root->left!=NULL)
    PrintTree(root->left);
  printf("%d ",root->value);
  if(root->right!=NULL)
    PrintTree(root->right);
}
int main()
{
  binaryTree *node;
  binaryTree* pNode8 = ContructBinaryTree(8);
  binaryTree* pNode6 = ContructBinaryTree(6);
  binaryTree* pNode10 = ContructBinaryTree(10);
  binaryTree* pNode5 = ContructBinaryTree(5);
  binaryTree* pNode7 = ContructBinaryTree(7);
  binaryTree* pNode9 = ContructBinaryTree(9);
  binaryTree* pNode11 = ContructBinaryTree(11);
  ConnectTreeNodes(pNode8, pNode6, pNode10);
  ConnectTreeNodes(pNode6, pNode5, pNode7);
  ConnectTreeNodes(pNode10, pNode9, pNode11);
  PrintTree(pNode8);
  node = GetNext(pNode5);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode6);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode7);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode8);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode9);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode10);
  if(node)printf("\n%d",node->value);
  node = GetNext(pNode11);
  if(node)printf("\n%d",node->value);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
#define STACK_ININ_SIZE 20//栈初始化长度
#define STACK_INCREMENT 10//每次增长长度
typedef struct Stack
{
    int *base;
    int *top;
    int stackSize;//栈长度
}Stack;
Stack* InitStack()
{
  Stack* stack = (Stack*)malloc(sizeof(Stack));
  stack->base = (int*)malloc(sizeof(int)*STACK_ININ_SIZE);
  if(stack->base)
    stack->stackSize = STACK_ININ_SIZE;
  else
    return false;
  stack->top = stack->base;
  return stack;
}
bool DestroyStack(Stack* stack)
{
  free(stack->top);
  free(stack);
}
bool PopStack(Stack *stack,int elem)
{
  int *a;
  //if((stack->top - stack->base)/sizeof(int)==stack->stackSize)
  if((stack->top - stack->base)==stack->stackSize)//等于的时候说明已经存满 指针相减就是指针指向类型的数目
  {
    a = (int*)realloc(stack->base,(stack->stackSize+STACK_INCREMENT)*sizeof(int));
    if(!a)
      return false;
    else
    {
      stack->base = a;
      stack->top = stack->base + stack->stackSize;
      stack->stackSize += STACK_INCREMENT;
    }
  }
  *stack->top++ = elem;
  return true;
}
int PushStack(Stack* stack)
{
  if(stack->top == stack->base)
    return false;
  return *--stack->top;
}
bool AppendTail(Stack* stack,int elem)
{
  if(PopStack(stack,elem))
    return true;
  else
    return false;
}
int DeleteHead(Stack* stack1)
{
  int head;
  Stack *stack2 = InitStack();
  while(stack1->top>stack1->base)
  {
    PopStack(stack2,PushStack(stack1));
  }
  head = PushStack(stack2);
  while(stack2->top>stack2->base)
  {
    PopStack(stack1,PushStack(stack2));
  }
  DestroyStack(stack2);
  return head;
}
int main()
{
  int i=0;
  int *p;
  Stack *stack1 = InitStack();
  /*构建栈*/
  for(i=1;i<31;i++)
  {
    AppendTail(stack1,i);
  }
  for(i=0;i<30;i++)
  {
    printf("%d ",DeleteHead(stack1));
  }
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int Fibonacci(unsigned int n)
{
  if(n==0)
    return 0;
  if(n==1)
    return 1;
  return Fibonacci(n-2)+Fibonacci(n-1);
}
int Fibonacci1(unsigned int n)
{
  int i;
  unsigned int fib1,fib2,fibN = 0;
  if(n==0)return 0;
  if(n==1)return 1;
  fib1 = 0;
  fib2 = 1;
  for(i=2;i<=n;i++)
  {
    fibN = fib1+fib2;
    fib1 = fib2;
    fib2 = fibN;
  }
  return fibN;
}
int main()
{
  int i;
  for(i=0;i<10;i++)
    printf("%d ",Fibonacci(i));
  printf("\n");
  for(i=0;i<10;i++)
    printf("%d ",Fibonacci1(i));
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int FindMin(int* data,int length)
{
  int indexHead = 0;
  int indexTail = length -1;
  int indexMiddle;
  int i;
  if(data[indexHead]<data[indexTail])
    return data[indexHead];
  while((indexTail-indexHead)>1)
  {
    indexMiddle = (indexHead+indexTail)/2;
    /*1 0 1 1 1 头尾中间都相等*/
    if(data[indexHead]==data[indexTail] && data[indexHead] == data[indexMiddle])
    {
      for(i=indexHead+1;i<indexTail;i++)
      {
        if(data[i]<data[indexHead])
          return data[i];
      }
      return false;
    }
    /*************************/
    if(data[indexMiddle]>=data[indexHead])
      indexHead = indexMiddle;
    else
      indexTail = indexMiddle;
  }
  return data[indexTail];
}
int main()
{
  int data[] = {2,3,4,5.6,7,8,1};
  printf("%d",FindMin(data,sizeof(data)/sizeof(int)));
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool HasPathCore(char* martrix,int rows,int cols,int row,int col,
  char* str,int* pathlength,bool* visit)//判断某位置是否有某字符
{
  bool hasPath = 0;
  if(str[*pathlength]=='\0')
    return true;
  //需要确定：1.行数在矩阵里 2.列数在矩阵里 3.相等 4.没用过
  if(row>=0 && row<rows && col>=0 && col<cols && str[*pathlength]==martrix[row*cols+col] && !visit[row*cols+col])
  {
    (*pathlength)++;
    visit[row*cols+col]=1;
    hasPath = (HasPathCore(martrix,rows,cols,row-1,col,str,pathlength,visit)
      ||HasPathCore(martrix,rows,cols,row+1,col,str,pathlength,visit)
      ||HasPathCore(martrix,rows,cols,row,col+1,str,pathlength,visit)
      ||HasPathCore(martrix,rows,cols,row,col-1,str,pathlength,visit));
    if(!hasPath)
    {//没找到就释放visit
      (*pathlength)--;
      visit[row*cols+col] = 0;
      return false;
    }
    else
    {
      return true;
    }
  }
  return false;
}
bool HasPath(char* martrix,int rows,int cols,char* str)
{
  int i = 0;
  int* pathLength;
  int row = 0;
  int col = 0;
  bool* visit; 
  if(martrix == NULL || rows<1 || cols<1 || str == NULL)
    return false;
  pathLength = (int *)malloc(sizeof(int));
  *pathLength = 0;
  visit = (bool*)malloc(sizeof(int)*(rows*cols));
  for(i=0;i<rows*cols;i++)
    visit[i]= 0;
  for(row = 0; row<rows; row++)
  {
    for(col = 0;col < cols;col++)
    {
      if(HasPathCore(martrix,rows,cols,row,col,str,pathLength,visit))
      {
        free(pathLength);
        free(visit);
        return true;
      }
    }
  }
  free(pathLength);
  free(visit);
  return false;
}
int main()
{
  char martrix[][4] = {{'A','B','T','G'},{'C','F','C','S'},{'J','D','E','H'}};
  char *str ="BFCEA";
  printf("%d",HasPath((char*)martrix,3,4,str));
  str = "BFCE";
  printf("%d",HasPath((char*)martrix,3,4,str));
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int GetDigitSum(int number)
{
  int sum = 0;
  while(number>0)
  {
    sum+=number%10;
    number/=10;
  }
  return sum;
}
int MovingCountCore(int threshold,int rows,int cols,int row,int col,bool* visit)
{
  int count = 0;
  if(row>=0 && row<rows && col>=0 && col<cols && GetDigitSum(row)+GetDigitSum(col)<=threshold && !visit[cols*row+col])
  {
    visit[cols*row+col] = 1;
    count = 1 + MovingCountCore(threshold,rows,cols,row+1,col,visit)+
    MovingCountCore(threshold,rows,cols,row-1,col,visit)+
    MovingCountCore(threshold,rows,cols,row,col+1,visit)+
    MovingCountCore(threshold,rows,cols,row,col-1,visit);
  }
  return count;
}
int MovingCount(int threshold,int rows,int cols)
{
  bool *visit;
  int count;
  int i = 0;
  if(rows<=0 || cols<=0 ||threshold<0)
    return false;
  visit = (bool*)malloc(sizeof(bool)*(rows*cols));
  for(i=0;i<rows*cols;i++)
  {
    visit[i] = 0;
  }
  count = MovingCountCore(threshold,rows,cols,0,0,visit);
  free(visit);
  return count;
}
int main()
{
  printf("%d",MovingCount(1,2,2));
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int MaxProductCutting1(int length)
{
  int *product;
  int i,j,max;
  if(length<2)return 0;
  if(length==2)return 1;
  if(length==3)return 2;
  product = (int*)malloc((length+1)*sizeof(int));
  for(i=0;i<length+1;i++)
    product[i]=0;
  product[0] = 0;
  product[1] = 1;
  product[2] = 2;
  product[3] = 3;
  for(i=4;i<length+1;i++)
  {
    for(j=1;j<=i/2;j++)
    {
      max = product[j]*product[i-j];
      if(max>product[i])
        product[i] = max;
    }
  }
  max = product[length];
  free(product);
  return max;
}
int MaxProductCutting2(int length)
{
  int timesOf3 = 0;
  int timesOf2 = 0;
  int result;
  if(length<2)return 0;
  if(length==2)return 1;
  if(length==3)return 2;
  timesOf3 = length/3;
  if(length%3 == 1)
  {
    timesOf3 -=1;
    timesOf2 = 2;
  }else if(length%3 == 2)
    timesOf2 = 1;
  result = (int)pow(3,timesOf3)*(int)pow(2,timesOf2);
  return result;
}
int MaxProductCutting3Core(int length)
{
  int i = 0;
  int max = 0;
  int product;
  if(length<1)return 0;
  if(length==1)return 1;
  if(length==2)return 2;
  if(length==3)return 3;//很重要
  for(i=1;i<=length/2;i++)
  {
    product = MaxProductCutting3Core(i)*MaxProductCutting3Core(length-i);
    if(product>max) max = product;
  }
  return max;
}
int MaxProductCutting3(int length)
{
  if(length<2)return 0;
  if(length==2)return 1;
  if(length==3)return 2;
  return MaxProductCutting3Core(length);
}
int main()
{
  int i;
  for(i=0;i<15;i++)
    printf("%d ",MaxProductCutting1(i));
  printf("\n");
  for(i=0;i<15;i++)
    printf("%d ",MaxProductCutting2(i));
  printf("\n");
  for(i=0;i<15;i++)
    printf("%d ",MaxProductCutting3(i));
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int NumberOf1(int n)
{
  int number=0;
  unsigned int flag =1;
  while(flag)
  {
    if(n & flag)number++;
    flag = flag<<1;
  }
  return number;
}
int main()
{
  int i;
  for(i=0;i<20;i++)
  printf("%d ",NumberOf1(i));
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int errorStatus;
double PowerWithUnsigned(double base,unsigned int exp)
{
  /*
  double result = 1;
  while(exp)
  {
    result*=base;
    exp--;
  }
  return result;*/
  double result;
  if(exp == 0)
    return 1;
  if(exp == 1)
    return base;
  result = PowerWithUnsigned(base,exp>>1);
  result*=result;
  if(exp & 0x1)
    result*= base;
  return result;
}
double Power(double base,int exp)
{
  const double eps = 1e-6;
  double result = 1;
  if(abs(base-0.0)<eps && exp<0)
  {
    errorStatus = 1;
    return 0;
  }
  if(exp<0)
    return 1.0/PowerWithUnsigned(base,-exp);
  else 
    return PowerWithUnsigned(base,exp);
}
int main()
{
  printf("%f ",Power(2,-3));
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#include <string.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int errorStatus;
void PrintNumber(char* number)
{
  bool begin = false;
  int i = 0;
  int length = strlen(number);
  for(i=0;i<length;i++)
  {
    if(!begin && number[i]!='0')
      begin = true;
    if(begin)
      printf("%c",number[i]);
  }
  printf("\t");
}
bool Increment(char* number)
{
  int i;
  int nSum = 0;
  int nTakeOver = 0;
  int isOverflow = 0;
  int length = strlen(number);
  for(i=length-1;i>=0;i--)
  {
    //只有最低位加一
    if(i==length-1)
      number[i]++;
    nSum = number[i] - '0' + nTakeOver;
    if(nSum==10)
    {
      nTakeOver = 1;
      if(i==0)
        isOverflow = 1;
      else
        number[i] = '0';
    }
    else
    {
      number[i] = nSum + '0';
      break;
    }
  }
  return isOverflow;
}
void Print(int n)
{
  char* number ;
  int i=0;
  if(n<=0)
    return;
  number = (char*)malloc(sizeof(char)*(n+1));
  for(i=0;i<n;i++)
    number[i] = '0';
  number[i] = '\0';
  while(!Increment(number))
  {
    PrintNumber(number);
  }
  free(number);
}
int main()
{
  Print(3);
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#include <string.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
int errorStatus;
void PrintNumber(char* number)
{
  bool begin = false;
  int i = 0;
  int length = strlen(number);
  for(i=0;i<length;i++)
  {
    if(!begin && number[i]!='0')
      begin = true;
    if(begin)
      printf("%c",number[i]);
  }
  printf("\t");
}
void Print1ToMaxCore(char* number, int length, int index)
{
  int i = 0;
    if (index == length)
    {
        PrintNumber(number);
        return;
    }
    for (i = 0; i < 10; i++)
    {
        number[index] = i + '0';
        Print1ToMaxCore(number, length, index + 1);
    }
}
void Print1ToMax(int n)
{
  char* number = (char*)malloc(sizeof(char)*(n+1));
  int i=0;
    if (n <= 0)
        return;
    number[n] = '\0';
    Print1ToMaxCore(number, n, 0);
    free(number);
}
int main()
{
  Print1ToMaxOfNDigits_2(3);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
void PrintList(listNode* head)
{
  listNode* p = head;
  if(p==NULL)
    return;
  while(p->next!=NULL)
  {
    printf("%d",p->data);
    p = p->next;
  }
  printf("%d\n",p->data);
}
listNode* CreateListNode(int data)
{
  listNode* newListNode = (listNode*)malloc(sizeof(listNode));
  if(!newListNode)return false;
  newListNode->data = data;
  newListNode->next = NULL;
  return newListNode;
}
void ConnectListNodes(listNode* node1,listNode* node2)
{
  node1->next = node2;
}
//传入结构体指针，只能改结构体，不能改结构体指针。因为头节点可能被改变
void DeleteNode(listNode** head, listNode* deleteNode)
{
  listNode* next;
  if(*head == NULL || deleteNode == NULL)
    return;
  if(deleteNode->next != NULL)//不是尾节点
  {
    next = deleteNode->next;
    deleteNode->data = next->data;
    deleteNode->next = next->next;
    free(next);
    next = NULL;
  }
  else if(deleteNode == *head)//只有一个节点 又头又尾
  {
    free(deleteNode);
    deleteNode = NULL;
    *head = NULL;
  }
  else
  {
    next = *head;
    while(next->next!=deleteNode)
    {
      next = next->next;
    }
    free(deleteNode);
    next->next = NULL;
    next = NULL;
  }
}
void Test(listNode* head,listNode* deleteNode)
{
  PrintList(head);
  DeleteNode(&head,deleteNode);
  PrintList(head);
}
int main()
{
  listNode* pNode1 = CreateListNode(1);
    listNode* pNode2 = CreateListNode(2);
    listNode* pNode3 = CreateListNode(3);
    listNode* pNode4 = CreateListNode(4);
    listNode* pNode5 = CreateListNode(5);
  ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
  Test(pNode1,pNode1);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
void PrintList(listNode* head)
{
  listNode* p = head;
  if(p==NULL)
    return;
  while(p->next!=NULL)
  {
    printf("%d",p->data);
    p = p->next;
  }
  printf("%d\n",p->data);
}
listNode* CreateListNode(int data)
{
  listNode* newListNode = (listNode*)malloc(sizeof(listNode));
  if(!newListNode)return false;
  newListNode->data = data;
  newListNode->next = NULL;
  return newListNode;
}
void ConnectListNodes(listNode* node1,listNode* node2)
{
  node1->next = node2;
}
void DeleteDuplication(listNode** head)
{
  listNode* pNode;//当前节点
  listNode* nextNode;//下一节点
  if(head==NULL || *head == NULL)//head==NULL说明链表指针为空 *head==NULL说明头结点为空
    return;
  pNode = *head;
  if(pNode->next == NULL)//只有一个节点
    return;
  nextNode = pNode->next;
  while(pNode->next!=NULL)
  { 
    if(pNode->data == nextNode->data)
    {
      pNode->next = nextNode->next;
      free(nextNode);
      if(pNode->next!=NULL)
        nextNode = pNode->next;
      else
        return;
    }
    else
    {
      pNode = pNode->next;
      nextNode = pNode->next;
    }
  }
}
void Test(listNode* head,listNode* deleteNode)
{
  PrintList(head);
  //DeleteNode(&head,deleteNode);
  DeleteDuplication(&head);
  PrintList(head);
}
int main()
{
  listNode* pNode1 = CreateListNode(1);
    listNode* pNode2 = CreateListNode(1);
    listNode* pNode3 = CreateListNode(2);
    listNode* pNode4 = CreateListNode(2);
    listNode* pNode5 = CreateListNode(3);
  listNode* pNode6 = CreateListNode(3);
  ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
  ConnectListNodes(pNode5, pNode6);
  Test(pNode1,pNode1);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
void PrintList(listNode* head)
{
  listNode* p = head;
  if(p==NULL)
    return;
  while(p->next!=NULL)
  {
    printf("%d",p->data);
    p = p->next;
  }
  printf("%d\n",p->data);
}
listNode* CreateListNode(int data)
{
  listNode* newListNode = (listNode*)malloc(sizeof(listNode));
  if(!newListNode)return false;
  newListNode->data = data;
  newListNode->next = NULL;
  return newListNode;
}
void ConnectListNodes(listNode* node1,listNode* node2)
{
  node1->next = node2;
}
void DeleteDuplication1(listNode** head)
{
  listNode* pNode;//当前节点
  listNode* nextNode;//下一节点
  listNode* preNode = NULL;//前一节点
  listNode* toBeDel;
  int val;
  int needDel;
  if(head==NULL || *head == NULL)//head==NULL说明链表指针为空 *head==NULL说明头结点为空
    return;
  pNode = *head;
  while(pNode!=NULL)
  {
    nextNode = pNode->next;//要保证pNode不为NULL 才能->next
    if(nextNode!=NULL && nextNode->data == pNode->data)
    {
      needDel = 1;
      toBeDel = pNode;
      val = pNode->data;
    }
    else
      needDel = 0;
    if(!needDel)
    {
      preNode = pNode;
      pNode = pNode->next;
    }
    else
    {
      while(toBeDel!=NULL && toBeDel->data == val)
      {
        pNode = toBeDel->next;
        free(toBeDel);
        toBeDel = pNode;
      }
      if(preNode == NULL)
        *head = pNode;
      else
        preNode->next = pNode;
    }
  }
}
void Test(listNode* head,listNode* deleteNode)
{
  PrintList(head);
  //DeleteNode(&head,deleteNode);
  DeleteDuplication1(&head);
  PrintList(head);
}
int main()
{
  listNode* pNode1 = CreateListNode(1);
    listNode* pNode2 = CreateListNode(1);
    listNode* pNode3 = CreateListNode(1);
    listNode* pNode4 = CreateListNode(2);
    listNode* pNode5 = CreateListNode(3);
  listNode* pNode6 = CreateListNode(3);
  ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
  ConnectListNodes(pNode5, pNode6);
  Test(pNode1,pNode1);

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool MatchCore(char* str,char* pattern)
{
  if(*str=='\0'&& *pattern=='\0')
    return true;
  if(*str!='\0' && *pattern=='\0')
    return false;
  if(*(pattern+1) == '*')
  {
    if(*(pattern+2)=='*')return false;
    if(*str == *pattern || *str!='\0'&& *pattern=='.')
    {
      return MatchCore(str+1,pattern)||MatchCore(str+1,pattern+2)||MatchCore(str,pattern+2);
    }
    else
      return MatchCore(str,pattern+2);
  }
  else
  {
    if(*str == *pattern || *str!='\0'&& *pattern=='.')
      return MatchCore(str+1,pattern+1);
    else
      return false;
  }
}
bool Match(char* str,char* pattern)
{
  if(str==NULL || pattern==NULL)
    return false;
  if(*pattern=='*')
    return false;
  MatchCore(str,pattern);
}
void main()
{
  char* str = "aaa";
  char* pattern = "ab*a*c*a";
  bool state = Match(str,pattern);
  if(state)printf("YES");
  else printf("NO");
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool ScanUnsignedInteger(const char **str)
{
  const char* before = *str;
  while(**str!='\0' && **str>='0' && **str<='9')
    (*str)++;
  if(*str!=before)
    return true;
  else 
    return false;
}
bool ScanInteger(const char **str)
{
  if(**str == '+'||**str == '-')
    (*str)++;
  return ScanUnsignedInteger(str);
}
bool IsNumeric(const char* str)
{
  bool numeric;
  numeric = ScanInteger(&str);
  if(*str == '.')
  {
    str++;
    numeric =  ScanUnsignedInteger(&str) || numeric;
  }
  else if(*str == 'e' || *str == 'E')
  {
    str++;
    numeric = numeric && ScanInteger(&str);
  }
  return numeric && (*str == '\0');
}
void main()
{
  char* str = "+12e-13";
  if(IsNumeric(str))
    printf("Success");
  else 
    printf("Fail");
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
bool func(int a)//是否是奇数 
{
  return a&0x1;
}
void Reorder(int* number,int length)
{
  int* start = &number[0];
  int* end = &number[length-1];
  int change;
  if(number == NULL || length == 0)
    return;
  while(start!=end)
  {
    while(start!=end && func(*start))
      start++;
    while(start!=end && !func(*end))
      end--;
    if(start!=end)
    {
      change = *end;
      *end = *start;
      *start = change;
    }
  }
}
void main()
{
  int number[] = {1,2,3,4,5};
  int i=0;
  Reorder(number,sizeof(number)/sizeof(int));
  for(i=0;i<sizeof(number)/sizeof(int);i++)
    printf("%d ",number[i]);
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
void PrintList(listNode* head)
{
  listNode* p = head;
  while(p!=NULL)
  {
    printf("%d ",p->data);
    p = p->next;
  }
}
listNode* CreateListNode(int data)
{
  listNode* newListNode = (listNode*)malloc(sizeof(listNode));
  if(!newListNode)return false;
  newListNode->data = data;
  newListNode->next = NULL;
  return newListNode;
}
void ConnectListNodes(listNode* node1,listNode* node2)
{
  node1->next = node2;
}
listNode* FindKthToTail(listNode* head,unsigned int k)
{
  listNode* p1 = head;
  listNode* p2 = NULL;
  if(head == NULL || k==0)
    return NULL;
  while(k!=1)
  {
    p1=p1->next;
    k--;
    if(p1==NULL)
      return NULL;
  }
  p2 = head;
  while(p1->next!=NULL)
  {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p2;
}
void main()
{
  int k=1;
  listNode* pNode1 = CreateListNode(1);
    listNode* pNode2 = CreateListNode(2);
    listNode* pNode3 = CreateListNode(3);
    listNode* pNode4 = CreateListNode(4);
    listNode* pNode5 = CreateListNode(5);
  ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
  //PrintList(pNode1);
  if(FindKthToTail(pNode1,k)!=NULL)
    printf("%d",FindKthToTail(pNode1,k)->data);
  else 
    printf("Error");
}

#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2
typedef struct ListNode
{
  int data;
  struct ListNode* next;
}listNode;
void PrintList(listNode* head)
{
  listNode* p = head;
  while(p!=NULL)
  {
    printf("%d ",p->data);
    p = p->next;
  }
}
listNode* CreateListNode(int data)
{
  listNode* newListNode = (listNode*)malloc(sizeof(listNode));
  if(!newListNode)return false;
  newListNode->data = data;
  newListNode->next = NULL;
  return newListNode;
}
void ConnectListNodes(listNode* node1,listNode* node2)
{
  node1->next = node2;
}
/*找到相遇的节点*/
listNode* MeetingNode(listNode* head)
{
  listNode* pSlow;
  listNode* pFast;
  if(head==NULL)return NULL;
  pSlow = head->next;
  if(pSlow==NULL)return NULL;
  pFast = pSlow->next;
  while( pFast != NULL)
  {
    if(pFast == pSlow)
      return pSlow;
    pSlow = pSlow->next;
    pFast = pFast->next;
    if(pFast == NULL)return NULL;
    pFast = pFast->next;
  }
  return NULL;
}
listNode* EntryNodeOfLoop(listNode* head)
{
  listNode* meetingNode = MeetingNode(head);
  listNode* next = NULL;
  listNode* pNode1 = NULL;
  listNode* pNode2 = NULL;
  int loopCount = 0;
  if(meetingNode == NULL)return NULL;
  next = meetingNode->next;
  loopCount++;
  while(next!= meetingNode)
  {
    next = next->next;
    loopCount++;
  }
  pNode2 = head;
  pNode1 = head;
  for(;loopCount>0;loopCount--)
  {
    pNode1 = pNode1->next;
  }
  while(pNode1->data!=pNode2->data)
  {
    pNode1 = pNode1->next;
    pNode2 = pNode2->next;
  }
  return pNode1;
}
void main()
{
  int k=1;
  listNode* pNode1 = CreateListNode(1);
    listNode* pNode2 = CreateListNode(2);
    listNode* pNode3 = CreateListNode(3);
    listNode* pNode4 = CreateListNode(4);
    listNode* pNode5 = CreateListNode(5);
  ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
  ConnectListNodes(pNode5, pNode3);
  if(EntryNodeOfLoop(pNode1)!=NULL)
    printf("%d",EntryNodeOfLoop(pNode1)->data);
  else
    printf("Error");
  //PrintList(pNode1);
}