左旋转字符串

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

左旋转字符串

字符序列S=”abcXYZdef”

要求输出循环左移3位后的结果

即“XYZdefabc”

public static String LeftRotateString(String str, int n) {
       if (str == null || str.length() == 0 || n < 0) {
           return "";
       }
       StringBuilder sb = new StringBuilder(str);
       int len = str.length();
       n = n % len;
       sb.append(str);
       return sb.substring(n, len + n);
   }

二叉搜索树的第k个结点

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

求二叉搜索树的第k个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。

例如:
     5
   /  \
  3    7
 / \  / \
2  4 6   8
中，按结点数值大小顺序第三个结点的值为4。

public static TreeNode KthNode(TreeNode pRoot, int k) {
    if (pRoot == null || k < 1) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    int count = 0;
    TreeNode KthNode = null;
    while (pRoot != null || !stack.isEmpty()) {
        while (pRoot != null) {
            stack.push(pRoot);
            pRoot = pRoot.left;
        }
        TreeNode node = stack.pop();
        count++;
        if(count == k){
            KthNode = node;
        }        
        pRoot = node.right;         
    }
    return KthNode;

}

数组中未出现的最小正整数

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

数组中未出现的最小正整数

arr=[-1,2,3,4] 返回 1

arr=[1,2,3,4] 返回 5

public static int missNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int l = 0; //目前已收集  1 ~ l 上的数
        int r = arr.length; // 后续最优的情况下 能收集  1 ~ r 上的数
        while (l < r) {
            if (arr[l] == l + 1) {
                l++;
            } else if (arr[l] < l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                r--;
            } else {
                swap(arr, l, arr[l] - 1);
            }
        }
        return l + 1;
    }

    public static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

数组中超过一半的数

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

原题 :（数组中超过一半（N/2）的数）

进阶 : 找到出现次数超过N/K的数

tips : 原题一个候选数一次删2个进阶题一次k-1个候选数一次删k个

public static void pirntKMajor(int[] arr, int k) {
        if (k < 2) {
            System.out.println("the value of k is invalid");
            return;
        }
        HashMap<Integer, Integer> cands = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (cands.containsKey(arr[i])) {
                cands.put(arr[i], cands.get(arr[i]) + 1);
            } else {
                if (cands.size() == k - 1) {
                    allCandsMinsusOne(cands);
                } else {
                    cands.put(arr[i], 1);
                }
            }
        }
        HashMap<Integer, Integer> reals = getReals(arr, cands);

        boolean print = false;
        for (Map.Entry<Integer, Integer> set : reals.entrySet()) {
            int value = set.getValue();
            int key = set.getKey();
            if (value > arr.length / k) {
                print = true;
                System.out.print(key + " ");
            }
        }
        System.out.println(print ? "" : "no such number");
    }

    private static HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> cands) {
        HashMap<Integer, Integer> reals = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (cands.containsKey(arr[i])) {
                if (reals.containsKey(arr[i])) {
                    reals.put(arr[i], reals.get(arr[i]) + 1);
                } else {
                    reals.put(arr[i], 1);
                }
            }
        }
        return reals;
    }

    private static void allCandsMinsusOne(HashMap<Integer, Integer> map) {
        List<Integer> removeList = new LinkedList<>();
        for (Map.Entry<Integer, Integer> set : map.entrySet()) {
            int key = set.getKey();
            int value = set.getValue();
            if (value == 1) {
                removeList.add(key);
            } else {
                map.put(key, value - 1);
            }
        }
        for (Integer removeKey : removeList) {
            map.remove(removeKey);
        }
    }

最小的K个数

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

给定一个无序数组，找到其中最小的K个数

利用最大堆,只要维护堆内有k个数即可

//利用最大堆
public static int[] getMinKNumByHeap(int[]arr ,int k){
    if(arr==null ||arr.length<k|| k<0){
        return null;
    }
    int[] kHeap = new int[k];
    for(int i =0 ; i<k; i++){
        heapInsert(kHeap,arr[i],i);
    }
    for(int i=k; i<arr.length; i++){
        if(kHeap[0]>arr[i]){
            kHeap[0] = arr[i];
            heapify(kHeap, 0, k);
        }
    }
    return kHeap;
} 
//建堆的过程
public static void heapInsert(int[] heap, int value, int index){
    heap[index] = value;
    int parent = (index-1)/2;
    while(index!=0){
        if(heap[index]>heap[parent]){
            swap(heap,index,parent);
            index = parent;
        }else{
            break;
        }
    }
}
//调整的过程
public static void heapify(int[] heap, int index, int heapSize){
    int left = 2*index +1;
    int right = 2*index +2;
    int largest = index;
    while(left < heapSize){
        if(heap[index]<heap[left]){
            //swap(heap,index,left);
            largest = left;
        }
        if(right < heapSize && heap[largest]<heap[right]){
            largest = right;
        }
        if(index!=largest){
            swap(heap,index,largest);
        }else{
            break;
        }
        index = largest;
        left = 2*index +1;
        right = 2*index +2;
    }

}
public static void swap(int[] arr, int low, int high){
    int temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
}

快排思想, 无需全部排序,保证前k个数有序即可

