2024年1月25日力扣题目训练

2024年1月25日开始进行编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和苦难题1道。

225. 用队列实现栈

链接: 队列实现栈
难度： 简单
题目：

运行示例：

思路：
栈：先进后出
队列：先进先出
利用两个队列实现栈queue1，queue2，queue1用于存放先存入的数字，queue1与queue2实现栈，queque2先保存新进入的数字，然后再将queue1的数字存入到queue2中，再将queque2与queue1交换即可。
出栈直接从queue1中出栈。
代码：

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;
    MyStack() {
    }
    
    void push(int x) {
        queue2.push(x);
        while(!queue1.empty()){
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1,queue2);
    }
    
    int pop() {
        int r  = queue1.front();
        queue1.pop();
        return r;

    }
    
    int top() {
        int r  = queue1.front();
        return r;

    }
    
    bool empty() {
        return queue1.empty();
    }
};

257. 二叉树的所有路径

链接: 二叉树
难度： 简单
题目：

运行示例：

思路：
本质就是二叉树的遍历，用DFS算法即可解决。
代码：

class Solution {
public:
    void dfs(TreeNode* root, string path, vector<string>& paths){
        if(root != NULL){
            path +=to_string(root->val);
            if(root->left == NULL && root->right == NULL){
                paths.push_back(path);
            }else{
                path += "->";
                dfs(root->left,path,paths);
                dfs(root->right,path,paths);
            }
        }else{
            return;
        }
        
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        dfs(root, "", paths);
        return paths;

    }
};

258. 各位相加

链接: 各位相加
难度： 简单
题目：

运行示例：

思路：
我主要是利用暴力法解决的，官方是数学方法。

代码：
暴力法

class Solution {
public:
    int addDigits(int num) {
        if(num >= 0 && num <= 9){
            return num;
        }
        long sum = 0;
        while(num){
            sum+=num%10;
            num /= 10;
        }
        return addDigits(sum);
    }
};

数学法

class Solution:
    def addDigits(self, num: int) -> int:
        if num==0:
            return 0
        if num%9==0:
            return 9
        return num%9

81. 搜索旋转排序数组 II

链接: 旋转排序数组
难度： 中等
题目：

运行示例：

思路：
排序题一般是利用二分法，虽然这个数组是被旋转的但是基本上排序没有变，所以二分法还可以用，这个题中有重复元素，所以应该跳过。
代码：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int begin = 0,end = n - 1;
        while(begin <= end){
            int mid = (begin+end)/2;
            if(nums[mid] == target) return true;
            if(nums[begin] == nums[mid] && nums[mid] == nums[end]){
                begin++;
                end--;
            }else if(nums[begin] <= nums[mid]){
                if (nums[begin] <= target && target < nums[mid]) {
                    end = mid - 1;
                }else{
                    begin = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[n-1]){
                    begin = mid + 1;
                }else{
                    end = mid - 1;
                }  
            }
        }
        return false;

    }
};

82. 删除排序链表中的重复元素 II

链接: 排序链表
难度： 中等
题目：

运行示例：

思路：
因为链表已经排序，所以重复的数字是连续的，故一次遍历即可。
代码：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head){
            return head;
        }
       ListNode* p= new ListNode(0, head);
        ListNode*curr = p;
        while(curr->next && curr->next->next){
            if(curr->next->val == curr->next->next->val){
                int x = curr->next->val;
                while(curr->next && curr->next->val == x){
                    curr->next = curr->next->next;
                }
            }else{
                curr = curr->next;
            }
        }
        return p->next;
    }
};

30. 串联所有单词的子串

链接: 单词的子串
难度： 困难
题目：

运行示例：

思路：
哈希表+滑动窗口

代码：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int slen = s.size();
        int wlen = words[0].size();
        int wnum = words.size();
        vector<int> ans;

        //建立哈希表
        unordered_map<string ,int> hh;
        for(int i=0;i<wnum; i++){
            hh[words[i]] = i+1;
        }
        //初始化答案数组
        vector<int> tt(wnum);
        for(int i=0;i<wnum;i++){
            tt[hh[words[i]]-1]++;
        }

        //分不同截取方式
        for(int i=0;i<wlen;i++){
            //记录不同单词数量
            vector<int> nn(wnum);
            //开头位置计算
            for(int j=i; j<wlen*wnum+i; j+=wlen){
                string st = s.substr(j,wlen);
                if(hh[st]){
                    nn[hh[st]-1]++;
                }
            }
            if(nn==tt) ans.push_back(i);
            //滑动窗口 
            for(int j=i; j<slen-wlen*wnum; j+=wlen){
                string sm = s.substr(j,wlen);
                string sp = s.substr(j+wlen*wnum, wlen);
                if(hh[sm]) nn[hh[sm]-1]--;
                if(hh[sp]) nn[hh[sp]-1]++;
                if(nn==tt) ans.push_back(j+wlen);
            }
        }
        return ans;

    }
};