目錄
- Robot Bounded In Circle
- Add to Array-Form of Integer
- Push Dominoes
- Elimination Game
- Battleships in a Board
- Multiply Strings
- Spiral Matrix
- Spiral Matrix II
1041. Robot Bounded In Circle
Easy
On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:
"G": go straight 1 unit;
"L": turn 90 degrees to the left;
"R": turn 90 degress to the right.
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
Input: "GGLLGG"
Output: true
Explanation:
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
題目大意：對一個機器人發(fā)送一系列重復(fù)的指令屑柔，要求判斷機器人會不會回到原點。
解題思路：指令是重復(fù)的，因此只要機器人不朝向北方掰邢，就有機會回到原點
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x = 0
y = 0
dir = 0 #direction - N W S E
#offset for each direction
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
for c in instructions:
if c == 'G': #go ahead by dir
x += dx[dir]
y += dy[dir]
elif c == 'L': #turn left
dir = (dir + 3)%4
elif c == 'R': #turn right
dir = (dir + 1)%4
return (x == 0 and y == 0) or dir != 0 #if go back to origin or not facing north
測試一下
Success
[Details]
Runtime: 32 ms, faster than 86.36% of Python3 online submissions for Robot Bounded In Circle.
Memory Usage: 13.2 MB, less than 100.00% of Python3 online submissions for Robot Bounded In Circle.
838. Push Dominoes
Medium
There are N dominoes in a line, and we place each domino vertically upright.
In the beginning, we simultaneously push some of the dominoes either to the left or to the right.
After each second, each domino that is falling to the left pushes the adjacent domino on the left.
Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.
Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.
Return a string representing the final state.
Example 1:
Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
Example 2:
Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.
題目大意：對于一組多米諾骨牌，給定一個初始化推的指令粟关，求出最終多米諾骨牌的狀態(tài)籽孙。
解題思路：通過推的指令，計算每一個骨牌的狀態(tài)向臀。
class Solution(object):
def pushDominoes(self, D):
"""
:type dominoes: str
:rtype: str
"""
max_int = 9999999
#record the distance from current dominoe to nearest push down one(left and right)
left_steps = [max_int for x in range(len(D))]
right_steps = [max_int for x in range(len(D))]
for i in range(len(D)):
if D[i] == 'L':
#if occur one push down domine
left_steps[i] = 0
#for all following domine that influenced
for j in range(i-1, -1, -1):
if D[j] != '.': #only influence '.'
break
left_steps[j] = left_steps[j+1]+1
elif D[i] == 'R':
right_steps[i] = 0
for j in range(i+1, len(D)):
if D[j] != '.':
break
right_steps[j] = right_steps[j-1]+1
#simulate the push work
ND = ''
for i in range(len(D)):
if left_steps[i] < right_steps[i]:
ND += 'L'
elif left_steps[i] > right_steps[i]:
ND += 'R'
else:
ND += '.'
return ND
測試一下，算法應(yīng)該是對的诸狭，但是用python實現(xiàn)會超時券膀，用golang或者cpp可以通過所有測試用例。
Time Limit Exceeded
[Details]
989. Add to Array-Form of Integer
Easy
For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].
Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.
Example 1:
Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234
題目大意：兩數(shù)相加驯遇，被加數(shù)以數(shù)組的形式提供芹彬。
解題思路：模擬手寫相加的方式，將進位保存在加數(shù)上叉庐。
class Solution(object):
def addToArrayForm(self, nums, k):
"""
:type A: List[int]
:type K: int
:rtype: List[int]
"""
nums.reverse()
ans = []
for i in range(len(nums)):
k += nums[i]
ans.append(k%10)
k //= 10
while k > 0:
ans.append(k%10)
k //= 10
ans.reverse()
return ans
測試一下舒帮，
Success
[Details]
Runtime: 264 ms, faster than 63.74% of Python online submissions for Add to Array-Form of Integer.
Memory Usage: 12.3 MB, less than 17.19% of Python online submissions for Add to Array-Form of Integer.
390. Elimination Game
Medium
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:
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6
題目大意：給一個數(shù)組[1:n]，從左到右陡叠，再從右到左玩郊，每隔一個元素消除一個，以此往復(fù)枉阵，直到只剩下一個元素译红。
解題思路：模擬消除元素的過程，直到剩下一個元素為止兴溜。
class Solution {
public int lastRemaining(int n) {
boolean left = true;
int remaining = n;
int step = 1;
int head = 1;
while (remaining > 1) {
if (left || remaining % 2 ==1) {
head = head + step;
}
remaining = remaining / 2;
step = step * 2;
left = !left;
}
return head;
}
}
lst = [i for i in range(1, n + 1)]
to_right = True
while len(lst) > 1:
print(lst)
if to_right:
lst = lst[1::2] #from the first node, skip by two
else:
lst = lst[len(lst)-2::-2] #from the last node, skip by two
lst.reverse() #do reverse
to_right = not to_right
if len(lst) == 1:
return lst[0]
else:
return -1 #no solution
測試一下
Success
[Details]
Runtime: 2 ms, faster than 100.00% of Java online submissions for Elimination Game.
Memory Usage: 33.8 MB, less than 93.66% of Java online submissions for Elimination Game.
419. Battleships in a Board
Medium
Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:
You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships.
Invalid Example:
...X
XXXX
...X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
題目大意：給一個矩陣作為地圖描述船的位置和形狀侦厚，要求求出船的數(shù)目反璃。
解題思路：從上往下，從左往右假夺，數(shù)出船的數(shù)目淮蜈。
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int ans = 0;
for (int i = 0; i < static_cast<int>(board.size()); i++) {
for (int j = 0; j < static_cast<int>(board[i].size()); j++) {
if (board[i][j] == 'X') {
if ((i < 1 || board[i - 1][j] == '.') && (j < 1 || board[i][j - 1] == '.')) {
ans++;
}
}
}
}
return ans;
}
};
測試結(jié)果，
Success
Details
Runtime: 4 ms, faster than 99.66% of C++ online submissions for Battleships in a Board.
Memory Usage: 9.7 MB, less than 45.37% of C++ online submissions for Battleships in a Board.
43. Multiply Strings
Medium
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
題目大意：以字符串的形式給定兩個數(shù)組已卷，求出兩數(shù)的乘積梧田，以字符串的形式返回。
解題思路：模擬手算兩數(shù)相乘的過程侧蘸。注意數(shù)字的高位是字符串的低位裁眯。注意最后結(jié)果字符串中零的處理，去除高位的無效零讳癌，但是結(jié)果為零時穿稳，需要保留最后一位零。
class Solution {
public:
string multiply(string num1, string num2) {
size_t m = num1.size(), n = num2.size();
string ans;
int sum = 0;
vector<int> prod(m + n);
//for (size_t i = m - 1; i >= 0; i--) {
// for (size_t j = n - 1; j >= 0; j--) {
// size_t low = i + j + 1,
// high = i + j; //in reverse order
// sum = (num1[i] - '0') * (num2[j] - '0') + prod[low];
// prod[high] += sum / 10;
// prod[low] = sum % 10;
// }
//} //do not use size_t in for loop
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
int p1 = i + j;
int p2 = i + j + 1;
int sum = (num1[i] - '0') * (num2[j] - '0') + prod[p2];
prod[p1] += sum / 10;
prod[p2] = sum % 10;
}
}
//find the highest valid bit
size_t idx = 0;
while (idx < prod.size() - 1 && prod[idx] == 0) {
idx++;
}
//combine the results
while (idx < prod.size()) {
ans += to_string(prod[idx++]);
}
return move(ans);
}
};
測試一下晌坤，
Success
Details
Runtime: 4 ms, faster than 98.40% of C++ online submissions for Multiply Strings.
Memory Usage: 9 MB, less than 61.35% of C++ online submissions for Multiply Strings.
54. Spiral Matrix
Medium
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
題目大意：以順時針螺旋的方式打印一個矩陣逢艘。
解題思路：模擬順時針讀矩陣的過程，方向：右-下-左-上-右...骤菠，用四條邊界來控制讀的停止它改。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if(matrix.size() == 0) //empty matrix
return ans;
int x = 0, y = 0, d = 0;
int total = matrix.size()*matrix[0].size();
int right = matrix[0].size() - 1, left = 0, up = 0, down = matrix.size() - 1;
//print until all elements have been printed
while(ans.size() < total){
switch(d){
case 0: //to right
if(y == right){
d = (d+1)%4; //change move direction
up++; //the uppest row is removed from next loop of reading
}else{
ans.push_back(matrix[x][y]);
y++; //print and advance
}
break;
case 1: //to down
if(x == down){
d = (d+1)%4;
right--;
}else{
ans.push_back(matrix[x][y]);
x++;
}
break;
case 2: //to left
if(y == left){
d = (d+1)%4;
down--;
}else{
ans.push_back(matrix[x][y]);
y--;
}
break;
case 3: //to up
if(x == up){
d = (d+1)%4;
left++;
}else{
ans.push_back(matrix[x][y]);
x--;
}
break;
}
}
return move(ans);
}
};
測試一下，
Success
Details
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Spiral Matrix.
Memory Usage: 8.7 MB, less than 40.35% of C++ online submissions for Spiral Matrix.
59. Spiral Matrix II
Medium
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
題目大意：對一個nxn的矩陣商乎，以順時針螺旋的方式賦值央拖。
解題思路：思路與上題相同，只是遍歷過程中處理的方式有差異鹉戚。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
if(n <= 0)
return vector<vector<int>>();
vector<vector<int>> ans(n, vector<int>(n, 0));
int total = n*n, cnt = 0, d = 0;
int right = n - 1, left = 0, up = 0, down = n - 1;
int x = 0, y = 0;
while(cnt < total){
switch(d){
case 0:
if(y == right){
d = (d+1)%4;
up++;
}else{
ans[x][y] = ++cnt; //assign value
y++;
}
break;
case 1:
if(x == down){
d = (d+1)%4;
right--;
}else{
ans[x][y] = ++cnt;
x++;
}
break;
case 2:
if(y == left){
d = (d+1)%4;
down--;
}else{
ans[x][y] = ++cnt;
y--;
}
break;
case 3:
if(x == up){
d = (d+1)%4;
left++;
}else{
ans[x][y] = ++cnt;
x--;
}
break;
}
}
return move(ans);
}
};
測試一下鲜戒，
Success
Details
Runtime: 4 ms, faster than 92.05% of C++ online submissions for Spiral Matrix II.
Memory Usage: 9 MB, less than 50.82% of C++ online submissions for Spiral Matrix II.
