经典算法笔试题

╰半夏微凉° 2022-12-11 02:28 184阅读 0赞

> 1、请写一个冒泡排序的算法

public class test {
        public static void main(String[] args) {
            int a[] ={34,23,45,2,11,200,1};        
            int temp = 0;
            for (int i = 0; i <a.length-1 ; i++) {          
                for (int j = 0; j <a.length-1 ; j++) {               
                    if (a[j]>a[j+1]){
                       
                        temp = a[j];
                      
                        a[j]=a[j+1];
                    
                        a[j+1]=temp;
                      
                    }
                }
    
            }   
        }
    
    }

## ##

> 2、给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
> 
> 示例 1:
> 
> 输入: "abcabcbb"  
> 输出: 3   
> 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。  
> 示例 2:
> 
> 输入: "bbbbb"  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。  
> 示例 3:
> 
> 输入: "pwwkew"  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。  
>      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路：

通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合， 即 \[i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 \[i, j)向右滑动 1 个元素，则它将变为 \[i+1, j+1)（左闭，右开）。 回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 \[i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中， 我们会继续滑动 j。直到 s\[j\] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i这样做，就可以得到答案。

public class TestSame {
        public static void main(String[] args) {
            String a="aaabcss";
            int i = FindSame(a);
            System.out.println(i);
        }
        public  static  int FindSame(String s){
            //利用set  set是无序 不可重复
            int n = s.length();//获得字符串的长度
            int ans = 0;//记录不含有重复字符串长度的个数
            Map<Character, Integer> map = new HashMap<>();       
            for (int j = 0, i = 0; j < n; j++) {                      
                //charAt返回指定位置的字符
                // Map 的containsKey() 方法来检测是否数据是否存在
                if (map.containsKey(s.charAt(j))) {//如果存在                
                    i = Math.max(map.get(s.charAt(j)), i);               
                }
                //如果不存在
                ans = Math.max(ans, j - i + 1);
                map.put(s.charAt(j), j + 1);
            }
            return ans;
    
        }
    }

> 3、给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

public class Solution {
        public static void main(String[] args) {
            int nums[] = {-1,2,1,-4};
            int target=1;
            int i = threeSumClosest(nums, target);
            System.out.println(i);
        }
        public static int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int temp;
            int min=Integer.MAX_VALUE;
            int result;
            int ii = 0,jj=0,kk=0;
            for(int i=0;i<nums.length-1;i++){
                for(int j=i+1;j<nums.length;j++){
                    temp=nums[i]+nums[j];
                    for(int k=nums.length-1;k>j;k--){
                        result=temp+nums[k];
                        if(min>Math.abs(result-target)){
                            ii=i;
                            jj=j;
                            kk=k;
                            min=Math.abs(result-target);
                        }
                    }
                }
            }
    
            // System.out.print("    最终"+(nums[ii]+nums[jj]+nums[kk]));
            return nums[ii]+nums[jj]+nums[kk];
        }
    }

>  4、给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。  
> 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。  
> 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。  
> 示例：  
> 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  
> 输出：7 -> 0 -> 8  
> 原因：342 + 465 = 807  
> 刚拿到这道题，可能的想法会是将链表以逆序恢复成两个百位数，然后将两个百位数相加，再以链表形式输出，那么时间就会浪费在链表转换成数字然后再转换成链表的过程中了。  
> 于是，我们产生了一个想法，为什么不直接在链表的基础上进行各位的相加呢？

public class ListNode {
        int val;
        ListNode next;
    
        public ListNode(int x){
            val=x;
        }
    }

public class ListNodes {
        public static void main(String[] args) {
                // 创建两个链表 // 第一个链表: 1-> 8 -> 7 -> 6 (在做加法运算代表的是6781)
                ListNode l1 = new ListNode(2); // 这是第一个链表的第一个节点(不能用这个节点去往下加数据)
                // 必须有一个指针去往第一个节点上去加数据
                ListNode p = l1;
                 // 这个指针节点会从链表的第一个节点一直往下走(直至最后一个节点)
                p.next = new ListNode(4);
                p = p.next;
                p.next = new ListNode(3);
               // p = p.next;
              //  p.next = new ListNode(1);
                // 第二个链表
                ListNode l2 = new ListNode(5);
                ListNode q = l2;
                q.next = new ListNode(6);
                q = q.next;
                q.next = new ListNode(4);
              //  q = q.next;
               // q.next = new ListNode(9);
                ListNode re = addTwoNumbers(l1, l2);
                while(re != null) {
                    System.out.println(re.val); re = re.next;
                }
        }
        public static ListNode addTwoNumbers(ListNode l1, ListNode l2)
        {
            ListNode xList = new ListNode(0);//上来链表为空，所以第一位为0
            ListNode newList = xList;
            System.out.println(xList + "==" + newList);
            int curr = 0;
            while(l1 != null || l2 != null){
                //取值
                int x = l1 != null?l1.val:0;
                int y = l2 != null?l2.val:0;
                //System.out.println(x + "==" + y);
                //计算
                int sum = curr + x + y;
                //存值
                curr = sum /10;//取整
                newList.next = new ListNode(sum%10);//取余先给下一个位置赋值
                //移动指针指向下一个值
                newList = newList.next;
                System.out.println(xList + "==" + newList + "==" + xList.next);
                //System.out.println(newList.val);
                //取下一个节点的指针
                if(l1 != null)l1 = l1.next;
                if(l2 != null)l2 = l2.next;
            }
    
            if(curr > 0){
                newList.next = new ListNode(curr);
            }
            return xList.next;
        }
    }