Leetcode 295. Find Median from Data Stream

题目链接295. Find Median from Data Stream

  在一个有序数组中找中位数,但需要支持再数组中添加新的元素。本来是有序里的,可以很轻易就查到中位数,但如果添加新数字后,不一定有序。如果先对数组排序,那代价就比较大了,每次排序时间复杂度O(n*log(n)),看discuss发现了一种很巧妙的解法,可以把添加数据的时间复杂度降低到O(log(n)) ,查询中位数O(1)。
Continue reading

Leetcode 467. Unique Substrings in Wraparound String

题目链接:Unique Substrings in Wraparound String
这里加段英文,不是为了凑字数,而是为了让别人搜索题目的时候能搜到我的博客。。
Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.
Continue reading

Leetcode 368. Largest Divisible Subset

题目链接:368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
  题目意思也很简单,给出一个不含重复数字的数组,找到最长的一个子数组,子数组里的元素必须两两整除。
Continue reading

Leetcode 240. Search a 2D Matrix II

题目链接:Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

  此题是74题Search a 2D Matrix的升级版,所给出的矩阵性质相对74题少了一条,只保证了每行和每列都是增序的,但依旧有O(m+n)的解法。

Continue reading

Leetcode 74. Search a 2D Matrix

题目链接:Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.

  这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。

Continue reading

Leetcode 11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

原题链接:Container With Most Water

Continue reading

Leetcode 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

原题链接:Longest Substring Without Repeating Characters

  此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。

Continue reading

Leetcode 198. House Robber

原题链接:198. House Robber

  一句话理解题意,有个偷马贼晚上要偷尽可能值钱的马,但连续两头马被偷会触发报警,问他如何在不触发报警(不偷连续的两匹马)的情况下偷到总价值最高马,返回最高总价值。
  看到maximum,就应该想到这是应该求解最优的问题,一想到求解最优,一般除了暴力就是动态规划了。

Continue reading

poj 1455 Crazy tea party

  这道题第一眼看去很难,其实不然,短短几行代码就搞定了。
  说一下大概思路,如果是排成一排的n个人,如 1 2 3 4 5 6 7 8 我们要变成 8 7 6 5 4 3 2 1 需要交换 28次,找规律的话就是 n*(n-1)/2,但这道题是一个圈,要让他们顺序变反的话不一定1要在8的位置上去,4 3 2 1 8 7 6 5 这样也是反的,我们只要把n个人分成两部分,然后按拍成一条线的方法来出来两部分就OK了。

Continue reading

hdoj 4768 Flyer

题目意思很容易理解,学校有n个社团,每个社团只给编号从a到b 的发传单,而且只给隔了c的人发,问最后谁收到的传单是单数,输出他的编号和收到的传单数量。

昨天做这题的时候看见很多人过了,感觉不会很难,但是打死都想不出来,看了别人的思路,一下子就想通了。这里我简要说一下,用二分,我们可以很容易求出一段区间里的总的传单数,因为保证最多有一个是单数,我们就看单数在哪边。

下面是java代码,刚开始学java,代码不是很简洁。

import java.util.Scanner;

public class Main {
    static long[] a = new long[20005];
    static long[] b = new long[20005];
    static long[] c = new long[20005];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            int n = cin.nextInt();
            for (int i = 1; i <= n; i++) {
                a[i] = cin.nextLong();
                b[i] = cin.nextLong();
                c[i] = cin.nextLong();
            }
            long r = Integer.MAX_VALUE, l = 0;
            while (l < r) {
                long mid = (l+r)>>1;
                long sum = 0;
                for (int i = 1; i <= n; i++) {
                    long minnum;
                    if (mid <= b[i])
                        minnum = mid;
                    else 
                        minnum = b[i];
                    if (minnum >= a[i]) {
                        sum += (minnum - a[i])/c[i] + 1;
                    }
                }
                if (sum%2 == 1)
                    r = mid;
                else l = mid+1;
            }
            if (l == Integer.MAX_VALUE) {
                System.out.println("DC Qiang is unhappy.");
                continue;
            }
            long ans = 0;
            for (int i = 1; i <= n; i++) {
                if (l >= a[i] && l <= b[i]) {
                    if ((l - a[i]) % c[i] == 0)
                        ans += 1;
                }
            }
            System.out.println(l + " " + ans);
        }
        cin.close();
    }
}

hdoj 4715 Difference Between Primes 素数筛选+二分查找


#include <string.h>
#include <stdio.h>
const int maxn = 1000006;
bool vis[1000006];
int pr[1000005];
int cnt = 1;

int bs(int l, int r, int v)
{
    int mid=(l+r)>>1;
    while(l < r)
    {
        if(pr[mid] < v)
            l = mid+1;
        else
            r = mid;
        mid= (l+r) >> 1;
    }
    return l;
}

void getpr()
{
    int i,j;
    for(i=2;i*i<maxn;i++) if(!vis[i])
    {
        pr[cnt++]=i;
        for(j=i*i;j<maxn;j+=i) vis[j]=1;
    }
    for(;i<maxn;i++)if(!vis[i])
    {
        pr[cnt++]=i;
    }
}

int main()
{
    memset(vis, 0, sizeof(vis));
    getpr();
    int n, t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int ans1 = 0;
        int ans2 = 0;
        for (int i = 1; i <= cnt; i++)
        {
            if (pr[i] <= n)
                continue;
            int x = bs(1, cnt-1, pr[i]-n);
            if (pr[i] - n == pr[x])
            {
                ans1 = pr[i];
                ans2 = pr[x];
                break;
            }
        }
        if (ans1)
            printf("%d %d\n",ans1, ans2);
        else
            puts("FAIL");
    }
    return 0;
}

poj 1503 高精度加法


把输入的数加起来,输入0表示结束。

先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger sum = BigInteger.valueOf(0);
        BigInteger a;
        a = cin.nextBigInteger();
        while (true) {
            sum = sum.add(a);
            if (a.compareTo(BigInteger.valueOf(0)) == 0)
                break;
            a = cin.nextBigInteger();
        }
        System.out.println(sum);
        cin.close();
    }
}

下面是我从网上找的C++代码,无外乎就是用数组模拟实现大数的加法。

#include<stdio.h>
#include<string.h>

#define N 20000

int ans[N],f,max;

void hadd(char a[])
{
    f=0;
    int n=strlen(a);
    for(int i=n-1;i>=0;i--)
    {
        a[i]-='0';
        ans[f]+=a[i];
        ans[f+1]+=ans[f]/10;
        ans[f]%=10;
        f++;
        if(max<f) max=f;
    }
}

int main()
{
    memset(ans,0,sizeof(ans));
    while(1)
    {
        char s[N];
        scanf("%s",s);
        if(strlen(s)==1&&s[0]=='0') break;
        hadd(s);
    }
    int flag=0;
    for(int i=N-1;i>=0;i--)
    {
        if((!flag&&ans[i]!=0)||flag||(!flag&&i==0))
        {printf("%d",ans[i]);flag|=1;}
    }
    puts("");
    return 0;
}