1、两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>result;
for (int i = 1; i < nums.size(); i++) {
int prev = nums[i - 1];
int j = i;
while(j < nums.size()) {
int curr = nums[j];
if (prev + curr == target) {
return {i - 1, j};
}
j++;
}
}
return {};
}
};2、两数相加
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int val1 = l1->val;
int val2 = l2->val;
int time = 10;
ListNode *node = new ListNode();
ListNode *head = node;
ListNode *node1 = l1;
ListNode *node2 = l2;
node->val = (val1 + val2) % time;
node->next = nullptr;
int flag = (val1 + val2) / time; // 进位
while (node1->next != nullptr || node2->next != nullptr || flag != 0) {
ListNode *n = new ListNode();
n->next = nullptr;
int a = flag;
if (node1->next != nullptr) {
node1 = node1->next;
a = a + node1->val;
}
if (node2->next != nullptr) {
node2 = node2->next;
a = a + node2->val;
}
n->val = a % time;
flag = a / time;
node->next = n;
node = n;
}
return head;
}
};7、整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意：
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示：
-231 <= x <= 231 – 1
class Solution {
public:
int reverse(int x) {
int time = 10;
// 提取个位数
int ret = x % time;
int a = x / 10;
while ((x > 0 && a > 0) || (x < 0 && a < 0)) {
int f = a % 10;
a = a / 10;
if (ret > INT_MAX / 10 || ret < INT_MIN / 10) {
return 0;
}
ret = ret * time + f;
}
return ret;
}
};9、回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
}
bool flag = true;
int len = this->length(x);
int time = 10;
int headIndex = pow(time, len);
int tailIndex = 10;
while (true) {
if (x / headIndex != x % tailIndex) {
flag = false;
break;
}
// 掐头去尾
x = x % headIndex;
x = x / 10;
len = len - 2;
headIndex = pow(time, len);
if (headIndex < 10) {
break;
}
}
return flag;
}
int length(int x) {
int time = 10;
int len = 0;
while (x / time > 0 || x / time < 0) {
len++;
x = x / time;
}
return len;
}
};13. 罗马数字转整数
class Solution {
public:
int romanToInt(string s) {
int len = s.length();
if (len == 1) {
return this->getNumByRomanChar(s[0]);
}
int ret = 0;
int i = 0;
for (; i < len - 1; i++) {
char curr = s[i];
char back = s[i + 1];
if (curr == 'I' && (back == 'V' || back == 'X')) {
ret = ret + this->getNumByRomanChar(back) - this->getNumByRomanChar(curr);
i++;
continue;
}
if (curr == 'X' && (back == 'L' || back == 'C')) {
ret = ret + this->getNumByRomanChar(back) - this->getNumByRomanChar(curr);
i++;
continue;
}
if (curr == 'C' && (back == 'D' || back == 'M')) {
ret = ret + this->getNumByRomanChar(back) - this->getNumByRomanChar(curr);
i++;
continue;
}
ret = ret + this->getNumByRomanChar(curr);
}
if (i == len - 1) {
ret = ret + this->getNumByRomanChar(s[i]);
}
return ret;
}
int getNumByRomanChar(char s) {
int ret = 0;
switch(s) {
case 'I':
ret = 1;
break;
case 'V':
ret = 5;
break;
case 'X':
ret = 10;
break;
case 'L':
ret = 50;
break;
case 'C':
ret = 100;
break;
case 'D':
ret = 500;
break;
case 'M':
ret = 1000;
break;
default:
ret = 0;
}
return ret;
}
};14. 最长公共前缀
最长公共前缀 – 横向扫描法
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int len = strs.size();
if (len <= 0) return "";
string s1 = strs[0];
for (int i = 1; i < len; i++) {
string s2 = strs[i];
s1 = this->LCP(s1, s2);
}
return s1;
}
string LCP(string str1, string str2) {
int len1 = str1.size(), len2 = str2.size(), i = 0;
while (i < len1 && i < len2 && str1[i] == str2[i]) {
i++;
}
return str1.substr(0, i);
}
};20. 有效的括号
利用栈的知识进行处理
class Solution {
public:
bool isValid(string s) {
stack<char> myStack;
if (s.size() % 2 == 1) return false;
myStack.push(s[0]);
auto length = s.size();
for (int i = 1; i < length; i++) {
char c2 = s[i];
char matchItem;
char c = ' ';
if (!myStack.empty()) {
c = myStack.top(); // 取出栈顶元素但不删除栈顶元素
}
switch (c2) {
case '[':
case '{':
case '(':
// 压入栈中
myStack.push(c2);
continue;
break;
case ')':
matchItem = '(';
break;
case ']':
matchItem = '[';
break;
case '}':
matchItem = '{';
break;
}
if (matchItem == c) {
myStack.pop(); // 删除栈顶元素
continue;
};
myStack.push(c2);
}
// cout << myStack.top() << endl;
return myStack.empty();
}
};21. 合并两个有序链表
我用的方法是，取出两个值，判断大小，小的链表移动到下一格，直到其中一个链表用尽，将剩下的链表绑定到新生成的有序链表后面即可。
迭代法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode();
ListNode *node = head;
if (!l1 && !l2) return l1;
if (!l1) return l2;
if (!l2) return l1;
int val1 = l1->val;
int val2 = l2->val;
if (val1 >= val2) {
node->val = val2;
l2 = l2->next;
} else {
node->val = val1;
l1 = l1->next;
}
while (l1 && l2) {
ListNode *tmpNode = new ListNode();
node->next = tmpNode;
node = tmpNode;
int val1 = l1->val;
int val2 = l2->val;
if (val1 >= val2) {
node->val = val2;
l2 = l2->next;
} else {
node->val = val1;
l1 = l1->next;
}
}
if (l1) node->next = l1;
if (l2) node->next = l2;
return head;
}
};官方的代码更加简洁
include
using namespace std;
/**
Definition for singly-linked list.
*/
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *result = new ListNode(-1); //哑节点简化代码
ListNode *workNode = result;
while (l1 != nullptr && l2 != nullptr)
{
if (l1->val <= l2->val)
{
workNode->next = l1;
l1 = l1->next;
}
else
{
workNode->next = l2;
l2 = l2->next;
}
workNode = workNode->next;
}
workNode->next = l1 != nullptr ? l1 : l2;
return result->next; }
};- 可以使用哑节点来存储链表的开头
- workNode->next 被赋值了l2或l1故不用在循环过程中生成新的节点，节约内存
26. 删除排序数组中的重复项
删除重复项，通过i下标控制顺序数组，通过j遍历整个数组，当遇到i下标指向的数字不等于j下标指向的数字，则++i之后将j下标指向的数字赋值给他即可，最后返回i+1的结果
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
if (len == 0) {
return 0;
}
int i = 0;
int j = 1;
for (i, j; i < len && j < len; j++) {
if (nums[i] != nums[j]) {
nums[++i] = nums[j];
}
}
return i+1;
}
};27. 移除元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
for (int j = 0; j < nums.size(); j++) {
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
}
return i;
}
};这道题做法基本同上
28. 实现 strStr()
class Solution {
public:
int strStr(string haystack, string needle) {
int hayLen = haystack.size();
int needLen = needle.size();
if (needLen == 0) return 0; // 没有字符串的时候为啥返回0 ？？？？
if (hayLen == 0) return -1;
if (needLen > hayLen) return -1;
int j = 0;
int flag = -1;
for (int i = 0; i < hayLen; i++) {
if (haystack[i] == needle[j]) {
int c = i;
while (haystack[c] == needle[j]) {
c++;
j++;
if (j >= needLen) {
return c - j;
}
}
}
j = 0;
}
return flag;
}
};不是很懂，当 needle 是空字符串时，为什么要返回0
35. 搜索插入位置
我只会用暴力解
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 假设数组中无重复元素
int len = nums.size();
for (int i = 0; i < len; i++) {
if (nums[i] >= target) {
return i;
}
}
return len;
}
};二分法解答
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
int left = 0;
int right = len - 1;
int mid = 0;
do {
mid = (left + right) / 2;
if (target <= nums[mid]) {
right = mid - 1;
} else{
left = mid + 1;
}
} while (mid != left && right >= left);
return left;
}
};拼拼凑凑，弄了个二分的解答
LeetCode官方给的解答
class Solution {
public:
int searchInsert(vector& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};
取mid的时候使用了位操作符右移操作，不是很懂
38. 外观数列
class Solution {
public:
string countAndSay(int n) {
string ans = "1";
if (n == 1) return ans;
ans = this->countAndSay(n - 1);
int len = ans.size();
string res = "";
for (int i = 0; i < len; i++) {
char item = ans[i];
int j = i;
while (j < len) {
if (item != ans[j]) {
break;
}
j++;
}
res += to_string(j - i);
res += item;
i = j - 1;
}
return res;
}
};利用递归算出之前的字符串，然后对字符串进行解释即可
53. 最大子序和
无法通过时间，没写好。先贴一个暴力方法写的
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 最大子序列和, 暴力解法
int window = 1; // 窗口大小默认1
int max = nums[0];
int len = nums.size();
while (window <= len) {
for (int i = 0; i <= len - window; i++) {
int ans = nums[i];
for (int j = i + 1; j < window + i; j++) {
ans += nums[j];
}
// cout << "ans = " << ans << endl;
if (ans > max) {
max = ans;
}
}
window++;
}
return max;
}
};正确的暴力解答（动态规划）：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0;
int max = nums[0];
for (int i = 0; i < nums.size(); i++) {
if (sum < 0) {
sum = nums[i];
} else {
sum += nums[i];
}
max = max > sum ? max : sum;
}
return max;
}
};真的非常不好理解，我感觉。
取了两个值，一个sum变量用来存储当前正在计算的和，另一个max变量用来存储当前已经算出来的最大的连续和。
当和小于0的时候，下一个值直接赋值给sum。考虑特殊情况，全为负数时，sum 始终小于0，则每次都将该值直接赋值给sum，即从该列表中找到最大的唯一一个值即可。
考虑另外一种特殊情况，当所有数为大于等于0 的时候，即把所有数相加即得max得值。
考虑剩下的情况，正数和负数同时出现在数列中的时候，如果当前的sum 小于 0，直接对比下一个值是否比该值大，因为存在正数，所以一定存在比sum大的值，故直接赋值给sum， 当sum >= 0的时候，将遇到的下一个值加在sum中，然后去与max比较大小，如果加上该值后，sum > max，则修改max 为当前的sum
我还是无法理解，淦
暂无评论