Tianji's Blog.

算法刷刷刷

Word count: 8,787 / Reading time: 47 min
2019/03/06 Share

一天刷10道，bat不是梦啊，加油

T： 时间复杂度 S：空间复杂度

n个数，大小0-(n-1)，判断是否有重复

条件: 无

方法一: 排序，扫描即可 O(nlogn)

方法二: 使用HashTable O(n)

方法三: 扫描下标为i的数字m时，判断m== i, 是，继续扫描，否，将m和下标为m的数字n进行比较,若相等，则重复，否则交换下标为m和下标为i的两个数字。

T: O(n)

S: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool duplicate(int numbers[], int length, int *duplication) {
    if(numbers == nullptr || length <=0) {
        return false;
    }

//    判断输入是否符合条件
    for(int i = 0; i< length; i++) {
        if(numbers[i] < 0 || numbers[i] > length - 1) {
            return false;
        }
    }

//    正式处理
    int temp = 0;
    for(int i = 0; i < length; ++i) {
        while(numbers[i] != i) {
//            有重复数字
            if(numbers[i] == numbers[numbers[i]]) {
                *duplication = numbers[i];
                return true;
            }
//            交换标为i 和下标为numbers[i]的两个数字
            temp = numbers[i];
            numbers[i] = numbers[numbers[i]];
            numbers[numbers[i]] = temp;
        }
    }

    return false;
}

判断是不是素数

1
2
3
4
5
6
7
8
9
10
11
private static boolean isPrime(int a) {
        boolean isPrime = true;
        int b = (int) (Math.sqrt(a) + 1);
        for(int i = 2; i <= b; i++) {
            if (a % b == 0 ) {
                isPrime = false;
            }
        }

        return isPrime;
    }

n+1个数，大小1-n，判断是否有重复

条件: 不修改原数组

方法一: 开辟一个新的数组，在使用上边的方法 T: O(n) S:O(n)

方法二: 把1-n的数字，从中间的数字m分为两部分，前一半为1-m,后一半为(m+1)-n,如果1~m的数字的数目超过m,那这一半区间存在重复。类似于二分法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
bool duplicate(int numbers[], int length, int *duplication) {
    if(numbers == nullptr || length <=0) {
        return false;
    }

//    判断输入是否符合条件
    for(int i = 0; i< length; i++) {
        if(numbers[i] < 1 || numbers[i] > length - 1) {
            return false;
        }
    }
// 4
// 1 1 2 3
//    正式处理
    int start = 1;
    int end = length - 1;
    int middle = 0;
    int count = 0;
    while(end >= start) {
        middle = ((end - start) >> 1) + start;
        count = countRange(numbers, length, start, middle);
        if(end == start) {
            if(count > 1) {
                *duplication = start;
                return true;
            } else {
                break;
            }
        }
//        计算差值
        if(count > (middle - start + 1)) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }

    *duplication = start;
    return false;
}

int countRange(int numbers[], int length, int start, int end) {
    int count = 0;
    for(int i = 0; i< length; i++) {
        if(numbers[i] >= start && numbers[i] <=end) {
            count++;
        }
    }

    return count;
}

将空格替换为%20

##时间复杂度

T: O(n) 首先遍历一遍字符串，找出所有的空格数，统计出最终字符串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <assert.h>

void ReplaceBlank(char str[], int length, int limit);

int main() {
	char str[50];
	printf("请输入一个字符串:");
	gets(str);
	printf("字符串: %s\n", str);
	int length = 0;
	length = strlen(str);
	printf("长度为:%d", length);
	ReplaceBlank(str, length, 50);
	printf("转换后的字符串:%s", str);
	return 0;
}

void ReplaceBlank(char str[], int length, int limit) {
	if(length == 0) {
		return;
	}
	int blanknumber = 0;
	for(int i = 0; i< length; i++) {
		if(str[i] == 32) {
			blanknumber++;
		}
	}

	int replaceStrLength = length + blanknumber * 2;
	if(replaceStrLength >= 50) {
		printf("超出范围");
		return;
	}
	str[replaceStrLength] = '\0';
	for(int i = length - 1; i >= 0; i--) {
		if(str[i] == 32) {
			str[replaceStrLength - 3] = '%';
			str[replaceStrLength - 2] = '2';
			str[replaceStrLength - 1] = '0';
			replaceStrLength -= 3;
		} else {
			str[replaceStrLength - 1] = str[i];
			replaceStrLength -= 1;
		}
	}
}

