九度-剑指Offer

二维数组中的查找

分析：既然已经给定了每一行从左至右递增，那么对于每一行直接二分查找即可，一开始还想着每一列同样查找一次，后来发现每一行查找一遍就能够遍历所有的元素了。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MaxN 1000
using namespace std;

int N, M, x;
int a[MaxN+5][MaxN+5]; 

bool bisearch(int *base, int delta, int l, int r, int val) {
    int mid, t;
    while (l <= r) {
        mid = (l + r) >> 1;
        t = *(base+delta*mid);
        if (t < val) l = mid + 1;
        else if (t > val) r = mid - 1;
        else return true;
    }
    return false;
}

int main() {
    bool exsit;
    while (scanf("%d %d", &N, &M) != EOF) {
        scanf("%d", &x);
        exsit = false;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 0; i < N && !exsit; ++i) {
            exsit = bisearch((int *)(a+i), 1, 0, M-1, x);
        }
        puts(exsit ? "Yes" : "No");
    }
    return 0;
}

用两个栈实现队列

分析：不要每次都翻转来翻转去，构造两个栈，一个栈专门用来倒序存放元素，另外一个栈用来顺序存储待出队的元素，如果待出队的元素不为空则输出，否则将前一个栈的元素倒进后一个栈。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

stack<int>stk[2];

int main() {
    char op[10];
    int N, x;
    while (scanf("%d", &N) != EOF) {
        while (!stk[0].empty()) stk[0].pop();
        while (!stk[1].empty()) stk[1].pop();
        for (int i = 0; i < N; ++i) {
            scanf("%s", op);
            if (op[1] == 'U') {
                scanf("%d", &x);
                stk[0].push(x);
            } else {
                if (!stk[1].empty()) {
                    printf("%d
", stk[1].top());
                    stk[1].pop();
                } else if (stk[0].empty()) puts("-1");
                else {
                    while (!stk[0].empty()) {
                        stk[1].push(stk[0].top());
                        stk[0].pop();
                    }
                    printf("%d
", stk[1].top());
                    stk[1].pop();
                }
            }
        }
    }
    return 0;
} 

二叉搜索树的后序遍历序列

分析：首先将后序遍历序列求一个前缀的最大值，然后根据后序遍历的规律，一棵子树的最后一个遍历元素为根元素，因此每次取一个序列的最后一个元素在前缀最大值中二分查找某个分界点，使得前半部分的最大值小于该根，前半部分即为根的左孩子，后半部分为右孩子。递归这个过程，并且记录这个划分过程的中序遍历，最后扫描这个序列是否递增即可。

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

int n, a[10005];
int b[10005];
int idx, rec[10005];

void gao(int l, int r) {
/*    if (l == r) {
        rec[idx++] = a[l];
        return;
    } */
    int p = upper_bound(b+l, b+r, a[r]) - (b+l);
//    printf("%d -> [%d, %d] && [%d, %d]
", a[r], a[l], a[l+p-1], a[l+p], a[r-1]);
    if (p) { // 说明有左孩子
        gao(l, l+p-1);
    }
    rec[idx++] = a[r];
    if (p != r-l) { // 说明有右孩子 
        gao(l+p, r-1);
    }
}

int main() {
//    freopen("1.in", "r", stdin);
    while (scanf("%d", &n) != EOF) {
        idx = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            b[i] = max(b[i-1], a[i]);
            // 求出前缀最大值
        }
        gao(1, n);
        int flag = true;
    //    printf("idx = %d
", idx);
    /*    for (int i = 0; i < idx; ++i) {
            printf("%d ", rec[i]);
        }
        puts(""); */
        for (int i = 1; i < idx; ++i) {
            if (rec[i] < rec[i-1]) {
                flag = false;
                break;
            }
        }
        puts(flag ? "Yes" : "No");
    }
    return 0;
}

二叉搜索树与双向链表

分析：这题使用字符串处理的方式没得到正确的输入数据，使用递归读入来简化输入。转化为双向链表的递归过程其实就是一个中序遍历的过程，只不过在中序遍历递归结束之后，增加两条链来使得相邻节点相连接。

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

int seq[1005]; 
int idx, sta, cnt;
struct Node {
    int val;
    int pre, nxt; // pre相当于左孩子，nxt相当于右孩子
}e[1005];


int build() { // 对某一段先序遍历区间进行二叉搜索树的构建
    int cur = idx++; // 申请一个节点
    e[cur].val = seq[sta++];
    if (seq[sta]) { // 如果有左孩子
        e[cur].pre = build();
    } else {
        ++sta;
        e[cur].pre = 0;
    }
    if (seq[sta]) {
        e[cur].nxt = build();
    } else {
        ++sta;
        e[cur].nxt = 0;
    }
    return cur;
}

void travel(int lp, int p, int d) {
    if (e[p].pre) {
        travel(p, e[p].pre, 0);
    }
//    printf("%d ", e[p].val);
    if (e[p].nxt) {
        travel(p, e[p].nxt, 1);
    }
    if (d == 0) { // 说明从左边递归下来
        int q = p;
        while (e[q].nxt) q = e[q].nxt;
        e[q].nxt = lp;
        e[lp].pre = q;
    }
    else if (d == 1) {
        int q = p;
        while (e[q].pre) q = e[q].pre;
        e[q].pre = lp;
        e[lp].nxt = q;
    }
}

void read() { // 递归读取数据
    scanf("%d", &seq[cnt]);
    if (seq[cnt++]) {
        read(), read();
    }
}

void run() {
    int rt = build(), head = rt;
    travel(-1, rt, -1);
    while (e[head].pre) head = e[head].pre;
    int q = head;
    while (q) {
        printf("%d ", e[q].val);
        q = e[q].nxt;
    }
    puts("");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        sta = cnt = 0;
        idx = 1;
        read();
        run();
    }
    return 0;
}

