Java教程

刷题

本文主要是介绍刷题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

      • 链表
        • 合并两个有序链表
        • 合并K个有序链表
        • [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
        • [剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)
        • 翻转列表递归版
      • 小Tips
        • 位运算的判断语句需要加括号，如 if((n & 1) == 0)
        • 异或
        • 剑指 Offer 65. 不用加减乘除做加法
        • [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)
        • [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)
        • 二分
        • 归并排序
        • 快排
        • vector
        • 双端队列
        • 二进制中1的个数
        • 快速幂算法
      • 搜索
        • 剑指 Offer 53 - II. 0～n-1中缺失的数字
        • [剑指 Offer 38. 字符串的排列](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/)
        • [剑指 Offer 12. 矩阵中的路径](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)
      • 数组
        • 单调队列
        • 扑克牌中的顺子
        • 数组中的逆序对（归并排序）
        • [剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)（数组双指针）
        • [剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)
        • [剑指 Offer 45. 把数组排成最小的数](https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)（数组加快排）
        • [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)（快慢指针）
        • 二分(!!!)
        • [739. 每日温度](https://leetcode-cn.com/problems/daily-temperatures/)
        • [581. 最短无序连续子数组](https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/)
        • [560. 和为K的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k/)
        • [448. 找到所有数组中消失的数字](https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/)
      • 树
        • 面试题34. 二叉树中和为某一值的路径
        • [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
        • 二叉树转成双链表
        • [剑指 Offer 33. 二叉搜索树的后序遍历序列](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)
        • [剑指 Offer 28. 对称的二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)
        • [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/)
        • [617. 合并二叉树](https://leetcode-cn.com/problems/merge-two-binary-trees/)
        • [543. 树的直径](https://leetcode-cn.com/problems/diameter-of-binary-tree/)
        • 二叉树的最近公共祖先
        • 437. 路径总和
      • 字符串
        • [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)
        • [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)
        • [763. Partition Labels](https://leetcode.com/problems/partition-labels/)
        • [647. Palindromic Substrings](https://leetcode-cn.com/problems/palindromic-substrings/)
        • [438. Find All Anagrams in a String](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)
      • 动态规划
        • 剑指 Offer 60. n个骰子的点数
        • [剑指 Offer 49. 丑数](https://leetcode-cn.com/problems/chou-shu-lcof/)
        • [剑指 Offer 46. 把数字翻译成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/)
        • [494. 目标和（待补充）](https://leetcode-cn.com/problems/target-sum/)

链表

合并两个有序链表

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    if ((!a) || (!b)) return a ? a : b;
    ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr; aPtr = aPtr->next;
        } else {
            tail->next = bPtr; bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}

合并K个有序链表

小根堆方法

class Solution {
public:
    // 小根堆的回调函数
    struct cmp{  
       bool operator()(ListNode *a,ListNode *b){
          return a->val > b->val;
       };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pri_queue;
        // 建立大小为k的小根堆
        for(auto elem : lists){
            if(elem) pri_queue.push(elem);
        }
        // 可以使用哑节点/哨兵节点
        ListNode dummy(-1);
        ListNode* p = &dummy;
        // 开始出队
        while(!pri_queue.empty()){
            ListNode* top = pri_queue.top(); pri_queue.pop();
            p->next = top; p = top;
            if(top->next) pri_queue.push(top->next);
        }
        return dummy.next;  
    }
};

链表两两合并方法

class Solution {
public:
    // 合并两个有序链表
    ListNode* merge(ListNode* p1, ListNode* p2){
        if(!p1) return p2;
        if(!p2) return p1;
        if(p1->val <= p2->val){
            p1->next = merge(p1->next, p2);
            return p1;
        }else{
            p2->next = merge(p1, p2->next);
            return p2;
        }
    }

     ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        ListNode* head = lists[0];
        for(int i = 1; i<lists.size(); ++i){
            if(lists[i]) head = merge(head, lists[i]);
        }
        return head;  
    }
};

分治合并方法

class Solution {
public:
   // 合并两个有序链表
   ListNode* merge(ListNode* p1, ListNode* p2){
       if(!p1) return p2;
       if(!p2) return p1;
       if(p1->val <= p2->val){
           p1->next = merge(p1->next, p2);
           return p1;
       }else{
           p2->next = merge(p1, p2->next);
           return p2;
       }
   }

   ListNode* merge(vector<ListNode*>& lists, int start, int end){
       if(start == end) return lists[start];
       int mid = (start + end) / 2;
       ListNode* l1 = merge(lists, start, mid);
       ListNode* l2 = merge(lists, mid+1, end);
       return merge(l1, l2);
   }

   ListNode* mergeKLists(vector<ListNode*>& lists) {
       if(lists.size() == 0) return nullptr;
       return merge(lists, 0, lists.size()-1);
   }
};

剑指 Offer 52. 两个链表的第一个公共节点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

题解：使用map将源节点与新建立的节点做一次映射，而后遍历即可

 Node* copyRandomList(Node* head) {
        if(!head) return head;
        map<Node*, Node*> mp;
        Node* cur = head;
        while(cur) {
            Node* nhead = new Node(cur -> val);
            mp[cur] = nhead;
            cur = cur -> next;
        }
        cur = head;
        while(cur) {
            mp[cur] -> next = mp[cur -> next];
            mp[cur] -> random = mp[cur -> random];
            cur = cur -> next;
        }
        return mp[head];

翻转列表递归版

 class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

小Tips

位运算的判断语句需要加括号，如 if((n & 1) == 0)

异或

异或满足结合律异或运算满足交换律和结合律
即 a ⨁ \bigoplus ⨁ b ⨁ \bigoplus ⨁ a=b ⨁ \bigoplus ⨁ a ⨁ \bigoplus ⨁ a=b ⨁ \bigoplus ⨁ (a ⨁ \bigoplus ⨁a)=b ⨁ \bigoplus ⨁ 0=b ⨁ \bigoplus ⨁a ⨁ \bigoplus ⨁b ⨁ \bigoplus ⨁a=b ⨁ \bigoplus ⨁a ⨁ \bigoplus ⨁a=b ⨁ \bigoplus ⨁a ⨁ \bigoplus ⨁a)=b ⨁ \bigoplus ⨁ 0=b。

剑指 Offer 65. 不用加减乘除做加法

int add(int a, int b) {
        while(b != 0) {
            int c = (unsigned int)(a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题解：数组全部异或一次可得到这两个只出现了一次的数字的异或和，根据数位为1的位置，将这两个数字分到两个不同的组，再异或一次即可得到结果

vector<int> singleNumbers(vector<int>& nums) {
        int res = 0;
        for(int num: nums)
            res ^= num;
        int div = 1;
        int a = 0;
        int b = 0;
        while((res & div) == 0) div <<= 1;
        for(int num: nums) {
            if(num & div)
                a ^= num;
            else b ^= num;
        }
        return {a, b};
    }

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
题解：所有出现了三次的数字，其各个二进制位1的个数也是三的倍数。统计32位1的个数膜三，即为只出现了一次的数字。

int singleNumber(vector<int>& nums) {
        int cnt[32];
        memset(cnt, 0, sizeof(cnt));
        for(int num: nums) {
            for(int i = 0; i < 32; ++i) {
                cnt[i] += (num & 1);
                num >>= 1;
            }
        }
        int res = 0;
        for(int i=31; i>=0; i--) {
            res <<= 1;
            res += cnt[i] % 3;
        }
        return res;
    }

二分

int bsupper(vector<int>& nums, int l, int r, int target) {
        while(l < r) {
        int mid = (l + r) >> 1;    
            if(nums[mid] <= target)
               l = mid + 1 ;
            else r = mid;
        }
        return --l;
    }

归并排序



快排




注意返回的下标， 返回pos为数组从0开始计算的下标
 不要和nums[r]比较,会造成swap(nums[pos], nums[r]);越界




    int partition1(vector<int>& nums, int l, int r) {
  
        int x = nums[r];
        int pos = l;
        for(int i = l; i < r; ++i) { // 在这里 i的范围为 i < r，不要写成 i <= r
            if(nums[i] <= x)
                swap(nums[i], nums[pos++]);
        }
        swap(nums[pos], nums[r]);
        return pos;
    }
    
    // 完整快排算法 平均复杂度为O(logN)
    void qsort(vector<string>& strs,int left, int right) {
        if(left >= right) return;
        string x = strs[right];
        int index = left;
        for(int i = left; i < right; ++i) {
            if(strs[i] + x <= x + strs[i])  //说明strs[i]应该在x的左边
                swap(strs[i], strs[index++]);
        }
        swap(strs[index], strs[right]);
        qsort(strs, left, index - 1);
        qsort(strs, index, right);
    }



vector


vector<int> v;
reverse(v.begin(), v.end(); // 翻转容器内的元素



双端队列


deque<int> q;
q.emplace_front(val); // 从前插入数据 
q.push_back(val); //等价
q.emplace_back(val); // 在尾端插入数据
q.pop_back(); //删除最后元素
q.pop_front(); // 算出最开始的元素



二进制中1的个数


    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n) {
            n = n & (n - 1);
            cnt++;
        }
        return cnt;
    }



快速幂算法


//模板1
    long qpow(int a, int k) {
        long ans = 1, p = a;
        while (k > 0) {
            if ((k & 1) > 0) ans = ans * p % mod;
            k >>= 1;
            p = p * p % mod;
        }
        return ans;
    }
    
//模板2
long modpow(long base, int exp, int modulus) {
  long result = 1;
  for (; exp > 0; exp >>= 1) {
    result = result * (exp & 1 ? base : 1) % modulus;
    base = base * base % modulus;
  }
  return result;
}   



搜索


剑指 Offer 53 - II. 0～n-1中缺失的数字




个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。




class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}
 



剑指 Offer 38. 字符串的排列


给出字符串的全排列
 题解：递归，每次固定一个位置，注意set集合要放在dfs函数内


class Solution {
private:
    vector<string> ans;
    
    void dfs(string s, int pos) {
        if(pos == s.size()-1) {
            ans.push_back(s);
            return;
        }
        set<char> str;
        for(int i = pos; i < s.size(); ++i) {
            if(str.find(s[i]) != str.end()) 
                continue;
            str.insert(s[i]);
            swap(s[i], s[pos]);
            dfs(s, pos + 1);
            swap(s[i], s[pos]);
        }
    }
public:
    vector<string> permutation(string s) {
        dfs(s, 0);
        return ans;
    }
};



剑指 Offer 12. 矩阵中的路径


在二维矩阵中搜索是否存在给定的字符串
 需要注意的是回溯之后要把标记返回为false，因为这个卡了几十分钟


class Solution {
private:
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool flag = true;
    bool vis[250][250];
public:
    bool dfs(int x, int y, vector<vector<char>>& board, string word, int idx) {
        if(idx == word.size()) return true;
        int row = board.size(); int col = board[0].size();
        if(x < 0 || x >= row || y < 0 || y >= col) return false;
        if(board[x][y] != word[idx]) return false;
        if(vis[x][y]){
            // cout<< "false:" << endl;
            return false;
        } 
        vis[x][y] = true;
        //  cout<<"x: " <<x << " y: " <<y<< endl;
        //  cout<< "idx: " << idx << " size: " << word.size() <<endl;
        if(board[x][y] == word[idx])
            for(int i = 0; i < 4; ++i) {
                if(dfs(x + dx[i], y + dy[i], board, word, idx + 1)) 
                    return true;
            }
        vis[x][y] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        if(row == 0) return false;
        int col = board[0].size();
        // if(dfs(0, 0, board, word, 0)) return true;
        for(int i = 0; i < row; ++i) {
            for(int j = 0; j < col; ++j) {
                memset(vis, false, sizeof(vis));
               if(dfs(i, j, board, word, 0)) 
                return true;
                
            }
        }
        return false;
    }
};



数组


单调队列




给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。




vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return {};
        deque<int> q;
        for(int i = 0; i < k; ++i) {
            while(!q.empty() && q.back() < nums[i])
                q.pop_back();
            q.push_back(nums[i]);
        }
 
        vector<int> ans;
        ans.push_back(q.front());
        for(int i = k; i < nums.size(); ++i){
            if(!q.empty() && nums[i - k] == q.front()) q.pop_front();
            while(!q.empty() && q.back() < nums[i]) 
                q.pop_back();
            q.push_back(nums[i]);
            ans.push_back(q.front());
        }
        return ans;
    }



扑克牌中的顺子




从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 记录扑克牌的最大值和最小值，且除去大小王不能有重复元素，若最大值-最小值小于5则为true




bool isStraight(vector<int>& nums) {
        set<int> s;
        int mi = 14;
        int ma = 0;
        for(int num: nums) {
            if(num == 0) continue;
            if(s.find(num) != s.end()) return false;
            s.insert(num);
            mi = min(mi, num);
            ma = max(ma, num);
        }
        if(ma - mi < 5) return true;
        return false;
    }



数组中的逆序对（归并排序）


class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = (l + r) / 2;
        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[pos] = nums[i];
                ++i;
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = nums[j];
                ++j;
            }
            ++pos;
        }
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = nums[k];
            inv_count += (j - (mid + 1));
        }
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = nums[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
        return inv_count;
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n - 1);
    }
};



剑指 Offer 57. 和为s的两个数字（数组双指针）




输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 题解： 双指针




vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0, j = nums.size() - 1;
        while(i < j) {
            if(nums[i] + nums[j] < target) i++;
            else if(nums[i] + nums[j] > target) j--;
            else return{nums[i], nums[j]};
        }
        return {};
    }



剑指 Offer 57 - II. 和为s的连续正数序列




输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 双指针解法：利用求和公式计算l到r的区间和sum，若sum < target，则移动右指针扩大sum，若sum > target则移动左指针。当l>=r时，则到达边界，可以停止




vector<vector<int>> findContinuousSequence(int target) {
        vector<int> tmp;
        vector<vector<int>> res;
        int l = 1, r = 2;
        while(l < r) {
            int sum = (l + r) * (r - l + 1) / 2;
            if(sum == target) {
                tmp.clear();
                for(int i = l; i <= r; ++i)
                    tmp.push_back(i);
                res.push_back(tmp);
                l++;
            }
            if(sum < target) r++;
            if(target < sum) l++;
        }
        return res;
    }



剑指 Offer 45. 把数组排成最小的数（数组加快排）




输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 快排思想，给字符串数组排序，根据 x + y < y + x 说明x应该在y的左侧




void qsort(vector<string>& strs,int left, int right) {
        if(left >= right) return;
        string x = strs[right];
        int index = left;
        for(int i = left; i < right; ++i) {
            if(strs[i] + x <= x + strs[i]) //说明strs[i]应该在x的左边
                swap(strs[i], strs[index++]);
        }
        swap(strs[index], strs[right]);
        qsort(strs, left, index - 1);
        qsort(strs, index, right);
    }
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        for(auto num: nums) 
            strs.push_back(to_string(num));
        
        qsort(strs, 0, strs.size() - 1);
        string res = "";
        for(auto str: strs)
            res += str;
        return res;
    }



剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（快慢指针）




输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。




//快慢指针
    vector<int> exchange(vector<int>& nums) {
        int slow = 0, fast = 0;
        while(fast < nums.size()) {
            if(nums[fast] & 1) {
                swap(nums[fast], nums[slow]);
                slow++;
            }
            fast++;
        }
        return nums;
    }



二分(!!!)




把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。




class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            }
            else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            }
            else {
                high -= 1;
            }
        }
        return numbers[low];
    }
};
 



739. 每日温度




题意：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 题解：可用单调栈




class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && T[i] > T[s.top()]) {
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

 



581. 最短无序连续子数组




题意：找出最短子数组，对其排序后能使整个数组有序


题解：无序数组中最小的元素决定无序数组的左边界，最大的无序元素决定无序数组的右边界。复杂度O(n)




class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int maxx = INT_MIN;
        int minn = INT_MAX;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] < nums[i - 1])
                minn = min(minn, nums[i]);
        }
            
        // cout<<endl;
        for(int i = nums.size() - 2; i >= 0; --i)  
            if(nums[i] > nums[i + 1])      
                maxx = max(maxx, nums[i]);
        
        int l = 0;
        int r = nums.size() - 1;
        for(int i = 0; i < nums.size(); ++i) 
            if(nums[i] > minn){
                l = i;
                break;
            }
        
        for( int i = nums.size() - 1; i >= 0; --i) {
            if(nums[i] < maxx) {
                r = i;
                break;
            }
        }

        if(maxx == INT_MIN) return 0; 
        return l >= r ? 0 : r - l + 1;
    } 
};



