头像

以凝




离线:2小时前


最近来访(340)
用户头像
慕明
用户头像
IdealDragon
用户头像
十二_
用户头像
Expelliarmus2011
用户头像
zhangyuzhe
用户头像
Resurgence1001
用户头像
mmmmm
用户头像
coldplaying97
用户头像
kokef
用户头像
じ夙愿ら
用户头像
Jackpot.
用户头像
simonhan
用户头像
AcWing2AK
用户头像
ღ衬衫的价格是
用户头像
天の痕
用户头像
用户头像
鸭梨打滚
用户头像
用户头像
77777777777
用户头像
坐牢日记


以凝
7天前

持续更新(题库搜索“考研”)

短除法+高精度除法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
#define pb push_back  


bool not_zero(vector<int> x) 
{
    for(auto a : x) 
    {
        if(a > 0) return 1; 
    }
    return 0 ;
}


vector<int> div(vector<int> x , int &r)
{
    vector<int> C ;

    for(int i = x.size() -1 ; i >= 0 ; i --) 
    {
        r = r * 10 + x[i] ; 
        C.pb(r / 2) ;
        r %= 2 ; 
    }

    reverse(C.begin() , C.end()) ;

    while(C.size() > 1 && C.back() == 0) C.pop_back() ;

    return C ;
}


void convert(vector<int> x) 
{

    string ans ;

    while(not_zero(x)) 
    {
        int r = 0 ;
        x = div(x , r) ;
        ans += r + '0' ;
    }
    reverse(ans.begin() , ans.end()) ;
    cout << ans << endl ;

}

int main()
{

    string raw ; 
    while(cin >> raw) 
    {
        if(raw == "0") 
        {
            puts("0") ;
            continue ;
        }
        vector<int> origin ; 
        for(int i = raw.length() -1 ; i >= 0 ; i --) 
        {
            origin.push_back(raw[i] - '0') ;
        }
        convert(origin) ;
    }

    return 0 ;
}

排序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1100 ;

typedef struct info
{
    int id ; 
    string name ;
    int score ;
};

info stu[N] ;
int n ; 
int order ; 


bool cmp_z(info a , info b) // 从高到低
{
    if (a.score != b.score)
    {
        return a.score > b.score ;
    }else 
    {
        return a.id < b.id ;
    }
}

bool cmp_o(info a , info b)
{
    if (a.score != b.score)
    {
        return a.score < b.score ;
    }else 
    {
        return a.id < b.id ;
    }
}

int main()
{
    cin >> n >> order ;
    for(int i = 0 ; i < n ; i ++) 
    {
        stu[i].id = i ;
        cin >> stu[i].name >> stu[i].score ;
    }

    if(order)
        sort(stu , stu+ n , cmp_o) ;
    else 
        sort(stu , stu+ n , cmp_z) ;

    for(int i = 0 ; i < n ; i ++) 
    {
        cout<< stu[i].name << " " << stu[i].score << endl ;
    }

    return 0 ;
}

数约数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1100;

int n ;
int a[N] ; 

void count(int n) 
{
    int ans = 0 ; 
    for(int i = 1 ; i <= n / i ; i ++) 
    {
        if(n % i == 0) ans +=2 ;
        if(i * i == n) 
        {
            ans -- ;
            break; 
        }
    }
    printf("%d\n" , ans) ;
}

int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i ++ ) 
    {
        cin >> a[i] ;
    }
    for(int i = 0 ; i < n ; i ++ ) 
    {
        count(a[i]) ;
    }

    return 0 ;
}

字符串翻转

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    string s ;
    while(cin >> s )
    {
        reverse(s.begin() , s.end()) ;
        cout << s << endl;
    }

    return 0 ;
}

先序变中序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string pre ;
void build(int &depth)
{
    if(depth > pre.size()) return ;
    char c = pre[depth] ;
    if(c == '#') return ;
    depth ++ ;
    build(depth) ;
    cout << c << " " ;
    depth ++ ;
    build(depth) ;
}

int main()
{

    cin >> pre ;
    int depth = 0 ;
    build(depth) ;

    return 0 ;
}

按位乘法

#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

const int N = 11 ;

typedef long long LL;

LL a , b ;
int A[N] , B[N] ;


int main()
{
    cin >> a >> b ; 
    int cnta = 0 ;
    while(a) 
    {
        A[cnta++] =  a %  10 ;
        a /= 10 ;
    }
    int cntb = 0 ;
    while(b)
    {
        B[cntb++] = b % 10 ;
        b /=10 ;
    }
    int ans = 0 ;
    for(int i = 0 ; i < cnta ; i ++) 
    {
        for(int j = 0 ; j < cntb ; j ++) 
        {
            ans += A[i] * B[j] ;
        }
    }

    cout << ans << endl;


    return 0 ;
}

