Less is more.

外观

📖 剑指offer刷题笔记(三)

3579字约12分钟

数据结构与算法剑指offer

2022-06-09

本文记录了牛客网剑指offer JZ31-JZ45的刷题过程。

文章中带*意味着二次做时需着重关注，特别是有其他方法待实现的。

整数中1的个数*

描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次。

题解

注意这里是需要数1的个数，而不是有1的有多少个，所以对每一位出现1直接计数就可以了。对于一个数对每个位分别为1进行计数：

image-20210619110657754

当前位分为3种情况：

  1. 当前位为 0 ，则左边的数字不能取到最大的时候，右边可以取完所有数字。
  2. 当前位为 1 ，则左边的数字取到最大的时候，右边可以从 0 取到最大；当左边不能取到最大的时候，右边可以取完所有数字。
  3. 当前位大于 1 ，则左边可以取完，右边也可以取完。

res={ left × right_bits_num × 10 , cur=0 left × right_bits_num × 10 +(right+1), cur=1 left × right_bits_num × 10 +right_bits_num × 10, cur>1 res= \left\{ \begin{array}{lr} \ left\ × \ right\_bits\_num \ × \ 10 \ ,\ cur=0 \\ \ left\ × \ right\_bits\_num \ × \ 10 \ + (right +1),\ cur=1 \\ \ left\ × \ right\_bits\_num \ × \ 10 \ + right\_bits\_num \ × \ 10, \ cur>1 \end{array} \right.

以当前位的最小值 base 为遍历策略， 即 1 代表当前位为第一位，10 代表当前位为第二位。那么有

former=number/ base=10×left+curlatter=number % base=rightbase=right_bits_num×10res=base×(former+8)/10+(former%10==1)(latter+1) \begin{array}{lr} former=number / \ base = 10×left+cur \\ latter=number \ \% \ base = right \\ base = right\_bits\_num×10 \\ \\ res = base×(former+8)/ 10+(former\%10==1)(latter+1) \end{array}

其中 (former+8)/10=left  (cur≤1)∣∣left+1(cur>1)(former+8)/10=left\;(cur\leq1)\vert\vert left+1(cur>1)

代码

​

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int cnt=0;
        for (int base=1; base<=n; base*=10) {
            int former=n/base, latter=n%base;
            // 注意这里的整数除 10 是有先后次序之分的
            cnt += base*((former+8)/10) + (former%10==1)*(latter+1);
        }
        return cnt;
};

把数组排成最小的数

描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

题解

一种另类排序，比较策略为先尝试两种拼接，返回拼接小的一种情况。

代码

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        string str="";
        sort(numbers.begin(), numbers.end(), [](int n1, int n2) ->bool {
            string str1 = to_string(n1);
            string str2 = to_string(n2);
            return (str1+str2)<(str2+str1);
        });
        for (int number: numbers)
            str += to_string(number);
        return str;
    }
};

丑数

描述

求出第 N 个大的丑数。

ugly_number=2x3y5z ugly\_ number = 2^x3^y5^z

题解

+++ 维护有序集合去重

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 0)
            return 0;
        // 虽然返回值是 int 在这个过程中会添加比返回值更大的数，这个数可能超过 int 比较可能为负数
        // 为什么这里要声明 long long ，取数时会按照左值的类型取数
        long long ret = 1;
        set<long long> ugly_set{1};
        for (int i=0; i<index; ++i) {
            // 取出最小的丑数并删除
            ret = *ugly_set.begin();
            ugly_set.erase(ugly_set.begin());
            // 加入丑数的 2，3，5倍数
            ugly_set.emplace(2*ret);
            ugly_set.emplace(3*ret);
            ugly_set.emplace(5*ret);
        }
        return ret;
    }
};

+++

+++ 三指针算法

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        // 三个指针依次是 乘 2、3、5 指针
        if(index <= 0)
            return 0;
        vector<int> v(index, 0);
        v[0] = 1;
        int twoPtr = 0, threePtr = 0, fivePtr = 0;
        for (int i = 1; i < index; i++) {
            int nextUglyNumber = min(2*v[twoPtr],min(3*v[threePtr],5*v[fivePtr]));
            // 注意这里是并行的，如若相等需要同时移动指针
            if (nextUglyNumber == 2*v[twoPtr])
                ++twoPtr;
            if (nextUglyNumber == 3*v[threePtr])
                ++threePtr;
            if (nextUglyNumber == 5*v[fivePtr])
                ++fivePtr;
            v[i] = nextUglyNumber;
        }
        return v[index-1];
    }
};

+++

第一个只出现一次的字符

描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

题解

采用哈希法，第一次统计，第二次遍历检查。