public static int partition(int[] arr,int start,int end){
    if(arr==null || arr.length==0){
        return -1; 
    }
    int l = start;
    int r = end;
    int temp = arr[l];
    if(l<r){
        while(l<r && temp >= arr[r]){
            r--;
        }
        if(l<r){
            arr[l++]=arr[r];
        }
        while(l<r && temp < arr[l]){
            l++;
        }
        if(l<r){
            arr[r--] = arr[l];
        }
    }
    arr[l] = temp;
    return l;
}
//利用快排思想
public static void getKNum(int[] arr,int start,int end, int k){
    int index = partition(arr, start, end);
    while(index != k-1){
        if(index < k-1){
            index = partition(arr, index+1, end);
        }else if(index > k-1){
            index = partition(arr, start, index-1);
        }else{
            return;
        }
    }
}

最长子数组

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

在未排序数组中找到和为k的最长子数组长度

public static int maxLength(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //这个map表示key第一次出现在value下标的位置
        HashMap<Integer, Integer> map = new HashMap<>();
        //表示 合为0 第一次出现在-1位置
        map.put(0, -1);

        int len = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - k)) {
                len = Math.max(i - map.get(sum - k), len);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }

反转链表

发表于 2018-10-05 | 分类于数据结构与算法，题目汇总

反转链表

// 非递归
public static Node reverseUnRecur(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        Node cur = head;
        while (cur != null) {
            //记住当前节点的
            next.next = cur.next;
            // 当前节点指向前一个节点
            cur.next = pre;
            // 让pre记住当前节点
            pre = cur;
            // 当前节点后移
            cur = next;
        }
        return pre;
    }

    
    // 递归
    public static Node reverseRecur(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node next = head.next;
        head.next = null;
        Node revNode = reverseRecur(next);
        next.next = head;
        return revNode;
    }

    class Node {
        int val;
        Node next;
    }

排序邻数差值

发表于 2018-10-04 | 分类于数据结构与算法，题目汇总

简述

求数组排序后相邻数的最大差值

public static int maxGap(int[] arr){
    if(arr == null || arr.length == 0){
        return 0;
    }
    int len = arr.length;
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i  <len; i++){
        max = Math.max(arr[i], max);
        min = Math.min(arr[i], min);
    }
    if(max == min){
        return 0;
    }
    int[] maxArr = new int[len+1];
    int[] minArr = new int[len+1];
    boolean[] hasNum = new boolean[len + 1];
    int k = 0;
    for(int i = 0; i < len; i++){
        k = getBucket(arr[i], max, min, len);
        maxArr[k] = hasNum[k] ? Math.max(arr[i], maxArr[k]) : arr[i];
        minArr[k] = hasNum[k] ? Math.min(arr[i], minArr[k]) : arr[i];
        hasNum[k] = true;
    }
    int lastMax = 0;
    int nextMin = 0;
    int i = 0;
    for(; i<len; i++){
        if(!hasNum[i]){
            lastMax = maxArr[i-1];
            break;
        }
    }
    while(i<len+1){
        if(hasNum[i]){
            nextMin = minArr[i];
            break;
        }
        i++;
    }
    return nextMin - lastMax;
}
/**
 * 计算进入哪个桶  max直接放入n+1桶中 
 */
public static int getBucket(int num, int max, int min, int len){
    return ((num - min) * len) / (max - min);
}

汉诺塔

发表于 2018-10-04 | 分类于数据结构与算法，题目汇总

public class hanoi { 
    
    public static void hanoi(int n){ 
        if(n > 0) { 
            fun(n, ”LEFT”, ”MID”, ”RIGHT”); 
        } 
    } 
    public static void fun(int n, String from, String mid, String to) { 
        if(n == 1) { 
            System.out.println(“move from ” + from + ” to ” + to); 
        } else { 
            fun(n-1, from, to, mid); 
            fun(1, from, mid, to); 
            fun(n-1, mid, from, to); 
        } 
    } 
}

左右差值绝对值最大

发表于 2018-10-04 | 分类于数据结构与算法，题目汇总

题目

给定一个长度为N(N>1)的整型数组arr，可以划分成左右两个部分，
左部分arr[0..K]，右部分arr[K+1..N-1]，K可以取值的范围是[0,N-2]。
求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，
最大是多少？例如[2,7,3,1,1]，当左部分为[2,7]，右部分为[3,1,1]时，
左部分中的最大值减去右部分最大值的绝对值为4。当左部分为[2,7,3]，
右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为6。
还有很多划分方案，但最终返回6。

public static int maxABS(int[] arr){
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
    }
    return max - Math.min(arr[0], arr[arr.length - 1]);

}

最优解，时间复杂度O(N)，额外空间复杂度O(1)。先求整个arr的最大值max，
因为max是全局最大值，所以不管怎么划分，max要么会成为左部分的最大值，
要么会成为右部分的最大值。如果max作为左部分的最大值，
接下来我们只要让右部分的最大值尽量小就可以了。
右部分的最大值怎么尽量小呢？
右部分只含有arr[N-1]的时候就是尽量小的时候。同理，
如果max作为右部分的最大值，只要让左部分的最大值尽量小就可以了，
左部分只含有arr[0]的时候就是尽量小的时候。
所以整个求解过程会变得异常简单

Zhengye Zhang

勇敢的少年快去创造奇迹

GitHub E-Mail