二叉树的公共祖先

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

int a ,b ;
set<int> s;

int main()
{
    cin >> a >> b ;
    while(a)
    {
        s.insert(a) ;
        a /=2 ;
    }
    while(b) 
    {
        if(s.count(b)) 
        {
            cout << b<< endl;
            return 0;
        }
        b /=2 ;
    }

    return 0 ;
}

2022.6.25

3381 手机键盘

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

map<char,int> T; // 定义字符-时间
map<char,int> group ; // 定义字符组


int main()
{
    for(int i = 0 ; i < 8 ; i ++ )
    {
        if(i == 5) 
        {
            for(int j = 0 ; j < 4 ; j ++) 
            {
                char c = 'a' + i*3 + j ;
                // cout << c<< endl;
                T.insert({c,j+1});
                group.insert({c,i});
            }
        }
        else if(i == 6) 
        {
            for(int j = 0 ; j < 3 ; j ++) 
            {
                char c = 'a' + i*3 +1 + j ;
                // cout << c<< endl;
                T.insert({c,j+1});
                group.insert({c,i});
            }
        }else if(i == 7) 
        {
            for(int j = 0 ; j < 4 ; j ++) 
            {
                char c = 'a' + i*3 +1 + j ;
                // cout << c<< endl;
                T.insert({c,j+1});
                group.insert({c,i});
            }
        }else 
        {
            for(int j = 0 ; j < 3 ; j ++) 
            {
                char c = 'a' + i*3 + j ;
                // cout << c<< endl;
                T.insert({c,j+1});
                group.insert({c,i});
            }
        }

    }
    // for(auto c : T)
    // {
    //     cout << c.first << " " << c.second << endl;
    // }


    string str ;
    while(cin >> str)
    {
        int ans = 0 ;
        for(int i = 0 ; i < str.size() ; i ++ ) 
        {
            char c = str[i] ;
            if(!i) ans += T[c] ;
            else 
            {
                if(group[str[i-1]] == group[c]) // 同组,等待2
                {
                    ans += 2 + T[c] ;
                }
                else 
                {
                    ans += T[c] ;
                }
            }

        }
        cout << ans << endl;
    }


    return 0; 
}

3397 众数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

const int N = 1e5+10 ;

int n , m ;
int ori[N] ;

int main()
{
    cin >> n >> m ;
    for(int i = 0 ; i < n ; i++) 
    {
        scanf("%d",&ori[i]) ;
    }

    for(int i = 0 ; i < m ; i ++) 
    {
        int count[10] ;
        memset(count , 0 , sizeof count) ;
        for(int j = 0 ; j < n ; j ++) 
        {
            int d = i? (ori[j] / (int)pow(10,i))  % 10:ori[j] % 10   ;
            count[d] ++ ;
        }


        int ans = 0 ;
        for(int j = 1 ; j <= 9 ; j++ ) 
        {
            if(count[ans] < count[j])
            {
                ans = j ;
            }
        }
        cout << ans << endl;
    }



    return 0 ;
}

6.27

3388 求root

这个题本身我觉得还是比较难的,没那么容易看出来,需要动笔算算。
这里定义一个序列N。
N用k的幂次表示,${a_n}$是系数。
N’被定义为${a_n}$的累加和。
然后(N-N’)%(k-1) = 0

然后N’表示成k的幂次,${b_n}$是其系数。
定义N’‘ 是${b_n}$的累加和。
(N’ - N’‘ ) % (k-1) 也一定是0

那这个N序列一直定义下去。
$N^{r-1} - N^{r} $ % (k-1) = 0
$N^{r}$ 刚好小于K。此时这是我们找的答案。

这时候我们把上面的式子左右分别相加。
$N - N^{r} $ % (k-1) = 0
然后$N^{r} $= N % (k-1)
求X^Y 的时候对K-1取模就行啦。
最后就是,这里的答案要求大于0,显然如果N%(k-1)得0,那么正好对应着$N$=k-1的时候,这时候特判输出k-1就行

#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

#define int long long 

int x , y , z ;
int qmi(int a, int b) 
{
    int res = 1 ;
    while(b) 
    {
        if(b&1) res = res * a % (z-1) ;
        a = a *a %(z-1) ;
        b >>= 1 ;
    }
    return res ;
}


