秋招突击——7/17——复习{二分查找——搜索插入位置、搜索二维矩阵，}——新作{链表——反转链表和回文链表，子串——和为K的子数组}

🕗 发布于 2024-07-19 04:41 矩阵链表线性代数

文章目录

引言

今天算法得是速通的，严格把控好时间，后面要准备去面试提前批了，项目得赶紧过！
今天复习一个模板，然后在整理一个模板！

新作

二分模板

 void binSearch(int[] nums,int l,int r){
 while(l<r){
 int mid = (l + r + 1) >> 1;
 if(nums[mid] >= tar) l = mid;
 else r = mid - 1;

二分查找——搜索插入位置

复习实现

这里是使用左边界的

class Solution {
    public int searchInsert(int[] nums, int tar) {
        int l = 0,r = nums.length - 1;
        while(l < r){
          int mid = (l + r) >> 1;
          if(nums[mid] > tar) r = mid;  
          else if(nums[mid] == tar) return mid;
          else l = mid + 1;
        }

        if(nums[l] < tar)   return l + 1;
        return l ;
    }
}

在这里插入图片描述
右边界

class Solution {
    public int searchInsert(int[] nums, int tar) {
        int l = 0,r = nums.length - 1;
        while(l < r){
          int mid = (l + r + 1) >> 1;
          if(nums[mid] < tar) l = mid;  
          else if(nums[mid] == tar) return mid;
          else r = mid - 1;
        }
        System.out.println(r);
        if(nums[r] < tar)   return l + 1;
        return r ;
    }
}

在这里插入图片描述

搜索二维矩阵

复习实现

这道题两种实现方式，一种是做两次二分查找，不过要明确好使用左边界还是右边界，是找第一个小的值还是第一个大的值，然后再确定是否存在，不存在直接跳出。这种比较耗时。
还有一种坐标转换，将所有的元素排成一个序列，然后从左到右进行查询，确定到具体的目标是转成对应二维矩阵的信息，进行比较！

class Solution {
    public boolean searchMatrix(int[][] mat, int tar) {
     
        // define the row and col of array
        int m = mat.length;
        int n = mat[0].length;

        // binSearch on the conversion of the index
        int l = 0;
        int r = m * n - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(mat[mid / n][ mid % n] >= tar)   r = mid;
            else l = mid + 1;
        }

        return mat[l / n][ l % n] == tar;
    }
}

在这里插入图片描述

我靠，这样写，出奇的顺利，差不多五分钟就写完了！

新作

反转链表

题目链接
在这里插入图片描述

个人实现

这个就是常规的反转链表，很常见！

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        // handle the edge situation
        if(head == null || head.next == null)   return head;
        
        // define dummy head to store the head node
        ListNode dummy = new ListNode();
        dummy.next = head;

        // reverse the node list
        ListNode left = dummy.next;
        ListNode right = left.next;
        ListNode temp = right.next;
        left.next = null;
        while(temp != null){
            right.next = left;
            left = right;
            right = temp;
            temp = temp.next;
        }

        right.next = left;
        left = right;
        dummy.next = right;

        return dummy.next;        
    }
}

在这里插入图片描述

写是写出来了，但是太散了，还是要参考一下啊

参考实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        // handle the edge situation
        if(head == null || head.next == null)   return head;
        
        // define dummy head to store the head node
        ListNode dummy = new ListNode();
        dummy.next = head;

        // reverse the node list
        ListNode left = null;
        ListNode right = dummy.next;;
        while(right != null){
            ListNode temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }

        dummy.next = left;

        return dummy.next;        
    }
}

总结

其实我的代码有很多重复的地方，完全没有必要，总结下来：
- 反转链表两节点，next和pre，临时保存用temp，最终返回是pre。

在这里插入图片描述

回文链表

题目链接

在这里插入图片描述

注意

链表节点数最少为1，直接返回
链表的值不用担心越界
要求时间复杂度是O(n)，空间复杂度是O(1)

个人实现

这个是回文链表，也就双指针可以做，因为空间复杂度是O(1)，并没有办法使用其他的数据结构，所以想想看，双指针怎么遍历。
- 如果节点数是奇数，一定不会是回文字符串，直接返回false
- 如果节点数是偶数，那么就要找到中间的节点数，直接将字符串进行拼接，然后再用反转不就行了！
遍历一遍，保存为字符串，先判定数量，数量一致，在使用字符串的操作。
看错了，回文是从前往后读，和从后往前读是一致的！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        StringBuilder  str = new StringBuilder("");

        // traverse the list and judge the length 
        while(temp != null){
            str.append("" + temp.val);
            temp = temp.next;
        }

       
        String substr1 = str.toString();
        //System.out.println(substr1 );
        String substr2 = str.reverse().toString();
        //System.out.println(substr2 );

        return substr1.equals(substr2);

    }
}