代码

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        // 采用 std::bitset<128>
        // bs1 出现过1次
        // bs2 出现过2次及以上
        bitset<128> bs1, bs2;
        for (const char ch: str) {
            if (!bs1[ch] && !bs2[ch])
                bs1[ch] = 1;
            else if (bs1[ch] && !bs2[ch])
                bs2[ch] = 1;
        }
        for (int i=0; i<str.length(); ++i) {
            if (bs1[str[i]] && !bs2[str[i]])
                return i;
        }
        return -1;
    }
};

数组中逆序对的个数

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

题解

可以采用归并排序的副作用。对于并的时候，前后两个有序数组比较一下可以获得多个逆序对。例如，{2, 3} {1, 4}，2>1则第一个数组中 2 后面的都大于 1 .

代码

class Solution {
public:
    int InversePairs(vector<int> data) {
        long long cnt = 0;
        vector<int> temp(data.size());
        merge_sort(data, temp, 0, data.size()-1, cnt);
        return cnt;
    }
private:
    const long long int kmod = 1000000007;
    void merge_sort(vector<int> &data, vector<int> &temp, int left, int right, long long &cnt) {
        if (left>=right)
            return;
        int mid = (left+right)/2;
        merge_sort(data, temp, left, mid, cnt);
        merge_sort(data, temp, mid+1, right, cnt);
        merge(data, temp, left, mid, right, cnt);
    }
    void merge(vector<int> &data, vector<int> &temp, int left, int mid, int right, long long &cnt) {
        int i = left, j = mid + 1, k = 0;
        while (i<=mid && j<=right) {
            if (data[i]>data[j]) {
                temp[k++] = data[j++];
                cnt += mid-i+1;
                cnt %= kmod;
            } else
                temp[k++] = data[i++];
        }
        while (i<=mid)
            temp[k++] = data[i++];
        while (j<=right)
            temp[k++] = data[j++];
        for (int i=left, k=0; i<=right; ++i, ++k)
            data[i] = temp[k];
    }
};

两个链表的第一个公共结点

描述

输入两个无环的单链表，找出它们的第一个公共结点。

题解

采用双指针：对于长度相等的链表，依次比较依次移动即可；对于长度不相等的链表：p1走完第一个链表走第二个链表，p2走完第二个链表走第一个链表，若有相同结点则在相同结点处相遇，否则p1和p2同时走到链表尾部。

代码

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1, *p2=pHead2;
        while (p1 && p2) {
            if (p1==p2)
                return p1;
            if (!p1->next && !p2->next) {
                return nullptr;
            } else if (p1->next && p2->next) {
                p1 = p1->next;
                p2 = p2->next;
            } else if (!p1->next && p2->next) {
                p1 = pHead2;
                p2 = p2->next;
            } else if (p1->next && !p2->next) {
                p1 = p1->next;
                p2 = pHead1;
            }
        }
        return nullptr;
    }
};

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

描述

统计一个数字在升序数组中出现的次数。

题解

先采用二分查找查找元素，再从这个元素往两边寻找。

代码

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.empty())
            return 0;
        // 二分查找
        int left = 0, right = data.size()-1;
        int mid = (left+right)/2;
        while (left<=right) {
            mid = (left+right)/2;
            if (data[mid]==k)
                break;
            else if (data[mid]>k)
                right = mid-1;
            else if (data[mid]<k)
                left = mid+1;
        }
        if (data[mid]!=k)
            return 0;
        // 计算命中值左右共有几个
        int cnt = 1;
        left = mid;
        right = mid;
        while (left>=0 && data[--left]==k) 
            ++cnt;
        while (right<data.size() && data[++right]==k)
            ++cnt;
        return cnt;
    }
};

求二叉树的深度

描述

求二叉树的深度

题解

递归求深度。

代码

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(!pRoot)
            return 0;
        int leftDepth = TreeDepth(pRoot->left);
        int rightDepth = TreeDepth(pRoot->right);
        return leftDepth>rightDepth? leftDepth+1 : rightDepth+1;
    }
};

是否为平衡二叉树

描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。注：我们约定空树是平衡二叉树。

题解

检验平衡二叉树作为求树的深度的副作用，及时剪枝即可。约定平衡二叉树的深度方法为若是平衡二叉树返回深度，否则返回-1.

代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        //空树为平衡二叉树
        return TreeDepth(pRoot)!=-1;
    }
    
     int TreeDepth(TreeNode* pRoot) {
        if (!pRoot)
            return 0;
        int left=TreeDepth(pRoot->left);
        if (left==-1)
            return -1;
        int right=TreeDepth(pRoot->right);
        if (right==-1)
            return -1;
         return abs(left-right)>1 ? -1 : 1+max(left,right);
    }
};

数组中出现一次的数*

描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题解

一个前提：两个数异或为 0 当且仅当两个数相等。

那么这些数字全异或起来就是 那两个只出现一次数字的异或值 从这个值取一个数位 00...1...00 与所有值想与，那么通过这个结果能将这个数组拆分为两个数组且这两个数组各含有 1 个只出现一次的数。再将这两个数组分别求异或能得到这两个值。

