阿里云几道高频题目
几道逻辑题
1000瓶药水找毒药
一共 1000 瓶药水,其中 1 瓶有毒药。已知小白鼠喝毒药一天内死。若想在一天内找到毒药,最少需要几只小白鼠?
10只。就是要把1000全表示出来,至少要10位。
每只老鼠作为10个bit里面的一位。
0000000001 第一只老鼠,喝第一瓶毒药
0000000010 第二只老鼠,喝第二瓶毒药
0000000011 第一只老鼠和第二只老鼠,喝第三瓶毒药
.。。。
这样,看哪些老鼠死了,找对应的bit位,就知道哪些瓶了。
抢30
抢 30 是双人游戏。游戏规则是:第一个人喊 “ 1 ”或 “ 2 ”,第二个人要接着往下喊一个或两个数,然后再轮到第以个人。两人轮流进行下去。最后喊 30 的人获胜。问喊数字的最佳策略。
要比另一个人抢到30,那就要提前抢到27,无论对方怎么喊,只要都回应3的倍数,就赢定了。对方喊2,他喊3;对方喊5,他喊6。。他喊27,对方喊28,29都无济于事。
灯泡开关
一个圆环上有 100 个灯泡,灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。 设计一种算法,对于任意初始状态,使所有灯泡全亮。
1-98按照其后后位,都能搞亮。
最后两个四种状态:
- 亮亮,完成。
- 亮暗、暗亮。
- 暗暗。按下100,则只有98变暗。
也就是最后都能到只有一个为暗的状态。三个一组,全暗。每个灯泡按一下,全亮。
11223344
一个天平
一个天平,有8个小球,其中7个一样重,还有一个稍微重点 。怎么选出重的,最优解怎么做?
首先分成三份,3 、 3、 2
- 如果3 和 3的重量一样,说明重点的在2那份里面,再称一次能得出结果,即称2次能得出答案。
- 如果3 和 3的重量不一样,说明已经知道重的在哪一份里面了,再把那份重的,再划分成三份:1、1、1,这样再称1次能得出答案。即称2次能得到答案。 所以综上,称2次就能选出稍微重的那一个。
100层会碎的两颗玻璃球
gdb多线程调试
要gdb同时查看代码,使用-tui
gdb main -tui
在TUI模式中,GDB窗口划分为两个子窗口——一个用于输入GDB命令,而另一个用于查看源代码。
内存泄漏检测工具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];
}
}
效果并不理想,应该是没有用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之后效率就上去了。
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;
}
}