链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//从尾到头打印链表
//使用递归，容易出现堆栈溢出
//使用栈
void PrintListReversingly_Iteratively(ListNode *pHead) {
    int result[20] = {0};
    ListNode *pNode = pHead;
    int length = 0;
    while(pNode != NULL) {
        result[length] = pNode->m_nValue;
        length++;
        pNode = pNode->m_pNext;
    }

    for(int i = length - 1; i >= 0; i--) {
        printf("%d\t", result[i]);
    }
}
//
//void Recursively(ListNode *pHead) {
//    if(pHead != NULL) {
//        if(pHead->m_pNext != NULL) {
//            Recursively(pHead->m_pNext);
//        }
//
//        printf("%d\t", pHead->m_nValue);
//    }
//}

树：

二叉搜索树: 左子节点总是小于或者等于根结点，二右子节点总是大于或者等于根结点。T： O(logn)

堆: 最大堆和最小堆，最大堆中根结点的值最大，最小堆中根结点的值最小，很多需要快速找到最大值或者最小值的问题可以用堆来解决。

红黑树: 把树中的节点定义为红黑两种颜色，并通过规则确保从根结点到叶节点的最长路径的长度不超过最短路径的两倍。

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，重建出二叉树，假设两种遍历结果中都不含重复的数字（方便确定根结点在中序中的位置）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
BinaryTreeNode *Construct(int *preorder, int *inorder, int length) {
    if(preorder == NULL || inorder == NULL || length <= 0) {
        return NULL;
    }

    return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1)
}

BinaryTreeNode *ConstructCore(int * startPreorder, int *endPreorder, int *startInorder, int * endInorder) {
//    前序遍历第一个值就是根结点的值
    int rootValue = startInorder[0];
    BinaryTreeNode *root = new BinaryTreeNode();
    root->m_nValue = rootValue;
    root->m_pLeft = root->m_pRight = NULL;

    if(startPreorder == endPreorder) {
        if(startInorder == endInorder && *startPreorder == *startInorder) {
            return root;
        } else{
//            输入有问题
            return NULL;
        }
    }

//    在中序遍历中找到根结点的值
    int * rootInorder = startInorder;
    while(rootInorder <= endInorder && *rootInorder != rootValue) {
        ++rootInorder;
    }

    if(rootInorder == endInorder && *rootInorder != rootValue) {
//        输入有误
        return NULL;
    }

//    获取左子树的长度
    int leftLength = rootInorder - startInorder;
    int *leftPreorderEnd = startPreorder + leftLength;

    if(leftLength > 0) {
//        构建左子树
        root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
    }

    if(leftLength < endPreorder - startPreorder) {
//        构建右子树
        root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
    }

    return root;             
}

数组中只出现一次的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || array.length < 2) {
            return;
        }
        
        int temp = 0;
        for(int i = 0; i< array.length; i++) {
            temp ^= array[i];
        }
        
        int flag = 1;          // 标志异或出来的结果二进制表示中第一个为1的位置
        while((flag & temp) == 0) flag <<= 1;
        for(int i = 0; i< array.length; i++) {
            if((flag & array[i]) == 0) {
                num1[0] ^= array[i];
            } else {
                num2[0] ^= array[i];
            }
        }
    }
}

按之字形打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) {
            return result;
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(null);
        queue.addLast(pRoot);
        boolean leftToRight = true;
        
        while(queue.size() != 1) {
            TreeNode node = queue.removeFirst();
            if(node == null) {        // 到达分层分隔符
                Iterator<TreeNode> iter = null;
                if(leftToRight) {
                    iter = queue.iterator();        // 从前往后遍历
                } else {
                    iter = queue.descendingIterator();             // 从后往前遍历
                }
                leftToRight = !leftToRight;
                while(iter.hasNext()) {
                    TreeNode temp = (TreeNode) iter.next();
                    list.add(temp.val);
                }
                result.add(new ArrayList<Integer>(list));
                list.clear();
                queue.addLast(null);           // 添加分隔符
                continue;
            }
            
            if(node.left != null) {
                queue.addLast(node.left);
            }
            if(node.right != null) {
                queue.addLast(node.right);
            }
        }
        
        return result;
    }

}