在这里插入图片描述

问题
将int转成String

String.valueOf(4);
Integer.toString(4);
“” + 4

StringBuilder的相关操作

添加元素：append，可以添加char，int还有string
删除元素：delete（start_idx,end_idx）,删除这段索引之间的字符串
转为String:toString
获取子串：substring（start_idx,end_idx），注意，一定要是小写
获取长度：length（），除了collection是用size，其他都是使用length，不过string系列的要加括号
字符串比较相等，使用equals，不要使用==，需要转为string
字符串反转，reverse()，只能使用stringBuilder进行调用

这题做的不容易，补充了好多知识，真不容易！

参考实现

参考样例实现了三个方法

方法一

将数组保存为数组，然后的使用双指针进行反向遍历，跟我的很像。

方法二

使用栈实现逆序遍历，然后正向读取数据，然后的入栈，在逐个出栈，就是反向遍历单链表了。

方法三——快慢指针

两倍快指针到了终点，然后慢指针就是中点
反转两个链表，分别进行比较，然后再反转回来！

逆序遍历出栈入栈，确定中点快慢指针

和为K的子数组

题目链接

在这里插入图片描述
注意

必须要连续的序列，并且不能为空
可以为1个，可能是两个
k是目标值，不会越界
数组是没有任何顺序的

个人实现

数组没有任何顺序，所以不能使用两数之和的方式进行计算，这里得想办法，表示一下两者的关系。
这里没有对时间复杂度做出要求，所以我们可以尝试直接暴力搜索去做。
实现思路如下
- 将前i项的序列保存为字典，O(n)
- 遍历每一个索引，并在字典中找到对应的索引值，找到了就符合条件，找不到跳过。O(n*n),最坏是平方。
  - S[k] - S[i] = k,i<k

class Solution {
    public int subarraySum(int[] nums, int k) {
        // res == result 
        int res = 0;

        // define the array to store the value of the sum
        int m = nums.length;
        int[] sumN = new int[m];
        sumN[0] = nums[0];

        // handle the special situation
        if(m == 1 && nums[0] != k)  return 0;

        Map<Integer,List<Integer>> map = new HashMap<>();
        List<Integer> tempZero = new ArrayList<Integer>();
        tempZero.add(0);
        map.put(nums[0],tempZero);
        if(nums[0] == k)    res ++;
        //System.out.println(map.get(nums[0]).toString());
        for(int i = 1;i < m;i ++)   {
            sumN[i] = nums[i] + sumN[i - 1];
            //System.out.println(sumN[i]);
            List<Integer> temp = map.getOrDefault(sumN[i],new ArrayList<Integer>());
            temp.add(i);
            map.put(sumN[i],temp);
            if(sumN[i] == k)    res ++;
        }
        System.out.println(res);
        
        // traverse the array to judge list 
        for(int r = 0;r < m;r ++){
            int resTar = sumN[r] - k;
            if(map.containsKey(resTar)){
                for(int x : map.get(resTar)){
                    if(x < r)   res ++;
                }   
            }
        }

        return res;
    }
}

在这里插入图片描述

整了半个小时，就整出来这么几个东西，尴尬，超时了！

问题
Arrays.asList和ArrayList并不兼容，会出错

Arrays.asList返回的是一个固定长度，然后ArrayList是返回一个不定长动态数组，这两个互不兼容，所以不能实现如下操作

List<Integer> temp = Arrays.asList(1);
temp.add(1)

new ArrayList (0):并不会创建一个包含元素零的Arraylist，会出错！

new ArrayList(x)：是返回一个初始长度为x的列表，并不是返回一个有0的ArrayList，可以使用如下方式创建
new ArrayList(Arrays.asList(1,2,3,0))：创建了包含四个元素的数组

参考实现

基本思路是一致的，但是我有一个地方没有考虑到，浪费了很多时间，具体如下。针对索引为i的目标而言，我只需要一个包含前i-1的前缀和序列就行，并不需要包含后续的，我添加的元素的过程不就是这样吗？但是我是先把所有的元素都添加完，然后再过滤的，这就是一个很大的问题！
边保存，边计算

