LeetCode刷题记录 6-10

马上要面试了，把前些天在LeetCode上刷的题再看一遍。

写上注释，算复习了，也方便以后复习。

带 * 号的为忘记怎么做的。

1. 2. 两数相加（链表基础）

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 首先要明确，无论是输入还是输出，都是低位在前，实际上是为计算提供了方便
        int carry = 0;  // 进位标志
        ListNode* head = NULL, *last;
        while (l1 != NULL && l2 != NULL) {
            int temp1 = l1->val + l2->val + carry;  // 要加进位标志
            carry = temp1 / 10;  // 取出进位标志
            temp1 %= 10;         // 获得去除进位标志后的结果
            ListNode* temp2 = new ListNode(temp1);
            // 第一次，初始化头结点
            if (!head) {
                head = temp2;
                last = head;
            }
            // 否则尾插法建表
            else {
                last->next = temp2;
                last = last->next;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1) {
            int temp1 = l1->val + carry;// 要加进位标志
            carry = temp1 / 10;// 取出进位标志
            temp1 %= 10;// 获得去除进位标志后的结果
            ListNode* temp2 = new ListNode(temp1);
            last->next = temp2;// 尾插法建表
            last = last->next;
            l1 = l1->next;
        }
        // 同上
        while (l2) {
            int temp1 = l2->val + carry;
            carry = temp1 / 10;
            temp1 %= 10;
            ListNode* temp2 = new ListNode(temp1);
            last->next = temp2;
            last = last->next;
            l2 = l2->next;
        }
        // 如果还有进位，则最高位必为1
        if (carry) {
            ListNode* temp2 = new ListNode(1);
            last->next = temp2;
            last = last->next;
        }
        return head;
    }
};

2. 283. 移动零（简单优化）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // -1 0 1 2 0 4 5 0 0
        int k = 0;
        int n = nums.size();
        // 这种写法的目的是省去一次循环，自己模拟一下就好了
        for (int i = 0; i < n; i++) {
            if (nums[i]) 
                if (i != k)
                    swap(nums[i], nums[k++]);
                else k++;
        } 
    }
};

3. 64. 最小路径和（动态规划）

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;
        // 二维vector初始化
        vector< vector<int> > dp(m, vector<int>(n, 0));
        // dp数组初始化
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) dp[0][i] = dp[0][i - 1] + grid[0][i];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 状态转移
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

4. 215. 数组中的第K个最大元素（Top K）

// 快速选择 注意vector必须是引用传参！
class Solution {
public:
    // 进行一次划分（对主元进行一次定位）
    int Partition(vector<int> &arr, int left, int right) {
        int pivot = arr[left];     // 采用三者取中可以加速，这里简单取了头元素
        while (left < right) {
            while (left < right && arr[right] >= pivot) right --;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left ++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        // 返回主元划分后的位置
        return left;
    }

    // 快速选择
    int QuikSelect(vector<int> &arr, int left, int right, const int k) {
        // 进行一次划分
        int location = Partition(arr, left, right);
        // 按照划分结果持续进行划分，直到满足location指向第k大
        while (location != arr.size() - k) {
            if (location > arr.size() - k) right = location - 1;
            else left = location + 1;
            location = Partition(arr, left, right);
        }
        return arr[location];
    }

    int findKthLargest(vector<int>& nums, int k) {
        return QuikSelect(nums, 0, nums.size() - 1, k);
    }
};

// 手写堆
/*
class Solution {
public:
    // 进行一次自上而下的调整
    void HeapAdjust(vector<int> &arr, int s, int m) {
        int temp = arr[s];
        for (int i = 2 * s + 1; i <= m; i = i * 2 + 1) {
            // i指向较大的
            if (i < m && arr[i] < arr[i + 1]) i++;
            // 已经调整完了
            if (temp > arr[i]) break;
            // 调整
            arr[s] = arr[i];
            s = i;
        }
        arr[s] = temp;
    }

    int HeapSort(vector<int> &arr, int n, int k) {
        // 建立大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            HeapAdjust(arr, i, n - 1);
        }
        // 进行k次排序，获得[n-k...n-1]的最值
        for (int i = n - 1; i >= n - k; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            HeapAdjust(arr, 0, i - 1);
        }
        return arr[n - k];
    }

    int findKthLargest(vector<int>& nums, int k) {
        return HeapSort(nums, nums.size(), k);
    }
};
*/

// STL优先队列
/*
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 建立小顶堆
        priority_queue<int, vector<int>, greater<int> > pri_que;
        for (auto num : nums) {
            pri_que.push(num);
            // 当超过k，把最小的弹出
            if (pri_que.size() > k) pri_que.pop(); 
        }
        return pri_que.top();
    }
};
*/

5. 48. 旋转图像（模拟）

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int a, c; // 控制变量，奇偶表现不同
        if (n % 2 == 0) {a = -1; c = -1;}
        else {a = 0; c = -1;}
        for (int i = 0; i <= n / 2 + a; i++) {
            for (int j = 0; j <= n / 2 + c; j++) {
                // 计算出4个坐标
                int x1 = i, y1 = j;
                int x2 = y1, y2 = n - 1 - x1; 
                int x3 = y2, y3 = n - 1 - x2; 
                int x4 = y3, y4 = n - 1 - x3;
                // 循环覆盖 
                int temp = matrix[x1][y1];
                matrix[x1][y1] = matrix[x4][y4];
                matrix[x4][y4] = matrix[x3][y3];
                matrix[x3][y3] = matrix[x2][y2];
                matrix[x2][y2] = temp;
            }
        }
    }
};