560. 和为K的子数组




给出数组和一个整数k，找出数组中连续子数组之和等于k的子数组数量
 解：前缀和加map，如果prefix[i]表示数字0~i的和，若prefix[i] - prefix[j] = k, 则i~j为满足条件的连续子数组。使用map保存前缀和sum以及sum出现的次数，一边遍历一边更新前缀和prefix，若map中存在prefix-k的前缀和，则加上对应的次数




public:
    int subarraySum(vector<int>& nums, int k) {
        int prefix = 0;
        map<int, int> mp;
        mp[0] = 1;
        int res = 0;
        for(int i = 0; i < nums.size(); ++i) {
            prefix += nums[i];
            if(mp.find(prefix - k) != mp.end()) 
                res += mp[prefix - k];
            mp[prefix]++;
        }
        return res;
    }
};



448. 找到所有数组中消失的数字




说明：数组长度为n，找出数组中没有在[1,n]中出现过的数字，1 <= nums[i] <= n


解：将原数组当做一个哈希表，从左到右遍历，将nums[i] - 1 ∈ [0, n-1] 为数组的下标范围，将nums[nums[i] - 1]变为负数。第二次遍历，如果nums[i]为正，则表示i+1未出现过，第二次遍历记得给nums[i]加绝对值




class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i) {
            int id = abs(nums[i]) - 1;
            if(nums[id] > 0)
                nums[id] *= -1;
        }
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i)
            if(nums[i] > 0)
                res.push_back(i + 1);
        return res;
    }
};