signed main()
{
    while(~scanf("%d%d%d",&x,&y,&z)) 
    {
        int res = qmi(x,y) ;
        if(res) cout << res << endl ;
        else printf("%d\n",z-1) ;
    }


    return 0 ;
}

求最大最小

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 11000 ;
int n ;
int a[N] ; 

int main()
{
    while(~scanf("%d",&n)) 
    {
        for(int i = 0 ; i < n ; i ++) 
        {
            scanf("%d" , &a[i]) ;
        }
        sort(a , a + n ) ;
        printf("%d %d\n" , a[n-1] , a[0]) ;
    }



    return 0;
}

6.28

极值点下标

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110 ;
int n  ;
int a[N] ;

int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i ++ ) 
    {
        cin >> a[i] ;
    }

    for(int i = 0 ; i < n ; i ++ ) 
    {
        if(!i) 
        {
            if(a[0] != a[1]) 
            {
                printf("0 " ) ; 
            }
        }else if(i == n -1) 
        {
            if(a[n-2] != a[n-1]) 
            {
                printf("%d " , n-1) ; 
            }
        }else 
        {
            if( 0 < (a[i] - a[i-1]) * (a[i] - a[i+1])) 
            {
                printf("%d " , i) ; 
            }
        }
    }
    return 0 ;
}

3434 与7无关的数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110 ;
int n  ;
bool a[N] ; 

bool judge(int x) 
{
    if(x %7 == 0 ) return 1 ;
    while(x) 
    {
        int d = x % 10 ;
        if(d == 7) return 1 ; 
        x /= 10 ; 
    }
    return 0 ;
}

void init()
{
    for(int i = 1 ; i < N ; i ++ ) 
    {
        if(!judge(i)) 
        {
            a[i] = 1 ; 
        }
    }
}

int main()
{
    init() ;
    cin >> n ;
    int ans = 0 ;
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        if(a[i]) 
        {
            ans += i * i  ;
        }
    }
    cout << ans << endl;

    return 0 ;
}

3435 位操作练习

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define us unsigned short

us a , b ;


void change(us &x) 
{
    int d = x >> 15  ;
    x <<= 1 ;
    x += d ;
}

int main()
{
    while(cin >> a >> b ) 
    {
        if(a > b ) swap(a,b) ;
        if(a == b ) 
        {
            puts("YES") ;
            continue ;
        }
        int cnt = 0 ;
        while(cnt < 17)
        {

            change(a) ;
            if(a == b) 
            {
                puts("YES") ;
                break ; 
            }
            cnt ++ ;
        }
        if(cnt == 17) puts("NO") ; // 多移动一次,避免附加多余条件
    }

    return 0 ;
}



以凝
10天前

本文援引自B站 IR艾若机器人

基于搜索的路径规划

Dijkstra

算法的思想是维护两个表,一个是open表另一个是closed表。
open存储即将访问的点(已经探测到存在的点),closed表存储已经探索完毕的点。
从open表中,依据距离起点的距离最短的标准,选取一个点,加入closed,然后基于该点更新其他未被遍历到的点,刷新他们到起点的距离。直到到达最终目标。
dij.png

'''
基于搜索的路径规划
author: yining(@以凝)
'''


import matplotlib.pyplot as plt
import math

render = True