数组中出现次数超过一半的数字

分析：最简单的方法O(N)，不是建立hash表，而是利用一个数组中超过一半数为同一个数这个特性，记录一个可能的正确值和这个正确值出现的次数，通过当前值是否为假设值来抵消这个假设值出现的次数。最后判定一次这个假设之是否满足过半。

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

int n, a[100005];

int main() {
    int num, ti, x;
    while (scanf("%d", &n) != EOF) {
        num = 0, ti = 1;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            if (a[i] != num) {
                --ti;
                if (!ti) {
                    num = a[i], ti = 1;
                }
            } else ++ti;
        }
        ti = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == num) ++ti;
        }
        if (ti * 2 > n) printf("%d
", num);
        else puts("-1");
    }
    return 0;
} 

把数组排成最小的数

分析：分析两个元素的大小关系只需要比较s1+s2和s2+s1这两个串的关系即可，因为两个元素交换位置与其他元素的值没有关系。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int n;
string a[105];

char get(const string &s1, const string &s2, int i, int len) {
    if (i < len) return s1[i];
    else return s2[i-len];
}

bool cmp(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    int mlen = len1 + len2;
    for (int i = 0; i < mlen; ++i) {
        char p = get(s1, s2, i, len1), q = get(s2, s1, i, len2);
        if (p != q) return p < q;
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a, a+n, cmp);
        for (int i = 0; i < n; ++i) {
            printf("%s", a[i].c_str());
        }
        puts("");
    }
    return 0;
} 

丑数

分析：方法一是通过一个优先队列，每次取出最小的元素，然后下一个元素，然后将这个当前最小元素乘以2、3、5后的值加入到优先队列中去，不同于普通的暴力枚举，该方法能够尽可能的减少无效解的空间开销。方法二就是通过已知的前面的序列由三个指针维护好分别乘以这三个数所产生的最小的值。

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

