• #每日一题合集#牛客JZ44-JZ53


    为了督促自己每天练一练编程
    时间:2022年9月11日-2022年9月20日
    网站:https://www.nowcoder.com/exam/oj/ta?tpId=13

    9.11-JZ44.数字序列中某一位的数字

    在这里插入图片描述
    参考了官方题解,使用了位数减法,先定位区间,然后定位数字。
    (我觉得这个不能算简单题QWQ,虽然代码短,但思考起来真的不太行)

    class Solution {
    public:
    
        int findNthDigit(int n) {
            // write code here
            int digit = 1;//记录位数
            long long start = 1;//记录区间的起始数字
            long long sum = 9;//记录区间总共有多少数字
            while(n > sum){
                n -= sum;
                start *= 10;
                digit++;
                sum = 9 * start * digit;
            }//得到区间的总位数
            int num = start + (n -1) / digit;//记录n在哪个数字上
            int index = (n - 1) % digit;//记录n在哪一位上
            return to_string(num)[index] - '0';
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    9.12-JZ45.把数组排成最小的数

    在这里插入图片描述
    直接比较重载即可,主要是把数组转换成字符串。

    class Solution {
    public:
        static bool cmp(string& x, string& y){
            return x + y < y + x;
        }
        
        string PrintMinNumber(vector<int> numbers) {
            string res = "";
            int n = numbers.size();
            if(n == 0)
                return res;
            vector<string> num;
            for(int i = 0; i < n; i++)
                num.push_back(to_string(numbers[i]));
            
            sort(num.begin(), num.end(), cmp);
            for(int i = 0; i < num.size(); i++)
                res += num[i];
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    9.13-JZ46.把数字翻译成字符串

    在这里插入图片描述
    这里关于10和20的判断参考了官方题解,主要是如果有0的话,前面不是1或者2,就一定不对。

    class Solution {
    public:
        int solve(string nums) {
            // write code here
            if(nums == "0")
                return 0;
            if(nums == "10" || nums == "20")
                return 1;
            for(int i = 1; i < nums.length(); i++){
                if(nums[i] == '0'){
                    if(nums[i-1] != '1' && nums[i-1] != '2')
                        return 0;
                }
            }
            
            vector<int> dp(nums.length()+1, 1);
            for(int i = 2; i <= nums.length(); i++){
                //在11-19,21-26之间有两种译码方式
                if((nums[i-2] == '1' && nums[i-1] != '0') || (nums[i-2] == '2' && nums[i-1] > '0' && nums[i-1] < '7'))
                    dp[i] = dp[i-1] + dp[i-2];
                else
                    dp[i] = dp[i-1];
            }
            return dp[nums.length()];
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    9.14-JZ47.礼物的最大价值

    在这里插入图片描述
    基础bp

    class Solution {
    public:
        int maxValue(vector<vector<int> >& grid) {     
            int m = grid.size(),  n = grid[0].size();
            int i, j;
            vector<vector<int>> dp(m, vector<int>(n, 0));
            dp[0][0] = grid[0][0];
            for(i = 1; i < m; i++)
                dp[i][0] = dp[i-1][0] + grid[i][0];
            for(i = 1; i < n; i++)
                dp[0][i] = dp[0][i-1] + grid[0][i];
            for(i = 1; i < m; i++)
                for(j = 1; j < n; j++)
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            
            return dp[m-1][n-1];
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    9.15-JZ48.最长不含重复字符的子字符串

    在这里插入图片描述
    用左右两个指针依次判断即可

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            // write code here
            unordered_map<char, int> mp;
            int res = 0;
            for(int left = 0, right = 0; right < s.length(); right++){
                mp[s[right]]++;
                while( mp[s[right]] > 1){
                    mp[s[left]]--;
                    left++;
                }
                res = max(res, right - left + 1);
            }
            return res;
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    9.16-JZ49.丑数

    在这里插入图片描述
    显然,丑数的形式就是2x3y5z
    定义一个数组res,存储第n个丑数,因为最小的丑数就是1,所以res[0]=1;剩下的抽丑数就是将res[n]去乘以 2、3、5,然后比较出最小的那个。

    class Solution {
    public:
        int GetUglyNumber_Solution(int index) {
            if(index == 0)
                return 0;
            int i2 = 0, i3 = 0, i5 = 0;
            vector<int> res(index);
            res[0] = 1;
            
            for(int i = 1; i < index; i++){
                res[i] = min(res[i2]*2, min(res[i3]*3,res[i5]*5));
                if(res[i] == res[i2]*2)
                    i2++;
                if(res[i] == res[i3]*3)
                    i3++;
                if(res[i] == res[i5]*5)
                    i5++;
            }
            return res[index-1];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    9.17-JZ50.第一个只出现一次的字符

    在这里插入图片描述
    直接遍历存储即可

    class Solution {
    public:
        int FirstNotRepeatingChar(string str) {
            unordered_map<char, int> mp;
            for(int i = 0; i < str.length(); i++)
                mp[str[i]]++;
            for(int i = 0; i < str.length(); i++){
                if(mp[str[i]] == 1)
                    return i;
            }
            return -1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    9.18-JZ51.数组中的逆序对

    在这里插入图片描述
    参考官方题解:
    step 1: 将待划分区间从中点划分成两部分,两部分进入递归继续划分,直到子数组长度为1.
    step 2: 使用归并排序递归地处理子序列,同时统计逆序对。在归并排序中,依次比较相邻两组子数组各个元素的大小,并累计遇到的逆序情况。而对排好序的两组,右边大于左边时,它大于了左边的所有子序列,基于这个性质我们可以不用每次加1来统计,减少运算次数。
    step 3: 将排好序的子序列合并,同时累加逆序对。

    class Solution {
    public:
        int mod = 1000000007;
        int merge(int left, int right, vector<int>& data, vector<int>& tmp){
            if(left >= right)
                return 0;
            int mid = (left + right) / 2;
            int res = merge(left, mid, data, tmp) + merge(mid + 1, right, data, tmp);
            res %= mod;
            int i = left, j = mid + 1;
            for(int k = left; k <= right; k++){
                tmp[k] = data[k];
            }
            for(int k = left; k <= right; k++){
                if(i == mid + 1)
                    data[k] = tmp[j++];
                else if(j == right + 1 || tmp[i] <= tmp[j])
                    data[k] = tmp[i++];
                else{
                    data[k] = tmp[j++];
                    res += mid - i + 1;
                }
            }
            return res % mod;
        }
        int InversePairs(vector<int> data) {
            int n = data.size();
            vector<int> res(n);
            return merge(0, n-1, data, res);
            
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    9.19-JZ52.两个链表的第一个公共结点

    在这里插入图片描述
    总体比较简答,一个个比较就行
    tips:尽量还是不要用l当变量,第一次脑残把l1打成了11,看了好久没看出来哪里都不对QWQ

    class Solution {
      public:
        int getlength(ListNode* head) {
            ListNode* p = head;
            int n = 0;
            while (p != NULL) {
                n++;
                p = p->next;
            }
            return n;
        }
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            int l1 = getlength(pHead1), l2 = getlength(pHead2);
            if(l1 >= l2){
    			int n = l1 - l2;
    			for(int i = 0; i < n; i++)
    				pHead1 = pHead1->next;
            } else{
             int n = l2 - l1;
             for(int i = 0; i < n; i++)
                 pHead2 = pHead2 -> next;
            }
            while ((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)) {
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
            return pHead1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    9.20-JZ53.数字在升序数组中出现的次数

    在这里插入图片描述
    最简单就是用暴力,也可以二分提高效率~

    class Solution {
    public:
        int GetNumberOfK(vector<int> data ,int k) {
            int n;
            for(int i = 0; i < data.size(); i++){
                if(k == data[i])
                    n++;
                if(k < data[i])
                    break;
            }
            return n;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 相关阅读:
    基于C51实现按键控制
    static关键字超详细总结
    记一次问题排查
    【 云原生 | K8S 】kubeadm 部署Kubernetes集群
    【kafka】五、kafka工作流程
    LCR 052.递增顺序搜索树
    110 个主流 Java 组件和框架整理,常用的都有,建议收藏!!
    亚信笔试题【带答案】
    Android Framework通信:Binder
    GGTalk 开源即时通讯系统源码剖析之:服务端全局缓存
  • 原文地址:https://blog.csdn.net/weixin_43476037/article/details/126778894