class Dijkstra :


    def __init__(self,ox,oy,resolution,robot_radius):
        '''
        ox : 障碍物的横坐标
        oy : 障碍物的纵坐标
        '''
        self.min_x = None
        self.min_y = None
        self.max_x = None
        self.max_y = None
        self.x_width = None
        self.y_width = None
        self.obstacle = None

        self.resolution = resolution
        self.robot_radius = robot_radius
        self.calc_obstacle(ox, oy)
        self.motion = [[1, 0, 1],
                  [0, 1, 1],
                  [-1, 0, 1],
                  [0, -1, 1],
                  [-1, -1, math.sqrt(2)],
                  [-1, 1, math.sqrt(2)],
                  [1, -1, math.sqrt(2)],
                  [1, 1, math.sqrt(2)]]

    class Node:

        def __init__(self,x,y,cost,pre):
            self.x = x 
            self.y= y 
            self.cost = cost 
            self.pre = pre
        def __str__(self):
            return str(self.x) + "," + str(self.y) + "," + str(
                self.cost) + "," + str(self.pre)

    def plan(self,sx,sy,gx,gy) :
        start = self.Node(
            self.calc_xy_index(sx,self.min_x) ,
            self.calc_xy_index(sy,self.min_y) ,
            0. , 
            -1
        )
        # print('*' * 50 )
        # print(start)
        # print(self.calc_index(start))
        # print('*' * 50 )

        target = self.Node(
            self.calc_xy_index(gx,self.min_x) ,
            self.calc_xy_index(gy,self.min_y) ,
            0.,
            -1
        )


        open_dic , closed_dic = dict() , dict()


        # 编号 --> node
        open_dic[self.calc_index(start)] = start

        while True :
            cid = min(open_dic , key = lambda o : open_dic[o].cost)  # 时间复杂度应该是On
            current = open_dic[cid] 
            # 取出当前node

            if render:  # pragma: no cover
                plt.plot(self.calc_position(current.x, self.min_x),
                         self.calc_position(current.y, self.min_y), "xc")
                # for stopping simulation with the esc key.
                plt.gcf().canvas.mpl_connect(
                    'key_release_event',
                    lambda event: [exit(0) if event.key == 'escape' else None])
                if len(closed_dic.keys()) % 10 == 0:
                    plt.pause(0.001)
               # 判断是否是终点
            if current.x == target.x and current.y == target.y:
                print("Find goal")
                target.pre = current.pre
                target.cost = current.cost
                break

            # Remove the item from the open set
            del open_dic[cid]

            # Add it to the closed set
            closed_dic[cid] = current

            # expand search grid based on motion model
            for move_x, move_y, move_cost in self.motion:
                node = self.Node(current.x + move_x,
                                 current.y + move_y,
                                 current.cost + move_cost, cid)
                n_id = self.calc_index(node)

                if n_id in closed_dic:
                    continue

                if not self.verify(node):
                    continue

                if n_id not in open_dic:
                    open_dic[n_id] = node  

                else:
                    if open_dic[n_id].cost >= node.cost:
                        # This path is the best until now. record it!
                        open_dic[n_id] = node

        rx, ry = self.calc_final_path(target, closed_dic)

        return rx, ry

    def calc_final_path(self,target , closed_dic) :
        '''
        生成最终路径
        返回值是 [路径的x],[路径的y]
        '''
        rx , ry  = [self.calc_position(target.x , self.min_x)] , [self.calc_position(target.y , self.min_y)] 

        pre = target.pre 
        while pre != -1 :
            tmp = closed_dic[pre] 
            rx.append(self.calc_position(tmp.x , self.min_x))
            ry.append(self.calc_position(tmp.y , self.min_y)) 
            pre = tmp.pre

        return rx, ry 


    def calc_position(self , index , minp) :
        '''
        实现了从逻辑位置(理论位置)到物理位置(在图上的位置)的映射
        '''
        return index * self.resolution + minp




    def calc_xy_index(self,position , minp) :
        '''
        计算position物理位置的编号,横坐标和纵坐标都可以
        '''
        return round((position - minp) / self.resolution )

    def calc_index(self,node) :
        '''
        计算当前的位置编号
        '''
        return node.y * self.x_width + node.x 



    def verify(self,node) :

        # 先利用逻辑位置计算出物理的位置
        px = self.calc_position(node.x , self.min_x) 
        py = self.calc_position(node.y , self.min_y) 

        # 我们利用物理位置进行判断
        # 是否出界
        if px < self.min_x or px >= self.max_x  or py < self.min_y or py >= self.max_y:
            return False
        # 是否是障碍
        if self.obstacle[node.x][node.y] :
            return False
        return True


    def calc_obstacle(self,ox,oy) :
        self.min_x = round(min(ox)) 
        self.min_y = round(min(oy))
        self.max_x = round(max(ox)) 
        self.max_y = round(max(oy)) 

        self.x_width = round((self.max_x - self.min_x) / self.resolution) 
        self.y_width = round((self.max_y - self.min_y) / self.resolution) 

        self.obstacle = [[False for _ in range(self.y_width)] for _ in range(self.x_width) ]

        for ix in range(self.x_width):
            x = self.calc_position(ix , self.min_x) # x 是物理位置
            for iy in range(self.y_width) :
                y = self.calc_position(iy,self.min_y) 

                for iox , ioy in zip(ox, oy) :
                    d = math.hypot(iox - x , ioy - y) 

                    if d <= self.robot_radius:
                        self.obstacle[ix][iy] = True
                        break            





