You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Solution {
public:
double myPow(double x, int n) {
double ans = 1.;
int sign = n>=0?1:-1;
n *= sign;
while(n){
if(n%2) ans *= x;
x *= x;
n /= 2;
}
if(sign==-1) ans = 1./ans;
return ans;
}
};
51, N-Queens
Question: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Question: Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
Idea: partial sum:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size(), ans = nums[0];
vector<int> P(n+1,0);
for(int i=1;i<=n;++i) P[i] = P[i-1] + nums[i-1];
for(int i=1,tmp=0;i<=n;++i){
ans = max(ans, P[i] - tmp);
tmp = min(tmp, P[i]);
}
return ans;
}
};
54, Spiral Matrix
Question: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Idea: figure out which direction to go at each position:
Question: Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Idea: The same as the previous version, i.e. using greedy,
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
if(n<=1) return true;
for(int i=0,j=nums[0];j<n-1;++i){
j = max(j,i+nums[i]);
if(i==j) return false; //### 这个顺序很，别犯低级错误
}
return true;
}
};
56, Merge Intervals
Question: Given a collection of intervals, merge all overlapping intervals.
Idea: sort and find ending points:
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
static bool cmp(const Interval &x, const Interval &y) {
if(x.start == y.start) return x.end < y.end;
return x.start < y.start;
}
class less{
public:
bool operator ()(const Interval &x, const Interval &y) const {
if(x.start == y.start) return x.end < y.end;
return x.start < y.start;
}
};
public:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> ans;
if(intervals.empty()) return ans;
//sort(intervals.begin(),intervals.end(),cmp);
sort(intervals.begin(),intervals.end(),less());
int s = INT_MIN, e = INT_MIN;
for(int i=0;i<intervals.size();++i){
if(intervals[i].start <= e) e = max(e, intervals[i].end);
else{
if(i) ans.push_back(Interval(s,e));
s = intervals[i].start;
e = intervals[i].end;
}
}
ans.push_back(Interval(s,e));
return ans;
}
};
57, Insert Interval
Question: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> ans;
int s = newInterval.start, e = newInterval.end, i = 0, n = intervals.size();
while(i<n && intervals[i].end < s) ans.push_back(intervals[i++]);
while(i<n && intervals[i].start<= e){
s = min(s,intervals[i].start);
e = max(e,intervals[i++].end);
}
ans.push_back(Interval(s,e));
while(i<n) ans.push_back(intervals[i++]);
return ans;
}
};
58, Length of Last Word
Question: Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
Idea: Easy string manipulation
class Solution {
public:
int lengthOfLastWord(string s) {
s = s.substr(0,s.find_last_not_of(" ")+1);
return s.size() - 1 - s.find_last_of(" ");
}
};
59, Spiral Matrix II
Question: Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order. For example, Given n = 3, You should return the following matrix:
Question: The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Idea: Residue count (every time divided by (l-1)!)
class Solution {
const string Str = "123456789";
vector<int> fac;
public:
string getPermutation(int n, int k) {
fac = vector<int>(n,1);
string ans = Str.substr(0,n);
--k;
for(int i=2;i<n;++i) fac[i] = i*fac[i-1];
for(int i=0;i<n;++i){
if(!k) return ans;
int m = k/fac[n-i-1];
if(m){
char c = ans[i+m];
for(int j=m-1;j>=0;--j) ans[i+j+1] = ans[i+j];
ans[i] = c;
}
k %= fac[n-i-1];
}
return ans;
}
};