Leetcode刷题（一）

发表于 | 分类于 | 阅读数 次
字数统计: 2.3k 字 | 阅读时长 ≈ 11 分钟

Leetcode 4 Longest Palindromic Substring 最长回文子串

最近在做Leetcode碰到这么一题,本以为很简单….主要还是自己太菜了
LeetCode回文串共有五倒题,除了这一题还有Palindrome Number,Validate Palindrome,Palindrome Paartitioning,Palindrome PartitioningII.
传统的验证回文串的方法就是两个两个的对称验证是否相等,那么对于找回文串的问题,就要以每一个字符为中心,向两边扩散来寻找回文串,这个算法的时间复杂度是O(n×n)
解法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution{
public:
  string longestPalindrome(string s){
    if(s.size()<2)
      return s;
    int n=s.size();
    int maxLen=0;
    int start=0;
    for(int i=0;i<n-1;i++){
      searchPalindrome(s,i,i,start,maxLen);
      searchPalindrome(s,i,i+1,start,maxLen);
    }
    return s.substr(start,maxLen);
  }

  void searchPalindrome(string s,int left,int right,int & start,int & maxLen){
    while(left>=0&&right<s.size()&&s[left]==s[right]){
      left--;
      right++;
    }
    if(maxLen<right-left-1){
      start=left+1;
      maxLen=right-left-1;
    }
  }




};

解法二:可以不利用子函数,直接一个函数写成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution{
public:
  string longestPalindrome(string s){
    if(s.size()<2) {
      return s;
    }
    for(int i=0;i<n;){
      if(n-i<=maxLen/2)
        break;
      int left=i,right=i;
      while(right<n-1&&s[right+1]==s[right])
      {
        right++;
      }
      i=right+1;
      while(right<n-1&&left>0&&s[right+1]==s[left-1]){
        right++;
        left--;
      }
      if(maxLen<right-left+1){
        maxLen=right-left+1;
        start=left;
      }

    }
    return s.substr(start,maxLen);

  }
};

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
8
[

  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        addingpar(res, "", n, 0);
        return res;
    }
    void addingpar(vector<string> &v, string str, int n, int m){
        if(n==0 && m==0) {
            v.push_back(str);
            return;
        }
        if(m > 0){ addingpar(v, str+")", n, m-1); }
        if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
    }
};

常见回溯法总结

回溯法如何设计

  1. 起手式
    回溯法，就是试探法，按照优选条件去向前搜索，以达到目标。
    但是在搜索到某一步时，发现原先这样并不能满足条件，就回退一步重新选择，这种走不通就退回再走的技术成为回溯法。
    在做回溯法的题目的时候，有添加状态或元素就一定有与之对应的回退状态和元素。若是寻找成功，回退以查看有没有其他满足条件的解；如果寻找不成功，回退以查看其它情况。
    解题一般步骤:
    (1)针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间至少包含问题的一个(最优)解
    (2)确定结点的扩展搜索规则
    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索.

八皇后问题(直接看其衍生NQueen)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
     bool IsConflict(vector<int> y,int b){
        for(int i=0;i<y.size();i++){
            int m=y.size();
            if(y[i]-b==0 ||abs(y[i]-b)==abs(m-i)){
                return false;
            }

        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        int k=1;
        vector<int> record;
        vector<vector<string>>S;
        vector<string> M;
        NQueen(k,n,record,S,M);
        return S;   
    }

    void NQueen(int k,int n,vector<int> record,vector<vector<string>> &S,vector<string> M){
        if(k<=n){
            for(int i=0;i<n;i++){
                string s="";
                if(IsConflict(record,i)){
                    for(int j=0;j<n;j++){
                        if(j==i){
                            s+="Q";
                        }
                        else{
                            s+=".";
                        }
                    }
                    M.push_back(s);
                    record.push_back(i);
                    NQueen(k+1,n,record,S,M);
                    record.pop_back();
                    M.pop_back();

                }

            }

        }
        else{
            S.push_back(M);

        }
    }
};

可以看到回溯法的一些特点：

  1. 需要递归的函数的形式为void
  2. 参数变量中需要有一个引用变量专门用来在递归时保存数据的.
  3. 返回到上一层递归函数时需要对已经进行过的操作进行撤回,以便用其他操作代替该操作
  4. 需要存在一个出口,在出口处保存下已经完成的序列.

最经典的回溯法是在树结构中的深度优先遍历(DFS).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
#include<stack>
#include<memory.h>

using namespace std;