树


面试题34. 二叉树中和为某一值的路径


              5
             / \
            4   8
           /   /   \
         11  13   4
         /  \      /  \
        7   2    5     1
// 这里的路径为根节点到叶子节点
void dfs(TreeNode* root, int target) {
        if(!root) return;
        path.push_back(root -> val);
        target -= root -> val;
        if(!root -> left && !root -> right && target == 0) 
            res.push_back(path);
        dfs(root -> left, target);
        dfs(root -> right, target);
        path.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }



剑指 Offer 68 - I. 二叉搜索树的最近公共祖先


TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ans = root;
        while(true) {
            if(p -> val < ans -> val && q -> val < ans -> val)
                ans = ans -> left;
            else if(ans -> val < p -> val && ans -> val < q -> val)
                ans = ans -> right;
            else break;
        }
        return ans;
    }



二叉树转成双链表




题解：初始化节点head,和pre。head用来表示头结点，pre记录前驱节点，当通过递归找到最左的节点后 使pre指向该最左节点。pre不为空后，每次访问节点使得 pre->right = cur; cur-> left = pre; pre = cur;最后，再通过head和pre连接头尾




class Solution {
private:
    Node* pre = NULL, *head = NULL;
public:
    void dfs(Node* cur) {
        if(!cur) return;
        dfs(cur -> left);
        if(!pre){
            pre = cur;
            head = cur;
        } 
       else {
            cur -> left = pre;
            pre -> right = cur;
            pre = cur;
       }
        dfs(cur -> right);
    }
 
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        dfs(root);
        head -> left = pre;
        pre -> right = head;
        return head;
    }
};