从上到下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayList;
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        
        LinkedList<TreeNode> queue =new LinkedList<>();
        queue.addLast(null);
        queue.addLast(root);
        
        while(queue.size() != 1) {
            TreeNode node = queue.removeFirst();
            if(node == null) {
                // 一层已经结束
                Iterator<TreeNode> iter = null;
                iter = queue.iterator();
                while(iter.hasNext()) {
                    TreeNode temp = (TreeNode) iter.next();
                    list.add(temp.val);
                }
                queue.addLast(null);
                continue;
            }
            if(node.left != null) {
                queue.addLast(node.left);
            }
            
            if(node.right != null) {
                queue.addLast(node.right);
            }
        }
        
        return list;
        
        
    }
}

二叉树中和为某个值的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) {
            return listAll;
        }
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) {
            listAll.add(new ArrayList<Integer>(list));
        }
        
        FindPath(root.left, target);
        FindPath(root.right, target);
        list.remove(list.size() - 1);
        return listAll;
    }
}

序列化二叉树+反序列化二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    int index = -1;
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null) {
            sb.append("#,");
            return sb.toString();
        }
        
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    
    TreeNode Deserialize(String str) {
        index++;
        String[] strr = str.split(",");
        TreeNode  node = null;
        if(!strr[index].equals("#")) {
            node = new TreeNode(Integer.valueOf(strr[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        
        return node;
    }
}

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = null;
        ListNode pNode = head;
        ListNode pPrev = null;
        while(pNode != null) {
            ListNode pNext = pNode.next;
            if(pNext == null) {
                newHead = pNode;
            }
            
            pNode.next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        
        return newHead;
    }
}

判断链表中是不是有环，以及环的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) {
            return null;
        }
        ListNode slow = pHead;     // 一次走1步
        ListNode fast = pHead;     // 一次走2步
        
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 找到相遇点
            if(slow == fast) {
                fast = pHead;
                // 找环的入口
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        
        return null;
    }
}

删除链表中重复节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) {
            return pHead;
        }
        
        ListNode nHead = new ListNode(0);
        nHead.next = pHead;
         
        ListNode pre = nHead;
        ListNode cur = pHead;
        
        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                // 找到最后一个相同节点
                while(cur.next != null && (cur.val == cur.next.val)) {
                    cur = cur.next;
                }

                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return nHead.next;
    }
}

二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        if(root.left == null && root.right == null) {
            return 1;
        }
        
        if(root.left == null || root.right == null) {
            return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
        }
        
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
}

从头到尾打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();
        ListNode cur = listNode;
        if(cur == null) {
            return result;
        }
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        Iterator<Integer> itr = list.descendingIterator();
        while(itr.hasNext()) {
            result.add(itr.next());
        }
        
        return result;
    }
}

链表中倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k < 0 || head == null) {
            return null;
        }
        
        ListNode temp = head;
        int length = 0;
        while(temp != null) {
            length++;
            temp = temp.next;
        }
        
        if(length < k) {
            return null;
        }
        
        temp = head;
        for(int i = 0; i < (length - k); i++) {
            temp = temp.next;
        }
        
        return temp;
        
    }
}

数组中超过一半的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 0) {
            return 0;
        }
        
        if(array.length == 1) {
            return array[0];
        }
        
        int count = 1;
        int k = array[0];
        for(int i = 1; i< array.length; i++) {
            if(array[i] == k) {
                count++;
            } else {
                count--;
                if(count == 0) {
                    k = array[i];
                    count = 1;
                }
            }
        }
        
        if(count > 1  || (count == 1 && k != array[array.length - 1])) {
            return k;
        }
        
        return 0;
    }
}

二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public void Mirror(TreeNode root) {
        if(root != null) {
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = temp;
            Mirror(root.left);
            Mirror(root.right);
        }
    }
}

判断是否是树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
public class TreeNode {
    int val = 0; 
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean isSubTree = false;
        if(root1 == null || root2 == null) {
            return false;
        }
        
        if(root1.val == root2.val) {
            isSubTree = judgeSubTree(root1, root2);
        }
        
        if(!isSubTree) {
            isSubTree = HasSubtree(root1.left, root2);
        }
        
