leetCode进阶算法题+解析(四)

作者: 唯有努力不欺人丶 | 来源:发表于2020-01-18 22:15 被阅读0次

两两交换链表中的节点

题目:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

思路:什么叫实际进行节点交换?有点看不懂啊。反正这个题又是一道实现不难,按照条件实现不知道。我先按照我自己的理解去试试吧。
我感觉我是思路对了,没直接交换值,都是节点来回来去赋值。并且一次通过性能超过百分之百,直接贴代码了:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode temp = new ListNode(0);
        ListNode n = temp;
        while(head!=null && head.next!=null ){
            n.next = head.next;
            n = n.next;
            head.next = head.next.next;
            n.next = head;
            n = n.next;
            head = head.next;
        }
        if(head!=null) n.next = head;
        return temp.next;
    }
}

首先我是新建一个链表然后一节一节挂数据。两个交换的挂。最后如果剩个单则挂上,不剩单说明正好两个一组。直接返回就行了。
这个题其实比较简单,但是我看了别人的代码,这个题大多数人选择了递归的方法实现。其实确实是这样,我上面的代码也不过是把递归转化成循环而已。
说到这顺便说点别的:递归
其实刷算法以来递归是一种常用的“套路”。我这里用套路来形容递归。
以前也多多少少提过,递归就是隐式的栈,栈是显式的递归。
但是我们仔细寻思寻思递归是什么?

  • 递归就是一遍遍的重复调用自身。直到不满足递归的条件。
  • 循环就是重复同一段代码,直到不满足循环的条件。

你自己看看两个,是不是大多数都是相同的,所以换言之,大多数时候循环和递归是可以互换的(是大多数不是绝对)。
所以这道题可以递归解决是很正常的。但是要和我说递归会比循环性能好多少我是不信的。因为其实本质一样,区别只不过是代码的表现形式而已。顺便立个flag,我打算什么时候有时间了专门写一篇关于递归的理解和使用的文章。
言归正传,说这个题如何用递归实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null ){
            return head;
        }
        ListNode cur = head.next;
        head.next = swapPairs(cur.next);
        cur.next =head;
        return cur;
    }
}

其实这个递归展开就是循环的代码。然后这道题就这样了,下一题吧。关于递归我会有时间单独整理的。

两数相除

题目:给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

思路:不使用除法,乘法,和取模运算。。。实在不行我用减法?这要是int最大值除1我还得减二十多亿次?有点过分了吧。。
好了,看了题解知道这个题的思路了,但是!!!我不服!!
右移1左移1就是乘二除二。所以只要不直接出现*/%符号就是ok的是么?这个题也太奇葩了吧。
然后就是如下代码:

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        for (int i=31; i>=0;i--) {
            if ((t>>i)>=d) {//找出足够大的数2^n*divisor
                result+=1<<i;//将结果加上2^n
                t-=d<<i;//将被除数减去2^n*divisor
            }
        }
        return negative ? -result : result;//符号相异取反
    }
}

首先这个被除数是0直接得0,其次这个-1和最小值才会出现溢出,直接返回int最大值。
这两个特殊情况写完了正常逻辑判断。逻辑判断就是d除2的31次方(右移是除法,而且最大值除2的32次方都不是1、所以从31次方开始算)。如果还大于除数,则可以开始正常计算倍数了如果不大于则被除数除2的30次方。直到除某数后还大于除数,开始计算倍数。
然后这道题就这样了,下一题吧。

下一个排序

题目:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。必须原地修改,只允许使用额外常数空间。

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路:这道题好像又做过,不知道是不是我理解错了。首先降序数组变成升序数组这个很明确。接下来就难了,我做了好多demo才明白这个题啥意思。比如1 2 3三个数组合,123是最小的,找到第二小的组合数字。1 2 3 还可以组成 321,132。但是我们要第二小的,所以只能选132。同理如下图,65342可以组成好多种数字。这个65342不是最大的,所以要拼成仅大于65342且最小的数。咱们先说可以的选项:65432.65423.这里65423最小,所以选择65423。这个题就是这样的意思(ps:吐槽一下出题人的语文表达能力。)

image.png
既然知道了题意开始说思路:首先分两步:
  • 如果已经是最大了则直接翻转。
  • 如果不是最大的则选择变成稍大。这个变成稍大稍微麻烦点。我是打算从后往前判断。首先前面的能不动就不动,因为前面位数大,变动肯定也大。自己看那个65342的例子其实能看出一些东西。
    首先要直到末位某元素后面有比这个元素更大的元素为止。其次更大的那个放在这个元素为止上,然后后面的要从小到大拜访。
    思路就是这么个思路,接下来我去代码实现了。
    这个题多次过了(面向测试案例编程,一点点改bug)。但是性能超过百分之九十九的人,所以我自己挺满意的,直接贴代码:
