威廉
12秒前

题目链接 LeetCode 351 安卓系统手势解锁(需要leetcode会员)

自己按照初步的想法写了一段代码,但是遇到一个奇怪的问题,一直想不明白

错误的代码:

    def numberOfPatterns(self, m: int, n: int) -> int:
        if not m or not n or m > n:
            return 0

        visited = set()
        res = 0

        def validate(x1, y1, x2, y2):
            if x2 < 0 or x2 > 2 or y2 < 0 or y2 > 2:
                return False
            if (x2, y2) in visited:
                return False
            a = abs(x2 - x1)
            b = abs(y2 - y1)
            if a + b == 1:
                return True
            if a == 1 and b == 1:
                return True
            if (a == 1 and b == 2) or (a == 2 and b == 1):
                return True

            return False

        def dfs(i, j, visited, cur):
            nonlocal res
            if cur > n:
                return 
            if cur >= m:
                res += 1

            for delta_x in [-2, -1, 0, 1, 2]:
                for delta_y in [-2, -1, 0, 1, 2]:
                    x = i + delta_x
                    y = j + delta_y

                    if validate(i, j, x, y):
                        visited.add((x, y))
                        dfs(x, y, visited, cur + 1)
                        visited.remove((x, y))


        for i in range(3):
            for j in range(3):
                dfs(i, j, {(i, j)}, 1)

        return res

理论上visited一定会先添加元素,再删除相同元素,但在例子 m = 2, n = 3时出现了visited删除一个里面
不存在元素的情况(1, 0),不太清楚问题出在哪里,辛苦各位大佬帮看下




y总的好简洁//
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
    return x&-x;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {   
        int x;
        int res=0;
        cin>>x;
        while(x)
        {
            x-=lowbit(x);
            res++;
        }
        cout<<res<<" ";
    }
return 0;   
} 
//
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int change(int x)
{   
    int res=0;
    while(x)
    {
        if(x&1)res++;
        x>>=1;
    }
    return res;
}
int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(i)cout<<" ";
        cout<<change(a[i]); 
    }   
}



//子序列//双指针模板题。
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数,表示 a1,a2,…,an。

第三行包含 m 个整数,表示 b1,b2,…,bm。

输出格式
如果 a 序列是 b 序列的子序列,输出一行 Yes。

否则,输出 No。

数据范围
1≤n≤m≤105,
−109≤ai,bi≤109
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int nn=1e5+7;
int a[nn],b[nn];
int f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];
    int i=1,j=1;
    while(i<=n&&j<=m)
    {
        if(a[i]==b[j])
            i++;
        j++;        
    }       
    if(i==n+1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;   
return 0;   
} 





题目描述

在第一次存入的时候同时记录

C++ 代码

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

int n, a[10001];
int main(){
    cin >> n;
    int max = 0, answer = 0;
    while (n--)
    {
        int temp;
        cin >> temp;
        a[temp]++;
        if(a[temp] > max) {
            max = a[temp];
            answer = temp;
        }
        if (a[temp] == max && temp < answer)
        {
            answer = temp;
        }

    }

    cout << answer;

}



题目描述

blablabla

样例

#include<iostream>

using namespace std;

int main()
{
    int n,count = 0;
    cin>>n;

    for(int i =0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        for(int z = x+1;z<y;z++) if(z%2) count+=z;
        cout<<count<<endl;
        count = 0;
    }




    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



include[HTML_REMOVED]

using namespace std;

int main()
{
int n,count = 0;
cin>>n;

for(int i =0;i<n;i++)
{
    int x,y;
    cin>>x>>y;
    if(x>y) swap(x,y);
    for(int z = x+1;z<y;z++) if(z%2) count+=z;
    cout<<count<<endl;
    count = 0;
}




return 0;

}




include[HTML_REMOVED]

using namespace std;

int main()
{
int n,count = 0;
cin>>n;

for(int i =0;i<n;i++)
{
    int x,y;
    cin>>x>>y;
    if(x>y) swap(x,y);
    for(int z = x+1;z<y;z++) if(z%2) count+=z;
    cout<<count<<endl;
    count = 0;
}




return 0;

}




罗耀龙
4小时前

主体思路

用数组模拟队列,没什么好说的,写就完了

注意细节

基础代码

package main
import (
    "fmt"
    "bufio"
    "os"
    )

var (
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
    queue  []int
    )

func push(x int) { queue = append(queue, x) }
func pop() []int { queue = queue[1:]; return queue }
func empty() string { if len(queue) != 0 { return "NO" }; return "YES" }
func query() int { return queue[0] }

func main() {
    var M int 
    fmt.Fscan(in, &M)
    for ; M > 0; M-- {
        var op string
        var x int 
        fmt.Fscan(in, &op)
        switch op {
        case "push":
            fmt.Fscan(in, &x)
            push(x)
        case "pop":
            pop()
        case "empty":
            fmt.Fprint(out, empty(), "\n")
        case "query":                                                                                                                                                                                                                                                                                       
            fmt.Fprint(out, query(), "\n")
        }
    }
    out.Flush()
}



数据量很小 不需要找规律吧 直接0开始一路dfs只要9ms

C++ 代码

#include <iostream>

using namespace std;

int n;

//基础课里的试除法判断素数函数
bool primes(int x)
{
    if(x < 2)
    {
        return false;
    }

    for(int i = 2; i<= x/i; i++)
    {
        if(x % i == 0)
        {
            return false;
        }
    }

    return true;
}

//u是位数 num是数值
//位数最大8位不需要数组 直接传递数值 回溯都省了
void dfs(int u, int num)
{
    //当前位数等于所需位数即找到
    //因为是素数才会进下一步所以不需要再判断
    if(u == n)
    {
        printf("%d\n", num);
        return;
    }

    //直接枚举增加一位从0~9的数值
    for(int i = 0; i<=9; i++)
    {
        int t = num * 10 + i;
        //如果这个数值是素数就继续往下搜
        if(primes(t))
        {
            dfs(u + 1, t);
        }
    }
}

//直接位数拿到从0开始搜
int main()
{
    scanf("%d", &n);

    dfs(0, 0);
}



class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string result;
        for(auto& temp : dictionary) {
            if(check(temp, s)) {
                if(result.empty() || result.size() < temp.size() || result.size() == temp.size() && result > temp) {
                    result = temp;
                }
            }
        }
        return result;
    }

    bool check(string& a, string& b) {
        int i = 0, j = 0;
        for( ;i < a.size() && j < b.size(); ) {
            if(a[i] == b[j]) i ++;
            j ++;
        }
        return i == a.size();
    }
};