剑指 Offer 33. 二叉搜索树的后序遍历序列




输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
 题解：递归，分治， 从左到右找到第一个大于根节点的值x,假设下标为j， 根据后序遍历树的特性可知，当前区间最后的节点为根节点，根据x可分为 [left，j-1] 和[j, right]，再向下递归可得结果.




bool solve(vector<int>& postorder, int lo, int hi) {
        if(lo >= hi) return true;
        // cout << lo <<" "<< hi << endl;
        int idx = lo;
        while(postorder[idx] < postorder[hi]) idx++;
        int left = idx;
        while(postorder[idx] > postorder[hi]) idx++;
        // cout << left <<" "<< idx - 1 << endl;
        return idx == hi && solve(postorder, left, idx - 1) && solve(postorder, lo, left - 1);
    }
    bool verifyPostorder(vector<int>& postorder) {
        return solve(postorder, 0, postorder.size() - 1);
    }



剑指 Offer 28. 对称的二叉树




请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。




public:
    bool isSame(TreeNode* r1, TreeNode* r2) {
        if(!r1 && !r2) return true;
        if(!r1 || !r2) return false;
        if(r1 -> val != r2 -> val) return false;
        return isSame(r1 -> left, r2 -> right) && isSame(r1 -> right, r2 -> left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isSame(root, root);
    }



剑指 Offer 26. 树的子结构




输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)




