Attack lab

简介

这是CSAPP的第三个实验，跟Bomb lab有些类似，都需要你对X86-64汇编语言以及一套调试的方式有着足够的理解，所不同的是，这一次更注重于写汇编语言的代码，并且以Byte的格式注入到程序内，用来攻击程序，简单地说，这个实验就是模拟一个黑客所做的事情。

实验分为两个部分注入攻击和返回值攻击，前者的栈的地址是固定的，裸奔状态，后者每次栈内存起始地址都会发生变化，难度有所增加。与Bomb lab不同的是，这个实验如果攻击失败，不会扣分，可以放心地进行各种调试和实验的操作。

Bomb Lab

简介

这是CMU15213课程的第二个实验，也是十分经典的一个实验，世界上用CSAPP当教科书的高校一般都会保留这个实验，实验要求是给一个用C语言编写的可执行文件bomb，你可以看到它主函数的C语言代码，除此之外，一概不知，实验分为六个阶段，每个阶段需要输入一串字符，有点像破译密码，如果六次输入的密码都是对的，炸弹解除，否则炸弹会爆炸(退出，并打印爆炸信息)，如果是CMU的学生，每个人获得的炸弹是不一样的（高超的 反作弊技巧），每次爆炸会扣0.5分，扣满20分为止。不过我们作为自学党，没有这个限制，用的是自学用bomb，随便炸，根本不虚，不过为了达成良好的学习效果，还是尽可能减少爆炸次数。

题目描述

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example :

1
2
3
4

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

• 1 <= A.length <= 30000
• 1 <= A[i] <= 30000
  Read more »

题目描述

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

1
2
3

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3

Input: 9973
Output: 9973
Explanation: No swap.

Note:

The given number is in the range [0, 108]

题目描述

Given a robot cleaner in a room modeled as a grid.

Each cell in the grid can be empty or blocked.

The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Input:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

Note:

• The input is only given to initialize the room and the robot’s position internally. You must solve this problem “blindfolded”. In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot’s position.
• The robot’s initial position will always be in an accessible cell.
  The initial direction of the robot will be facing up.
• All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
• Assume all four edges of the grid are all surrounded by wall.

起源

Boyer-Moore Vote Algorithm由UT Austion的Robert S. Boyer 和 J Strother Moore提出，是为了解决找出一个数组中出现次数大于n / 2 的数的，其中n为数组长度，乃至可以类推到找出k - 1个出现次数大于n / k的数。这个问题直观上来可以使用哈希表统计出现次数，不过对于算法优化的追求，使得许多存储空间是不必要的，通过使用Boyer-Moore Majority Vote Algorithm（可译为摩尔投票）空间复杂度可以降低到O(1)，这道题现在经常出现在公司面试题中。

intution

如果存在出现次数大于n / k的 k - 1个数，那么剩下的数字的总数必然小于(k - 1) * k / n，比如找出大于一半的数，如果这个数存在则剩下所有的数的出现次数总和必然小于一半。即将数组抽象为两个部分，出现n / 2次数的数k，和非k。

算法

• Initialize an element m and a counter i with i = 0
• For each element x of the input sequence:
  • If i = 0, then assign m = x and i = 1
  • else if m = x, then assign i = i + 1
• else assign i = i − 1
• Return m
  用找大于n / 2来举例，设置一个candidate和count，如果找到一个数等于candidiate则count + 1，否则count - 1如果count变成0，则将candidate更新为当前指针所指的新数字。
  下图来自于wikipedia，直观上说明了为什么这个算法是可行的：

题目

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

1
2
3
4

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

1
2
3
4

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
    with the number of occurrence being 4, 3, 2 and 1 respectively.

题目描述

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

1
2
3
4
5
6
7
8

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Note:

• A.length <= 30000
• 0 <= S <= A.length
• A[i] is either 0 or 1

题目描述

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

题目描述

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.