牛客网——刷题篇

​

文章目录

比较版本号

 二叉树的中序遍历

数组中只出现一次的两个数字

合并区间

比较版本号

知识点：字符串，双指针

题解：

import java.util.*;

public class Solution {

public int compare (String version1, String version2) {
    // write code here
    String[] numsOfV1 = version1.split("\\."); // 记得这里分割的时候需要加两个斜杠
    String[] numsOfV2 = version2.split("\\.");
    
    int index = 0;
    
    while (index < numsOfV1.length && index < numsOfV2.length) {
        int num1 = Integer.parseInt(numsOfV1[index]);
        int num2 = Integer.parseInt(numsOfV2[index]);
        if (num1 > num2) {
            return 1;
        } else if (num1 < num2) {
            return -1;
        }
        index ++;
    }
    
    while (index < numsOfV1.length) {
        int num1 = Integer.parseInt(numsOfV1[index]);
        if (num1 > 0) {
            return 1;
        }
        index ++;
    }
    
    while (index < numsOfV2.length) {
        int num2 = Integer.parseInt(numsOfV2[index]);
        if (num2 > 0) {
            return -1;
        }
        index ++;
    }
    
    return 0;
}

}
 二叉树的中序遍历

知识点：树，递归，广度优先搜索(BFS)

 题解：

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 {

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
public int[] inorderTraversal (TreeNode root) {
    // write code here
    if(root == null)return new int[0];
    ArrayList<Integer> ans = new ArrayList<>();
    inOrder(root, ans);
    int[] res = new int[ans.size()];
    int i=0;
    for(int n: ans){
        res[i++] = n;
    }
    return res;
}
public void inOrder(TreeNode node, ArrayList<Integer> ans){
    if(node == null)return;
    inOrder(node.left, ans);
    ans.add(node.val);
    inOrder(node.right, ans);
}

}
数组中只出现一次的两个数字

知识点：位运算，哈希

 题解：

import java.util.*;

public class Solution {

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] FindNumsAppearOnce (int[] array) {
    // write code here
    int tmp = 0, n = array.length;
    for(int i=0; i<n; i++){
        tmp ^= array[i];
    }
    int div = 1;
    while(tmp != 0){
        if((tmp & 1) == 1) div <<= 1;
        tmp >>= 1;
    }
    int a = 0, b = 0;
    for(int i=0; i<n; i++){
        if((array[i] & div) != 0) a ^= array[i];
        else b ^= array[i];
    }
    return new int[]{b, a};
}

}
合并区间

知识点：排序，数组

题解：

import java.util.*;
/**

• Definition for an interval.
• public class Interval {
• int start;
• int end;
• Interval() { start = 0; end = 0; }
• Interval(int s, int e) { start = s; end = e; }
• }

*/
public class Solution {

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    if (intervals.size() == 0) {
        return new ArrayList<>();
    }
    Collections.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval o1, Interval o2) {
            if (o1.start != o2.start) {
                return o1.start - o2.start;
            } else {
                return o1.end - o2.end;
            }
        }
    });
    
    ArrayList<Interval> result = new ArrayList<>();
    result.add(intervals.get(0));
    int count = 0;
    for (int i = 1; i < intervals.size(); i++) {
        Interval o1 = intervals.get(i);
        Interval origin = result.get(count);
        if (o1.start > origin.end) {
            result.add(o1);
            count++;
        } else {
            result.remove(count);
            Interval s = new Interval(origin.start, o1.end);
            if (o1.end < origin.end) {
                s.end = origin.end;
            }
            result.add(s);
        }
    }
    return result;
    
}

}

​