long long rec[1505];
/*
priority_queue<long long,vector<long long>,greater<long long> >q;

void pre() {
    set<long long>st;
    int cnt = 1500, idx = 1;
    q.push(1);
    st.insert(1);
    while (cnt--) {
        rec[idx] = q.top();
        q.pop();
        long long a = rec[idx]*2;
        long long b = rec[idx]*3;
        long long c = rec[idx]*5;
        if (!st.count(a)) {
            q.push(a);
            st.insert(a);
        }
        if (!st.count(b)) {
            q.push(b);
            st.insert(b);
        }
        if (!st.count(c)) {
            q.push(c);
            st.insert(c);
        }
        ++idx;
    }
}
*/

void pre() {
    int cnt = 1500, idx = 1;
    rec[idx++] = 1;
    int pa = 1, pb = 1, pc = 1;
    while (cnt--) {
        int x = min(rec[pa]*2, min(rec[pb]*3, rec[pc]*5));
        rec[idx++] = x;
        if (x == rec[pa]*2) pa++;
        if (x == rec[pb]*3) pb++;
        if (x == rec[pc]*5) pc++; 
    }
}

int main() {
    pre();
    int n;
    while (scanf("%d", &n) != EOF) {
        printf("%d
", rec[n]);
    }
    return 0;
}

数字在排序数组中出现的次数

分析：这题直接使用map映射读入的10^6个数MLE了，采用离散化询问的1000个数使得空间需求量减少。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map> 
using namespace std;

map<int,int>mp;
int n, m, cnt;
int a[1000005];
int seq[1005];
int c[1005];
int ans[1005];
 
int main() {
    while (scanf("%d", &n) != EOF) {
        mp.clear();
        memset(ans, 0, sizeof (ans));
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d", &seq[i]);
            c[i] = seq[i];
        }
        sort(c, c+m);
        cnt = unique(c, c+m) - c;
        for (int i = 0; i < cnt; ++i) {
            mp[c[i]] = i;
        }
        for (int i = 0; i < n; ++i) {
            if (mp.count(a[i])) {
                ans[mp[a[i]]]++;
            }
        }
        for (int i = 0; i < m; ++i) {
            printf("%d
", ans[mp[seq[i]]]);
        }
    }
    return 0;
}

数组中只出现一次的数字

分析：如果将题目中的数字改成只有一个出现一次，其余出现两次，那么直接异或就能够得到答案。现在有两个数值出现了一次，那么先将所有的数异或起来，那么最后的结果就是两个不同的数异或的结果，取出这个数的某一位为1的位，按照这个为1的位将整个数组进行分组，每个分组里面必定含有一个只出现一次的数。因为某位的异或值为1，那么必定是0和1异或的结果。这个解法真的非常的好。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int a[1000005];

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

void gao(int x) {
    int bound = lowbit(x);
    int xx = 0, yy = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] & bound) xx ^= a[i];
        else yy ^= a[i];
    }
    if (xx > yy) swap(xx, yy);
    printf("%d %d
", xx, yy);
} 

int main() {
    int x;
    while (scanf("%d", &n) != EOF) {
        x = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            x ^= a[i];
        }
        gao(x);
    }
    return 0;
}

和为S的两个数字

分析：题目其实没有说明输入的数字都是正整数，我的写法是二分出k/2所在位置，然后从0开始往这个分界位置，对于每一个在分界之后寻找匹配的数。由于要求出乘积最小的组合，因此从前往后遇到匹配项即退出，时间复杂度O(nlogn)。另外一种写法是O(n)的，想法是定义两个指针，分别指向收尾，然后向中间靠拢来得到最终的结果。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MaxN = int(1e6);
int n, k;
int a[MaxN+5];

void getint(int &t) {
    char c;
    while (c = getchar(), c < '0' || c > '9');
    t = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') {
        t = t * 10 + c - '0';
    }
}

