Sao phải dislike nhiều thế nhỉ, bài này hồi sinh viên cũng có làm, dùng phép trừ và vòng lặp là xong mà
vì bọn leetcode nó chơi giới hạn độ phức tạp, tăng limit input đến tận INT_MAX và INT_MIN. Nói cách khác, bác mà xài phép trừ là "time limit exceeded" ngay
Nay thấy topic này vắng quá. Nên mình sẽ share bài mình mới làm chiều nay.
https://leetcode.com/problems/powx-n/
Yêu cầu là implement hàm pow.
Đọc đề xong thấy bài này easy vkl, k hiểu sao lại là medium, nghĩ trong bụng bài này chắc done trong 1 nốt nhạc. Chỉ cần 1 vòng for chạy từ 0->n rồi nhân lại là xong. dpt là O(n). Đến lúc submit thì bị timeout
.
Lúc đó ngồi nghĩ kỹ lại mới thấy bài này hoàn toàn có thể giải với đpt là O(logN).
tại vì m^n = m^(n/2)*m^(n/2) như vậy mình chỉ cần tính m^(n/2) 1 lần thôi.
Bài này chắc là kinh điển, nên chắc nhiều anh em cũng từng làm qua rồi.C++:class Solution { public: double myPow(double x, int n) { double result = 1; x = n > 0 ? x : 1/x; for (int i = 0; n != 0; i++){ result *= n%2!=0 ? x : 1; n/=2; x = x*x; } return result; } };
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
return self.myPow(1/x, -n)
elif n == 0:
return 1.0
elif n == 1:
return x
else:
if n%2 == 0:
half = self.myPow(x, n/2)
return half*half
else:
num = int(n/2)
half = self.myPow(x, num)
return half * x * half
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
multimap<int,int >mp;
sort(a,a+n,greater<int>() );
for(int i=0;i<n;i++){
int d=1;
while(a[i]==a[i+1]){
d++;
i++;
}
mp.insert({d,a[i]});
}
int b[n];
int k=0;
for(auto &it:mp){
for(int i=0;i<it.first;i++){
b[k]=it.second;
k++;
}
}
reverse(b,b+n);
for(int i=0;i<n;i++) cout<<b[i]<<" ";
cout<<endl;
}
}Ntn đã đủ gọn chưa bạn?
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
return self.myPow(1/x, -n)
elif n == 0:
return 1.0
elif n == 1:
return x
else:
half = self.myPow(x, n//2)
return half*half if n%2 == 0 else half * x * halfNtn đã đủ gọn chưa bạn?
Python:class Solution: def myPow(self, x: float, n: int) -> float: if n < 0: return self.myPow(1/x, -n) elif n == 0: return 1.0 elif n == 1: return x else: half = self.myPow(x, n//2) return half*half if n%2 == 0 else half * x * half
.
À, em có biết kiểu return này, quên mất, cảm ơn bác
Mà cái n//2 để lấy kiểu int em dùng python được hơn năm rồi mà chưa biết luôn ấy bác.
class Solution:
@cache
def myPow(self, x: float, n: int) -> float:
if n <= 2:
return x ** n if n >= 0 else self.myPow(1/x, -n)
return self.myPow(x, n // 2) * self.myPow(x, n // 2) * self.myPow(x, n % 2)
Python:class Solution: @cache def myPow(self, x: float, n: int) -> float: if n <= 2: return x ** n if n >= 0 else self.myPow(1/x, -n) return self.myPow(x, n // 2) * self.myPow(x, n // 2) * self.myPow(x, n % 2)
Đú code ngắn
Python:class Solution: @cache def myPow(self, x: float, n: int) -> float: if n <= 2: return x ** n if n >= 0 else self.myPow(1/x, -n) return self.myPow(x, n // 2) * self.myPow(x, n // 2) * self.myPow(x, n % 2)
Đú code ngắn
Mình nghĩ có thể bỏ @cache đi.Python:class Solution: @cache def myPow(self, x: float, n: int) -> float: if n <= 2: return x ** n if n >= 0 else self.myPow(1/x, -n) return self.myPow(x, n // 2) * self.myPow(x, n // 2) * self.myPow(x, n % 2)
Đú code ngắn
self.myPow(x, n // 2) * self.myPow(x, n // 2)self.myPow(self.myPow(x, n // 2), 2)Mình nghĩ có thể bỏ @cache đi.
thay
thànhPython:self.myPow(x, n // 2) * self.myPow(x, n // 2)
Ngắn hơn được 1 khúc nữa.Python:self.myPow(self.myPow(x, n // 2), 2)
Cái này cố viết ngắn hơn nhằm mục đích giải trí là chủ yếu thôi bạn.
Vậy thôi viết làDùng x**n đâu có tính đâu bác, vậy là cheat rồi
x if n == 1 else 1
.
Mấy cái lý thuyết lúc đầu đọc khó hiểu lắm. Làm nhiều sau đó đọc lại lý thuyết rồi nghiền ngẫm thì sẽ ngộ ra được thôi.Các bác chia sẻ với em cách các bác tiếp cận Greedy và thuần thục nó được không? Em đần quá mãi mấy hôm nay không thông não được
Greedy + math ở những bài A trên codeforces khó cực, em tìm ra được cái pattern rồi nhưng vẫn chưa nghĩ ra được công thức Để giải bàiMấy cái lý thuyết lúc đầu đọc khó hiểu lắm. Làm nhiều sau đó đọc lại lý thuyết rồi nghiền ngẫm thì sẽ ngộ ra được thôi.
Bản chất của greedy là các bài toán dạng tối ưu hóa và thường yêu cầu khả năng chứng minh được tại sao greedy lại đúng. Trong trường hợp chưa chứng minh được tính đúng đắn, khả năng rất cao là greedy sẽ bị sai nên bác hãy thử tìm phản ví dụ.Các bác chia sẻ với em cách các bác tiếp cận Greedy và thuần thục nó được không? Em đần quá mãi mấy hôm nay không thông não được
/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
var result = 0;
var sign = 1;
var tmp = [];
for(var i = 0; i < s.length; i++)
{
if(s[i] >= '0' && s[i] <= '9')
{
var nums = 0;
while(i < s.length && s[i] >= '0' && s[i] <= '9')
{
nums = nums * 10 + (s[i] - '0');
i++;
}
result = result + (nums * sign);
i--;
}
if(s[i] == '+')
{
sign = 1;
}
if(s[i] == '-')
{
sign = -1;
}
if(s[i] == '(')
{
tmp.push(result);
tmp.push(sign);
result = 0;
sign = 1;
}
if(s[i] == ')')
{
result = result * tmp[tmp.length - 1];
tmp.pop();
result = result + tmp[tmp.length - 1];
tmp.pop();
}
}
return result;
};
Bài này nằm trong mục daily challenge hôm nay và cũng là bài hard level đầu tiên tôi sử dụng JavaScript giải thành công. Nói thật bài này xứng đáng với mức medium chứ nó còn dễ hơn kha khá bài medium khác nữachuẩn rồi, bài này chỉ ở mức medium thôi. Làm xong trong 1 nốt nhạc.Độ khó: hard
Cho một chuỗi string s có nội dung là một biểu thức. Hãy tính biểu thức của chuỗi s này và trả về kết quả
Lưu ý: không được sử dụng những hàm dựng sẵn có tác dụng chuyển đổi string thành biểu thức toán học như eval()
Các hạn chế:
Độ dài chuỗi từ 1 cho đến 3 * (10 ^ 5)
Chuỗi chỉ bao gồm các chữ số, phép cộng, phép trừ, dấu ngoặc và khoảng trống
Mọi con số đều thuộc định dạng 32bit
https://leetcode.com/problems/basic-calculator/
Giải bằng JavaScript:
JavaScript:/** * @param {string} s * @return {number} */ var calculate = function(s) { var result = 0; var sign = 1; var tmp = []; for(var i = 0; i < s.length; i++) { if(s[i] >= '0' && s[i] <= '9') { var nums = 0; while(i < s.length && s[i] >= '0' && s[i] <= '9') { nums = nums * 10 + (s[i] - '0'); i++; } result = result + (nums * sign); i--; } if(s[i] == '+') { sign = 1; } if(s[i] == '-') { sign = -1; } if(s[i] == '(') { tmp.push(result); tmp.push(sign); result = 0; sign = 1; } if(s[i] == ')') { result = result * tmp[tmp.length - 1]; tmp.pop(); result = result + tmp[tmp.length - 1]; tmp.pop(); } } return result; };
ủa thằng multimap này nó tự sắp xếp giảm dần luôn hả thímKhông có gì đặc sắc hay khó khăn lắm, cơ mà bác nào có ý tưởng hay ho không?
Em mới tìm hiểu về map từ 2 hôm trước tự nhiên có bài này ốp vào ngon luôn
O(n.logn) vì cái sort
C++:#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } multimap<int,int >mp; sort(a,a+n,greater<int>() ); for(int i=0;i<n;i++){ int d=1; while(a[i]==a[i+1]){ d++; i++; } mp.insert({d,a[i]}); } int b[n]; int k=0; for(auto &it:mp){ for(int i=0;i<it.first;i++){ b[k]=it.second; k++; } } reverse(b,b+n); for(int i=0;i<n;i++) cout<<b[i]<<" "; cout<<endl; } }
