Leetcode刷题-(26~35)-Java

算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写算法题吧。

遇事不决，可问春风，春风不语，即是本心。

我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

1、删除有序数组中的重复项

2、移除元素

3、找出字符串中第一个匹配项的下标

4、两数相除

5、串联所有单词的子串

6、下一个排列

7、最长有效括号

8、搜索旋转排序数组

9、在排序数组中查找元素的第一个与最后一个位置

10、搜索插入位置

1、删除有序数组中的重复项

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

思路：双指针，左指针用于固定修改位置，右指针向后遍历，不相等啧修改元素。

class Solution {
    public int removeDuplicates(int[] nums) {
        // 数组是有序的,用双指针
        int left = 0 ;
        for(int i=1; i<nums.length; i++){
            if(nums[i] != nums[left]){
                nums[left+1] = nums[i] ;
                left ++ ;
            }
        }
        return left + 1 ;
    }
}

2、移除元素

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-element/description/

思路：双指针，左侧指针标记位置，右侧向后遍历，不等于val则可以修改进行原地移除。

class Solution {
    public int removeElement(int[] nums, int val) {
       // 原地移除，也是用双指针
       int left = 0 ;
       for(int i=0; i<nums.length; i++){
        if(nums[i] != val){
            nums[left] = nums[i] ;
            left ++ ;
        }
       }
       return left  ;
    }
}

3、找出字符串中第一个匹配项的下标

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

思路：本质上就是字符串匹配，其实对于Java等编程语言，可以通过indexOf这种api直接解决，当然考虑到是算法题，需要手写indexOf函数。

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle) ;
    }
}

利用双指针模拟字符串匹配过程，匹配到就返回左侧指针的位置，匹配不到就返回-1。

class Solution {
    public int strStr(String haystack, String needle) {
        char [] c1 = haystack.toCharArray() ;
        char [] c2 = needle.toCharArray() ;
        int n = c1.length, m = c2.length ;
        for(int i=0; i<=n-m; i++){
            int b1 = i, b2 = 0 ;
            while(b2<m && c1[b1]==c2[b2]){
                b1 ++ ;
                b2 ++ ;
            }
            if(b2 == m){
                return i ;
            }
        }
        return -1 ;
    }
}

4、两数相除

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/divide-two-integers/description/

思路：要求不允许使用乘法、除法以及取余运算，硬生生把简单题复杂化，直接除一下就可以了，如下：

class Solution {
    public int divide(int dividend, int divisor) {
        long res = (long) dividend / (long) divisor ;
        if(res > Integer.MAX_VALUE){
            res = Integer.MAX_VALUE ;
        }
        if(res < Integer.MIN_VALUE){
            res = Integer.MIN_VALUE ;
        }
        return (int)res ;
    }
}

当然，上述的题解不是本题所考查的方面，通过循环减法，减的次数就是两数相除的结果。

class Solution {
    public int divide(int dividend, int divisor) {
       // 特殊的case处理
       if(dividend == Integer.MIN_VALUE ){
        if(divisor == -1){
            return Integer.MAX_VALUE;
        }
        if(divisor == 1){
            return Integer.MIN_VALUE ;
        }
       }
       if(divisor == 1){
        return dividend ;
       }
       // 判断最终结构的正负值
       int op = dividend < 0 ? -1 : 1 ;
       op = divisor < 0 ? -op : op ;

       // 转换为负数计算
       dividend = -Math.abs(dividend) ;
       divisor = -Math.abs(divisor) ;

       // 除法对应的思路是循环求减
       int res = 0 ;
       while(dividend <= divisor){
        dividend -= divisor ;
        res ++ ;
       }
       return res*op ;

    }
}

5、串联所有单词的子串

6、下一个排列

7、最长有效括号

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/longest-valid-parentheses/description/

思路：用栈存储下标模拟有效括号的匹配过程，先在栈中存储一个-1，如果遇到左括号，就将当前的括号位于字符串中的索引存储到栈中，如果遇到右括号，出栈，如果栈空，则重新记录栈顶索引，否则，计算最大连续匹配括号。

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0 ;
        LinkedList<Integer> stack = new LinkedList<>() ;
        stack.push(-1) ;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i) ;
            if(c == '('){
                stack.push(i) ;
            }else{
                stack.pop() ;
                if(stack.isEmpty()){
                    stack.push(i) ;
                }else{
                    max = Math.max(max, i-stack.peek()) ;
                }
            }
        }
        return max ;
    }
}

8、搜索旋转排序数组

题目链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

思路：二分查找的思想，数组长度为0或1的情况下，可以直接找出target的位置，数组长度大于1的情况下，为了保证O(logn)的时间复杂度，使用二分查找法：若中间值与目标值相等，则直接找到，否则，比较第一个元素与中间元素的大小，进一步比较第一个元素与目标元素以及中间元素与目标元素的大小。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length ;
        if(n==0){
            return -1;
        }
        if(n==1){
            int res =  nums[0] == target  ? 0  : -1 ;
            return res ;
        }
        int left = 0, right = n - 1 ;
        // 二分查找的变种
        while(left<=right){
            int mid = (left + right) >> 1 ;
            if(nums[mid] == target){
                return mid ;
            }
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && nums[mid] > target){
                    right = mid - 1;
                }else{
                    left = mid + 1 ;
                }
            }else{
                if(nums[0] > target && nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1 ;
                }
            }
        }
        return -1 ;
    }
}

9、在排序数组中查找元素的第一个与最后一个位置

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

思路：

Java版：

如果不考虑时间复杂度，使用O(n)的时间复杂度，则直接模拟标记法即可。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        boolean first = false, second = false ;
        int one = -1, two = -1 ;
        for(int i=0; i<nums.length; i++){
            if(nums[i] == target){
                if(first == false){
                    first = true ;
                    one = i ;
                }else{
                   two = i ;
                   second = true ;
                }
            }
        }
        if(first && second){
            return new int []{one, two} ;
        }
        if(first){
            return new int []{one, one} ;
        }
        return new int []{-1, -1} ;
    }
}

二分查找，从每次从中间找，初始化结果值为最大值，不停地更新，二分查找的第三个参数约束，当为true时，找出最左边相等的，当为false时，找到最右边的那个就不再找了。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target, true) ;
        int rightIndex = binarySearch(nums, target, false) - 1;
        if(leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == target && nums[rightIndex] == target){
            return new int []{leftIndex, rightIndex} ;
        }
        return new int[]{-1, -1} ;
    }
    public int binarySearch(int [] nums, int target, boolean flag){
        int low = 0, high = nums.length - 1 ;
        int ans = nums.length  ;
        while(low <= high){
            int mid = (low + high) >> 1 ;
            if(nums[mid] > target || (flag && nums[mid] >= target)){
                high = mid - 1 ;
                ans = mid ;
            }else{
                low = mid + 1 ;
            }
        }
        return ans ;
    }
}

10、搜索插入位置

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/search-insert-position/description/

思路：初始化最终值为数组长度，二分查找过程中，当中间值大于等于目标值时，记录当前中间值所在位置为待插入的位置。

Java版：

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 二分查找的思想
        int low = 0, high = nums.length - 1 , ans = nums.length ;
        while(low <= high){
            int mid = (low + high) >> 1 ;
            if(nums[mid] >= target){
                high = mid - 1 ;
                ans = mid  ;
            }else{
                low = mid + 1 ;
            }
        }
        return ans ;
    }
}