leetcode解题思路分析（五十一）440 - 446 题

Dear 丶 2022-12-24 10:59 162阅读 0赞

1.  字典序的第k小数字  
    给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

**字典序其实就是一颗字典树，需要解决的问题是以i开头并小于n的数字有多少个，然后依次求解即可**

class Solution { 
    public:
    typedef long long LL;
        int findKthNumber(int n, int k) { 
            int prefix = 1;
            k--; // k记录要找的数字在prefix后的第几个
            while (k>0){ 
                int cnt = getCnt(n, prefix); // 当前prefix 下有多少个元素;包含prefix
                if (cnt <= k) {  // 向右
                    k -= cnt;
                    prefix++;
                } else {  // 向下
                    k--;
                    prefix*=10;
                }
            }
            return prefix;
        }
        int getCnt(LL n, LL prefix){ 
            LL cnt = 0;
            for (LL first = prefix, second = prefix+1; first<=n; first*=10, second*=10){ 
                cnt+= min(n + 1, second) - first;
            }
            return cnt;
        }
    };

1.  排列硬币  
    你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围内。

**最快速高效的当然是公式直接算**

class Solution { 
    public:
        int arrangeCoins(int n) { 
            
            return (int)(((sqrt(1+8*(long long)n)-1)/2.0));
    
        }
    };

1.  数组中重复的数据  
    给定一个整数数组 a，其中1 ≤ a\[i\] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

**本题关键在于如何原地标记。解法在于我们以该元素为索引，修改该元素索引对应值，并同时保证其本值也可以使用，因此采用取模的方式进行**

class Solution { 
    public:
        vector<int> findDuplicates(vector<int>& nums) { 
            vector<int> res;
            if (nums.empty()) return res;
            int n=nums.size();
            for (int i = 0; i < n; i++)
            { 
                int index = (nums[i] - 1) % n;//对n取余，防止数字越界
                nums[index] += n;         //对应位置加n
            }
            for (int i = 0; i < n; i++)
            { 
                //出现两次，则对应位置大于2n
                if(nums[i] > 2 * n)
                    res.push_back(i + 1);
            }
            return res;
        }
    };

1.  压缩字符串  
    给定一组字符，使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。在完成原地修改输入数组后，返回数组的新长度。

**双指针滑动问题**

class Solution { 
    public:
        int compress(vector<char>& chars) { 
            int curr = 0, res = 0;
            for (int start = 0, end = 0; start < chars.size(); start = end) { 
                while (end < chars.size() && chars[start] == chars[end]) end++;
                chars[curr++] = chars[start];
    
                if (end - start == 1) continue;
    
                for (auto c : to_string(end - start)) {  
                    chars[curr++] = c;
                }
            }
            return curr;
        }
    };

1.  两数相加2  
    给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

**如果要求不用额外空间，则对链表反转相加最后返回长的链表即可。如果要求不改变链表，则采取栈存储，最后生成新的链表并返回**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 
            stack<int> s1, s2;
            while (l1) { 
                s1.push(l1 -> val);
                l1 = l1 -> next;
            }
            while (l2) { 
                s2.push(l2 -> val);
                l2 = l2 -> next;
            }
            int carry = 0;
            ListNode* ans = nullptr;
            while (!s1.empty() or !s2.empty() or carry != 0) { 
                int a = s1.empty() ? 0 : s1.top();
                int b = s2.empty() ? 0 : s2.top();
                if (!s1.empty()) s1.pop();
                if (!s2.empty()) s2.pop();
                int cur = a + b + carry;
                carry = cur / 10;
                cur %= 10;
                auto curnode = new ListNode(cur);
                curnode -> next = ans;
                ans = curnode;
            }
            return ans;
        }
    };

1.  等差数列划分 II - 子序列  
    返回数组 A 中所有等差子序列的个数。

**如果求全部子序列则用回溯求解，求个数则可以用动态规划节约空间。动态规划的核心思想在于状态转移方程，这里的转移方程就是第i位结尾，公差为d的子序列个数。**

#define LL long long
    class Solution { 
    public:
        int numberOfArithmeticSlices(vector<int>& A) { 
            int n = A.size();
            LL ans = 0;
            vector<map<LL, int>> cnt(n);
            for (int i = 1; i < n; i++) { 
                for (int j = 0; j < i; j++) { 
                    LL delta = (LL)A[i] - (LL)A[j];
                    int sum = 0;
                    if (cnt[j].find(delta) != cnt[j].end()) { 
                        sum = cnt[j][delta];
                    }
                    cnt[i][delta] += sum + 1;
                    ans += sum;
                }
            }
    
            return (int)ans;
        }
    };