int main() {
    while (scanf("%d %d", &n, &k) != EOF) {
        for (int i = 0; i < n; ++i) {
            getint(a[i]);
        }
        int x = -1, y = -1, i, j;
        int pos = lower_bound(a, a+n, k/2) - a;
        if (a[pos] == k/2) ++pos;
        for (i = 0; i < pos; ++i) {
            j = lower_bound(a+pos, a+n, k-a[i]) - a;
            if (j != n && a[j] == k-a[i]) {
                x = a[i], y = a[j];
                break;
            }
        }
        printf("%d %d
", x, y);
        
    /*    int i, j, x = -1, y = -1;
        for (i = 0, j = n-1; i < j;) {
            if (a[i] + a[j] > k) --j;
            else {
                if (a[i] + a[j] == k) {
                    x = a[i], y = a[j];
                    break;
                }
                ++i;
            }
        }
        printf("%d %d
", x, y);*/
    }
    return 0;
}

N个骰子的点数

分析：n个m个面的骰子，通过母函数计算出所有的结果，然后排序即可。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

int n, m, tot;
int f[2][85];

struct Node {
    int val, cnt;
    friend bool operator < (const Node &a, const Node &b) {
        if (a.cnt != b.cnt) return a.cnt > b.cnt;
        else return a.val < b.val;
    }
}e[85];

void gao() {
    memset(e, 0, sizeof (e));
    memset(f, 0, sizeof (f));
    tot = 0;
    int cur = 0;
    f[!cur][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= 80; ++j) {
            for (int k = 1; k <= m; ++k) {
                f[cur][j+k] += f[!cur][j];
            }
            f[!cur][j] = 0;
        }
        cur = !cur;
    }
    for (int i = 1; i <= 80; ++i) {
        e[i].val = i, e[i].cnt = f[!cur][i];
        tot += e[i].cnt;
    }
    for (int i = 1; i <= 80; ++i) {
        e[i].cnt = (int)floor(100.0*e[i].cnt/tot+0.5);
    }
    sort(e, e + 80);
    for (int i = 0; i < 3; ++i) {
        printf("%d %.2f
", e[i].val, 1.0*e[i].cnt/100);
    }
    puts("");
}

int main() {
//    freopen("1.in", "r", stdin);
    while (scanf("%d %d", &n, &m), n) {
        gao();
    }
    return 0;
}

求1+2+……+n

分析：公式是n*(n+1)/2，把n分解成二进制数然后位运算相加。

#include <cstdlib>
#include <cstdio>
using namespace std;

int mask[20] = {
    1<<0, 1<<1, 1<<2, 1<<3, 1<<4,
    1<<5, 1<<6, 1<<7, 1<<8, 1<<9,
    1<<10, 1<<11, 1<<12, 1<<13, 1<<14,
    1<<15, 1<<16, 1<<17, 1<<18, 1<<19
};

int n;

int main() {
    while (scanf("%d", &n) != EOF) {
        long long ret = 0;
        ret += ((n+1) << 0) * (bool)(n & mask[0]);
        ret += ((n+1) << 1) * (bool)(n & mask[1]);
        ret += ((n+1) << 2) * (bool)(n & mask[2]);
        ret += ((n+1) << 3) * (bool)(n & mask[3]);
        ret += ((n+1) << 4) * (bool)(n & mask[4]);
        ret += ((n+1) << 5) * (bool)(n & mask[5]);
        ret += ((n+1) << 6) * (bool)(n & mask[6]);
        ret += ((n+1) << 7) * (bool)(n & mask[7]);
        ret += ((n+1) << 8) * (bool)(n & mask[8]);
        ret += ((n+1) << 9) * (bool)(n & mask[9]);
        ret += ((n+1) << 10) * (bool)(n & mask[10]);
        ret += ((n+1) << 11) * (bool)(n & mask[11]);
        ret += ((n+1) << 12) * (bool)(n & mask[12]);
        ret += ((n+1) << 13) * (bool)(n & mask[13]);
        ret += ((n+1) << 14) * (bool)(n & mask[14]);
        ret += ((n+1) << 15) * (bool)(n & mask[15]);
        ret += ((n+1) << 16) * (bool)(n & mask[16]);
        ret += ((n+1) << 17) * (bool)(n & mask[17]);
        ret += ((n+1) << 18) * (bool)(n & mask[18]);
        ret += ((n+1) << 19) * (bool)(n & mask[19]);
        printf("%lld
", ret >> 1);
    }
    return 0;
}