介绍

计算机历史上有一个非常经典的问题叫做Maximum-Subarray-Problem， 求数组的最大子序列，要求该子序列和为最大值，子序列应当连续。

比如 [−2, 1, −3, 4, −1, 2, 1, −5, 4]， 最大应该子序列为 [4, −1, 2, 1]。

暴力的解法是算出所有的子序列，然后求和，该方法的时间复杂度为O(n^2).

Kadane’s Algorithm

Kadane’s Algorithm是求解该类问题的一个通法，原理是利用Dynamic Programming保存所有以i结尾的子序列的最大长度，dp公式为:

题目描述

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

• A move is guaranteed to be valid and is placed on an empty block.
• Once a winning condition is reached, no more moves is allowed.
• A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
  Read more »

题目描述

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list’s nodes, only nodes itself may be changed.
  Read more »

题目描述

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.
  Read more »

前言

之前出于无聊投了一次Bytedance的后端校招，刚刚收到一面，前面聊项目还是十分愉快的，到了算法部分，遇到了一个不是很常规的题目，很遗憾，当时并没有解出来，体现了我对于陌生题目的思考速度的欠缺，以及心态可能还是不够稳定，不过这也展现了宇宙条手撕代码的难度，居然会出LeetCode上没有的题(Leetcode114有一点相似，但并不完全一样)特此记录分享一下。

题目描述

题目其实挺有意思，二叉树和双向链表很相像(说实话在此之前从来没有注意过这一点)，都是有两个指针指向两个不同的地方，要求将二叉树的中序遍历转换为双向链表，原地转换，不允许借助辅助空间。

题目描述

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

题目描述

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

题目描述

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

1
2
3
4
5
6
7
8

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

解析

题目描述

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

1
2
3

Example1:
Input: prob = [0.4], target = 1
Output: 0.40000

1
2
3

Example2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

1
2

Explanation:
[[3,1]] is also accepted.

1
2
3
4
5

Constraints:
1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

解析