CE代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int size;

void down(int x) {
    int t = x;
    if(x * 2 <= size && h[x * 2] < h[t]) t = x * 2;
    if(x * 2 + 1 <= size && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
    if(t != x) {
        swap(h[t], h[x]);
        down(t);
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    size = n;

    for(int i = n / 2; i ; i --) down(i);

    while(m --) {
        printf("%d ", h[1]);
        h[1] = h[size --];
        down(1);
    }
    return 0;
}

把size改成s就ac了，很奇怪。
AC代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int s;

void down(int x) {
    int t = x;
    if(x * 2 <= s && h[x * 2] < h[t]) t = x * 2;
    if(x * 2 + 1 <= s && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
    if(t != x) {
        swap(h[t], h[x]);
        down(t);
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    s = n;

    for(int i = n / 2; i ; i --) down(i);

    while(m --) {
        printf("%d ", h[1]);
        h[1] = h[s --];
        down(1);
    }
    return 0;
}

很郁闷，不知道哪里出了问题， 知道的大佬可以告诉我一下，万分感谢。QAQ

题目描述

经典约瑟夫环问题

//1.数组模拟过程
class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n == 1) return 0; // 特判
        vector<bool> res(n, true); //用数组来模拟枪毙过程
        int t = m - 1, s = 1; 
        while(s ++ < n) { //模拟n-1次，每次枪毙一个数
            res[t % n] = false; //枪毙！标记该位
            int k = m;
            while(k) { //在还活着的数当中向后数第m个
                t ++ ;
                if(res[t % n] == true) k -- ;
            }
        }
        return t % n;
    }
};

//2.链表模拟过程
#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        list<int> nums;
        for (int i = 0; i < n; ++i) nums.push_back(i);
        auto it = nums.begin();
        while (nums.size() > 1){
            int k = m - 1;
            while (k --){
                it++;
                if (it == nums.end()) it = nums.begin();//别迭代器移到开头实现模拟环形列表
            }
            it = nums.erase(it);//删除第m个元素
            if (it == nums.end()) it = nums.begin();
        }
        return nums.front();
    }
};

//2.DP递推写法
class Solution {
public:
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        vector<int> f(n + 1);
        f[1] = 0;
        for(int i = 2; i <= n ; i ++){
            f[i] = (f[i - 1] + m) % i; //核心递推关系式
        }
        return f[n];
    }
};

//3.DP递归写法
class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};

两次二分即可

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5;
int ans[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < n ; ++ i) scanf("%d", &ans[i]);
    while(m --){
        int num;
        scanf("%d", &num);
        //先二分找下界
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >>1;
            if(ans[mid] < num) l = mid + 1;
            else r = mid; 
        }

        if(ans[l] != num) cout << "-1 -1" << endl;
        else{
            cout << l << " ";
            //再二分找上界
            l = 0, r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(ans[mid] > num) r = mid -1;
                else l = mid;
            }
            cout << l << endl;
        }
    }
    return 0;
}

使用lowbit运算

C++ 代码

#include <iostream>
using namespace std;
int n, ans;

int lowbit(int x){
    return x & -x;
}

int main()
{
    cin >> n;
    while(n --){
        cin >> ans;
        int res = 0;
        while(ans){
            ans -= lowbit(ans);
            ++ res;
        }
        cout << res << ' ';
    }
    return 0;
}

按照区间左端点排序

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
int n;

int main()
{
    cin >> n;
    vector<PII> v(n);
    for(int i = 0; i < n; ++ i){
        cin >> v[i].first >> v[i].second;
    }
    sort(begin(v), end(v));
    vector<PII> ret;
    for(int i = 0; i < n; ++ i){
        if(ret.empty() || ret.back().second < v[i].first){
            ret.emplace_back(v[i]);
        } else{
            ret.back().second = max(ret.back().second, v[i].second);
        }
    }
    cout << ret.size() << endl;
    return 0;
}

n = int(input())
k = list(map(int, input().strip().split(' ')))
st = []
for m in k:
    while len(st) !=0 and st[-1] >= m:
        st.pop()
    if len(st) != 0:
        print(st[-1],end=' ')
    else:
        print(-1,end=' ')
    st.append(m)

