whoway

# ♻️编码技巧

  • 递归/迭代

  • 打表，记忆化

  • 链表/数组

以前，对于很多概念都混淆，现在用自己的理解，将概念进行分类：
将具体实现代码的手法，我称之为『编程技巧』，不用“算法思想”那么高的高度进行描述。
1
2

# 📑 目录

  • ⭐️1、双指针『应对-数组』
  • ✡️2、递归『应对-链表-树』
  • 🍀3、将『栈和递归』转换得炉火纯青
  • ✏️4、迭代
  • ☁️5、空间换时间之打表、记忆化（前、后缀等）

[TOC]

# 1.双指针

  • 有的书上叫“尺取法”

# 1.1.综述：双指针的常见技巧

  • 快慢指针（fast和low）
  • 左右指针（left和right）
  • 滑动窗口

# 1.2.low和fast指针『快慢指针』

//框架开始
ListNode * low=pHead;
ListNode * fast=pHead;

while( nullptr!=fast->next && nullptr!=fast->next->next )
{
    //记得一定要先走
	low=low->next;
	fast=fast->next->next;
//框架结束
	if( low==fast )
    {
        low=pHead;
        while( low!=fast )
        {
            low=low->next;
            fast=fast->next;
        }
        return fast;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 1.3.左右指针

  • 二分查找用到了
  • 判断是否回文

# 1.4.滑动窗口『模板』

  • 框架
string str;
int Left=0,Right=0,Len=str.size();
while( Right<Len )
{
	//右侧强制更新的,下面必须保留，否则++Right之后会更新
    char CurChar=s[Right];
    WindowsHash[ CurChar ]++;
    ++Right;
    //右侧非强制更新的，本部分不需要更新
            

	//『何时使得窗口不符合条件』，使得左侧需要更新？收缩？
	//用的while循环收缩，毕竟可能要收缩很多次
	while( how to shrink)
	{
        char c=s[Left];
        WindowsHash[c]--;
        ++Left;
        //其他的
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 例题1-26. 删除有序数组中的重复项 (opens new window)

  • 严格来说是“左右指针”，不全是“滑动窗口”
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
 
        int Left=0;
        int Right=1; //“滑动窗口”在本题中的改进点1
        int Len=nums.size();

        while( Right<Len )
        {
            //改进点2
            if( nums[Right]==nums[Left] )
            {
                nums.erase( nums.begin()+Right, nums.begin()+Right+1 );
                --Len;
            }
            else if( nums[Right]!=nums[Left] )
            {
                ++Left;
                ++Right;
            }
        }


        return Len;
    }
};
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

# 例题2-3. 无重复字符的最长子串 (opens new window)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res=0;
        unordered_map<char,int> WindowsHash;
        int Left=0,Right=0;
        int Len=s.size();

        while( Right<Len )
        {
            //右侧强制更新的,下面必须保留，否则++Right之后会更新
            char CurChar=s[Right];
            WindowsHash[ CurChar ]++;
            ++Right;
            //右侧非强制更新的，本部分不需要更新
            

            //『何时使得窗口不符合条件』，使得左侧需要更新？收缩？
            while( WindowsHash[ CurChar ] >1 )
            {
                char c=s[Left];
                WindowsHash[c]--;
                ++Left;
            }

            res=max( res, Right-Left );
        }

        return res;
    }
};
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

# 2.递归⭐️

# 2.1.递归套路『重要』⭐️

  • 来自《算法基础与在线实践》
#include<bits/stdc++.h>
using namespace std;

int n;
//表示，begin借助help杆子，到end上面去，这次的目标是移动n个元素
void hanota(char begin, char help, char end, int n)
{
	if( n<1 )	return ;
	if( 1==n ) 
	{
		printf("%c->%c\n", begin, end);
		return ;
	}

	//这个递归，是观察小部分的调用获得的idea
	hanota( begin, end, help, n-1);
	printf("%c->%c\n", begin, end);
	hanota( help, begin, end, n-1);
}

int main()
{
	while( ~scanf("%d",&n) )
	{
		hanota( 'A', 'B', 'C', n);
	}

	return 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

# 3.将『栈和递归』转换得炉火纯青⭐️

# 3.1.递归转栈『万能模板』⭐️

0、使用结构体量的成员变量或指针变，抽象原先解决问题的『递归函数』的形式参数
1、设置 『问题栈』并且，画出和书上差不多的解决问题，栈变化表
2、初始化『第1个问题』
    st.push( root );
3、用while循环，模拟栈
1
2
3
4
5

# 3.2.递归解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector<int> ret;

void trave( TreeNode * root )
{
    if( nullptr==root )
    {
        return ;
    }

    ret.push_back( root->val );
    trave( root->left );
    trave( root->right );
}
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        
        ret.clear();
        trave( root );
        return ret;
    }
};
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

