阿里云几道高频题目


几道逻辑题

1000瓶药水找毒药

一共 1000 瓶药水,其中 1 瓶有毒药。已知小白鼠喝毒药一天内死。若想在一天内找到毒药,最少需要几只小白鼠?

10只。就是要把1000全表示出来,至少要10位。

每只老鼠作为10个bit里面的一位。

0000000001 第一只老鼠,喝第一瓶毒药

0000000010 第二只老鼠,喝第二瓶毒药

0000000011 第一只老鼠和第二只老鼠,喝第三瓶毒药

.。。。

这样,看哪些老鼠死了,找对应的bit位,就知道哪些瓶了。

抢30

抢 30 是双人游戏。游戏规则是:第一个人喊 “ 1 ”或 “ 2 ”,第二个人要接着往下喊一个或两个数,然后再轮到第以个人。两人轮流进行下去。最后喊 30 的人获胜。问喊数字的最佳策略。

要比另一个人抢到30,那就要提前抢到27,无论对方怎么喊,只要都回应奇数,就赢定了。对方喊2,他喊3;对方喊5,他喊7。。。他喊27,对方喊28,29都无济于事。

灯泡开关

一个圆环上有 100 个灯泡,灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。 设计一种算法,对于任意初始状态,使所有灯泡全亮。

1-98按照其后后位,都能搞亮。

最后两个四种状态:

  • 亮亮,完成。
  • 亮暗、暗亮。
  • 暗暗。按下100,则只有98变暗。

也就是最后都能到只有一个为暗的状态。三个一组,全暗。每个灯泡按一下,全亮。

11223344

image-20220301000612923

一个天平

一个天平,有8个小球,其中7个一样重,还有一个稍微重点 。怎么选出重的,最优解怎么做?

首先分成三份,3 、 3、 2

  1. 如果3 和 3的重量一样,说明重点的在2那份里面,再称一次能得出结果,即称2次能得出答案。
  2. 如果3 和 3的重量不一样,说明已经知道重的在哪一份里面了,再把那份重的,再划分成三份:1、1、1,这样再称1次能得出答案。即称2次能得到答案。 所以综上,称2次就能选出稍微重的那一个。

100层会碎的两颗玻璃球

gdb多线程调试

要gdb同时查看代码,使用-tui

gdb main -tui

在TUI模式中,GDB窗口划分为两个子窗口——一个用于输入GDB命令,而另一个用于查看源代码。

image-20220228232132823

image-20220228234215357

内存泄漏检测工具valgrind神器。

coredump

程序运行过程中,发生异常,程序会退出,os把程序当前的内存状况存储在core文件中,即coredump。

在程序运行的过程中,有的时候我们会遇到Segment fault(段错误)这样的错误。这种看起来比较困难,因为没有任何的栈、trace信息输出。该种类型的错误往往与指针操作相关。往往可以通过这样的方式进行定位。

操作系统在程序发生异常而异常在进程内部又没有被捕获的情况下,会把进程此刻内存、寄存器状态、运行堆栈等信息转储保存在一个文件里。可以用gdb分析里面的具体内容。

215. 数组中的第K个最大元素

最小堆

时间复杂度:nlogk

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 两个方法:最小堆、快速选择
        // 1
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0;i<k;i++) {
            minHeap.add(nums[i]);
        }

        for(int i=k;i<nums.length;i++) {
            minHeap.add(nums[i]);
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

快速选择

玛德,一段时间不写一时之间还写不对。

class Solution {
    public int findKthLargest(int[] nums1, int k) {
        int[] nums = Arrays.copyOfRange(nums1,0,nums1.length);
        int left = 0;
        int right = nums.length-1;

        k = nums.length-k;
        
        while(left<right) {
            int p = nums[left];
            int start = left;
            int end = right;
            while(start<end) {
                while(start<end&&nums[end]>=p) end--;
                nums[start] = nums[end];
                while(start<end&&nums[start]<p) start++;
                nums[end] = nums[start];
            }
            nums[start] = p;
            if(start==k) return nums[start];
            else if(start>k) right=start-1;
            else if(start<k) left=start+1;
        }
        return nums[left];
    }
}

image-20220228212556761

效果并不理想,应该是没有用Random。

class Solution {
    public int findKthLargest(int[] nums1, int k) {
        int[] nums = Arrays.copyOfRange(nums1,0,nums1.length);
        int left = 0;
        int right = nums.length-1;

        Random random = new Random();
        k = nums.length-k;
        
        while(left<right) {
            int rand = left+random.nextInt(right-left);
            swap(nums,left,rand);
            int p = nums[left];
            int start = left;
            int end = right;
            while(start<end) {
                while(start<end&&nums[end]>=p) end--;
                nums[start] = nums[end];
                while(start<end&&nums[start]<p) start++;
                nums[end] = nums[start];
            }
            nums[start] = p;
            //System.out.println(Arrays.toString(nums));
            if(start==k) return nums[start];
            else if(start>k) right=start-1;
            else if(start<k) left=start+1;
        }
        return nums[left];
    }

    private void swap(int[] nums,int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

加了Random之后效率就上去了。

image-20220228212903388

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();
        ListNode cur = head;
        while(cur!=null) {
            deque.addLast(cur);
            cur = cur.next;
        }
        ListNode fakeHead = new ListNode();
        ListNode p = fakeHead;
        while(!deque.isEmpty()) {
            p.next = deque.pollLast();
            p = p.next;
        }
        p.next = null;
        return fakeHead.next;
    }
}

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        //  a     b     c     d     e
        //                  before  cur    next
        if(head==null||head.next==null) return head;
        ListNode before = null;
        ListNode cur = head;
        ListNode n = cur.next;
        while(cur!=null) {
            n = cur.next;
            cur.next = before;
            before = cur;
            cur = n;
        }
        return before;
    }
}

递归

递归并不好理解。

class Solution {
    public ListNode reverseList(ListNode head) {
        // a   b   c    d
        //        head cur
        // a -> b ->  c  <-  d
        //     head          cur
        if(head==null||head.next==null) return head;
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}

19. 删除链表的倒数第 N 个结点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        // 找到第N-1个结点。
        ListNode fakeHead = new ListNode();
        fakeHead.next = head;
        ListNode fast = fakeHead;
        for(int i=0;i<n+1;i++) {
            fast = fast.next;
        }
        ListNode slow = fakeHead;
        while(fast!=null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode toBeDeleted = slow.next;
        slow.next = slow.next.next;
        toBeDeleted.next = null;
        return fakeHead.next;
    }
}

5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        for(int i=0;i<s.length();i++) {
            int left = i;
            int right = i;
            int len = 1;
            while(left>=1&&right<s.length()-1&&s.charAt(left-1)==s.charAt(right+1)) {
                len+=2;
                left--;
                right++;
            }
            if(len>result.length()) {
                result = s.substring(left,right+1);
            }
        }

        for(int i=0;i<s.length()-1;i++) {
            int left = i+1;
            int right = i;
            int len = 1;
            while(left>=1&&right<s.length()-1&&s.charAt(left-1)==s.charAt(right+1)) {
                len+=2;
                left--;
                right++;
            }
            if(len>result.length()) {
                result = s.substring(left,right+1);
            }
        }

        return result;
    }
}