13.2万

AlbertEdison

Hasity
violet_garden
Misaki_2
Kristen

AGang

ssolidy

dtl

yydsw2x

5个月前

(KMP) $O(n+m)$

1. next[i]记录子串ha[1, 2, , , i - 1, i]的最长相等前后缀的前缀最后一位下标，或者说是子串的最长相等前后缀的长度
2. 预处理出next数组。
3. 遍历字符串ha
● 当ha字符串和ne字符串发生失配时，根据next数组回退到其他位置。
● 当匹配ne字符串的终点时，用匹配终点i减去字符串ne的长度m即是答案。

KMP核心思路如下图所示：

C++代码

class Solution {
public:
int strStr(string ha, string ne) {
int n = ha.size(), m = ne.size();
if(m == 0) return 0;
vector<int> next(m + 1);
ha = ' ' + ha ,ne = ' ' + ne;
for(int i = 2, j = 0; i <= m; i++){
while(j && ne[i] != ne[j + 1]) j = next[j];
if(ne[i] == ne[j + 1]) j++;
next[i] = j;
}
for(int i = 1, j = 0; i <= n; i++){
while(j && ha[i] != ne[j + 1]) j = next[j];
if(ha[i] == ne[j + 1]) j++;
if(j == m){
return i - m;
}
}
return -1;
}
};


Java代码

class Solution {
public int strStr(String ha, String ne) {
if (ha.isEmpty()) return 0;
int n = ha.length(), m = ne.length();
ha = " " + ha;
ne = " " + ne;
int[] next = new int[m + 1];
for (int i = 2, j = 0; i <= m; ++i) {
while (j > 0 && ne.charAt(i) != ne.charAt(j + 1)) j = next[j];
if (ne.charAt(i) == ne.charAt(j + 1)) j++;
next[i] = j;
}
for (int i = 1, j = 0; i <= n; ++i) {
while (j > 0 && ha.charAt(i) != ne.charAt(j + 1)) j = next[j];
if (ha.charAt(i) == ne.charAt(j + 1)) j++;
if (j == m) {
return i - m;
}
}
return -1;
}
}


Go代码

func strStr(ha string, ne string) int {
if len(ne) == 0 {
return 0
}
n, m := len(ha), len(ne)
ha, ne = " " + ha, " " + ne
next := make([]int, m + 1)
for i, j := 2, 0; i <= m; i++ {
for j > 0 && ne[i] != ne[j + 1] {
j = next[j]
}
if ne[i] == ne[j+1] {
j++
}
next[i] = j
}
for i, j := 1, 0; i <= n; i++ {
for j > 0 && ha[i] != ne[j + 1] {
j = next[j]
}
if ha[i] == ne[j + 1] {
j++
}
if j == m {
return i - m
}
}
return -1
}


5个月前

(数组) $O(n)$

C++代码

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for(int i = 0; i < nums.size(); i++){
if(!i || nums[i] != nums[i - 1])
nums[k++] = nums[i];
}
return k;
}
};


Java代码

class Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0 || nums[i] != nums[i - 1])
nums[k++] = nums[i];
}
return k;
}
}


Go代码

func removeDuplicates(nums []int) int {
k := 0
for i := 0; i < len(nums); i++ {
if i == 0 || nums[i] != nums[i - 1] {
nums[k] = nums[i]
k++
}
}
return k
}


5个月前

(链表) $O(n)$

1. 将后k个元素进行倒序操作，共操作k - 1次，详细操作看代码（注意：需要确保有k个元素才操作）
2. 将后k个元素倒序后的序列的尾部指向后k + 1的元素
3. 将p->next指向倒序后的序列的头部
4. 更新p指针的位置，即指向倒序后的序列的尾部

C++代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy =  new ListNode(-1);
for(auto p = dummy; ;)
{
auto q = p;
for(int i = 0;  i < k && q; i++) q = q->next;
if(!q) break;
auto a = p->next,b = a->next;
for(int i = 0; i < k - 1; i++)
{
auto next = b->next;
b->next = a;
a = b, b = next;
}
auto c = p->next;
c->next = b,p->next = a;
p = c;
}
return dummy->next;
}
};


