zkkKillua's Blog

面试题62. 圆圈中最后剩下的数字

发表于 2020-03-30 更新于 2024-03-02 分类于 leetcode

约瑟夫环

n个人编号0,1,2,…,n-1，每数m次删掉一个人
假设有函数f(n)表示n个人最终剩下人的编号
n个人删掉1个人后可以看做n-1的状态，不过有自己的编号。
n个人删掉的第一个人的编号是(m-1)%n，那么n个人时删掉第一个人的后面那个人(m-1+1)%n一定是n-1个人时候编号为0的那个人，即n个人时的编号m%n（这个编号是对于n个人来考虑的）。
n-1个人时编号为i的人就是n个人时(m+i)%n
所以f(n)=(m+f(n-1))%n
f(1)=0，因为1个人时只有一个编号0。
从人数为1个时逆推即可。

作者：fu-sang-shu-xie
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/li-jie-gui-lu-hen-jian-dan-javascriptjie-fa-by-fu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

阅读全文 »

面试题59 - II. 队列的最大值

发表于 2020-03-29 更新于 2020-09-13 分类于 leetcode

class listNode {
public:
    listNode() {val = 0; next = NULL;}
    listNode(int v) {val = v; next = NULL;}
    listNode(int v, listNode *n) {val = v; next = n;}
    int val;
    listNode *next;
};

class MaxQueue {
public:
    MaxQueue() {
        head = NULL;
        tail = NULL;
        maxVal = NULL;
    }
    
    int max_value() {
        if (maxVal == NULL)
            return -1;
        else
            return maxVal->val;
    }
    
    void push_back(int value) {
        listNode *newNode = new listNode(value, NULL);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
            maxVal = newNode;
        }
        else {
            tail->next = newNode;
            tail = newNode;
            if (value >= maxVal->val)
                maxVal = newNode;
        }
    }
    
    int pop_front() {
        if (head == NULL)
            return -1;
        else {
            int res;
            if (head == tail) {
                res = head->val;
                delete head;
                head = NULL;
                tail = NULL;
                maxVal = NULL;
            } else {
                listNode *temp = head->next;
                res = head->val;
                if (head == maxVal) {
                    maxVal = head->next;
                    listNode *p = maxVal->next;
                    while (p != NULL) {
                        if (p->val >= maxVal->val)
                            maxVal = p;
                        p = p->next;
                    }
                }
                delete head;
                head = temp;
            }
            return res;
        }
    }
private:
    listNode *head;
    listNode *tail;
    listNode *maxVal;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

1162. As Far from Land as Possible

发表于 2020-03-29 更新于 2020-09-13 分类于 leetcode

框架

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {

    }
};

1. 朴素

统计每个0和1的位置，储存到vector中，对每个0直接求到所有1的曼哈顿距离的最小值。
时间O(n^2logn)，空间O(n).
超时了

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        bool hasZero = false, hasOne = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (hasZero && hasOne)
                    break;
                if (grid[i][j] == 0 && !hasZero)
                    hasZero = true;
                if (grid[i][j] == 1 && !hasOne)
                    hasOne = true;
            }
        }
        if (!hasZero || !hasOne)
            return -1;

        vector<pair<int, int> > zeros;
        vector<pair<int, int> > ones;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0)
                    zeros.push_back(make_pair(i, j));
                else
                    ones.push_back(make_pair(i, j));
            }
        }

        int ans = 0;
        for (int i = 0; i < zeros.size(); i++) {
            int curAns = 2 * n;
            for (int j = 0; j < ones.size(); j++) {
                int dis = abs(zeros[i].first - ones[j].first) + abs(zeros[i].second - ones[j].second);
                curAns = curAns <= dis ? curAns : dis;
                if (curAns == 1)
                    break;
            }
            ans = ans >= curAns ? ans : curAns;
        }

        return ans;
    }
};

阅读全文 »

820.Short Encoding of Words

发表于 2020-03-29 更新于 2020-09-13 分类于 leetcode

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is [“time”, “me”, “bell”], we can write it as S = “time#bell#” and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

阅读全文 »

914.X of a Kind in a Deck of Cards

发表于 2020-03-27 更新于 2020-09-13 分类于 leetcode

In a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards.
All the cards in each group have the same integer.

Example 1:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].
Example 2:

阅读全文 »

999. Available Captures for Rook

发表于 2020-03-26 更新于 2020-09-13 分类于 leetcode

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1:

阅读全文 »

892.Surface Area of 3D Shapes

发表于 2020-03-25 更新于 2020-09-13 分类于 leetcode

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

Example 1:

阅读全文 »

面试题 17.16. 按摩师

发表于 2020-03-24 更新于 2020-09-13 分类于 leetcode

A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appoint ment requests, find the optimal (highest total booked minutes) set the masseuse can honor. Return the number of minutes.

Note: This problem is slightly different from the original one in the book.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Accept request 1 and 3, total minutes = 1 + 3 = 4
Example 2:

阅读全文 »

面试题57 - II. 和为s的连续正数序列

发表于 2020-03-23 更新于 2020-09-13 分类于 leetcode

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

阅读全文 »

876.Middle of the Linked List

发表于 2020-03-23 更新于 2020-09-13 分类于 leetcode

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:

阅读全文 »