        if(!isSubTree) {
            isSubTree = HasSubtree(root1.right, root2);
        }
        
        return isSubTree;
    }
    
    private boolean judgeSubTree(TreeNode root1, TreeNode root2) {
        if(root2 == null) {
            return true;
        }
        
        if(root1 == null) {
            return false;
        }
        
        if(root1.val != root2.val) {
            return false;
        }
        
        return judgeSubTree(root1.left, root2.left) && judgeSubTree(root1.right, root2.right);
    }
    
}

连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
使用动态规划
F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max（F（i-1）+array[i] ， array[i]）
res：所+有子数组的和的最大值
res=max（res，F（i））

import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length == 0) {
            return 0;
        }
        int res = array[0];
        int tempsum = array[0];
        for(int i = 1; i < array.length; i++) {
            tempsum = Math.max(tempsum + array[i], array[i]);
            res = Math.max(tempsum, res);
        }
        return res;
    }
}

数组中重复数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        for(int i = 0; i< length; i++) {
            int index = numbers[i] % length;
            if(numbers[index] >= length) {
                duplication[0] = numbers[i] % length;
                return true;
            }
            numbers[index] = numbers[index] + length;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
把当前序列当成是一个下标和下标对应值是相同的数组；
遍历数组，判断当前位的值和下标是否相等： 2.1. 若相等，则遍历下一位； 2.2. 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则成功！若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2.

链接：https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8
来源：牛客网

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // 判断数组是否合法（每个数都在0~n-1之间）
    for ( int i=0; i<length; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // key step
    for( int i=0; i<length; i++ ){
        while( i!=array[i] ){
            if ( array[i] == array[array[i]] ) {
                duplication[0] = array[i];
                return true;
            }

            int temp = array[i];
            array[i] = array[array[i]];
            array[array[i]] = temp;
        }
    }

    return false;
}

跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int JumpFloor(int target) {
        if(target <= 0) {
            return 0;
        }
        
        if(target == 1) {
            return 1;
        }
        
        if(target == 2) {
            return 2;
        }
        
        int f_1 = 1;
        int f_2 = 2;
        int result = 0;
        for(int i = 0; i < target - 2; i++) {
            result = f_1 + f_2;
            f_1 = f_2;
            f_2 = result;
        }
        
        return result;
    }
}

变态跳台阶

1
2
3
4
5
6
7
8
9
public class Solution {
    public int JumpFloorII(int target) {
        if(target <= 0) {
            return 0;
        }
        int a = 1;
        return a << (target - 1);
    }
}

leetcode

计算从上到下路径和最小的值。

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int depth = triangle.size();
        for(int i = depth - 2; i >= 0; i--) {
            for(int j = 0; j < triangle.get(i).size(); j++) {
                triangle.get(i).set(j, Math.min(triangle.get(i).get(j) + triangle.get(i + 1).get(j), 
                                                         triangle.get(i).get(j) + triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

二叉树两个子节点的公共祖先

从根节点开始遍历，如果node1和node2中的任一个和root匹配，那么root就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先. 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 发现目标节点，就通过返回值标记孩子树发现了某个目标节点
        if(root == null || root == p || root == q) return root;
        
        // 查看左子树是否有目标节点，没有返回null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        
        // 查看右子树是否有目标节点，没有返回null
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        //都不为空，说明左 右子树都有目标结点，则公共祖先就是本身  
        if(left != null && right != null) return root;
        
        // 如果发现了目标节点，则继续向上标记为该目标节点
        return left == null ? right : left;
    }
}

二叉树后序遍历

递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        
        test(root, list);
        return list;
    }
    
    private void test(TreeNode root, ArrayList<Integer> list) {
        if(root.left != null) {
            test(root.left, list);
        }
        
        if(root.right != null) {
            test(root.right, list);
        }
        
        list.add(root.val);
    }
}

非递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            if((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))){
                list.add(cur.val);
                stack.pop();
                pre = cur;
            } else {
                if(cur.right != null) {
                    stack.push(cur.right);
                }
                if(cur.left != null) {
                    stack.push(cur.left);
                }
            }
        } 
        
        return list;
    }
}

二叉树先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if(temp.right != null) {
                stack.add(temp.right);
            }
            if(temp.left != null) {
                stack.add(temp.left);
            }
        }
        return list;
    }
}

二叉树的最小深度