Java代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
for(ListNode p = dummy;;)
{
ListNode q = p;
for(int i = 0;i < k && q != null; i++) q = q.next;
if(q == null)  break;
ListNode a = p.next, b = a.next;
for(int i = 0; i < k - 1; i++)
{
ListNode next = b.next;
b.next = a;
a = b;
b = next;
}
ListNode c = p.next;
c.next = b;
p.next = a;
p = c;
}
return dummy.next;
}
}


Go代码

func reverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{Val : -1, Next : nil}
p := dummy
for p.Next != nil {
q := p
for i := 0; i < k && q != nil; i++ {
q = q.Next
}
if q == nil {
break
}
a := p.Next
b := a.Next
for i := 0; i < k - 1; i++ {
next := b.Next
b.Next = a
a = b
b = next
}
c := p.Next
c.Next = b
p.Next = a
p = c
}
return dummy.Next
}


5个月前

(模拟) $O(n)$

1、首先定义p = dummya = p->nextb = a->next
2、遍历整个链表，第一步先将pnext指针指向b，即p->next = b
3、然后将anext指向b->next，即a->next = b->next
4、最后将bnext指向a，即b->next = a

5、最后返回虚拟头节点的下一个节点

C++代码

class Solution {
public:
ListNode*  dummy = new ListNode(-1);  //虚拟头节点
for(auto p = dummy; p->next && p->next->next; )
{
auto a = p->next, b = a->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};


Java代码

class Solution {
ListNode dummy = new ListNode(0);
for(ListNode p = dummy; p.next != null && p.next.next != null;)
{
ListNode a = p.next;    //虚拟头节点
ListNode b = a.next;
p.next = b;
a.next = b.next;
b.next = a;
p = a;
}
return dummy.next;
}
}


Go代码

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
dummy := &ListNode{Val : -1, Next : nil}
p := dummy
for p.Next != nil && p.Next.Next != nil {
a := p.Next
b := a.Next
p.Next = b
a.Next = b.Next
b.Next = a
p = a
}
return dummy.Next
}


5个月前

(优先队列） $O(nlogk)$

struct cmp{ //自定义排序规则
bool operator() (ListNode* a, ListNode* b){
return a->val > b->val;  // val值小的在队列前
}
};


1、定义一个优先队列，并让val值小的元素排在队列前。
2、新建虚拟头节点dummy，定义 cur指针并使其指向 dummy
3、首先将k个链表的头节点都加入优先队列中。
4、当队列不为空时：

• 取出队头元素t（队头即为k个指针中元素值最小的指针）;
• curnext 指针指向t，并让cur后移一位；
• 如果tnext指针不为空，我们将t->next加入优先队列中；

5、最后返回dummy->next

C++代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

struct cmp{   //自定义排序规则
bool operator()(ListNode* a, ListNode * b){
return a->val > b->val;  //元素值小的在前面
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(auto l : lists) if(l) heap.push(l);
ListNode* dummmy = new ListNode(-1);
ListNode* cur = dummmy;
while(heap.size()){
auto t = heap.top();
heap.pop();
cur = cur->next = t;
if(t->next) heap.push(t->next);
}
return dummmy->next;
}
};


Java代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((x,y) -> (x.val - y.val));
for(ListNode l : lists) if(l != null) heap.add(l);
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(!heap.isEmpty()){
ListNode t = heap.poll();
cur = cur.next = t;
}
return dummy.next;
}
}


Go代码

