leetcode 389~399 solution

本次题解包括:

  • 389 Find the Difference
  • 390 Elimination Game
  • 391 Perfect Rectangle
  • 392 Is Subsequence
  • 393 UTF-8 Validation
  • 394 Decode String
  • 395 Longest Substring with At Least K Repeating Characters
  • 396 Rotate Function
  • 397 Integer Replacement
  • 398 Random Pick Index
  • 399 Evaluate Division

389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

传送门:leetcode Find the Difference

题意:给定只包含小写字母的两个字符串s和t,t是将s随机打乱并添加一个字母x组成。字母x

思路:

直接计数 看看不相等的即可。 当然python可以 one line

 

 

390. Elimination Game

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

传送门:leetcode Elimination Game

题意:给定一个数n,要求每次轮流从左到右、从右到左删除剩下的数(间隔一个删除一个),求最后剩下的数

思路:用链表模拟的话O(nlogn),但是可以直接计算出每次开头和结尾的地方,复杂度O(logn)

注意到每次删除上一轮之后,可以看成是下一次的步长step *= 2(初始为2,所以删除1,3,5,7….)

记录左右两个端点left和right,

  • 若是从左到右,发现 left + (right – left) // step * step == right,则需要更新右端点。
  • 若从右到左,right – (right – left) // step * step == left 则更新左端点。
  • 上面的//是整除的意思

Python

 

 

 

 

 

 

391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

Example 2:

Example 3:

Example 4:

传送门:leetcode Perfect Rectangle

题意:给定一些矩形,求这些矩形是否能恰好组成一个矩形面积。

思路:

合法的矩形区域有什么条件呢?

参考 https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination

0_1472399247817_perfect_rectangle.jpg

  • 上图中蓝色的点只能出现1次
  • 绿色的点有2个矩形的某个顶点一致
  • 红色的有4个矩形某个顶点一致

首先,遍历所有的矩形,对其四个端点进行编号(左下1,右下2,右上4,左上8,编号为1,2,4,8是为了方便位运算)。然后对于每个点(比如左上角),如果在之前的矩形中,同样也是作为左上角出现,那么说明重复了,返回False。具体的操作是用位运算(看下面的check函数)

最后判断蓝色的点是否为4个,还有总面积是否相等。

Python

下面的这种方法从上面的改进,由于绿色出现2次,红色4次,那么用一个Hash记录即可,若当前点不存在,添加,存在则删除。最后剩下的只可能是4个蓝色的点,并且总面积要相等。

Python

 

 

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

传送门:leetcode Is Subsequence

题意:给定字符串s和很长的字符串t,判断s是否是t的子串。比如ace是abcde子串,而aec不是。

思路:双指针,一个指向s一个指向t,当s[i] == t[j]则 继续判断s的下一个字符和j之后的是否匹配。这样的正确性在于as是b的子串,它的相对顺序是不变的。

Python

 

 

393. UTF-8 Validation

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  1. For 1-byte character, the first bit is a 0, followed by its unicode code.
  2. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

Example 2:

传送门:leetcode UTF-8 Validation

题意:给定一个数组,数组中每个数字为UTF8的4个byte的编码。判断该数组是否是合法的UTF-8序列。合法的序列如下表。

比如以1110开头的,后面需要有2个10开头的数字。

思路:直接扫描判断需要有几个10开头的数字即可,然后看看是否足够。

Python

 

 

394. Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

传送门:leetcode Decode String

题意:给定一个缩略表示法的字符串,要求将其展开。比如s = “3[a]表示有3个a 应该展开为aaa。题目保证输入串合法,无额外的空格。

思路:用栈,碰到数字就算一下,碰到字母就放进当前的字符串,碰到[则压入栈,碰到]则从栈顶弹出并更新当前字符串。

Python

 

 

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Example 2:

传送门:leetcode Longest Substring with At Least K Repeating Characters

题意:给定一个字符串s和k,求字符串最长的子串T,在T中的所有字符至少出现k次。

思路:

枚举起点和终点,对于满足条件的进行计算。(貌似还可以分治?过阵子看看)

Python

但是由于是小写字母,所以可以用位运算来快速的判断是否符合条件。(上面的是每次扫整个hash表)

Python

C++

 

 

 

396. Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

传送门:leetcode Rotate Function

题意:给定数组A, 将A进行循环右移,每次分别计算 F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1].(B为循环右移K次的值),求max(F(k))

思路:先求出和以及F(0)。 然后每次循环右移的时候,显然是上一次的结果+s – n*A[i](这个已经到第0个位置,清除掉)

Python

 

 

 

397. Integer Replacement

Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

 

Example 2:

传送门:leetcode Integer Replacement

题意:给定一个数n,若n为奇数可以加一或者减一,若n为偶数,则/2,求把它变为1至少需要几步?

思路:直接递归暴力求值。

Python

要让其有最少的步数,就要尽量在n为奇数的时候减少1的个数。

例如15,二进制为1111

  • 1111->10000->1000->100->10->1
  • 1111->1110->111->110->11->10->1

如果一个数以0b11结尾,那么,+1显然是更好的选择(因为加一会至少消掉2个1),否则可以-1。当然,3是例外。

Python

 

 

398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

传送门:leetcode Random Pick Index

题意:给定一个数组,每次给定一个数x,要求随机返回数组中x的下标(等概率)

思路:用hash + list MLE了。 那就类似于之前的 382. Linked List Random Node

扫描数组,若当前数字等于x,则有 1/cnt的概率取代它(cnt为当前出现了多少次x)

Python

 

 

 

 

399. Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , whereequations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

传送门:leetcode Evaluate Division

题意:给定一些表达式和它对应的值,然后要求求解一些表达式的值,如果不存在则返回-1.

思路:

用图的思想来做。对于x/y = v,建立(x,y,v)和(y,x,1/v)两条边,表示x->y值为v,y->x值为1/v,(v!=0)

对于求解a/b,若有解,我们只需要能找到这样的路径,从a出发,经过若干个点之后,到达b。 则它们路途中的值相称就是对应的解。

比如有边(a,c)  (c,d) (d,b) 表示a/c ,c/d, d/b,相乘即可。

于是建立好图之后,进行DFS,并沿路求积。

Python

 

 

这是leetcode 389~399的题解,更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 389~399 solution
本文地址:https://www.hrwhisper.me/leetcode-389-399-solution/

打赏一杯咖啡钱呗

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *