力扣刷题

第一题，寻找数组的中心索引

给你一个整数数组 nums ，请计算数组的中心下标。

数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

class Solution{
    public int pivotIndex(int [] nums){
        int sum = 0;
        for(int i = 0 ; i < length ; i ++){
            sum = sum + nums[i];
        }
        
        int left_sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            sum = sum - nums[i];
            if(sum == left_sum){
                return i;
            }
            left_sum = left_sum + nums[i];
        }
        return -1;
    }   
}

第二题：搜索数组插入的位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置，请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

nums 为无重复元素的升序排列数组

-10^4 <= target <= 10^4

class Solution{
    public int searchInsert(int [] nums, int target){
        for(int i = 0 ; i < nums.length ; i++ ){
            //只要他的值小于或者等于nums[i]直接返回索引，否则返回数组长度
            if(target <= nums[i]){
                return i;
            }
        }
        return nums.length;
    }
}

//只要提到排序的数组，我们首先要考虑的就是能不能使用二分法
class Solution{
    public int insertSearch(int[] nums, int target ){
        int lo = 0 ; 
        int hi = nums.length - 1;
        while(lo <= hi){

            //获取中间的值
            int mid = lo + (hi - lo) / 2;
            int midValue = nums[mid];
            if(midValue > target){
                hi = mid - 1;
            }else if(midValue < target){
                lo = mid + 1;
            }else{
                //如果找到就返回
                return mid; 
            }
            //没找到就返回应该插入的位置
            return lo;
        }
    }
}

第三题：合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：
1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

class Solution{
    public int [][] merge(int [][] intervals){
        if(intervals.length == 0) return intervals;
        //1.对二维数组按照第一列进行升序排序
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        //进行合并数组
        List<int []> list = new ArrayList<>();
        //临时空间，判断是否需要合并集合，是否放入结果条
        int term[] = intervals[0]; 
        for(int i = 1 ; i < intervals.length ; i ++){
            if(term[1] >= intervals[i][0]){
                term[1] = Math.max(term[1],intervals[i][1]);
            }else{
                list.add(term);
                term = intervals[i];
            }
        }
        list.add(term);
        return list.toArray(new int [list.size()][2]);
    }
}

第四题：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

解法一：

class Solution{
    public int[] twoSum(int [] nums , int target){
        //声明一个数组用来存储数组下标
        int [] res = new int [2];
        for(int i = 0; i < nums.length ; i ++){
            for(int j = i + 1; j < nums.length; j ++){
                if(num[i] + num[j] = target){
                    res[0] = i;
                    res[1] = j;
                    break;
                }
            }
        }
        return res;
    }
}

解法二：

class Solution{
    public int[] twoSum(int [] nums , int target){
        int [] res = new int [2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0 ; i < nums.length ; i ++){
            if(map.containKey(nums[i])){
                res[0] = map.get(nums[i]);
                res[1] = i;
            }
            map.put(target - nums[i],i);
        }
        return res;
    } 
}

第五题：回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

-2^31 <= x <= 2^31 - 1

解法一：

class Solution {
    public boolean isPalindrome(int x) {
        
        if(x == 0) return true;

        if(x < 0 || x % 10 == 0) return false;

        int reversed = 0;
        while(x > reversed){
            reversed = reversed * 10 + x % 10;
            x = x/10;
        }
        return x == reversed || x == reversed / 10;
    }
}

解法二：

class Solution{
    public boolean isPalindrome(int x){
        StringBuilder sb = new StringBuilder();
        //将数字添加到字符串中
        sb.append(x);
        sb.reverse();
        return sb.toString().equals(""+ x);
    }

}

第六题：罗马数字转整型

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = “III”
输出: 3

示例 2:

输入: s = “IV”
输出: 4

示例 3:

输入: s = “IX”
输出: 9

示例 4:

输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.