递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        if(root.left == null && root.right == null) {
            return 1;
        }
        
        if(root.left == null || root.right == null) {
            return Math.max(run(root.left), run(root.right)) + 1;
        }
        return Math.min(run(root.left), run(root.right)) + 1;
    }
}

非递归:

广度优先遍历，也就是层级遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public int run(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        if(root.left == null && root.right == null) {
            return 1;
        }
        
        Queue queue = new LinkedList();
        queue.offer(root);
        int level = 1;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = (TreeNode) queue.poll();
                if(node.left == null && node.right == null) {
                    return level;
                }
                
                if(node.left != null) {
                    queue.add(node.left);
                }
                
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            level+=1;
        }
        return level;
    }
}

最多共线点数

这道题给了我们一堆二维点，然后让我们求最大的共线点的个数，根据初中数学我们知道，两点确定一条直线，而且可以写成y = ax + b的形式，所有共线的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率，每个斜率代表一条直线，对每一条直线，带入所有的点看是否共线并计算个数，这是整体的思路。但是还有两点特殊情况需要考虑，二是当两个点重合时，无法确定一条直线，但这也是共线的情况，需要特殊处理。二是斜率不存在的情况，由于两个点(x1, y1)和(x2, y2)的斜率k表示为(y2 - y1) / (x2 - x1)，那么当x1 = x2时斜率不存在，这种共线情况需要特殊处理。我们需要用到哈希表来记录斜率和共线点个数之间的映射，其中第一种重合点的情况我们假定其斜率为INT_MIN，第二种情况我们假定其斜率为INT_MAX，这样都可以用map映射了。我们还需要顶一个变量duplicate来记录重合点的个数，最后只需和哈希表中的数字相加即为共线点的总数.

由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标，而求GCD的函数如果用递归来写那么一行就搞定了，叼不叼，这个方法能很好的避免除法的出现，算是牺牲了空间来保证精度吧，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import java.util.*;
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        int res = 0;
        for(int i = 0; i < points.length; i++) {
            Map<Map<Integer, Integer>, Integer> map = new HashMap<>();
            // 保存重合点的个数
            int duplicate = 1;
            for(int j = i + 1; j < points.length; ++j) {
                // 重合点
                if(points[i].x == points[j].x && points[i].y == points[j].y) {
                    ++duplicate;
                    continue;
                }
                
                // 计算斜率
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                
                // 计算最大公约数
                int d = gcd(dx, dy);
                Map<Integer, Integer> t = new HashMap<>();
                t.put(dx / d, dy / d);
                map.put(t, map.getOrDefault(t, 0) + 1);
            }
            
            res = Math.max(res, duplicate);
            for(Map.Entry<Map<Integer, Integer>, Integer> e: map.entrySet()) {
                res = Math.max(res, e.getValue() + duplicate);
            }
        }
        return res;
    }
    
    public int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
}

计算已生成语法树的表达式的值

利用异常，判断是否是操作符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i = 0; i< tokens.length; i++) {
            try {
                int num = Integer.parseInt(tokens[i]);
                stack.add(num);
            } catch(Exception e) {
                int b = stack.pop();
                int a = stack.pop();
                stack.add(get(a, b, tokens[i]));
            }
        }
        
        return stack.pop();
    }
    
    private int get(int a, int b, String operator) {
        switch(operator) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "/":
                return a / b;
            case "*":
                return a * b;
            default:
                return 0;
        }
    }
}

在O(nlogn)时间内排序链表

因为题目要求复杂度为T: O(nlogn), S: O(1)故可以考虑归并排序的思想。

归并排序的一般步骤为：

1）将待排序数组（链表）取中点并一分为二；

2）递归地对左半部分进行归并排序；

3）递归地对右半部分进行归并排序；

