# 1. 两数之和

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

  • 最简单的办法就是暴力循环,每两个数相加一次,时间复杂O(n²)。
  • 用空间换取时间是常用的方法,若i + j = target,称j为i的补数。以每个数和他的补数建立hash表。
    • 建立一次表格,循环查表格一次,需要两次遍历。
    • 可以进一步优化,在建立表格的同时进行查表。若是没有找到对应的元素,插入表中,否则返回结果。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            int n = nums[i];
            if(m.find(n) != m.end()) {
                vector<int> result = {m[n], i};
                return result;
            } else {
                m[target - n] = i;
            }
        }
        vector<int> result = {0, 1};
        return result;
    }
};

# 2. 两数相加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807

思路

这道题不难,只是模仿加法进位。需要注意的一点是当两个数的位数不一样的时候。如9876 + 321,此时l2的指针遍历到3之后就指向null了,第一该指针不该向前继续遍历,第二在之后的计算中该位按0处理。

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l3 = new ListNode(0);
        struct ListNode* L3 = l3;

        int carry = 0;
        int n1, n2, num;
        while(1) {
            //取得当前位数的值,为null则按0处理
            if(l1 == NULL) 
                n1 = 0;
            else 
                n1 = l1->val;
            if(l2 == NULL) 
                n2 = 0;
            else 
                n2 = l2->val;
            
            //取得进位符和计算结果
            num = (n1 + n2 + carry) % 10;
            carry = (n1 + n2 + carry) / 10;
            l3->val = num;

            //非空时候指向下一个指针,否则则不变。
            if(l1 != NULL) l1 = l1->next;
            if(l2 != NULL) l2 = l2->next;
            
            //计算完毕,返回结果
            if(l1 == NULL && l2 == NULL && carry == 0) {
                return L3;
            }
			//计算未完,节点加入链表
            l3->next = new ListNode(0);
            l3 = l3->next;
            l3->next = NULL;

            
        }
    }
};

# 3. 无重复字符的最长子串

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路

例如一个字符串abcdba,先维护一个set来存储已经发现的字符串。从a开始遍历,abcd分别入set。此刻最长无重复字符串是abcd

循环到b时候发现b在队列,则把第一个b以及之前的a全部清除,此刻最长无重复字符串是cdb

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        unordered_set<char> set;
        char c;
        int i = 0, j = 0, maxStr = 0;
        for(; i < s.size(); i++) {
            while(set.find(s[i]) != set.end()) {
                set.erase(s[j]);
                j++;
            }
            maxStr = max(maxStr, i - j + 1);
            set.insert(s[i]);
        }            
        return maxStr;
    }
};

# 4.寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3] nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2] nums2 = [3, 4]

则中位数是 (2 + 3) / 2 = 2.5

# 5.最长回文字串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd" 输出: "bb"

# 6. Z字变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

L C I R E T O E S I I G E D H N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释:

L D R E O E I I E C I H N T S G

思路

找到变换后的字符串的规律,以LEETCODEISHIRING四行为例,输出字符在原字符串中的位置如下:

0 6 12

1 5 7 11 13

2 4 8 10 14

3 9 15

可以看到头尾都是3个,位置之间间隔6个, 间隔数为 2n - 1。于是头从0开始, 尾从n - 1开始,以间隔为 2n - 1循环输出字符。

代码

class Solution {
public:
    string convert(string s, int n) {
        if (n == 1) return s;

        int m = 2 * n - 2;
        int l = s.length();
        string result;
        
        for (int i = 0; i < l; i += m){
            result = result + s[i];
        }
        for (int j = n - 2; j > 0; j--) {
            for (int i = n - 1, k = l + m; i < k; i += m) {
                if ((i - j) < l)
                    result = result + s[i - j];
                if ((i + j) < l)
                    result = result + s[i + j];
            }
        }
        for (int i = n - 1; i < l; i += m) {
            result = result + s[i];
        }

        return result;
    }
};