class Solution {
    public void nextPermutation(int[] nums) {        
        int len = nums.length-1;
        if(len==0) return;
        for(int i=0;i<len;i++){
            if(nums[i]<nums[i+1])break;
            if(i==len-1){//降序排列,转成升序
                i++;
                int l = 0;
                while(l<i){
                    int temp = nums[l];
                    nums[l] = nums[i];
                    nums[i] = temp;
                    l++;
                    i--;
                }
                return;
            }
        }
        int max = nums[len];
        int idx = -1;
        for(int i = len-1;i>=0;i--){
            if(max>nums[i]){//后面有比前面大的元素了.
                max = nums[i];
                idx = i;
                break;
            }
            max = Math.max(max,nums[i]);
        }
        //从第idx个到最后重排序,重排序的标准是比idx值大的最小元素放最前,然后从小到大放 
        int min = nums[idx];
        //大于第idx最小的元素
        int min1 = 2000000000;
        //大于idx最小元素的下标
        int idx1 = -1;
        for(int i = idx+1;i<len+1;i++){
            if(nums[i]>min && min1>nums[i]){
                min1 = nums[i];
                idx1 = i;
            }
        }
        int t = nums[idx];
        nums[idx] = nums[idx1];
        nums[idx1] = t;
        int n = idx+1;
        while(n<len){
            int tm = 2000000000;
            int idx2 = -1;
            for(int i = n;i<len+1;i++){
                if(tm>nums[i]){
                    idx2 = i;
                    tm = nums[i];
                }
            }
            if(idx2!=n){
                int tp = nums[n];
                nums[n] = nums[idx2];
                nums[idx2] = tp;
            }
            n++;
        }
    }
}

代码的逻辑步骤就是按照上面的思路,写的墨迹点但是起码手动实现性能还行。这道题其实不难,就是复杂,墨迹。
首先判断是不是降序数组,然后判断后面有较大值的元素下标idx。然后判断仅大于idx值的数和下标,然后交换。然后后面的升序排列。
整个逻辑就是这样,现在理得很清楚了,所以这道题过。

搜索旋转数组

题目:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

思路:感觉这道题的难点是时间复杂度O(logn)。不然简单遍历绝对是ok的。我记得二分法就是logn的时间复杂度,其实这有个很好的判断。判断第一个元素和target大小和target与最后的元素的大小。如果大于最后的小于第一的则直接-1.剩下的二分判断,我先尝试去实现。
这道题终于做完了,各种if-else。。写的都要晕了。然后用的二分法,我先贴代码再一点点说,对了,速度超过百分之九十的人,将将及格!还是很开心的:

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length-1;
        if(len<0) return -1;
        if(target>nums[len] && target<nums[0]){
            return -1;                                  
        }
        int l = 0;
        int r = len;
        if(target==nums[0]) return 0;
        if(target==nums[len]) return len;
        //flag是true说明target在前面的升序中,否则在后面的升序中
        boolean flag = target>nums[0]? true:false;
        while(l<r){
            int mid = (l+r)/2;
            if(flag){
                if(nums[mid]>target){
                    r = mid;
                }else if(nums[mid]<target){
                    if(nums[mid]>nums[0]){
                        l = mid+1;
                    }else{//说明mid到了后段
                        r = mid;
                    }
                }else{
                    return mid;
                }                
            }else{
                if(nums[mid]<target){
                    l = mid+1;
                }else if(nums[mid]>target){
                    if(nums[mid]>nums[len]){//这是前半段,要往后半段凑
                        l = mid+1;
                    }else{
                        r = mid;
                    }
                }else{
                    return mid;
                }
            }            
        }
        return -1;        
    }
}

哈哈,看着就眼晕是不是。首先判断这个数是在前半个升序列里还是后半个里。
然后二分法判断,这个判断1,大小判断。2,这个数属于前半段列里还是后半段。
刚刚看了性能第一的代码,差不多思路,就是具体的写法略有不同,然后我复制粘贴提交。。。到我手里也是1ms,还是超过百分之九十的人。。反正贴出来分享下:

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len-1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < nums[right]){
                if(nums[mid] < target && target <= nums[right])
                    left = mid+1;
                else
                    right = mid-1;
            }
            else{
                if(nums[left] <= target && target < nums[mid])
                    right = mid-1;
                else
                    left = mid+1;
            }
        }
        return -1;
    }
}

明天就要回家过年了,而且手头现在有一个多租户的概念打算整理写下,还有一个递归的理解使用打算整理一下。。。然后每天三道保底题是为了leetcode的20积分,最近可能算法只刷保底了~感觉时间真的飞快,从一个完全的小白到简单的算法都能做出来,感觉自己有进步呦!哈哈
然后今天的笔记就记到这里,如果稍微帮到你了记得点个喜欢点个关注呦!也祝大家工作顺顺利利!

相关文章

网友评论

    本文标题:leetCode进阶算法题+解析(四)

    本文链接:https://www.haomeiwen.com/subject/iyckzctx.html