4）将两个半部分进行合并（merge）,得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        // 如果链表为空
        if(head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = getMid(head);
        ListNode midNext = mid.next;
        // 将链表截为两段落
        mid.next = null;
        return mergeSort(sortList(head), sortList(midNext));
    }
    
    /**
     * 获取链表中间的节点
     */
    private ListNode getMid(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head, quick = head;
        while(quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        
        return slow;
    }
    
    // 合并两个链表
    private ListNode mergeSort(ListNode n1, ListNode n2) {
        if(n1 == null)
            return n1;
        if(n2 == null)
            return n2;
        
        ListNode first = n1.next, second = n2.next;
        ListNode res; // 指向当前已排好序的最后一个节点
        ListNode newHead;
        if(n1.val < n2.val) {
            newHead = res = n1;
            second = n2;
        } else {
            newHead = res = n2;
            first = n1;
        }
        
        while(first != null || second != null) {
            if(first == null) {
                //第一条链表空
                res.next = second;
                return newHead;
            }else if(second == null) {
                // 第二条链表空
                res.next = first;
                return newHead;
            } else if(first.val < second.val) {
               // 第一个值比较小
                res.next = first;
                first = first.next;
                res = res.next;
            } else {
                res.next = second;
                second = second.next;
                res = res.next;
            }
        }
        
        return newHead;
    }
}

快速排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }
    
    private void quickSort(ListNode head, ListNode end) {
        if(head != end) {
            ListNode partion = partion(head);
            quickSort(head, partion);
            quickSort(partion.next, end);
        }
    }
    
    private ListNode partion(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null) {
            if(fast.val < head.val) {
                slow = slow.next;
                // 交换值
                fast.val = slow.val ^ fast.val ^ (slow.val = fast.val);
            }
            
            fast  = fast.next;
        }
        
        slow.val = head.val ^ slow.val ^ (head.val = slow.val);
        return slow;
    }
}

链表插入排序

创建一个新的链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dumy = new ListNode(Integer.MIN_VALUE);
        ListNode cur = head;
        ListNode pre = dumy;
        while(cur != null) {
            ListNode next = cur.next;
            pre = dumy;
            // 寻找节点正确节点
            while(pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            
            // 将当前节点添加到链表中
            cur.next = pre.next;
            pre.next = cur;
            
            // 处理下一个节点
            cur = next;
        }
        
        return dumy.next;
    }
}

合并两个排序链表

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        
        if(l2 == null) {
            return l1;
        }
        
        ListNode newHead, res;
        ListNode first = l1.next;
        ListNode second = l2.next;
        
        if(l1.val < l2.val) {
            newHead = l1;
            res = l1;
            second = l2;
        } else {
            newHead = l2;
            res = l2;
            first = l1;
        }
        
        while(first != null || second != null) {
            if(first == null) {
                res.next = second;
                return newHead;
            } else if(second == null) {
                res.next = first;
                return newHead;
            } else if(first.val < second.val) {
                res.next = first;
                first = first.next;
                res = res.next;
            } else {
                res.next = second;
                second = second.next;
                res = res.next;
            }
        }
        
        return newHead;
    }
}

递归排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        
        if(l2 == null) {
            return l1;
        }
        
        ListNode head;
        if(l1.val > l2.val) {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        } else {
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        }
        
        return head;
    }
}

寻找字符串中没有重复的最长子串

滑动窗口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }
        
        // 新建一个map进行存储char
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int leftBound = 0;
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 窗口左边可能为下一个char,可能不变
            leftBound = Math.max(leftBound, (map.containsKey(c)) ? map.get(c) + 1 : 0);
            max = Math.max(max, i - leftBound + 1);    // 当前窗口长度
            map.put(c, i);
        }
        
        return max;
    }
}

word pattrern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

class Solution {
public boolean wordPattern(String pattern, String str) {
        if(pattern == null || str == null) {
            return false;
        }
        String[] words = str.split(" ");
        if(words.length != pattern.length()) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
    
        for(int i = 0; i< pattern.length(); i++) {
            char c = pattern.charAt(i);
            if(map.containsKey(c)) {
                if(!map.get(c).equals(words[i])) {
                    return false;
                }            
            } else {
                if(map.containsValue(words[i])) {
                    return false;
                }
                
                map.put(c, words[i]);
            }
        }
        return true;
    }
}

相同子集和分割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.offer_shua;

import java.util.ArrayList;

/**
 * @author HT
 * @version V1.0
 * @package com.offer_shua
 * @date 2019-03-16 16:10
 */