class Solution {
public:
     bool isSame(TreeNode* A, TreeNode* B) {
         if(!B) return true;
         if(!A) return false;
         if(A -> val != B -> val) return false;
        return isSame(A -> left, B -> left) && isSame(A -> right, B -> right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;
        return isSame(A, B) ? true : isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};



617. 合并二叉树


合并两个二叉树




递归同步建树




class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2;
        if(!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1 -> left, root2 -> left);
        root1->right = mergeTrees(root1 -> right, root2 -> right);
        return root1;
    }
};



543. 树的直径




树中任意两个节点之间的最长距离
 解：最长路径可以看成是由一个父节点和其左右子树的最长节点数拼接而成




class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int d = 0;
        solve(root, d);
        return d;
    }
    int solve(TreeNode* node, int &d) {
        if(!node) return 0;
        int l = solve(node->left, d);
        int r = solve(node->right,d);
        d = max(l+r,d);
        return max(l,r) + 1;
    }
};



二叉树的最近公共祖先


bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return false;
        bool left = dfs(root -> left, p, q);
        bool right = dfs(root -> right, p, q);
        if((left && right) || (root -> val == p -> val || root -> val == q -> val) && (left || right) ){
            ans = root;
        }
        return left || right || (root -> val == q -> val|| root -> val == p ->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p, q);
        return ans;
    }



437. 路径总和




给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。






解法：使用前缀和


  • map的使用: key 表示前缀和， value表示该前缀和节点的数量
  • 节点前缀和为根节点到该节点的路径