# 3.3.栈解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector<int> ret;
stack< TreeNode * > st;//第1步，设置 『问题栈』
void trave( TreeNode * root )
{
    //第2步，初始化『第1个问题』
    st.push( root );

    //第3步，用while循环，模拟栈
    while( !st.empty() )
    {
        TreeNode * top=st.top();
        st.pop();

        if( nullptr!=top )
        {
            st.push ( top->right );
            st.push( top->left );
            ret.push_back( top->val ); //着手解决问题
        }
    }

}
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        
        ret.clear();
        while( !st.empty() )
        {
            st.pop();
        }
        trave( root );
        return ret;
    }
};
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

# 4.迭代

  • 链表遍历
void  MyReverse( ListNode * root )
{
    while( nullptr!=root )
    {
        cout<< (root->val) <<endl;
        root = root->next;
    }
}
1
2
3
4
5
6
7
8

# 5.空间换时间

  • 比如，求素数

# 6.前缀/中缀/后缀表达式⭐️

#include<bits/stdc++.h>
using namespace std;

struct node
{
    double num; //操作数字
    char op;    //操作符
    bool flag;  //true表示操作数，false表示操作符
};

string str;
stack<node> s;//操作符栈
queue<node> q;//后缀表达式序列
map<char,int> op;

//将中缀表达式转换为后缀表达式
void Change();

void Cal();


int main()
{
    op['+']=op['-']=1;  //设定操作符的优先级
    op['*']=op['/']=2;

    while( getline(cin,str), str!="0" )
    {
        for( string::iterator it=str.end(); it!=str.begin(); it-- )
        {
            //将表达式中的空格删掉
            if( ' '==(*it) ) str.erase(it);
        } 
        while( !s.empty() )
        {
            s.pop();    //初始化栈
        }

        //将中缀表达式转换为后缀表达式
        Change();
        //计算后缀表达式
        printf("%.2f\n", Cal() );
    }

    return 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

# 6.1.中缀表达式转换为后缀表达式


void Change()
{
    double num;
    node temp;
    for( int i=0; i<str.length(); )
    {
        if( isdigt(str[i]) )
        {
            temp.flag=true;//标记是数字
            temp.num=str[i++]-'0';//记录这个操作数的的1个数位
            while( i<str.length() && isdigt(str[i]) )
            {
                //更新该操作数『常见编程技巧』
                temp.num=temp.num*10+( str[i]-'0' );
                ++i;
            }
            //将这个操作数压入后缀表达式的队列
            q.push(temp);
        }
        else
        {
            //如果是操作符
            temp.flag=false;
            //只要操作符的栈顶元素比该操作符优先级高
            //就把操作符栈顶元素弹出到后缀表达式的队列中
            while( s.empty() && op[ str[i] ]<=op[ s.top().op ] )
            {
                q.push( s.top() );
                s.pop();
            }

            temp.op=str[i];
            s.push(temp);   //把该操作符压入操作符栈中
            ++i;
        }//#end inner if

        //如果操作符栈中还有操作符，就把它弹出到后缀表达式中
        while( !s.empty() )
        {
            q.push( s.top() );
            s.pop();
        }
        
    }//#end for

}
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

# 6.2.计算后缀表达式

void Cal()
{
    double temp1,temp2;
    node cur,temp;

    while( !q.empty() )
    {
        //cur记录队首元素
        cur=q.front();
        q.pop();

        //如果是操作数，直接压入栈
        if( true==cur.flag ) 
        {
            s.push(cur);
        }
        else
        {
            //如果是操作符，号
            temp2=s.top().num;  //弹出第2操作数
            s.pop();
            temp1=s.top().num;  //弹出第1操作数
            s.pop();

            //临时记录操作数
            temp.flag=true;
            if( '+'==cur.op )
            {
                temp.num=temp1+temp2;
            }
            else if( '-'==cur.op )
            {
                temp.num=temp1-temp2;
            }
            else if( '*'==cur.op )
            {
                temp.num=temp1*temp2;
            }
            else
            {
                temp.num=temp1/temp2;
            }

            //将该操作数压入栈
            s.push( temp );
        }//#end inner if & else


    }//#end while

    //栈顶元素就是后缀表达式的值
    return s.top().num;
}
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

# 6.3.启发性的方法

请写一个整数计算器，支持加减乘三种运算和括号。
1
  • 参考思路：labuladong

# 7.负数取模

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        vector<int> diff( s.size()+1 );
        for(auto & t : shifts )
        {
            if( 0==t[2] )
            {
                diff[ t[0] ]--;
                diff[ t[1]+1 ]++;      
            }
            else
            {
                diff[ t[0] ]++;
                diff[ t[1] +1]--; 
            }
        }

        for(int i=1; i<s.size(); ++i)
        {
            diff[i]+=diff[i-1];
            diff[i]%=26;
        }

        for(int i=0; i<s.size(); ++i)
        {
            //核心的地方，如何处理取模
            int c = s[i] - 'a';
            c = ((c + diff[i]) % 26 + 26) % 26; //核心：差分数组+重点是（负数取模）技巧
            s[i] = (char) (c + 'a');
        }

        return s;
    }
};
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