type minHeap []*ListNode

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) {
*h = append(*h, x.(*ListNode))
}
func (h *minHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

func mergeKLists(lists []*ListNode) *ListNode {
h := new(minHeap)
for i := 0; i < len(lists); i++ {
if lists[i] != nil {
heap.Push(h, lists[i])
}
}
dummy := new(ListNode)
cur := dummy
for h.Len() > 0 {
t := heap.Pop(h).(*ListNode)
cur.Next = t
cur = cur.Next
if t.Next != nil {
heap.Push(h, t.Next)
}
}
return dummy.Next
}


5个月前

(dfs) $O(C_{2n}^{n})$

● 1、左右括号数量相等
● 2、任意前缀中左括号数量 >= 右括号数量 （也就是说每一个右括号总能找到相匹配的左括号）

void dfs(int n ,int lc, int rc ,string str)


n是括号对数，lc是左括号数量，rc是右括号数量，str是当前维护的合法括号序列。

● 1、初始时定义序列的左括号数量lc 和右括号数量rc都为0
● 2、如果 lc < n，左括号的个数小于n，则在当前序列str后拼接左括号。
● 3、如果 rc < n && lc > rc , 右括号的个数小于左括号的个数，则在当前序列str后拼接右括号。
● 4、当lc == n && rc == n 时，将当前合法序列str加入答案数组res中。

C++代码

class Solution {
public:
vector<string> res;
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0, "");
return res;
}

void dfs(int n, int lc, int rc, string str){
if(lc == n && rc == n){
res.push_back(str);
return ;
}
if(lc < n) dfs(n, lc + 1, rc, str + '(');
if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ')');
}
};


Java代码

class Solution {
static List<String> res = new ArrayList<String>();  //记录答案

public List<String> generateParenthesis(int n) {
res.clear();
dfs(n, 0, 0, "");
return res;
}
public void dfs(int n ,int lc, int rc ,String str) {
if( lc == n && rc == n) res.add(str);   //递归边界
else {
if(lc < n) dfs(n, lc + 1, rc, str + "(");            //拼接左括号
if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ")"); //拼接右括号
}
}
}


Go代码

var res []string

func generateParenthesis(n int) []string {
res = make([]string, 0)
dfs(n, 0, 0, "")
return res
}

func dfs(n int, lc int, rc int, path string) {
if lc == n && rc == n {
res = append(res, path)
return
} else {
if lc < n {
dfs(n, lc + 1, rc, path + "(")
}
if rc < lc {
dfs(n, lc, rc + 1, path + ")")
}
}

}


5个月前

(线性合并) $O(n)$

1、新建虚拟头节点 dummy，定义 cur指针并使其指向 dummy
2、当l1l2都不为为空时：
○ 若l1->val < l2->val，则令 curnext 指针指向l1l1后移；
○ 若l1->val >=l2->val，则令 curnext 指针指向l2l2后移；
cur后移一步；
3、将剩余的 l1l2 接到 cur 指针后边。
4、最后返回dummy->next

C++代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while(l1 && l2){
if(l1->val < l2->val){
cur->next = l1;
l1 = l1->next;
}else{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if(l1) cur->next = l1;
if(l2) cur->next = l2;
return dummy->next;
}
};


Java代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}
else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null) cur.next = l1;
if(l2 != null) cur.next = l2;
return dummy.next;
}
}


Go代码

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{Val : -1, Next : nil}
cur := dummy
for l1 != nil && l2 != nil {
if(l1.Val < l2.Val){
cur.Next = l1;
l1 = l1.Next
} else {
cur.Next = l2;
l2 = l2.Next
}
cur = cur.Next
}
if(l1 != nil) {
cur.Next = l1
}
if(l2 != nil) {
cur.Next = l2
}
return dummy.Next
}


5个月前

