数据结构与算法整理一

数组

// 找出某个目标数 在一二维数组中是否存在 
public boolean find(int target,int [][] array){

    if(array == null || array.length <= 0){
        return false;
    }

    int row = array.length - 1;

    int col = 0;
    int cols = array[0].length;

    while(row >= 0 && col < cols){
        int cur = array[row][col];
        if(cur < target){
            col ++;
        }else if(cur > target){
            row --;
        }else{
            return true;
        }
    }

    return false;
}

//求连续子列 最大和
int MaxSubSeqSub(int [] a,int N){
        int thisSum = 0;
        int maxSum = 0;
        for(int i = 0;i < N;i++){
            thisSum +=a[i];
            if(thisSum > maxSum){
                maxSum = thisSum;
            }else if(thisSum < 0){
                thisSum = 0;
            }
        }
        return maxSum;
    }

链表

 // 单链表节点的结构
public static class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
//链表反转
ListNode reverse(ListNode head) {
        if (head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

//反转链表前n 个节点
ListNode successor = null;
    ListNode reverseN(ListNode head,int n){
        if(n == 1){
            //记录第 n+1 个节点
            successor = head.next;
            return head;
        }

        //以head.next 为起点，需要反转前n-1个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }

// 打印链表
static void printListNode(ListNode head){
        if(head.next == null){
            System.out.println(head.val);
            System.out.println("end");
            return;
        }
        ListNode node = head.next;
        System.out.println(head.val);
        printListNode(node);
        System.out.println(" end "+node.val);
    }