vector<vector<int>> tree;//声明一个二维向量
int flag[10];//用于搜索到了节点i的第几个节点
stack <int>stk;//声明一个堆栈
int ar_tree[8] = { 1,1,1,3,5,3,5,7 };
void DFS(int node) {
	cout << node <<" ";
	if (flag[node] == 0) {
		stk.push(node);
	}
	int temp;
	//判断node的子节点是否搜索完成
	if (flag[node] < tree[node].size()) {
		temp = tree[node][flag[node]];
		flag[node]++;
		DFS(temp);
	}
	else {//若已经完成
		stk.pop();//弹出子节点
		if (!stk.empty()) {//若堆栈不为空
			temp = stk.top();//取此时的栈顶元素，即为node的上一级节点
			DFS(temp);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	memset(flag, 0, sizeof(flag));
	register int i,temp;
	tree.resize(10);//图中的数共有九个节点
	//生成树
	for (i = 2; i <=9; i++) {
		temp = ar_tree[i - 2];
		tree[temp].push_back(i);//表示第i个节点为第temp个节点的子节点
	}
	//DFS
	cout << "DFS过程：" << endl;
	DFS(1);
	cout << endl;
	return 0;
}

算法过程:

  1. 从根节点开始
  2. 放入一个节点(起始时放入的是根节点)
  3. 如果这个节点是第一次出现,则放入堆栈中
  4. 判断该节点的子节点是否搜索完成
    a.如果是则将该节点出栈,判断该栈是否为空
    a.1若为空则结束
    a.2若不为空则取栈顶元素,并回到第2步
    b.如果没有完成搜索,取未被搜索的根节点,并返回到第2步

迷宫问题的求解

有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从一个位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，如何找到一条到达终点的通路。本文将用两种不同的解决思路，四种具体实现来求解迷宫问题。
用二维矩阵来模拟迷宫地图，1代表该位置不可达，0代表该位置可达。每走过一个位置就将地图的对应位置标记，以免重复。找到通路后打印每一步的坐标，最终到达终点位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>  
#include <iomanip>  
#include <cstdlib>  
using namespace std;

#define MaxSize 100  
int maze[10][10] =   //定义一个迷宫，0表示通道，1表示墙  
{
    { 1,1,1,1,1,1,1,1,1,1 },
    { 1,0,0,1,1,0,0,1,0,1 },
    { 1,0,0,1,0,0,0,1,0,1 },
    { 1,0,0,0,0,1,1,0,0,1 },
    { 1,0,1,1,1,0,0,0,0,1 },
    { 1,0,0,0,1,0,0,0,0,1 },
    { 1,0,1,0,0,0,1,0,0,1 },
    { 1,0,1,1,1,0,1,1,0,1 },
    { 1,1,0,0,0,0,0,0,0,1 },
    { 1,1,1,1,1,1,1,1,1,1 }
};

struct Try //定义一个栈，保存路径  
{
    int i;               //当前方块的行号  
    int j;               //当前广场的列号  
    int d;              //di是下一可走方位的方位号  
} path[MaxSize];         //定义栈  

int top = -1;            //初始化栈指针  

void findPath(int xb, int yb, int xe, int ye);

int main()
{
    int x1, x2, y1, y2;
    cout << "请设定起点（x1，y1）：" << endl;
    cout << "x1:";
    cin >> x1;
    cout << "y1:";
    cin >> y1;
    cout << "请设定终点（x2，y2）：" << endl;
    cout << "x2:";
    cin >> x2;
    cout << "y2:";
    cin >> y2;
    findPath(x1, y1, x2, y2);    //从（x1，y1）进入，从（x2，y2）出
    system("pause");
    return 0;
}

void findPath(int xb, int yb, int xe, int ye)            //路径为从(xb,yb)到(xe,ye)  
{
    int i, j, d, find, k;
    top++;                                             //初始方块进栈  
    path[top].i = xb;
    path[top].j = yb;
    path[top].d = -1;
    maze[xb][yb] = -1;
    while (top>-1)                                      //栈不为空时循环  
    {
        i = path[top].i;
        j = path[top].j;
        d = path[top].d;
        if (i == xe && j == ye)                             //找到了出口，输出路径  
        {
            cout << "迷宫路径如下：\n";
            for (k = 0; k <= top; k++)
            {
                cout << "\t(" << path[k].i << "," << path[k].j << ")";
                if ((k + 1) % 5 == 0)
                    cout << endl;            //每输出五个方块后换一行  
            }
            cout << endl;
            return;
        }
        find = 0;
        while (d<4 && find == 0)                          //找下一个可走的点  
        {
            d++;
            switch (d)
            {
            case 0:  //向上  
                i = path[top].i - 1;
                j = path[top].j;
                break;
            case 1: //向右  
                i = path[top].i;
                j = path[top].j + 1;
                break;
            case 2:  //向下  
                i = path[top].i + 1;
                j = path[top].j;
                break;
            case 3:  //向左  
                i = path[top].i;
                j = path[top].j - 1;
                break;
            }
            if (maze[i][j] == 0) find = 1;                      //找到通路  
        }
        if (find == 1)                                        //找到了下一个可走方块  
        {
            path[top].d = d;                               //修改原栈顶元素的d值  
            top++;                                         //下一个可走方块进栈  
            path[top].i = i;
            path[top].j = j;
            path[top].d = -1;
            maze[i][j] = -1;                                 //避免重复走到这个方块  
                                                             //cout << "\t(" << path[top].i << "," << path[top].j << ")"; //显示经过的试探  
        }
        else  //没有路可走，则退栈  
        {
            maze[path[top].i][path[top].j] = 0;                  //让该位置变成其它路径可走方块  
            top--;
        }
    }
    cout << "没有可走路径！"<<endl;
}

-------------本文结束感谢您的阅读-------------