Nếu vậy thì là tốt rồi. Ráng lên chú e. Có gì cần giúp đỡ thì cứ lên đây hỏi.e năm 1 bác ạ, vừa mới thi xong c, tự lần mò c++ biết mỗi mấy cái hàm với cái vector, map vớ vẩn @@, mấy cái auto gì kia e k biết. Nói chung là tuy là c++ mà e code như c thôi, chẳng khác tí gì
Link test: LC
class Solution {
public:
int longestCommonSubseq(string& s1,string& s2){
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(n1+1,vector<int>(n2+1));
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
dp[i][j]=s1[i-1]==s2[j-1] ? dp[i-1][j-1] + 1 : max(dp[i][j-1],dp[i-1][j]);
}
}
return dp[n1][n2];
}
int longestPalindromeSubseq(string s) {
string rev = s;
reverse(s.begin(),s.end());
return longestCommonSubseq(s,rev);
}
};
9h30 có cuộc thi nhé fen, cố làm được bài 1
hay fen, cần 1 lời chứng minh, tại sao string và restring lấy LCS là ra đáp án?
class Solution {
public:
char findTheDifference(string s, string t) {
int x=0,y=0;
for(int i=0;i<s.length();i++){
x+=(int)(s[i]);
}
for(int i=0;i<t.length();i++){
y+=(int)(t[i]);
}
return (char)(y-x);
}
};
bài này sort rồi so sánh cũng ổn
vâng bác, em giờ mới bắt đầu học. Giờ bắt đầu tìm hiểu con trỏ các thứ, mong được các bác chỉ giáoNếu vậy thì là tốt rồi. Ráng lên chú e. Có gì cần giúp đỡ thì cứ lên đây hỏi.
Cái auto đơn giản là để compiler nó tự suy luận ra kiểu của dữ liệu, dựa vào value mình init.
Bài này cách đơn giản nhất là dùng greedy nhé. Lấy sum của nguyên dãy. Sau đó sort theo thứ tự giảm dần. Rồi lấy ra n phần tử đầu tiên > sum/2. Code như này:
C++:class Solution { public: vector<int> minSubsequence(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); sort(nums.begin(), nums.end(), greater()); int sumSub = 0; auto it = nums.begin(); while (sumSub <= sum/2){ sumSub += *it; it++; } return vector(nums.begin(), it); } };
Runtime: 10 ms, faster than 14.73% of C++ online submissions for Minimum Subsequence in Non-Increasing Order.
Cách này chưa được tối ưu lắm. Có tgian mình sẽ nghĩ cách tốt hơn.
func minSubsequence(nums []int) []int {
totalSum := calculateSum(nums)
sort.Slice(nums, func(i,j int) bool{
return nums[i] > nums[j]
})
accumulateSum := 0
for i := range nums {
accumulateSum += nums[i]
if accumulateSum <= totalSum - accumulateSum {
continue
}
return nums[0:i+1]
}
return nums
}
func calculateSum(nums []int) int {
sum := 0
for _, num := range nums {
sum += num
}
return sum
}
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m, n = len(board), len(board[0])
count = 0
for r in range(m):
for c in range(n):
if board[r][c] == 'X' and ((r == 0) or board[r - 1][c] != 'X') and ((c == 0) or board[r][c - 1] != 'X'): # đây là ô đầu tàu
count += 1
return countT thử lại rồi. Cùng 1 solution đó mà lúc chỉ beats 3%, lúc thì beats 90%,
. Chắc có thể do testcase k đủ lớn, nên nhiều khi tùy vào work load của hệ thống bên leetcode mà nó chạy nhanh chậm khác nhau.
Nó có nhiều CTDL & thư viện hỗ trợ thuật toán tốt hơn.
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
q = deque([(root, 0)])
res = []
while q:
node, level = q.popleft()
if not node:
continue
while level >= len(res):
res.append([])
res[level].append(node.val)
for child in node.children:
q.append((child, level + 1))
return res
int n;
vector<int> A, p;// predecessor array
void print_LIS(int i) { // backtracking routine
if (p[i] == -1) {
cout << A[i] << " ";
return;
}// base case
print_LIS(p[i]); // backtrack
cout << A[i] << " ";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// note: A[n] must be set as the largest value ("INF")
// so that all LIS (that can start anywhere) will end at n
cin >> n;
A.assign(n + 1, 0);
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
A[n] = INF; // set A[n] = INF
cout << "n = " << n << ": ";
for (int i = 0; i < n; ++i)
cout << A[i] << " ";
cout << "\n";
int k = 0, lis_end = 0;
vi L(n, 0), L_id(n, 0);
p.assign(n + 1, -1);
for (int i = 0; i < n; ++i) { // O(n)
int pos = lower_bound(L.begin(), L.begin() + k, A[i]) - L.begin();
L[pos] = A[i]; // greedily overwrite this
L_id[pos] = i; // remember the index too
p[i] = pos ? L_id[pos - 1] : -1; // predecessor info
if (pos == k) { // can extend LIS?
k = pos + 1; // k = longer LIS by +1
lis_end = i; // keep best ending i
}
}
cout << "Final LIS is of length " << k << ": ";
print_LIS(lis_end);
return 0;
}@thuyduong2007 @_Gia_Cat_Luong_ @clonemasteruwu
K rành C++ lắm nhưng về logic thì thay lower_bound thành upper_bound ?