def main():
    sx = -9.0  # [m]
    sy = -9.0  # [m]
    gx = 38.0  # [m]
    gy = 50.0  # [m]
    grid_size = 3.0  # [m]
    robot_radius = 1.0  # [m]

    ox, oy = [], []
    for i in range(-20, 60):
        ox.append(i)
        oy.append(-10.0)
    for i in range(-20, 60):
        ox.append(60.0)
        oy.append(i)
    for i in range(-20, 61):
        ox.append(i)
        oy.append(60.0)
    for i in range(-20, 61):
        ox.append(-10.0)
        oy.append(i)
    for i in range(-20, 30):
        ox.append(20.0)
        oy.append(i)
    for i in range(0, 20):
        ox.append(40.0)
        oy.append(60.0 - i)



    if render :
        plt.plot(ox, oy, ".k")  # 障碍
        plt.plot(sx, sy, "og")  # 起点
        plt.plot(gx, gy, "xb")  # 终点
        plt.grid(True)   
        plt.axis("equal")

    dij = Dijkstra(ox,oy , grid_size , robot_radius) 
    rx , ry = dij.plan(sx,sy,gx,gy) 

    if render :
        plt.plot(rx, ry, "-r")
        plt.show()



if __name__ == '__main__':
    main()

A*

懂了Dijkstra,A*也好理解很多,就和算法提高课讲的A*是一样的,基于Dijkstra,改掉标准,改成A*的标准,也即f(x) = g(x) + h(x) ,其中g(x)是已经花费的真实代价,h(x)是估计代价。
astar.png

'''
基于搜索的路径规划
author: yining(@以凝)
'''


import matplotlib.pyplot as plt
import math

render = True


class Astar :


    def __init__(self,ox,oy,resolution,robot_radius):
        '''
        ox : 障碍物的横坐标
        oy : 障碍物的纵坐标
        '''
        self.min_x = None
        self.min_y = None
        self.max_x = None
        self.max_y = None
        self.x_width = None
        self.y_width = None
        self.obstacle = None

        self.resolution = resolution
        self.robot_radius = robot_radius
        self.calc_obstacle(ox, oy)
        self.motion = [[1, 0, 1],
                  [0, 1, 1],
                  [-1, 0, 1],
                  [0, -1, 1],
                  [-1, -1, math.sqrt(2)],
                  [-1, 1, math.sqrt(2)],
                  [1, -1, math.sqrt(2)],
                  [1, 1, math.sqrt(2)]]

    class Node:

        def __init__(self,x,y,cost,pre):
            self.x = x 
            self.y= y 
            self.cost = cost 
            self.pre = pre
        def __str__(self):
            return str(self.x) + "," + str(self.y) + "," + str(
                self.cost) + "," + str(self.pre)



    def plan(self,sx,sy,gx,gy) :
        start = self.Node(
            self.calc_xy_index(sx,self.min_x) ,
            self.calc_xy_index(sy,self.min_y) ,
            0. , 
            -1
        )
        # print('*' * 50 )
        # print(start)
        # print(self.calc_index(start))
        # print('*' * 50 )

        target = self.Node(
            self.calc_xy_index(gx,self.min_x) ,
            self.calc_xy_index(gy,self.min_y) ,
            0.,
            -1
        )


        open_dic , closed_dic = dict() , dict()


        # 编号 --> node
        open_dic[self.calc_index(start)] = start

        while True :

            if len(open_dic) == 0 :
                print("open表是空的") 
                break


            # 选择扩展点的标准变了
            cid = min(open_dic , key = lambda o : open_dic[o].cost + self.h(target , open_dic[o]))  # 时间复杂度应该是On



            current = open_dic[cid] 
            # 取出当前node

            if render:  # pragma: no cover
                plt.plot(self.calc_position(current.x, self.min_x),
                         self.calc_position(current.y, self.min_y), "xc")
                # for stopping simulation with the esc key.
                plt.gcf().canvas.mpl_connect(
                    'key_release_event',
                    lambda event: [exit(0) if event.key == 'escape' else None])
                if len(closed_dic.keys()) % 10 == 0:
                    plt.pause(0.001)
               # 判断是否是终点
            if current.x == target.x and current.y == target.y:
                print("Find goal")
                target.pre = current.pre
                target.cost = current.cost
                break

            # Remove the item from the open set
            del open_dic[cid]

            # Add it to the closed set
            closed_dic[cid] = current

            # expand search grid based on motion model
            for move_x, move_y, move_cost in self.motion:
                node = self.Node(current.x + move_x,
                                 current.y + move_y,
                                 current.cost + move_cost, cid)
                n_id = self.calc_index(node)

                if n_id in closed_dic:
                    continue

                if not self.verify(node):
                    continue

                if n_id not in open_dic:
                    open_dic[n_id] = node  

                else:
                    if open_dic[n_id].cost >= node.cost:
                        # This path is the best until now. record it!
                        open_dic[n_id] = node

        rx, ry = self.calc_final_path(target, closed_dic)

        return rx, ry



    def h(self,node1 , node2):
        return math.hypot(node1.x - node2.x , node1.y - node2.y) 


    def calc_final_path(self,target , closed_dic) :
        '''
        生成最终路径
        返回值是 [路径的x],[路径的y]
        '''
        rx , ry  = [self.calc_position(target.x , self.min_x)] , [self.calc_position(target.y , self.min_y)] 

        pre = target.pre 
        while pre != -1 :
            tmp = closed_dic[pre] 
            rx.append(self.calc_position(tmp.x , self.min_x))
            ry.append(self.calc_position(tmp.y , self.min_y)) 
            pre = tmp.pre

        return rx, ry 


    def calc_position(self , index , minp) :
        '''
        实现了从逻辑位置(理论位置)到物理位置(在图上的位置)的映射
        '''
        return index * self.resolution + minp




    def calc_xy_index(self,position , minp) :
        '''
        计算position物理位置的编号,横坐标和纵坐标都可以
        '''
        return round((position - minp) / self.resolution )

    def calc_index(self,node) :
        '''
        计算当前的位置编号
        '''
        return node.y * self.x_width + node.x 



    def verify(self,node) :

        # 先利用逻辑位置计算出物理的位置
        px = self.calc_position(node.x , self.min_x) 
        py = self.calc_position(node.y , self.min_y) 

        # 我们利用物理位置进行判断
        # 是否出界
        if px < self.min_x or px >= self.max_x  or py < self.min_y or py >= self.max_y:
            return False
        # 是否是障碍
        if self.obstacle[node.x][node.y] :
            return False
        return True


    def calc_obstacle(self,ox,oy) :
        self.min_x = round(min(ox)) 
        self.min_y = round(min(oy))
        self.max_x = round(max(ox)) 
        self.max_y = round(max(oy)) 

        self.x_width = round((self.max_x - self.min_x) / self.resolution) 
        self.y_width = round((self.max_y - self.min_y) / self.resolution) 

        self.obstacle = [[False for _ in range(self.y_width)] for _ in range(self.x_width) ]

        for ix in range(self.x_width):
            x = self.calc_position(ix , self.min_x) # x 是物理位置
            for iy in range(self.y_width) :
                y = self.calc_position(iy,self.min_y) 

                for iox , ioy in zip(ox, oy) :
                    d = math.hypot(iox - x , ioy - y) 

                    if d <= self.robot_radius:
                        self.obstacle[ix][iy] = True
                        break            





