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
import java.util.*;
import java.lang.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        quicksort(nums);
        
        return nums[nums.length - k];
    }
    public void quicksort(int[] nums) {
        if(nums.length <= 1) {
            return;
        }else {
            quick(nums,0,nums.length - 1);
        }
    }
    public void quick(int[] nums,int left,int right) {
        if(left < right) {
            int index = partition(nums,left,right);
            //1.quick(nums,left,index - 1);而不是quick(nums,left,index);
            //因为[left,index - 1]都小于哨兵，[index + 1,right]都大于哨兵
            quick(nums,left,index - 1);
            quick(nums,index + 1,right);
        }
    }
    public int randomPartition(int[] nums,int left,int right) {
        Random random = new Random();
        int flag = random.nextInt(right - left + 1) + left;
        int privot = nums[flag];
        int index = left - 1;
        swap(nums,flag,right);
        for(int i = left;i <= right;i ++) {
            if(nums[i] <= privot) {
                index ++;
                swap(nums,i,index);
            }
        }
        return index;
    }
    //
    public int partition(int[] nums,int left,int right) {
        int privot = nums[left];
        //2.确定哨兵之后，和nums[right]交换是必须的
        //把nums[left]的值，放到最右侧，就是为了算法结束之后，nums[left]能把数组分成两部分，一部分是小于等于nums[left]的，另一部分是大于nums[left]的
        swap(nums,left,right);
        //index的意思是区间[left,index]都小于等于哨兵，因此index的初始值是left - 1，并当nums[i]小于哨兵，先让index增加
        int index = left - 1;
        for(int i = left;i <= right;i ++) {
            if(nums[i] <= privot) {
                index ++;
                swap(nums,i,index);
            }
        }
        return index;
    }
    public void swap(int[] nums,int index1,int index2) {
        int tem = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tem;
    }
}

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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0) {
            return new int[0];
        }else if(k >= arr.length) {
            return arr;
        }else {
            int[] heap = new int[k];
            for(int i = 0;i < k;i ++) {
                heap[i] = arr[i];
            }
            //1.对于数组heap要建大顶堆堆
            buildMaxHeap(heap,k);
            for(int i = k;i < arr.length;i ++) {
                //2.heap[0]是大顶堆最大的元素，如果arr[i]小于heap[0]，那么arr[i]就把heap[0]替换，从0开始调整堆，注意这里不是建堆
                if(arr[i] < heap[0]) {
                    heap[0] = arr[i];
                    heapify(heap,0,k);
                }
            }
            return heap;
        }   
    }
    //寻找前k个最小的数，用大顶堆。调整容量为k的大顶堆,k就是大顶堆的容量
    public void buildMaxHeap(int[] heap,int k) {
        //大顶堆heap[0]是最大的
        //3.建堆应该自底向上，不应该自上而下，因此下面的for循环是不对的
        /*
        for(int i = 0;i <= (k - 1) / 2;i ++) {
            heapify(heap,i,k);
        }
        */
        for(int i = (k - 1) / 2;i >= 0;i --) {
            heapify(heap,i,k);
        }
    }
    //4.调整heap[index]的左节点heap[2 * index  + 1]和右节点heap[2 * index + 2]，符合大顶堆的定义
    public void heapify(int[] heap,int index,int k) {
        if(index >= k) {
            return;
        }else {
            int leftindex = 2 * index + 1;
            int rightindex = 2 * index + 2;
            int maxindex = index;
            if(leftindex < k && heap[maxindex] < heap[leftindex]) {
                maxindex = leftindex;
            }
            if(rightindex < k && heap[maxindex] < heap[rightindex]) {
                maxindex = rightindex;
            }
            if(maxindex != index) {
                int tem = heap[index];
                heap[index] = heap[maxindex];
                heap[maxindex] = tem;
                //如果index和它的左节点或者右节点交换，应该考虑heap[index]被交换到heap[maxindex]会不会继续引发堆调整
                heapify(heap,maxindex,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
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
class Solution {
    //可以按任意顺序返回答案
    //时间复杂度必须优于 O(n log n)
    //前k个高频的，构建小顶堆
    HashMap<Integer,Integer> map;
    public int[] topKFrequent(int[] nums, int k) {
        map = new HashMap<>();
        //LinkedList<Integer> list = new LinkedList<>();
        if(nums.length == 0 || k == 0) {
            return new int[0];
        }else {
            for(int i = 0;i < nums.length;i ++) {
                if(map.containsKey(nums[i])) {
                    map.put(nums[i],map.get(nums[i]) + 1);
                }else {
                    map.put(nums[i],1);
                }
            }
            //keys是去重的nums元素
            int[] keys = new int[map.keySet().size()];
            int index = 0;
            for(int key : map.keySet()) {
                keys[index ++] = key;
                //System.out.println(index);
            }
            //答案不要求数组元素的顺序，如果k大于等于keys的长度，可以直接返回key
            if(k >= map.keySet().size()) {
                return keys;
            }else {
                int[] answer = new int[k];
                //1.把answer作为小顶堆，先填充数据，然后进行建堆
                for(int i = 0;i < k;i ++) {
                    answer[i] = keys[i];
                }
                //2.自下而上建小顶堆
                buildHeap(answer,k);
                for(int i = k;i < keys.length;i ++) {
                    if(map.get(keys[i]) > map.get(answer[0])) {
                        //3.替换堆顶元素，引发堆调整
                        answer[0] = keys[i];
                        heapify(answer,0);
                    }
                }
                return answer;
            }
        }
    }
    //4.建堆函数，自下而上调整，详见数据结构，不能自上而下，也就是不能for(i = 0;i < length;i ++){code}
    public void buildHeap(int[] heap,int length) {
        //把i --写成i ++导致错误
        //i建议从length开始，方便记忆
        //当然也可以从(length - 1) / 2 + 1开始，因为这个节点对应的左子树或者右子树是heap数组的最后一个节点
        /*
        for(int i = length;i >=0;i --) {
            heapify(heap,i);
        }
        */
        for(int i = (length - 1) / 2 + 1;i >=0;i --) {
            heapify(heap,i);
        }
    }
    //5.堆调整函数
    //调整heap[index]的左右子节点heap[2*index + 1],heap[2*index + 2],依据是他们出现的次数
    public void heapify(int[] heap,int index) {
        if(index >= heap.length) {
            return;
        }else {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int min = index;
            if(left < heap.length && map.get(heap[min]) > map.get(heap[left])) {
                min = left;
            }
            if(right < heap.length && map.get(heap[min]) > map.get(heap[right])) {
                min = right;
            }
            //小顶堆比较的依据不是元素的大小而是出现的次数
            /*
            if(right < heap.length && heap[min] > heap[right]) {
                min = right;
            }
            */
            if(min != index) {
                int tem = heap[index];
                heap[index] = heap[min];
                heap[min] = tem;
                //index和子节点交换之后，可能会触发新一轮的交换，因此要调用一下，这个时候，heap[min]保存的是之前heap[index]
                heapify(heap,min);
            }
        }
    }
}

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
class Solution {
    public String minNumber(int[] nums) {
        //
		/*
		Integer[] nums1 = new Integer[nums.length];
		for(int i = 0; i < nums.length;i ++) {
			nums1[i] = new Integer(nums[i]);
		}
        StringBuilder sb = new StringBuilder();
        Arrays.sort(nums1,new Comparator<Integer>() {
            public int compare(Integer a,Integer b) {
                return a * 10 + b - b * 10 + a;
            }
        });
        */
		String[] nums1 = new String[nums.length];
		for(int i = 0; i < nums.length;i ++) {
			nums1[i] = String.valueOf(nums[i]);
		}
        StringBuilder sb = new StringBuilder();
        Arrays.sort(nums1,new Comparator<String>() {
            public int compare(String a,String b) {
                //return Integer.parseInt(a + b) - Integer.parseInt(b + a);
                return (a + b).compareTo((b + a));
            }
        });
        for(int i = 0;i < nums1.length;i ++) {
            sb.append(nums1[i]);
        }
        return sb.toString();
    }
}

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.Arrays;
class Solution {
    public String largestNumber(int[] nums) {
        if(nums.length == 0) {
            return null;
        }else {
            //1.转化为String数组
            String[] strings = new String[nums.length];
            for(int i = 0;i < nums.length;i ++) {
                strings[i] = String.valueOf(nums[i]);
            }
            Arrays.sort(strings,new Comparator<String>(){
                
                public int compare(String a,String b) {
                    //错误return Integer.parseInt(a + b) - Integer.parseInt(b + a);
                    //2.比较字符串调用compareTo方法
                    return (b + a).compareTo(a + b);
                }
            });
            StringBuilder sb = new StringBuilder();
            if(strings[0].equals("0")) {
                return "0";
            }
            for(int i = 0;i < strings.length;i ++) {
                //错误sb.add(nums[i]);
                //3.详见StringBuilder的append方法，可以把基本数据类型转换为Character加入StringBuilder中
                sb.append(strings[i]);
            }
            return sb.toString();
        }
    }
}

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
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(k > nums.length){
            return 0;
        }
        /*
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(nums.length,(a,b) -> a - b);
        
        for(int i = 0;i < nums.length;i ++){
            minHeap.add(nums[i]);
        }
        for(int i = 0;i < nums.length - k;i ++){
            minHeap.poll();
        }
        return minHeap.peek();
        */
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a - b);
        for(int i = 0;i < k;i ++){
            minHeap.add(nums[i]);
        }
        for(int i = k;i < nums.length;i ++){
            if(nums[i] > minHeap.peek()){
                minHeap.poll();
                minHeap.add(nums[i]);
            }
        }
        return minHeap.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1){
            return s.length();
        }
        HashMap<Character,Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for(int i = 0;i < s.length();i ++){
            if(map.containsKey(s.charAt(i))){
                //更新left的时候与i无关
                left = Math.max(map.get(s.charAt(i)) + 1,left);
            }
            //更新max
            max = Math.max(max,i - left + 1);
            //添加map
            map.put(s.charAt(i),i);
        }
        return max;
    }
}

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
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode ans = reserveN(head,2);
        
        ans.next.next = swapPairs(ans.next.next);
        return ans;
    }
    ListNode lastofnext = null;
    //从head节点开始反转N个链表
    public ListNode reserveN(ListNode head,int N){
        if(N == 1){
            lastofnext = head.next;
            return head;
        }
        //last是指向反转后头节点的指针，因此应返回last
        ListNode last = reserveN(head.next,N - 1);
        head.next.next = head;
        head.next = lastofnext;
        //返回的是last而不是head
        return last;
    }
}

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
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length <= 1) {
            return nums.length;
        }else {
            HashSet<Integer> set = new HashSet<>();
            int answer = 1;
            int currentlength;
            int currentnumber;
            for(int i = 0;i < nums.length;i ++) {
                set.add(nums[i]);
            }
            for(int i = 0;i < nums.length;i ++) {
                //点睛之处，对于数N，如果N - 1也在set里，那么最长的递增序列一定不是从N开始的，
                //最长的递增序列，开始的数字X，set里肯定没有X - 1
                if(! set.contains(nums[i] - 1)) {
                    currentlength = 1;
                    currentnumber = nums[i];
                    while(set.contains(currentnumber + 1)) {
                        currentlength ++;
                        currentnumber ++;
                    }
                    answer = Math.max(answer,currentlength);
                }
                
            }
            return answer;
        }
    }
}

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
class Solution {
    StringBuilder sb;
    public String reverseWords(String s) {
        sb = new StringBuilder();
        //第一个单词变成最后一个单词，因此第一个单词加入sb的时候，不加空格
        getReverseWord(sb,s,0,false);
        return sb.toString();
    }
    //把单词存储到sb中，left表示从s的下标left开始添加下一个单词，flag表示在sb后面添加单词之后，sb后面还要不要加空格，原来的第一个单词加入sb之后，sb后面不需要加了
    public void getReverseWord(StringBuilder sb,String s,int left,boolean flag) {
        while(left < s.length() && s.charAt(left) == ' ') {
            left ++;
        }
        //left指向下一个单词的开始字母，或者left等于s.length()
        if(left == s.length()) {
            return;
        }
        int right = left;
        //right指向空格（left指向那个单词之后的第一个空格）或者right等于s.Length()
        while(right < s.length() && s.charAt(right) != ' ') {
            right ++;
        }
        getReverseWord(sb,s,right,true);
        //下面可以代替上面的for循环，
        //sb.append(s.substring(left,right));
        //为什么是小于right?因为right没有指向单词的字母
        
        for(int i = left;i < right;i ++) {
            sb.append(s.charAt(i));
        }
        
        if(flag) {
            sb.append(' ');
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String countAndSay(int n) {
         if(n == 1){
             return "1";
         }else{
            String before = countAndSay(n - 1);
            StringBuilder sb = new StringBuilder();
            int index = 0;
            while(index < before.length()){
                int counter = 1;
                char character = before.charAt(index);
                while(index + 1 < before.length()  && before.charAt(index + 1) == character){
                    index ++;
                    counter ++;
                }
                sb.append(counter);
                sb.append(character);
                index ++;
            }
            return sb.toString();
         }
    }
}

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
class Solution {
    //
    public ArrayList<Integer>[] graph;
    //点如果涂颜色，就加入map
    public HashMap<Integer,Integer> map;
    //0代表红色，1代表蓝色
    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph = new ArrayList[N + 1];
        map = new HashMap<Integer,Integer>();
        for(int i = 0;i <= N;i ++){
            graph[i] = new ArrayList<Integer>();
        }
        //graph[i]表示i + 1不能共存的链表
        for(int i = 0;i < dislikes.length;i ++){
            graph[dislikes[i][0]].add(dislikes[i][1]);
            graph[dislikes[i][1]].add(dislikes[i][0]);
        }
        for(int i = 1;i <= N;i ++){
            if(! map.containsKey(i) && ! dfs(i,0)){
                return false;
            }
        }
        return true;
    }
    //把node的节点涂成color，是否合理
    public boolean dfs(int node,int color){
        //如果node已经存在，判断node的值与color是否相同
        if(map.containsKey(node)){
            return map.get(node) == color;
        }
        //如果不含有key
        map.put(node,color);
        for(int i = 0;i < graph[node].size();i ++){
            //^是逐位 
            if(! dfs(graph[node].get(i),color ^ 1)){
                return false;
            }
        }
        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
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        //dp[i]代表凑成i元，需要的硬币个数
        int[] dp = new int[amount + 1];

        Arrays.sort(coins);
        for(int i = 0;i < coins.length && coins[i] <= amount;i ++){
            dp[coins[i]] = 1;
        }
        if(dp[amount] != 0){
            return dp[amount];
        }

        for(int i = coins[0];i <= amount;i ++){
            if(dp[i] == 1){
                continue;
            }else{
                //下面的超时间
                /*
                int min = Integer.MAX_VALUE;
                for(int j = coins[0];j <= i - coins[0];j ++){
                    if(dp[j] != 0 && dp[i - j] != 0){
                        min = Math.min(min,dp[j] + dp[i - j]);
                    }
                }
                if(min == Integer.MAX_VALUE){
                    dp[i] = 0;
                }else{
                    dp[i] = min;
                }
                */
                int min = Integer.MAX_VALUE;
                for(int j = 0;j < coins.length && coins[j] <= i;j ++){
                    if(dp[i - coins[j]] != 0){
                        min = Math.min(dp[coins[j]] + dp[i - coins[j]],min);
                    }
                    
                }
                dp[i] = min == Integer.MAX_VALUE ? 0 : min;
            }
        }
        //System.out.println(dp[10]);
        return dp[amount] == 0 ? -1 : dp[amount];
    }
    public int find(int[] array,int target){
        return 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int coinChange(int[] coins,int amount) {
        if(amount == 0){
            return 0;
        }
        int[] dp =new int[amount + 1];
        //第一个不一样的地方
        Arrays.fill(dp,amount + 1);
        //循环计算dp[i]
        //第二个不一样的地方
        dp[0] = 0;
        //金钱的循环再外面，否则会出现重复的情况
        for(int coin : coins){
            for(int i = coin;i <= amount;i ++){
                //第三个不一样的地方
                dp[i] = Math.min(dp[i],dp[i - coin] + 1);
            }
        }
        //第四个不一样的地方
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //类似于爬楼梯
    public int change(int amount, int[] coins) {
        if(amount == 0){
            return 1;
        }
        int[] dp =new int[amount + 1];
        //循环计算dp[i]
        dp[0] = 1;
        //金钱的循环再外面，否则会出现重复的情况
        for(int coin : coins){
            for(int i = coin;i <= amount;i ++){
                //相当于爬楼梯问题
                //dp[n] = dp[n - 1] + dp[n - 2]
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //递减栈的思想
    public int[] dailyTemperatures(int[] T) {
        if(T.length <= 1){
            return new int[T.length];
        }else{
            //存储数据并不方便，因为还要得到数组下标，因此不如直接存储下标
            Stack<Integer> stack = new Stack<>();
            int[] answer = new int[T.length];
            for(int i = 0;i < T.length;i ++){
                while(! stack.isEmpty() && T[i] > T[stack.peek()]){
                    answer[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
            return answer;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //按照身高递减，身高相同排名递增的顺序重新排列二维数组
        Arrays.sort(people,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });
        List<int[]> list = new LinkedList<>();
        for(int[] p : people){
            //在list的指定下标插入数据
            list.add(p[1],p);
        }
        return list.toArray(new int[people.length][2]);
    }
}

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
class LRUCache {
    public int capacity;
    public HashMap<Integer,Integer> map;
    public LinkedList<Integer> list;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }
    
    public int get(int key) {
        //
        if(map.containsKey(key)){
            /*
            //使用就把key从list中取出来加到队尾
            int index = 0;
            for(int i = 0;i < list.size();i ++){
                if(list.get(i) == key){
                    index = i;
                    break;
                }
            }
            list.remove(index);
            list.addLast(key);
            */
            //应该注意remove(index)和remove(Object key)的区别
            //这里不能直接remove(key)
            list.remove((Integer) key);
            list.addLast(key);
            return map.get(key);
        }else{
            return  -1;
        }
    }
    
    public void put(int key, int value) {
        //如果有key存在也触发使用条件
        if(map.containsKey(key)){
            list.remove((Integer) key);
            list.addLast(key);
            map.put(key,value);
        }else if(list.size() < capacity){
            //长度小于capacity可以put
            map.put(key,value);
            list.addLast(key);
        }else{
            map.remove(list.getFirst());
            list.removeFirst();
            map.put(key,value);
            list.addLast(key);
        }
    }
}

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
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if(rec1.length != 4 || rec2.length != 4){
            throw new IllegalArgumentException();
        }else{
            
            int[] array1 = {rec1[0],rec1[2]};
            int[] array2 = {rec2[0],rec2[2]};
            int[] array3 = {rec1[1],rec1[3]};
            int[] array4 = {rec2[1],rec2[3]};
            if(judge(array1,array2) && judge(array3,array4)){
                return true;
            }else{
                return false;
            }
        }
    }
    //降维
    public boolean judge(int[] array1,int[] array2){
        if(array1.length != 2 || array2.length != 2){
            return false;
        }else{
            
            if(array1[0] <= array2[0]){
                //根据题意等于不对
                if(array1[1] > array2[0]){
                    return true;
                }
            }else{
                if(array2[1] > array1[0]){
                    return true;
                }
            }
            return false;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }else if(x < 10){
            return true;
        }else{
            String number = Integer.toString(x);
            int left = 0;
            int right = number.length() - 1;
            while(left < right){
                if(number.charAt(left) != number.charAt(right)){
                    return false;
                }else{
                    left ++;
                    right --;
                }
            }
            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
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }else if(x < 10){
            return true;
        }else{
            int div = 1;
            int tem = x;
            //必须是大于等于10
            while(tem >= 10){
                tem = tem / 10;
                div *= 10;
            }
            //System.out.println(div);
            //x >= 10不对，无法解决1000021的情况
            while(x > 0){
                int left = x % 10;
                int right = x / div;
                if(left != right){
                    return false;
                }else{
                    //原来的x除去最高位和最低位
                    x = (x % div) / 10;
                    div = div / 100;
                }
            }
            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
class Solution {
    public String multiply(String num1, String num2) {
        //999*999=998001
        //x位的数乘以y位的数，结果肯定是x+y位的数
        if(num1 == null){
            return num2;
        }else if(num2 == null){
            return num1;
        }else if(num1.equals("0") || num2.equals("0")){
            //不应该用==，应该用.equals()
            return "0";
        }else{
            int[] answer = new int[num1.length() + num2.length()];
            /*
            int number1;
            int number2;
            */
            //经过反转之后，个位在0
            num1 = reverse(num1);
            num2 = reverse(num2);
            for(int i = 0;i < num1.length();i ++){
                for(int j = 0;j < num2.length();j ++){
                    //最后统一进位
                    answer[i + j] += ((num1.charAt(i) - '0') * (num2.charAt(j) - '0'));
                    /*
                    answer[i + j] += (number1 * number2) % 10;
                    answer[i + j + 1] += (number1 * number2) / 10;
                    */
                }
            }
            //统一进位，注意一个是等于一个是加等于,并且顺序不能反
            for(int i = 0;i < answer.length - 1;i ++){
                /*
                answer[i] = answer[i] % 10;
                answer[i + 1] += answer[i] / 10;
                */
                answer[i + 1] += answer[i] / 10;
                answer[i] = answer[i] % 10;
            }
            StringBuilder sb = new StringBuilder();
            int i = 0;
            for(i = answer.length - 1;i >= 0;i --){
                if(answer[i] != 0){
                    break;
                }
            }
            for(;i >= 0;i --){
                sb.append(answer[i]);
            }
            return sb.toString();
        }
    }
    //反转字符串函数
    public String reverse(String num){
        if(num == null){
            return null;
        }else{
            StringBuilder sb = new StringBuilder();
            for(int i = num.length() - 1;i >= 0;i --){
                sb.append(num.charAt(i));
            }
            return sb.toString();
        }
    }
}

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
//解法：快慢指针+双指针
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode node = getNode(head);
        //面试写的时候，就是忘记判断node == null，导致NullPointerException
        if(node == null) {
            return null;
        }else {
            ListNode answer = head;
            int length = getLength(node);
            //让front先向前走length步，answer和front一起往后一次走一步
            ListNode front = head;
            for(int i = 0;i < length;i ++) {
                front = front.next;
            }
            while(answer != front) {
                answer = answer.next;
                front = front.next;
            }
            return answer;
        }
    }
    //如果有环，得到环的长度
    public int getLength(ListNode node) {
        int answer = 1;
        ListNode tem = node.next;
        while(node != tem) {
            answer ++;
            tem = tem.next;
        }
        return answer;
    }
    //快慢指针，返回的要么是环中的节点，要么是null
    public ListNode getNode(ListNode head) {
        if(head == null) {
            return null;
        }else {
            ListNode fast = head.next;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
                if(fast == slow) {
                    return fast;
                }
                slow = slow.next;
                
                fast = fast.next.next;
            }
            return null;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    //直接求nums数组的和可能会溢出
    public int missingNumber(int[] nums) {
        if(nums.length == 0){
            throw new IllegalArgumentException();
        }else{
            int sum = 0;
            for(int i = 0;i < nums.length;i ++){
                sum += nums[i];
            }
            return nums.length * (nums.length + 1) / 2 - sum;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //直接求nums数组的和可能会溢出
    public int missingNumber(int[] nums) {
        if(nums.length == 0){
            throw new IllegalArgumentException();
        }else{
            /*
            int sum = 0;
            for(int i = 0;i < nums.length;i ++){
                sum += nums[i];
            }
            return nums.length * (nums.length + 1) / 2 - sum;
            */
            //原理和上面的一样，但是避免了int溢出
            int result = 0;
            for(int i = 1;i <= nums.length;i ++){
                result += i - nums[i - 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
38
39
40
class Solution {
    //存储答案的Stringbuilder的先存储
    public String addBinary(String a, String b) {
        if(b == null || b.equals("0")){
            return a;
        }else if(a == null || a.equals("0")){
            return b;
        }else{
            int index1 = a.length() - 1;
            int index2 = b.length() - 1;
            int number = 0;
            int sum = 0;
            StringBuilder sb = new StringBuilder();
            while(index1 >= 0 && index2 >= 0){
                sum = number + (a.charAt(index1) - '0') + (b.charAt(index2) - '0');
                number = sum / 2;
                sb.append(sum % 2);
                index1 --;
                index2 --;
            }
            while(index1 >= 0){
                sum = (a.charAt(index1) - '0') + number;
                number = sum / 2;
                sb.append(sum % 2);
                index1 --;
            }
            while(index2 >= 0){
                sum = (b.charAt(index2) - '0') + number;
                number = sum / 2;
                sb.append(sum % 2);
                index2 --;
            }
           
            if(number != 0){
                sb.append(number);
            }
            return sb.reverse().toString();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
class Solution {
    //异或是逐位异或的，比如0^3=3
    public int missingNumber(int[] nums) {
        int answer = 0;
        for(int i = 0;i < nums.length;i ++){
            answer ^= (i ^ nums[i]);
        }
        return answer ^ nums.length;
    }
}

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
class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0){
            return true;
        }else if(s.length() % 2 == 1) {
            return false;
        }else {
            HashMap<Character,Character> map = new HashMap<>();
            map.put(')','(');
            map.put('}','{');
            map.put(']','[');
            Stack<Character> stack = new Stack<>();
            for(int i = 0;i < s.length();i ++){
                char c = s.charAt(i);
                if(! map.containsKey(c)){
                    stack.push(c);
                }else{
                    if(! stack.isEmpty() && stack.peek() == map.get(c)){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
            return stack.isEmpty();
            /*
            map.put('(',1);
            map.put(')',-1);
            map.put('[',2);
            map.put(']',-2);
            map.put('{',3);
            map.put('}',-3);
            Stack<Character> stack = new Stack<>();
            for(int i = 0;i < s.length();i ++){
                if(! map.containsKey(s.charAt(i))){
                    return false;
                }else if(map.get(s.charAt(i)) > 0){
                    stack.push(s.charAt(i));
                }else{
                    if(! stack.isEmpty() 
                    && (map.get(s.charAt(i)) + map.get(stack.peek()) == 0)){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
            
            if(stack.isEmpty()){
                return true;
            }else{
               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
class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length <= 1){
            return;
        }else{
            //忘记写下面一句
            k = k % nums.length;
            reverse(nums,0,nums.length - 1);
            reverse(nums,0,k -1);
            reverse(nums,k,nums.length - 1);
        }
    }
    public void reverse(int[] nums,int left,int right){
        int tem = 0;
        //当left = right的情况下，循环结束
        //当一开始的时候，left = right，不需要反转
        while(left < right){
            tem = nums[left];
            nums[left] = nums[right];
            nums[right] = tem;
            //忘记写下面的两句了
            left ++;
            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
class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length <= 1 || k < 1){
            return;
        }else{
            //忘记写下面一句
            k = k % nums.length;
            //counter表示已经交换的个数
            int counter = 0;
            int index = 0;
            int start = 0;
            int pre;
            int tem = 0;
            while(counter < nums.length){
                index = start;
                pre = nums[start];
                do{
                    int next = (index + k) % nums.length;
                    tem = nums[next];
                    nums[next] = pre;
                    pre = tem;
                    index = next;
                    next = (next + k) % nums.length;
                    counter ++;
                } while(index != start);
                start = (start + 1) % nums.length;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestPalindrome(String s) {
        if(s.length() == 0 && s.length() == 1) {
            return s.length();
        }else {
            HashMap<Character,Integer> map = new HashMap<>();
            int answer = 0;
            for(int i = 0;i < s.length();i ++) {
                if(map.containsKey(s.charAt(i))) {
                    map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
                }else {
                    map.put(s.charAt(i), 1);
                }
            }
            for(char key : map.keySet()){
                answer += map.get(key) % 2;
            }
            return answer == 0 ? s.length() : s.length() - answer + 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
38
class Solution {
    //flag表示题目所给的树是不是平衡二叉树，其值为false就表示不是平衡二叉树
    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }else {
            //最终目的不是为了获得dp函数的返回值，因此直接调用即可
            dp(root);
            return flag;
        }
    }
    //dp函数返回的数组，第一个元素表示左子树的高
    //第二个元素表示右子树的高
    public int[] dp(TreeNode root) {
        int[] answer = new int[2];
        //root为空直接返回
        //flag为false，表示题目中的树的子树已经失衡，直接返回即可
        if(root == null || flag == false) {
            return answer;
        }else {
            int[] left = dp(root.left);
            int[] right = dp(root.right);
            if(get(left[0],left[1]) > 1 || get(right[0],right[1]) > 1){
                flag = false;
            }
            answer[0] = Math.max(left[0],left[1]) + 1;
            answer[1] = Math.max(right[0],right[1]) + 1;
            if(get(answer[0],answer[1]) > 1){
                flag = false;
            }
            return answer;
        }
    }
    public int get(int a,int b){
        return Math.abs(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
36
37
38
class MinStack {
    //辅助栈存储的元素的多少每时每刻都和数据栈一样
    //辅助栈的栈顶元素对应数据栈从栈底到栈顶的最小值
    public Stack<Integer> datastack;
    public  Stack<Integer> helpstack;
    /** initialize your data structure here. */
    public MinStack() {
        this.datastack = new Stack<>();
        this.helpstack = new Stack<>();
    }
    
    public void push(int x) {
        //加入辅助栈的条件：1.辅助栈为空或者x小于辅助栈栈顶元素
        //2.否则，也就是辅助栈不为空并且栈顶元素小于x，那么辅助栈加入栈顶元素
        if(helpstack.isEmpty() || x < helpstack.peek()) {
            helpstack.push(x);
        }else {
            helpstack.push(helpstack.peek());
        }
        //加入数据栈
        datastack.push(x);
    }
    
    public void pop() {
        if(! datastack.isEmpty() && ! helpstack.isEmpty()) {
            datastack.pop();
            helpstack.pop();
        }
    }
    
    public int top() {
        return datastack.peek();
    }
    
    public int min() {
        return helpstack.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 0) {
            throw new IllegalArgumentException();
        }else if(nums.length == 1) {
            return nums[0];
        }else {
            int counter = 1;
            int number = nums[0];
            for(int i = 1;i < nums.length;i ++) {
                if(nums[i] == number) {
                    counter ++;
                }else {
                    counter --;
                }
                if(counter == 0) {
                    number = nums[i];
                    counter = 1;
                }
            }
            return number;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public char firstUniqChar(String s) {
        //s.equals('');
        if(s == null) {
            return ' ';
        }else {
            //用一个int的数组，来模拟HashMap
            //因为char是一个字节，二进制对应的阿西克码是0--255
            int[] array = new int[256];
            for(int i = 0;i < s.length();i ++) {
                //这是合法的，能自动把s.charAt(i)转化为对应的整数
                array[s.charAt(i)] += 1;
            }
            for(int i = 0;i < s.length();i ++) {
                if(array[s.charAt(i)] == 1) {
                    return s.charAt(i);
                }
            }
            return ' ';
        }
        
        
    }
}

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 Solution {
    //Insert one char from stringstream
    int[] array = new int[256];
    StringBuilder sb = new StringBuilder();
    public void Insert(char ch)
    {
        array[ch] += 1;
        sb.append(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //由于寻找的是字符流中的第一个出现一次的字符，因此下面不对
        //比如google，ggg#ll这是正确的输出，但是下面会输出ggg#le
        /*
        for(int i = 0; i < 256;i ++) {
            if(array[i] == 1) {
                return (char) i;
            }
        }
        return '#';
        */
        for(int i = 0;i < sb.length();i ++) {
            if(array[sb.charAt(i)] == 1) {
                return sb.charAt(i);
            }
        }
        return '#';
    }
}

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
public class Solution {
    //Insert one char from stringstream
    int[] array = new int[256];
    int index = 1;
    //StringBuilder sb = new StringBuilder();
    public void Insert(char ch)
    {
        if(array[ch] == 0) {
            array[ch] = index;
        }else {
            array[ch] = -1;
        }
        //sb.append(ch);
        index ++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //由于寻找的是字符流中的第一个出现一次的字符，因此下面不对
        //比如google，ggg#ll这是正确的输出，但是下面会输出ggg#le
        /*
        for(int i = 0; i < 256;i ++) {
            if(array[i] == 1) {
                return (char) i;
            }
        }
        return '#';
        */
        char answer = '';
        int minindex = Integer.MAX_VALUE;
        for(int i = 0;i < 256;i ++) {
            if(array[i] >= 1 && array[i] < minindex) {
                answer = (char) i;
                minindex = array[i];
            }
        }
        if(answer == '') {
            return '#';
        }else {
            return answer;
        }
        
    }
}

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
class Solution {
    public static HashMap<Character,Integer> map;
    public int romanToInt(String s) {
        if(s.length() == 0) {
            return 0;
        }else {
            map = new HashMap<>();
            map.put('I',1);
            map.put('V',5);
            map.put('X',10);
            map.put('L',50);
            map.put('C',100);
            map.put('D',500);
            map.put('M',1000);
            int prenumber = 0;
            int number = map.get(s.charAt(s.length() - 1));
            int answer = number;
            //number>=prenumber,answer += number否则asnwer -= number
            for(int i = s.length() - 2;i >= 0;i --) {
                prenumber = number;
                number = map.get(s.charAt(i));
                if(number >= prenumber) {
                    answer += number;
                }else {
                    answer -= number;
                }
            }
            return answer;
        }
    }
}

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
class Solution {
    public static HashMap<Integer,String> map;
    public String intToRoman(int num) {
        if(num == 0) {
            return null;
        }else {
            //关键的是把900,400,90,40,9,4的写法写出来，
            //600可以不写，因为DC是符合贪心规则的
            map = new HashMap<>();
            map.put(1000,"M");
            map.put(900,"CM");
            map.put(600,"DC");
            map.put(500,"D");
            map.put(400,"CD");
            map.put(100,"C");
            map.put(90,"XC");
            map.put(60,"LX");
            map.put(50,"L");
            map.put(40,"XL");
            map.put(10,"X");
            map.put(9,"IX");
            map.put(6,"VI");
            map.put(5,"V");
            map.put(4,"IV");
            map.put(1,"I");
            int[] array = {1000,900,600,500,400,100,90,60,50,40,10,9,6,5,4,1};
            StringBuilder sb = new StringBuilder();
            int number = 0;
            //判断条件增加一个num > 0剪枝，也可以不写
            for(int i = 0;i < array.length && num > 0;i ++) {
                number = num / array[i];
                for(int j = 0;j < number;j ++) {
                    sb.append(map.get(array[i]));
                }
                
                num = num % array[i];
            }
            return sb.toString();
        }
    }
}

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
class CQueue {
    //一个栈负责进栈，另一个栈负责出栈
    Stack<Integer> stackpush;
    Stack<Integer> stackpop;
    public CQueue() {
        this.stackpush = new Stack<>();
        this.stackpop = new Stack<>();
    }
    
    public void appendTail(int value) {
        stackpush.push(value);
    }
    
    public int deleteHead() {
        if(stackpop.isEmpty()) {
            if(stackpush.isEmpty()) {
                return -1;
            }else {
                while(! stackpush.isEmpty()) {
                    stackpop.push(stackpush.pop());
                }
                return stackpop.pop();
            }
        }else {
            return stackpop.pop();
        }
    }
}

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
//用两个栈，来回倒数，总是一个栈空另一个栈不空，或者两个栈都空
//可以认为进栈是addLast()出栈是removeFirst()
class MyStack {
    //java中LinkedList实现了Queue接口
    LinkedList<Integer> list1;
    LinkedList<Integer> list2;
    /** Initialize your data structure here. */
    public MyStack() {
        this.list1 = new LinkedList<>();
        this.list2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        if(list1.isEmpty()) {
            list2.addLast(x);
        }else if(list2.isEmpty()) {
            list1.addLast(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(this.empty()) {
            return -1;
        }else if(list1.isEmpty()) {
            while(list2.size() != 1) {
                list1.addLast(list2.removeFirst());
            }
            return list2.removeLast();
        }else {
            while(list1.size() != 1) {
                list2.addLast(list1.removeFirst());
            }
            return list1.removeLast();
        }
    }
    
    /** Get the top element. */
    public int top() {
        if(this.empty()) {
            return -1;
        }else if(list1.isEmpty()) {
            return list2.peekLast();
        }else {
            return list1.peekLast();
        }
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return list1.isEmpty() && list2.isEmpty();
    }
}

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
class Solution {
    public boolean validateStackSequences(int [] pushed,int [] poped) {
      if(pushed.length != poped.length) {
          //throw new IllegalArgumentException();
          return false;
      }else if(pushed.length == 0) {
          return true;
      }else {
          Stack<Integer> stackhelp = new Stack<>();
          int index = 0;
          //pushed数组的每一个元素都是要进栈的，只是出栈的时机不同而已
          for(int i = 0;i < pushed.length;i ++) {
              stackhelp.push(pushed[i]);
              while(! stackhelp.isEmpty() && stackhelp.peek() == poped[index]) {
                  index ++;
                  stackhelp.pop();
              }
              //这个不能放到while循环之后，因为如果入栈的出栈的顺序都是12345
              //要是放到while循环之后，那么push数组的1放到栈就取不出来了
              //stackhelp.push(pushed[i]);
          }
          return stackhelp.isEmpty();
      }    
    }
    
}

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
class Solution {
    //假设这个表达式总是有效的,并且表达式总会得出有效数值且不存在除数为 0 的情况。
    public int evalRPN(String[] tokens) {
        if(tokens.length == 0) {
            return 0;
        }else {
            Stack<Integer> stack1 = new Stack<>();
            //Stack<String> stack2 = new Stack<>();
            HashSet<String> set = new HashSet<>();
            set.add("+");
            set.add("-");
            set.add("*");
            set.add("/");
            int answer = 0;
            for(int i = 0;i < tokens.length;i ++) {
                //1.set的contains()方法调用的是equals方法
                if(! set.contains(tokens[i])) {
                    stack1.push(Integer.parseInt(tokens[i]));
                }else {
                    //stack2.push(tokens[i]);
                    int number1 = stack1.pop();
                    int number2 = stack1.pop();
                    //int result = 0;
                    if(tokens[i].equals("+")) {
                        answer = (number1 + number2);
                    }else if(tokens[i].equals("-")) {
                        answer = (number2 - number1);
                    }else if(tokens[i].equals("*")) {
                        answer = (number1 * number2);
                    }else {
                        //3.注意谁除以谁
                        answer = (number2 / number1);
                    }
                    //2.运算结果还要入栈，因此上面的表达式是=不是+=
                    stack1.push(answer);
                }
            }
            //4.题目给的逆波兰表达式总是有效的，因此最后栈中只有一个数字，就是答案
            return stack1.pop();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int compareVersion(String version1, String version2) {
        //得用\.分割不能用.分割
        String[] numbers1 = version1.split("\.");
        String[] numbers2 = version2.split("\.");
        int length1 = numbers1.length;
        int length2 = numbers2.length;
        int number1 = 0;
        int number2 = 0;
        for(int i = 0;i < Math.max(length1,length2);i ++) {
            number1 = i >= length1 ? 0 : Integer.parseInt(numbers1[i]);
            number2 = i >= length2 ? 0 : Integer.parseInt(numbers2[i]); 
            if(number1 != number2) {
                return number1 > number2 ? 1 : -1;
            }           
        }
        return 0;
    }
}