public class SumEqual {
    public static void main(String [] args) {
        int [] nums = {1, 5, 10, 5, 1};
        boolean isCan = canPartition(nums);
        if(isCan) {
            System.out.println("ok");
        }
    }

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num: nums) {
            sum += num;
        }

        if(sum % 2 == 1) return false;
        int target = sum >> 1;

        int [] enough = new int[target + 1];
        for(int i = 0; i< target + 1; i++) {
            enough[i] = -1;
        }
        boolean [] dp = new boolean[target + 1];
        dp[0] = true;

        int j = 0;
        for(int num : nums) {
            for(int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
                if(dp[i] && enough[i] == -1) {
                    enough[i] = j;
                }
            }

            j++;
        }

        ArrayList<Integer> list = new ArrayList<>();
        while(target != 0) {
            list.add(enough[target]);
            target = target - nums[enough[target]];
        }

        StringBuffer str1 = new StringBuffer("");
        StringBuffer str2 = new StringBuffer("");
        for(int i = 0; i < nums.length; i++) {
            if(list.contains(i)) {
                str1.append(nums[i]).append(" ");
            } else {
                str2.append(nums[i]).append(" ");
            }
        }

        System.out.println(str1);
        System.out.println(str2);
        return dp[target];
    }
}

杂项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package com.offer_shua;
import com.sun.org.apache.xpath.internal.SourceTree;

import java.nio.charset.Charset;
import java.util.*;

/**
 * @author HT
 * @version V1.0
 * @package com.offer_shua
 * @date 2019-03-08 10:48
 */
public class MatchJudger {
    private Map<Character, Character> pair = null;

    public MatchJudger() {
        pair = new HashMap<>();
        pair.put(')', '(');
        pair.put('}', '[');
        pair.put('}', '{');
    }

    public boolean isMatch(String s) {
        Stack<Character> sc = new Stack<>();
        for(int i = 0; i< s.length(); i++) {
            Character c = s.charAt(i);
            if(pair.containsValue(c)) {
                sc.push(c);
            } else if(pair.containsKey(c)) {
                if(sc.empty()) {
                    return false;
                } else {
                    if(Objects.equals(sc.peek(), pair.get(c))) {
                        sc.pop();
                    } else {
                        return false;
                    }
                }
            }
        }

        return sc.isEmpty();
    }

    public static void main(String [] args) {
        MatchJudger matchJudger = new MatchJudger();
        System.out.println(matchJudger.isMatch("{******}()()"));
    }
}

如何给100亿个数字排序

实现思路

1.把这个37GB的大文件，用哈希分成1000个小文件，每个小文件平均38MB左右（理想情况），把100亿个数字对1000取模，模出来的结果在0到999之间，每个结果对应一个文件，所以我这里取的哈希函数是 h = x % 1000，哈希函数取得”好”，能使冲突减小，结果分布均匀。

2.拆分完了之后，得到一些几十MB的小文件，那么就可以放进内存里排序了，可以用快速排序，归并排序，堆排序等等。

3.1000个小文件内部排好序之后，就要把这些内部有序的小文件，合并成一个大的文件，可以用二叉堆来做1000路合并的操作，每个小文件是一路，合并后的大文件仍然有序。

首先遍历1000个文件，每个文件里面取第一个数字，组成 (数字, 文件号) 这样的组合加入到堆里（假设是从小到大排序，用小顶堆），遍历完后堆里有1000个 (数字，文件号) 这样的元素
然后不断从堆顶拿元素出来，每拿出一个元素，把它的文件号读取出来，然后去对应的文件里，加一个元素进入堆，直到那个文件被读取完。拿出来的元素当然追加到最终结果的文件里。
按照上面的操作，直到堆被取空了，此时最终结果文件里的全部数字就是有序的了。

注：堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。

JAVA 利用HashMap实现LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.offer_shua;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author HT
 * @version V1.0
 * @package com.offer_shua
 * @date 2019-03-11 21:57
 */
public class LRU<K, V> {
    private static final float hashLoadFactory = 0.75f;
    private LinkedHashMap<K, V> map;
    private int cacheSize;

