输入两个链表，找出它们的第一个公共节点。思路一：先统计两个链表的长度，比如l1长度为10，l2长度为6。然后l1先走4步，l1和l2再同时出发，如果l1等于l2则找到公共节点。代码：class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA == nullptr || headB == nullptr) return nullptr; int a = 0,b = 0; ListNode* aTmp = headA; ListNode* bTmp = headB; while(aTmp) { a++; aTmp = aTmp->next; } while(bTmp) { b++; bTmp = bTmp->next;
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。思路：使用归并排序，在归并的过程，统计逆序对的数量。比如两个待归并的数组为l=[5,6,12],r=[1,9,10]。归并的时候从右到左归并。12比10大，此时统计逆序对的数量，显然此时逆序对的数量是r的长度。把12放到排序数组的最末端。然后比较6和10，此时逆序对的数量为0，把10放入排序数组，在12的前面，接着比较6和9，逆序对的数量为0，把9放入排序数组，放在10的前面。比较6和1，此时逆序对的数量为1，把6放入排序数组，放在9的前面。接着比较5和1，此时逆序对的数量为1，把5放入排序数组，放在6的前面。最后把1放入排序数组，最左边的位置，排好序，同时，逆序对的数量也统计好了。代码：class Solution { public: int reversePairsRecursive(vector<int>& nums, vector<int>& copy, int start, int end) {
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。思路：统计每个字符出现的次数，第一个出现次数为1的字符即是答案代码class Solution { public: char firstUniqChar(string s) { int len = s.length(); if(len == 0) return ' '; unordered_map<char,int> count; for(int i = 0;i < len;i++) { count[s[i]]++; } for(int i = 0;i < len;i++) { if(count[s[i]] == 1) { return s[i]; } } return ' '; } };
把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。思路：因为丑数只包含质因子2、3、5，所以第n个丑数，必由第i个丑数乘以2或3或5得来，1<=i<n,而对于乘以2、乘以3和乘以5的i可能不一样。设index2表示乘以2的下标，index3表示乘以3的下标，index5表示乘以5的下标。dp[i]表示第i个丑数，则dp[i]=min(min(dp[index2]*2,dp[index3]*3),dp[index5]*5)，初始时,index2=1,index3=1,index5=1。如果dp[i]==dp[index2]*2,则index2加一,index3和index5也一样。代码：class Solution { public: int nthUglyNumber(int n) { vector<int> dp(n+1); dp[1] = 1; int index2 = 1; int index3 = 1; int
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。思路：设字符串为s，dp[i]表示以下标i为结尾字符串最长子字符串的长度。则dp[i]=dp[i-1]+1,i的前dp[i-1]个字符串中没有与s[i]重复的。dp[i]=min(i-j,dp[i-1]+1),j表示i的前dp[i-1]个字符串中与s[i]重复的字符下标。用一个unordered_map记录字符的下标。代码：class Solution { public: int lengthOfLongestSubstring(string s) { int length = s.size(); if(length == 0) return 0; vector<int> dp(length); dp[0] = 1; unordered_map<char,int> indexMap; indexMap[s[0]] = 0; int maxL = 1;