def main():
    sx = -9.0  # [m]
    sy = -9.0  # [m]
    gx = 38.0  # [m]
    gy = 50.0  # [m]
    grid_size = 3.0  # [m]
    robot_radius = 1.0  # [m]

    ox, oy = [], []
    for i in range(-20, 60):
        ox.append(i)
        oy.append(-10.0)
    for i in range(-20, 60):
        ox.append(60.0)
        oy.append(i)
    for i in range(-20, 61):
        ox.append(i)
        oy.append(60.0)
    for i in range(-20, 61):
        ox.append(-10.0)
        oy.append(i)
    for i in range(-20, 30):
        ox.append(20.0)
        oy.append(i)
    for i in range(0, 20):
        ox.append(40.0)
        oy.append(60.0 - i)



    if render :
        plt.plot(ox, oy, ".k")  # 障碍
        plt.plot(sx, sy, "og")  # 起点
        plt.plot(gx, gy, "xb")  # 终点
        plt.grid(True)   
        plt.axis("equal")

    astar = Astar(ox,oy , grid_size , robot_radius) 
    rx , ry = astar.plan(sx,sy,gx,gy) 

    if render :
        plt.plot(rx, ry, "-r")
        plt.show()



if __name__ == '__main__':
    main()




以凝
1个月前
/**
 * Definition for singly-linked list.
 * 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* mergeKLists(vector<ListNode*>& lists) {

        ListNode* res = new ListNode() ;
        ListNode* vis = res ;

        while(1) 
        {

            bool f = 0 ;
            for(int i = 0 ;  i < lists.size() ; i ++ ) 
            {
                if(lists[i])
                {
                    f = 1 ;
                    break ;
                } 
            }
            if(!f) break ; 
            ListNode* tmp = nullptr;
            int p = 0 ;
            for(int i = 0 ; i < lists.size() ; i++ ) 
            {
                if(lists[i])
                {
                    tmp = lists[i] ;
                    p = i ;
                    break ;

                } 
            } 
            for(int i = 0  ; i < lists.size() ; i ++ )
            {
                if(lists[i])
                {
                    if(lists[i] -> val < tmp -> val) 
                    {
                        tmp = lists[i] ;
                        p = i ; 
                    }
                }
            }
            vis -> next = tmp ;
            vis = tmp ;
            lists[p] = lists[p] -> next ;
            vis -> next = nullptr;
        }

        return res -> next ;

    }
};


活动打卡代码 LeetCode 22. 括号生成

以凝
1个月前
class Solution {
public:
    vector<string> res ;

    void dfs(int l, int r ,string path , int lim) 
    {
        if(r > l) return ; 
        if(l + r == 2*lim ) 
        {
            if(r == l)
            {
                res.push_back(path) ;
            }
            return ;
        }
        dfs(l + 1 , r , path + "(" , lim) ;
        dfs(l , r + 1 , path + ")" , lim) ; 
    }

    vector<string> generateParenthesis(int n) {

        dfs(0,0,"",n) ; // l , r , path , d 
        return res ;
    }
};



以凝
1个月前
/**
 * Definition for singly-linked list.
 * 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* h1, ListNode* h2) {
        ListNode* dummy = new ListNode(-1)  ;
        ListNode* vis = dummy ;

        while(h1   && h2) 
        {
            if(h1 -> val <= h2 -> val)  
            {   
                vis -> next = h1 ;
                vis = h1 ;
                h1 = h1 -> next ; 
            }else 
            {
                vis ->next = h2  ;
                vis = h2 ;
                h2 = h2 ->next ;
            }
        }

        if(h1) 
        {
            vis -> next  = h1 ;
        }
        if(h2  ) 
        {
            vis -> next  = h2 ;
        }
        return dummy -> next ;
    }
};


活动打卡代码 LeetCode 20. 有效的括号

以凝
1个月前
class Solution {
public:
    bool isValid(string s) {

        stack<char> sk ;
        bool res = 1 ; 
        for(int i = 0 ; i < s.size() ; i++ ) 
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') 
            {
                sk.push(s[i]) ;
            }
            else if(sk.size())
            {
                // 遇到了右括号
                if(s[i] == ')' && sk.top() == '(' || s[i] == ']' && sk.top() =='['|| s[i] == '}'&& sk.top() == '{')  // 弹出左括号
                {
                    sk.pop() ;
                }
                else 
                {
                    res = 0 ;
                    break; 
                }
            }else 
            {
                res = 0 ;
                break; 
            }
        }
        if(sk.size() != 0 ) res = 0 ;
        return res ; 

    }
};



以凝
2个月前
/**
 * Definition for singly-linked list.
 * 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* removeNthFromEnd(ListNode* head, int n) {

        int cnt = 1 ;
        ListNode* h = head ;
        while(h->next != nullptr) 
        {
            cnt ++ ;
            h = h -> next ;
        }

        if(cnt == n)  // 删除第一个结点
        {
            head = head -> next ;
        }else if( n == 1) // 删除最后一个
        {
            h = head ;
            int c = 1 ;
            while(c < cnt-1) 
            {
                c ++ ;
                h = h -> next ;
            }
            h -> next = nullptr;
        }else 
        {
            h = head ;
            int c = 1 ;
            while(c < cnt-n ) 
            {
                c ++ ;
                h = h -> next ;
            }
            h -> next = (h ->next) ->next;
        }



        return head ;
    }
};



以凝
2个月前

复习时间紧张,不愿意动脑子了

class Solution {
public:
    vector<string> letterCombinations(string str) {

        vector<string> tabular ;
        tabular.push_back("");
        for(int i = 1 ; i <= 9 ; i ++ ) 
        {
            if(i == 1)
            {
                tabular.push_back("") ;
            }
            else 
            {
                if(i == 2 ) 
                {
                    tabular.push_back("abc") ;
                }else if(i == 3 ) 
                {
                    tabular.push_back("def") ;
                }else if(i == 4 ) 
                {
                    tabular.push_back("ghi") ;
                }else if(i == 5) 
                {
                    tabular.push_back("jkl") ;
                }else if(i == 6) 
                {
                    tabular.push_back("mno") ;
                }else if(i == 7 ) 
                {
                    tabular.push_back("pqrs") ;
                }else if(i == 8)
                {
                    tabular.push_back("tuv") ;
                }else if(i == 9 ) 
                {
                    tabular.push_back("wxyz") ;
                }

            }
        }

        vector<string> res ;
        int len_s = str.size()  ;
        if(!len_s) 
        {
            return res ;
        }
        if(len_s == 1) 
        {
            int t = str[0] - '0' ;
            for(int i = 0 ; i < tabular[t].size() ; i ++ ) 
            {
                string s ;
                s.push_back(tabular[t][i]);
                res.push_back(s) ;
            }
            return res ;
        }
        if(len_s == 2) 
        {
            int x = str[0] - '0', y = str[1] - '0' ;
            for(int i = 0 ; i < tabular[x].size() ; i ++ ) 
            {
                for(int j = 0 ; j < tabular[y].size() ; j ++ )
                {
                    string s ; 
                    s.push_back(tabular[x][i]) ;
                    s.push_back(tabular[y][j]) ;
                    res.push_back(s) ;
                }
            }
            return res ; 
        }
        if(len_s == 3) 
        {
            int x = str[0] - '0', y = str[1] - '0' , z = str[2] - '0' ;
            for(int i = 0 ; i < tabular[x].size() ; i ++ ) 
            {
                for(int j = 0 ; j < tabular[y].size() ; j ++ )
                {
                    for(int k = 0 ; k < tabular[z].size() ; k ++ )
                    {
                        string s ; 
                        s.push_back(tabular[x][i]) ;
                        s.push_back(tabular[y][j]) ;
                        s.push_back(tabular[z][k]) ;
                        res.push_back(s) ;
                    }

                }
            }
            return res ; 
        }
        if(len_s == 4) 
        {
            int x = str[0] - '0', y = str[1] - '0' , z = str[2] - '0' , q = str[3] - '0' ;
            for(int i = 0 ; i < tabular[x].size() ; i ++ ) 
            {
                for(int j = 0 ; j < tabular[y].size() ; j ++ )
                {
                    for(int k = 0 ; k < tabular[z].size() ; k ++ )
                    {
                        for(int p = 0 ; p < tabular[q].size() ; p ++ )
                        {
                            string s ; 
                            s.push_back(tabular[x][i]) ;
                            s.push_back(tabular[y][j]) ;
                            s.push_back(tabular[z][k]) ;
                            s.push_back(tabular[q][p]) ;
                            res.push_back(s) ;
                        }

                    }

                }
            }
            return res ;
        }
        return res ;
    }
};



以凝
2个月前
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        int tmp = 0x3f3f3f3f ;
        int res = 0x3f3f3f3f ; 

        sort(nums.begin() , nums.end()) ;
        for(int i = 0 ; i < nums.size() ; i ++ ) 
        {
            if(i && nums[i] == nums[i-1]) continue ;
            for(int j = i + 1 , k = nums.size() - 1 ; j < k ; j ++ ) 
            {
                if(j > i + 1  && nums[j] == nums[j-1]) continue ;
                while(j < k -1 && nums[i] + nums[j] + nums[k-1] >= target) k -- ;

                if(abs(nums[i] + nums[j] + nums[k] - target) < tmp)
                {
                    tmp = abs(nums[i] + nums[j] + nums[k] - target) ; 
                    res = nums[i] + nums[j] + nums[k] ;
                }
                if(k > j + 1)   // 再去探测一下小于target的差值
                {
                    k -- ;
                    if(abs(nums[i] + nums[j] + nums[k] - target) < tmp)
                    {
                        tmp = abs(nums[i] + nums[j] + nums[k] - target) ; 
                        res = nums[i] + nums[j] + nums[k] ;
                    }
                    k ++ ;
                }
            } 
        }

        return res ; 

    }
};


活动打卡代码 LeetCode 15. 三数之和

以凝
2个月前
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {


        vector<vector<int>> res ;

        if(nums.size() <=2) return res ;
        if(nums.size() == 3 && nums[0] + nums[1] + nums[2] != 0) return res ;

        sort(nums.begin() , nums.end()) ;
        for(int i = 0 ; i < nums.size() ;  i  ++ ) 
        {
            if( i && nums[i] == nums[i-1]) continue ;
            for(int j = i + 1 , k = nums.size() -1 ; j < k ; j  ++ ) 
            {
                if(j > i + 1  && nums[j] == nums[j-1]) continue ;
                while(j < k - 1  && nums[i]+nums[j] + nums[k-1] >= 0 ) k -- ; 
                if(nums[i] + nums[j] + nums[k] ==0 ) 
                {
                    res.push_back({nums[i] , nums[j] , nums[k]}) ;
                } 
            } 
        }
        return res ; 
    }
};