    public LRU(int cacheSize) {
        this.cacheSize = cacheSize;
        int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;

        map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > LRU.this.cacheSize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized void clear() {
        map.clear();
    }

    public synchronized int usedSize() {
        return map.size();
    }

    public void print() {
        for(Map.Entry<K, V> entry: map.entrySet()) {
            System.out.println(entry.getValue() + "--");
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package com.offer_shua;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author HT
 * @version V1.0
 * @package com.offer_shua
 * @date 2019-03-11 21:57
 */
public class LRU {
    public static class ListNode {
        int val = 0;
        String key = "";
        ListNode prev = null;
        ListNode next = null;

        public ListNode(String key, int val) {
            this.key = key;
            this.val = val;
        }

        public ListNode() {}
    }

    private int capacity = 1024;

    private Map<String, ListNode> table;

    private ListNode head;

    private ListNode tail;

    public LRU(){
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        head.prev = null;
        tail.prev = head;
        tail.next = null;
        this.table = new ConcurrentHashMap<>(capacity);
    }

    public LRU(int capacity) {
        this();
        this.capacity = capacity;
        this.table = new ConcurrentHashMap<>(capacity);
    }

    public Integer get(String key) {
        ListNode node = table.get(key);

//        如果node不在map中，说明没有缓存
        if(node == null) {
            return null;
        }

//        删除该节点
        node.prev.next = node.next;
        node.next.prev = node.prev;

//        移动节点到头部
        node.next = head.next;
        node.next.prev = node;
        node.prev = head;
        head.next = node;

//        添加到缓存表
        table.put(key, node);
        return node.val;
    }

    public void put(String key, Integer value) {
        ListNode node = table.get(key);
//        如果node不在表中
        if(node == null) {
            if(table.size() == capacity) {
//                删除尾部节点
                table.remove(tail.prev.key);
                ListNode delete = tail.prev;
                delete.prev.next = tail;
                tail.prev = delete.prev;
            }

            node = new ListNode(key, value);
            table.put(key, node);
        }

//      移动Node节点到表头
        node.next = head.next;
        node.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    public static void main(String[] args) {
        LRU cache = new LRU(4);
        cache.put("key1", 1);
        cache.put("key2", 2);
        cache.put("key3", 3);
        cache.put("key4", 4);
        cache.get("key2");
        cache.put("key5", 5);
        cache.get("key2");
    }
}

原文作者: Tianji

原文链接: https://www.tiandiwuji.top/posts/53933/

发表日期: March 6th 2019, 10:16:02 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 一天刷10道，bat不是梦啊，加油
  2. 2. T： 时间复杂度 S：空间复杂度
    1. 2.1. n个数，大小0-(n-1)，判断是否有重复
    2. 2.2. 判断是不是素数
    3. 2.3. n+1个数，大小1-n，判断是否有重复
    4. 2.4. 将空格替换为%20
    5. 2.5. 重建二叉树
    6. 2.6. 数组中只出现一次的数
    7. 2.7. 按之字形打印二叉树
    8. 2.8. 从上到下打印二叉树
    9. 2.9. 二叉树中和为某个值的路径
    10. 2.10. 序列化二叉树+反序列化二叉树
    11. 2.11. 反转链表
    12. 2.12. 判断链表中是不是有环，以及环的入口
    13. 2.13. 删除链表中重复节点
    14. 2.14. 二叉树的深度
    15. 2.15. 从头到尾打印链表
    16. 2.16. 链表中倒数第K个节点
    17. 2.17. 数组中超过一半的数
    18. 2.18. 二叉树的镜像
    19. 2.19. 判断是否是树的子结构
    20. 2.20. 连续子数组的最大和
    21. 2.21. 数组中重复数字
    22. 2.22. 跳台阶
    23. 2.23. 变态跳台阶
  3. 3. leetcode
    1. 3.1. 二叉树两个子节点的公共祖先
    2. 3.2. 二叉树后序遍历
    3. 3.3. 二叉树先序遍历
    4. 3.4. 二叉树的最小深度
    5. 3.5. 最多共线点数
    6. 3.6. 计算已生成语法树的表达式的值
    7. 3.7. 在O(nlogn)时间内排序链表
    8. 3.8. 链表插入排序
    9. 3.9. 合并两个排序链表
    10. 3.10. 寻找字符串中没有重复的最长子串
    11. 3.11. word pattrern
    12. 3.12. 相同子集和分割
  4. 4. 杂项
  5. 5. 如何给100亿个数字排序
  6. 6. JAVA 利用HashMap实现LRU
Total : 77
2099
2019
2018
pwn ctf web安全 ctf_php_debug 置顶 工具手册 dubbo jvm linux 运维 mysql php python python安全 前端 zookeeper 渗透测试 安全体系建设
安全