class Solution {
    public int subarraySum(int[] nums, int k) {
        // res == result 
        int res = 0;

        // define the array to store the value of the sum
        int m = nums.length;
        int[] sumN = new int[m];
        sumN[0] = nums[0];

        // handle the special situation
        if(m == 1 && nums[0] != k)  return 0;

        Map<Integer,Integer> map = new HashMap<>();
        //List<Integer> tempZero = new ArrayList<Integer>();
        //tempZero.add(0);
        map.put(nums[0],1);
        if(nums[0] == k)    res ++;
        //System.out.println(map.get(nums[0]).toString());
        for(int i = 1;i < m;i ++)   {
            sumN[i] = nums[i] + sumN[i - 1];
            
            // judge fron 1 to i 
            int resTar = sumN[i] - k;
            res += map.getOrDefault(resTar,0);
            map.put(sumN[i],map.getOrDefault(sumN[i],0) + 1);
            if(sumN[i] == k)    res ++;
        }
   
        return res;
    }
}

在这里插入图片描述

这就过了，关键是怎么记忆？

字串和哈希，边算边添加

总结

老是会把问题想复杂，然后明明能做出来的，但是会超时，不应该这样的！
又做了那么久的算法，下午还得补专利，估计没啥时间弄项目了，不行呀！
又是一个深夜，今天晚上去看电影了，过了一遍百度的一个面经，然后做了几道算道题，有投了两家公司，但是专利还是没有写，明天上午先写专利，在做项目，然后的再刷算法！

原文地址：https://blog.csdn.net/Blackoutdragon/article/details/140485222

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：android11 屏蔽usb通过otg转接口外接鼠标设备
下一篇：提示工程的技术与策略分类

一款集成编码器的无刷电机驱动板
本实物模块从实物外观、组成原理及功能说明三部分来介绍这款集成编码器的无刷电机驱动板。
阅读更多2024-11-15
找不到Windows SDK 版本 10.0.22621.0
这意味着系统找不到，这是你构建项目所需要的 SDK 版本。
阅读更多2024-11-15
python制作一个简单的端口扫描器，用于检测目标主机上指定端口的开放状态
创建一个 socket 对象，AF_INET 表示使用 IPv4，SOCK_STREAM 表示使用 TCP。print("请正确指定目标端口，使用 -p 参数输入目标端口信息（多个端口用逗号
阅读更多2024-11-15
Java 实现鼠标单击右键弹出菜单项
在界面的任意地方右键点击出现一个菜单项 "Intro"，并且点击该项后弹出一个NewWindow。
阅读更多2024-11-15
dynamodb——事务
目的：提供在同一区域内对跨表的数据项执行原子和可序列化操作的能力，同时保证性能的可预测性，并且因此，没有采用传统意义上的交互式事务而是引入了两个新的单请求操作实现，实现从一致的快照中检索多个条目，
阅读更多2024-11-15
拆解测试显示Mac Mini (2024)固态硬盘并未锁定互换硬盘后仍可使用
当然那这里又会存在一个新坑：某些二手交易平台上价格相对较低的 Mac Mini (2024) 16GB+2TB 版有可能就是替换的硬盘，如果用户不了解这种情况的话可能就会被割韭菜。不过知名拆解网站 i
阅读更多2024-11-15
Ubuntu 24.04 安装 JDK 21
Ubuntu 24.04 安装 JDK 21
阅读更多2024-11-15
讲解C语言关键字
C语言是一种结构化的编程语言，它有一组特殊的保留字，称为“关键字”。这些关键字在程序中具有特定的含义和用途，不能用作标识符（例如变量名、函数名等）。
阅读更多2024-11-15
git入门环境搭建
git官网地址：https://git-scm.com/然后一路next 默认路径默认勾选就行。如果没有魔法的话，官网这个地址能卡死你。今天就写到这吧，11点多了该睡了，，，这里给个国内的git
阅读更多2024-11-15
定时器简介
在第一部分,我们主要讲的是定时器基本定时的功能，也就是定一个时间，然后让定时器每隔这个时间产生一个中断，来实现每隔一个固定时间执行一段程序的目的，比如你要做个时钟、秒表，或者使用一些程序算法的时候，都
阅读更多2024-11-15

秋招突击——7/17——复习{二分查找——搜索插入位置、搜索二维矩阵，}——新作{链表——反转链表和回文链表，子串——和为K的子数组}

文章目录

引言

新作

二分模板

二分查找——搜索插入位置

复习实现

搜索二维矩阵

复习实现

新作

反转链表

个人实现

参考实现

回文链表

个人实现

参考实现

和为K的子数组

个人实现

参考实现

总结

相关文章