文章目录
session Ⅰ Algorithm
problem Ⅰ
344. Reverse String
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: s = [“h”,“e”,“l”,“l”,“o”]
Output: [“o”,“l”,“l”,“e”,“h”]
Example 2:
Input: s = [“H”,“a”,“n”,“n”,“a”,“h”]
Output: [“h”,“a”,“n”,“n”,“a”,“H”]
class Solution {
public:
void reverseString(vector<char>& s) {
int len = s.size();
for(int i=0;i<len/2;i++){
char tmp = s[i];
s[i] = s[len-1-i];
s[len-1-i] = tmp;
//swap(s[i], s[len-1-i]);
}
}
};
problem Ⅱ
557. Reverse Words in a String III
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Example 2:
Input: s = “God Ding”
Output: “doG gniD”
my solution
time complexity O(N)
Space complexity O(1)
class Solution {
public:
string reverseWords(string s) {
int i,j;i=j=0;
int len=s.size();
while(i < len){
while(s[i] != ' ' && i != len-1)++i;
if(i != len-1){
int lent = i-j;
for(int p=j; p < j+lent/2; p++)
swap(s[p], s[2*j+lent-1-p]);
++i;j=i;
}else{
++i;
int lent = i-j;
for(int p=j; p < j+lent/2; p++)
swap(s[p], s[2*j+lent-1-p]);
}
}
return s;
}
};
others solution
- using space i.e., space complexity : O(N)
string reverseWords(string s) {
string str="",temp="";
int i=0;
for(;i<s.size();i++)
{
if(s[i]!=' ')
temp=s[i]+temp;
else
{
str+=temp+' ';
temp="";
}
}
str+=temp;
return str;
}
}
- without space i.e., Space complexity O(1) :
string reverseWords(string s) {
int i=0,j=0,temp;
for(int i=0;i<s.size();i++)
{
if(s[i]==' ' || i==s.size()-1)
{
if(s[i]==' ')
temp=i-1;
else
temp=i;
while(j<temp)
{
swap(s[j],s[temp]);
j++;
temp--;
}
j=i+1;
}
}
return s;
}
};
session Ⅱ DataStructure
problem Ⅰ
119. Pascal’s Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
my solution (recursion)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> currArr = {1};
if(rowIndex==0)return currArr;
vector<int> preArr = getRow(rowIndex-1);
for(int i=1;i<rowIndex; i++)
currArr.push_back(preArr[i-1] + preArr[i]);
currArr.push_back(1);
return currArr;
}
};
my solution (loop)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> curr,pre;
pre = {1};
if(rowIndex==0)return {1};
for(int i=1; i<=rowIndex; i++){
curr = {};
curr.push_back(1);
for(int j=1; j<i; j++)
curr.push_back(pre[j-1] + pre[j]);
curr.push_back(1);
pre = curr;
}
return curr;
}
};
my solution (loop with pre declare)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> curr,pre={1};
if(rowIndex==0)return {1};
for(int i=1; i<=rowIndex; i++){
curr = {};
curr.push_back(1);
for(int j=1; j<i; j++)
curr.push_back(pre[j-1] + pre[j]);
curr.push_back(1);
pre = curr;
}
return curr;
}
};
problem Ⅱ
48. Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i=0; i<n-1; i++)
for(int j=i+1; j<n; j++)
swap(matrix[i][j], matrix[j][i]);
for(int col=0; col<n; col++)
for(int i=0; i<n/2; i++)
swap(matrix[col][i], matrix[col][n-1-i]);
}
};
note:
i came up with this solution in a whim, maybe thanks to my solid foundation in linear algebra
so my solution is that:
- first we just transpose the matrix,
- and my we reverse ever rows of the matrix
reverse a array is like this problrm
problem Ⅲ
59. Spiral Matrix II
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
#define up 0
#define down 1
#define left 2
#define right 3
vector<vector<int>> matrix(n, vector<int>(n,0));
int i,j,pre=right;
i=j=0;
for(int num=1; num<=n*n; num++){
matrix[i][j] = num;
switch (pre)
{
case up:
if(i > 0 && !matrix[i-1][j]) i--;
else {pre=right; j++;}
break;
case down:
if(i < n-1 && !matrix[i+1][j]) i++;
else {pre=left; j--;}
break;
case left:
if(j>0 && !matrix[i][j-1]) j--;
else {pre=up; i--;}
break;
case right:
if(j < n-1 && !matrix[i][j+1]) j++;
else {pre=down; i++;}
break;
}
}
return matrix;
}
};
note:
i think this problem is a state transition, we have 4 state:
- left
- right
- up
- down
and we have 4 state transition:
- right->down
- down->left
- left->up
- up->right
the schematic diagram is as follows
state transition
right->down
down->left
left->up
up->right
1
pre=right and j<n-1: right
pre=right and j=n-1: down
2
pre=left and j>0: left
pre=left and j=0: up
3
pre=down and i<n-1: down
pre=down and i=n-1:left
4
pre=up and i>0: up
pre=up and i=0: right