class Solution {
public:
    int cnt = 0;
    unordered_map<int, int> prefix;
    void solve(TreeNode* root, int sum, int cur, int& cnt) {
        if(!root) return;
        cur += root -> val;
        if(prefix.find(cur - sum) != prefix.end())
            cnt += prefix[cur - sum];
        prefix[cur]++; 
        solve(root -> left, sum, cur, cnt);
        solve(root -> right, sum, cur, cnt);
        prefix[cur]--; //回溯
    }
    int pathSum(TreeNode* root, int sum) {
        prefix[0] = 1;
        solve(root, sum, 0, cnt);
        return cnt;
    }
};



字符串


剑指 Offer 58 - II. 左旋转字符串




  • 将字符串倍增或通过取余




for(int i = n; i < n + len; ++i)
            res += s[i%len]；



剑指 Offer 48. 最长不含重复字符的子字符串


请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 题解： 双指针加哈希表。哈希表记录字母出现的最后位置。


 int lengthOfLongestSubstring(string s) {
        int fast = 0, slow = 0;
        map<char, int> mp;
        int res = 0;
        while(fast < s.size()) {
            char ch = s[fast];
            if(mp.find(ch) != mp.end()) 
                slow = max(slow, mp[ch] + 1);
            res = max(res, fast - slow + 1); 
            mp[ch] = fast;
            fast++;
            
        }
        return res;
 }



763. Partition Labels


题意：将字符串分割，使得字符串中的每个字母最多只在一个part中出现
 题解：贪心，从左往右遍历，找到每个字符最后出现的下标j，不断扩张j，直到i==j。


class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> last(26);
        for(int i = 0; i < S.size(); ++i) {
            last[S[i] -'a'] = i;
        }
        int str = 0, j = 0;
        vector<int> ans;
        for(int i = 0; i < S.size(); ++i) {
            j = max(j, last[S[i] - 'a']);
            if(i == j) {
                ans.push_back(j - str + 1);
                str = i + 1;
            }
        }
        return ans;
    }
};



647. Palindromic Substrings


计算字符串中有多少个回文串
 方法一
 中心扩展：枚举每个字符，当成回文串的中心，向两边扩展。


class Solution {
public:
    int ans = 0;
    void solve(string s, int l, int r) {
        while(l >= 0 && r <= s.size()) {
            if(s[l] == s[r]) {
                l--;
                r++;
                ans++;
            } else break;
        }
    }
    int countSubstrings(string s) {
        for(int i = 0 ; i < s.size(); ++i) {
            solve(s, i, i);
            solve(s, i, i + 1);
        }
        return ans;
    }
};



方法二
 Manacher算法O(n)复杂度


class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};



438. Find All Anagrams in a String


找到字符串中所有字母异位词
 解法：滑动窗口


  • vector存储字符出现的频率，由于只有26个字母，空间大小只需26
  • vector<int, int> win, cnt。win统计字符串s窗口大小为k的字符串词频， cnt统计匹配字符串的词频
  • win=cnt时将窗口左侧位置加入res


class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(p.size() > s.size()) return {};
        vector<int> res;
        vector<int> cnt(26, 0);
        vector<int> win(26, 0);
        int k = p.size();
        int target = p.size();
        for(char ch: p) {
            cnt[ch - 'a']++;
        }
        
        for(int i = 0; i < p.size(); ++i) {
            win[s[i] - 'a']++;
        }
        if(win == cnt) 
            res.push_back(0);
        
        for(int i = p.size(); i < s.size(); ++i) {
            win[s[i] -'a']++;
            win[s[i-k] -'a']--;
            if(win == cnt)
                res.push_back(i-k+1);
        }
        return res;
    }
};



动态规划


剑指 Offer 60. n个骰子的点数




题意：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
 题解：dp[i][j]表示i个骰子点数为j的概率，可以看成是dp[i - 1][j]加上一个骰子的概率
 即dp[i][j] = dp[i - 1][j - k] * 1.0 / 6.0; k∈（1.6）,且每次更新只用到了上一层的数据，所以对空间还可进一步优化，可使用滚动数组。




vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0/6.0);
        for(int i = 2; i <= n; ++i) {
            vector<double> tmp(i * 5 + 1, 0);
            for(int j = 0; j < dp.size(); ++j) {
                for(int k = 0; k < 6; ++k) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }



剑指 Offer 49. 丑数




我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 题解：a表示前(a-1)个数已经乘过2， b表示前（b-1）个数已经乘过3，c表示前（c-1）个数已经乘过5，则第i个丑数只能由这几个状态转移过来




int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0] = 1;
        int a = 0,b = 0,c = 0;
        for(int i = 1; i < n; ++i) {
            dp[i] = min(min(2 * dp[a], 3 * dp[b] ), 5 * dp[c]);
            if(dp[i] == 2 * dp[a]) a++;
            if(dp[i] == 3 * dp[b]) b++;
            if(dp[i] == 5 * dp[c]) c++;
        }
        return dp[n - 1];
    }



剑指 Offer 46. 把数字翻译成字符串


给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 题解：找出动态转移方程



     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
        
         =
        
        
         
          {
         
         
          
           
            
             
              
               d
              
              
               p
              
              
               [
              
              
               j
              
              
               −
              
              
               1
              
              
               ]
              
             
            
           
           
            
             
              
               O
              
              
               t
              
              
               h
              
              
               e
              
              
               r
              
              
               s
              
             
            
           
          
          
           
            
             
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               −
              
              
               1
              
              
               ]
              
              
               +
              
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               −
              
              
               2
              
              
               ]
              
             
            
           
           
            
             
              
               10
              
              
               <
              
              
               =
              
              
               t
              
              
               m
              
              
               p
              
              
               <
              
              
               =
              
              
               25
              
             
            
           
          
         
        
       
       
        dp[i][j] = \begin{cases} dp[j - 1] & Others \\ dp[i - 1] + dp[i - 2] & 10 <= tmp <= 25 \\ \end{cases}
       
      
     dp[i][j]={dp[j−1]dp[i−1]+dp[i−2]​Others10<=tmp<=25​


int translateNum(int num) {
        string s = to_string(num);
        int l = 1;
        int m = 1;
        int r = 1;
        for(int i = 1; i < s.size(); ++i) {
             r = 0;
            int tmp = (s[i - 1] - '0') * 10 + (s[i] - '0');
            //  cout<< "tmp: " <<tmp << endl;
            if(10 <= tmp && tmp <= 25)
                r += l;
            r += m;
            
            l = m;
            m = r;
        }
        return r;
    }



494. 目标和（待补充）


题意：给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。


dp[i][j]表示第i个位置，和为j的方法共有几种
 其动态转移方程为：


dp[i][j] = dp[i - 1][j - num[i]] + dp[i - 1][j + num[i]]



写成递推的形式为


dp[i][j + num[i]] = dp[i - 1][j];
dp[i][j - num[i]] = dp[i - 1][j];



由于j的值最小为-1000，所以可以预先给数组加1000防止越界，变为


dp[i][j + num[i] + 1000] = dp[i - 1][j + 1000];
dp[i][j -  num[i] + 1000] = dp[i - 1][j + 1000];



代码如下


class Solution {
public:
 
    int findTargetSumWays(vector<int>& nums, int S) {
        vector<vector<int>> dp(nums.size() + 1, vector<int>(2001,0));
        dp[0][nums[0] + 1000] = 1;
        dp[0][-nums[0] + 1000] += 1;
        for(int i = 1; i < nums.size(); ++i) {
            for(int sum = -1000; sum <= 1000; ++sum) {
                if(dp[i - 1][sum + 1000] > 0) {
                    dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
                    dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
                }
                 
            }
        }
        return S > 1000 ? 0 : dp[nums.size() - 1][S + 1000];
    }
};


                    

                        这篇关于刷题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
                    


                


                
                
 

                
                

                    

                        
您可能喜欢

                        
                    

                

                

            

             
            
            
            
        

        
        

        

            

                
栏目导航