(排序 + 双指针） $O(n^2)$

1. 将整个nums数组按从小到大排好序
2. 枚举每个数，表示该数nums[i]已被确定，在排序后的情况下，通过双指针lr分别从左边l = i + 1和右边r = n - 1往中间靠拢，找到nums[i] + nums[l] + nums[r] == 0的所有符合条件的搭配
3. 在找符合条件搭配的过程中，假设sum = nums[i] + nums[l] + nums[r]
sum > 0，则r往左走，使sum变小
sum < 0，则l往右走，使sum变大
sum == 0，则表示找到了与nums[i]搭配的组合nums[l]和nums[r]，存到res中
4. 判重处理
确定好nums[i]时，l需要从i + 1开始
nums[i] == nums[i - 1]，表示当前确定好的数与上一个一样，需要直接跳过
当找符合条件搭配时，即sum == 0,需要对相同的nums[l]nums[r]进行判重处理

C++代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++){
if(i && nums[i] == nums[i - 1]) continue;  //跳过相同的i，保证每次都是新开始
int l = i + 1, r = n - 1;
while(l < r){
int sum = nums[i] + nums[l] + nums[r];
if(sum > 0) r--;
else if(sum < 0) l++;
else if(sum == 0){
res.push_back({nums[i], nums[l], nums[r]});
do l++; while(l < r && nums[l] == nums[l - 1]);  //跳过相同的l
do r--; while(l < r && nums[r] == nums[r + 1]);  //跳过相同的r
}
}
}
return res;
}
};


Java代码

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for(int i = 0;i < n ;i ++){
if(i != 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1,r = n - 1;
while(l < r){
int sum = nums[i] + nums[l] + nums[r];
if(sum > 0) r--;
else if(sum < 0) l++;
else if(sum == 0){
do l ++; while(l < r && nums[l] == nums[l - 1]);
do r --; while(l < r && nums[r] == nums[r + 1]);
}
}
}
return res;
}
}


Go代码

func threeSum(nums []int) [][]int {
res := [][]int{}
sort.Ints(nums)
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
l, r := i + 1, len(nums) - 1
for l < r {
sum := nums[i] + nums[l] + nums[r]
if sum > 0 {
r--
}else if sum < 0 {
l++
}else if sum == 0 {
res = append(res, []int{nums[i], nums[l], nums[r]})
for l < r && nums[l] == nums[l + 1] {
l++
}
for l < r && nums[r] == nums[r - 1] {
r--
}
l++; r--
}
}
}
return res
}


5个月前

(字符串)

1、我们以第一个字符串为基准，枚举第一个字符串的每一位。
2、遍历整个字符串数组，让其他字符串的每一位同第一个字符串做比较，如果不相等或者到达了其他字符串终点，则直接返回结果。
3、否则说明最长公共前缀可以扩展，结果加上第一个字符串的当前位。

C++代码

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if(strs.empty()) return res;
string str1 = strs[0];
for(int i = 0; i < str1.size(); i++){
for(string str : strs){
if(i >= str.size() || str[i] != str1[i]) return res;
}
res += str1[i];
}
return res;
}
};


Java代码

class Solution {
public String longestCommonPrefix(String[] strs) {

StringBuilder res = new StringBuilder();
for (int i = 0; i < strs[0].length(); ++i) {
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; ++j) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return res.toString();
}
}
res.append(c);
}
return res.toString();
}
}


Go代码

func longestCommonPrefix(strs []string) string {
res := ""
if len(strs) == 0 {
return res
}
str1 := strs[0]
for i := 0;  i < len(str1); i++ {
for j := 1; j < len(strs); j++ {
if i >= len(strs[j]) || str1[i] != strs[j][i] {
return res
}
}
res += string(str1[i])
}
return res
}


5个月前

C++代码

class Solution {
public:
string intToRoman(int num) {
int  valus[]={
1000,
900,500,400,100,
90, 50, 40, 10,
9,  5,  4,  1
};
string luoma[]{
"M",
"CM","D","CD","C",
"XC","L","XL","X",
"IX","V","IV","I"
};
string res;
for(int i = 0; i < 13; i++)
{
while(num >= valus[i])
{
num -= valus[i];
res += luoma[i];
}
}
return res;
}
};


Java代码

class Solution {
static String[] luoma = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
static int[] values = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
public String intToRoman(int num) {
String res = "";
for(int i = 0;i < 13; i++)
{
while(num >= values[i])
{
num -= values[i];
res += luoma[i];
}
}
return res;
}
}


Go代码

func intToRoman(num int) string {
values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
luoma := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
res := ""
for i := 0; i < 13; i++ {
for num >= values[i] {
num -= values[i]
res += luoma[i]
}
}
return res
}