_Gia_Cat_Luong_
Senior Member
Tại lười đấy fen. Não nghĩ sao viết vậy cho nó nhẹ đầu :v.Python mà nhiều chữ thế ct.
Tại lười đấy fen. Não nghĩ sao viết vậy cho nó nhẹ đầu :v.Python mà nhiều chữ thế ct.
return accumulate([[1]] * numRows, lambda n, _: [sum(p) for p in zip(n + [0], [0] + n)])
return accumulate([[1]] * numRows, lambda n, _: list(map(sum, pairwise([0] + n + [0]))))
class Solution {
public:
vector<vector<int>> generate(int numRows) {
std::vector<std::vector<int>> res(numRows, {1});
std::transform(res.begin(), res.end() - 1, res.begin() + 1, res.begin() + 1, [](auto &v1, auto &v2) {
std::adjacent_difference(v1.begin(), v1.end(), std::inserter(v2, v2.begin()), std::plus<int>());
return std::move(v2);
});
return res;
}
};
s
để đánh index => các index array đều đã được sort.word
, dùng binary search để tìm trong các index array kia.public class Solution {
Dictionary<char, List<int>> index = new ();
public int NumMatchingSubseq(string s, string[] words) {
for (char c = 'a'; c <= 'z'; c++)
index.Add(c, new List<int>());
for (var i = 0; i < s.Length; i++)
{
index[s[i]].Add(i);
}
int count = 0;
foreach (var word in words)
{
if (isSs(word))
{
count++;
}
}
return count;
}
bool isSs(string word)
{
int pre = -1;
foreach (var c in word)
{
if (index[c] == null)
return false;
int found_index = index[c].BinarySearch(pre+1);
if (found_index < 0)
found_index = ~found_index;
if (found_index >= index[c].Count)
return false;
pre = index[c][found_index];
}
return true;
}
}
- Lưu vị trí xuất hiện của các ký tự tiếp theo kể từ một index cho trước
Đi ngược từ cuối mảng lên nha fen. Với mỗi index thì update lại vị trí của ký tự tương ứng, chi phí thực ra là O(26*s)bác có thể đề xuất thuật toán để tính cái này trong thời gian O(s) không?
dp = []
nextIndex = [inf for _ in range(26)]
for i in range(len(s) - 1, -1, -1):
dp.append(nextIndex.copy())
nextIndex[ord(s[i]) - ord('a')] = i
dp.reverse()
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) i++;
j++;
}
return i == s.length();
}
Đi ngược từ cuối mảng lên nha fen. Với mỗi index thì update lại vị trí của ký tự tương ứng, chi phí thực ra là O(26*s)
Python:dp = [] nextIndex = [inf for _ in range(26)] for i in range(len(s) - 1, -1, -1): dp.append(nextIndex.copy()) nextIndex[ord(s[i]) - ord('a')] = i dp.reverse()
Chuẩn rồi fen. Một bên là 26*s một bên là log(s). Dễ thấy để mà 26 < log(s) thì s phải dài đến 2^26 = 70tr ký tự. Trong khi bài này chỉ tầm 10k.Thử lại thấy không nhanh hơn dùng binary search.
Có lẽ cách này sẽ có tác dụng khi tìm kiếm với số lượng từ lớn.
map = functools.reduce(lambda _, n: d[n[1]].append(n[0]) or d, enumerate(s), d:=defaultdict(list))
return sum(1 for w in words if functools.reduce(lambda p, n: p + [next((i for i in map[n] if i > p[-1]), -1)], w, [-2]).count(-1) == 0)
return [reduce(lambda p, n: p[1:] if p and p[0] == n else p, s, w) == '' for w in words].count(True)
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
first=ListNode(next=head)
idx=0
cur=first
last=None
# find nodes before left and after right
while cur:
if idx==left:
prev_node=last
if idx==right:
next_node=cur.next
idx+=1
last=cur
cur=cur.next
# reverse left->right and connect
p1,p2=next_node,prev_node.next
while True:
tmp=p2.next
p2.next=p1
p1=p2
p2=tmp
if p2==next_node:
break
prev_node.next=p1
return first.next
One pass dễ màBài hnay e chỉ có nghĩ đc cách này thôi. Hóng các cao nhân one-pass
Python:class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: first=ListNode(next=head) idx=0 cur=first last=None # find nodes before left and after right while cur: if idx==left: prev_node=last if idx==right: next_node=cur.next idx+=1 last=cur cur=cur.next # reverse left->right and connect p1,p2=next_node,prev_node.next while True: tmp=p2.next p2.next=p1 p1=p2 p2=tmp if p2==next_node: break prev_node.next=p1 return first.next