题目描述

给定一个字符串，请找出最长的不包含重复字符的子串。
请注意子串和子序列的区别：

• 子串一定是连续的一段
• 子序列不一定是连续的一段，但下标要求是递增的

样例

给定 "abcabcbb"，答案是"abc"，长度是3.
给定 "bbbbb"，答案是"b"，长度是1.
给定 "pwwkew"，答案是"wke"，长度是3.

算法

参考y总讲解

C++ 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {    
        unordered_map<char, int> map;
        int res = 0;
        for (int i = 0, j = 0; j < s.size(); j++) {
            map[s[j]]++;
            while (map[s[j]] > 1) map[s[i++]]--;
            res = max(res, j - i + 1);
        }

        return res;
    }
};

Go 代码

func lengthOfLongestSubstring(s string) int {
    hash := map[byte]int{}
    n := len(s)
    res := 0

    for i, j := 0, 0; j < n; j++ {
        hash[s[j]]++;
        for hash[s[j]] > 1 {
            hash[s[i]]--
            i++
        }
        res = max(res, j - i + 1)
    }
    return res
}

func max(i int, j int) int {
    if i > j {
        return i
    } 
    return j
}

分析：

代码

#include<iostream>
#include<cstring>
using namespace std;
const int M = 1510;
int f[M][2];
bool st[M];
int e[M], ne[M], h[M], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int root)
{
    f[root][1] = 1, f[root][0] = 0;
    for(int i = h[root]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[root][1] += min(f[j][0], f[j][1]);
        f[root][0] += f[j][1];
    }
}

int main()
{

    int N;
    while(scanf("%d", &N) == 1)
    {
        //多次输入，清空h数组，注意idx 也要清空，否则只会越来越大，最后越界。
        memset(h, -1, sizeof h);
        idx = 0;
        //多次输入，清空st的缓存
        memset(st, 0, sizeof st);
        for(int i = 0; i < N; ++i)
        {
            int sub, num, j = 0;
            scanf("%d:(%d)", &j, &num);
            while(num--)
            {
                scanf("%d", &sub);
                add(j, sub);
                st[sub] = true;
            }
        }
        //需要判断谁父节点吗？随意设置一个点成为父节点可以吗？
        //题目已经规定了父节点和字节点，树的结构固定了。
        int root = 0;
        while(st[root])root++;
        dfs(root);
        cout << min(f[root][1], f[root][0]) << endl;
    }
    return 0;
}

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
    double k;string a,b;
    double count=0;
    cin>>k>>a>>b;
    double len=a.length();
    for(int i = 0 ;i<len ;i++){
        if(a[i]==b[i]){
            count++;
        }
    }

    if(count/len >=k) {
        printf("yes");
    }else {
        printf("no");
    }

    return 0;

}

LeetCode13 罗马数字转整数

题目描述

上一题的逆运算，字符串==>数字

样例

输入: "III"
输出: 3

输入: "IV"
输出: 4

输入: "IX"
输出: 9

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

算法分析

• 1、用哈希表存储 字符和数值的对应关系
• 若[i,i + 1]的字符串能在哈希表中存在，则表示[i,i + 1]的字符串能表示成一个数值，则 ans 加上该数值
  若不存在，则只能翻译i位置的字符成一个数值，ans加上该数值
• 若是 小大 需要减小 小
• IV 15 => ans -1 +5 == ans + 4

时间复杂度

Java代码

class Solution {
    public int romanToInt(String s) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        map.put("I",1);map.put("V",5);
        map.put("X",10);map.put("L",50);
        map.put("C",100);map.put("D",500);
        map.put("M",1000);

        int res = 0;
        for(int i = 0; i < s.length(); i++){
            if(i + 1 < s.length() && map.get(s.substring(i,i+1))< map.get(s.substring(i+1,i+2))){
                res -= map.get(s.substring(i,i+1));
            }else{
                res += map.get(s.substring(i,i+1));
            }
        }

        return res;


    }
}