代码

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // 总体异或的值
        int xorAns=0;
        for (int number: array)
            xorAns ^= number;
        // 找到最右边的1,compare值为0000...1(...000)
        // x&(x-1) 是消去最右边的 1，在剑指offer二进制 1 的个数有涉及到
        int compare = xorAns - (xorAns&(xorAns-1));
        vector<int> nums1, nums2;
        //遍历分组
        //mark err number&compare==0
        for(int number: array)
            ((number&compare)==0)?nums1.push_back(number):nums2.push_back(number);
        //对二组求异或
        int num1=0, num2=0;
        for(int number: nums1)
            num1^=number;
        for(int number: nums2)
            num2^=number;
        vector<int> ret;
        if(num1>num2){
            ret.push_back(num2);
            ret.push_back(num1);
        }
        else{
            ret.push_back(num1);
            ret.push_back(num2);
        }
        return ret;
    }
};

和为 N 的连续数列

描述

有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

题解

题解一：采用前缀和，然后相减得到。

题解二：采用滑动窗口，值大了左窗口滑动，值小了有窗口滑动。

代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ret;
        // 前闭后开的滑动窗口
        // 值小了右窗口滑动
        // 值大了左窗口滑动
        // 终止条件是左窗口大于和的一半（最少是两个的和）
        int i=1, j=3;
        int curSum = 3;
        while (i<=sum/2) {
            if (curSum>sum) {
                curSum -= i;
                ++i;
            } else if (curSum<sum) {
                curSum += j;
                ++j;
            } else {
                // 值相等窗口内所有值进数组
                // 后左右窗口同时滑动
                // 这里可以左窗口滑动两下
                vector<int> v;
                for(int k=i; k<j; ++k)
                    v.push_back(k);
                ret.push_back(v);
                curSum = curSum + j -i -i -1;
                i += 2;
                ++j;
            }
        }
        return ret;
    }
};

和为 S 的两个数字

描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。

题解

采用双指针，左指针指向头，右指针指向尾。和小了左指针移动，和大了右指针移动，寻找到一组解后双指针同时移动判定。

代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> ret;
        if (array.size()<=1)
            return ret;
        int lptr= 0;
        int rptr= array.size()-1;
        while (lptr<rptr) {
            if (array[lptr]+array[rptr]>sum)
                --rptr;
            else if (array[lptr]+array[rptr]<sum)
                ++lptr;
            else{
                if (ret.empty())
                    ret = {array[lptr], array[rptr]};
                else {
                    if (ret[0]*ret[1]>array[lptr]+array[rptr])
                        ret = {array[lptr], array[rptr]};;
                }
                --rptr;
                ++lptr;
            }
        }
        return ret;
    }
};

循环左移

描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出（保证 K 小于等于 S 的长度）。例如，字符序列S=”abcXYZdef”,要求输出循环左移 3 位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

题解

(A−1B−1)−1=BA (A^{-1}B^{-1})^{-1}=BA

循环左移了 A 的长度。

代码

class Solution {
public:
    string LeftRotateString(string str, int n) {
        // 已保证 n 的值为正常
        reverse(str.begin(), str.begin()+n);
        reverse(str.begin()+n, str.end());
        reverse(str.begin(), str.end());
        return str;
    }
};

翻转单词序列

描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

题解

和上题差不多

(Z−1Y−1...A−1)−1=A...YZ (Z^{-1}Y^{-1}...A^{-1})^{-1}=A...YZ

代码

class Solution {
public:
    string ReverseSentence(string str) {
        auto curL = str.begin();
        for (auto cur = str.begin(); cur!=str.end(); ++cur) {
            if (*cur==' ') {
                // 找到空格，则进行一次翻转
                reverse(curL, cur);
                curL = cur+1;
            }
        }
        // 最后一个单词翻转
        reverse(curL, str.end());
        // 翻转所有
        reverse(str.begin(),str.end());
        return str;
    }
};

扑克牌顺子

描述

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。 有如下规则：

  1. A为1，J为11，Q为12，K为13，A不能视为14

  2. 大、小王为 0，0可以看作任意牌

  3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。

例如：给出数据[6,0,2,0,4] 中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4] 这样这五张牌在[2,6]区间连续，输出true 数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

题解

是顺子当且仅当：

  1. 非王牌不能相同
  2. 非王牌数的差不能大于4

代码

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        for(int i=0;i<5;i++){
            // 是王牌不参与比较
            if(numbers[i]==0)
                continue;
            for(int j=i+1;j<5;j++){
                // 是王牌不参与比较
                if(numbers[j]==0)
                    continue;
                if(numbers[i]==numbers[j]||abs(numbers[i]-numbers[j])>4)
                    return false;
            }
        }
        return true;
    }
};