来源：力扣（LeetCode） 链接：https://leetcode-cn.com/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
leetcode001-两数之和
题目重述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题解
程序员小吴(C++) Karl Xavier(Go)
C++版本思路及代码
设置一个map容器和record用来记录元素的值与索引，然后遍历数组nums。
- 每次遍历中使用临时变量
complement用来保存目标值与当前值的差值 - 在此次遍历中查找
record，查看是否有与complement一致的值，如果查找成功则返回查找值的索引与当前nums中变量值的索引i - 如果未找到，则在
record中保存该元素与索引值i
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> record;
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
if (record.find(complement) != record.end()) { // 如果在 map 里没有查找到，就返回 end()
int res[] = {i, record[complement]};
cout << res << endl;
cout << res + 2 << endl;
return vector<int>(res, res + 2);
}
record[nums[i]] = i; // 查到了， 将原数组值变为其下标
}
return vector<int>();
}
};
// [2,7,11,15]
// 9
int main() {
vector<int> nums = {2, 7, 11, 15};
vector<int> res;
int target = 9;
Solution s = *new Solution();
res = s.twoSum(nums, target);
for (int i = 0; i < res.size(); ++i) {
cout << res[i] << endl;
}
}
Go版本思路及代码
- 创建
map映射v，存放目标数组的相关信息 - 遍历目标数组，并获取目标值
target与数组元素nums[i]的差值dif - 将差值
dif作为map中的key，目标数组nums的索引作为map中的value - 判断
map中是否包含差值dif，如果包含则返回对应的value - 如果
map中没有，则把其放到map中
package main
import "fmt"
func twoSum(nums []int, target int) []int {
v := make(map[int]int)
for i := 0; i < len(nums); i++ {
dif := target - nums[i]
c, ok := v[dif]
if ok != false {
return []int{c, i}
}
v[nums[i]] = i
}
return []int{-1, -1}
}
// [2,7,11,15]
// 9
func main() {
target := 9
nums := []int{2, 7, 11, 15}
fmt.Print(twoSum(nums, target))
}
leetcode002-两数相加
题目重述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
题解
陈乐乐(c++) dp0qb(go)
C++版本思路及代码
将长度较短的链表在末尾补0使得两个链表长度相等，然后再一个一个元素对其相加，需要注意的是要考虑进位。
- 获取两个链表的长度
- 较短的链表末尾补零
- 对齐相加，注意考虑进位
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {} // 定义链表的构造方法
};
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int len1 = 1; // 记录L1的长度
int len2 = 1; // 记录L2的长度
ListNode *p = l1;
ListNode *q = l2;
while (p->next != NULL) {
// 获取 L1 的长度
len1++;
p = p->next;
}
while (q->next != NULL) {
// 获取 L2 的长度
len2++;
q = q->next;
}
if (len1 > len2) {
// 如果 L1 比 L2 长，在 L2 末尾补零
for (int i = 0; i <= len1 - len2; ++i) {
q->next = new ListNode(0);
q = q->next;
}
} else {
// L2 长 就在 L1 后面补 0
for (int i = 0; i <= len2 - len1; ++i) {
p->next = new ListNode(0);
p = p->next;
}
}
p = l1;
q = l2;
bool count = false; // 记录进位
ListNode *l3 = new ListNode(-1); // 结果链表
ListNode *w = l3; // L3 的移动指针
int i = 0; // 记录相加结果
while (p != NULL && q != NULL) {
i = count + p->val + q->val;
w->next = new ListNode(i % 10);
count = i >= 10 ? true : false;
w = w->next;
p = p->next;
q = q->next;
}
if (count) {
// 如果最后还有进位
w->next = new ListNode(1);
w = w->next;
}
return l3->next; // L3 头为 -1
}
};
Go版本思路及代码
- 依次正常遍历链表，按照对应位两数相加，如果超过
10，则取结果的个位数，下一位加1 - 如果一个链表比另一个链表短，那么长的链表就直接加
0 - 如果最后一位相加之和大于
10，那么最后不要忘记加上一个1结点
/** Definition for singly-linked list. **/
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var i, s int // 分别表示 相加是否大于10 ，以及 两数之和
res := &ListNode{Val: 0} // 头结点
now := res // 当前节点
for true {
if i > 0 {
// 前面两数之和大于10，当前的和加 1
s = l1.Val + l2.Val + 1
} else {
s = l1.Val + l2.Val
}
if s >= 10 {
// 两数之和大于10 该位 s-10 否则就是 本身，并设置 i标记
now.Next = &ListNode{Val: s - 10}
i = 1
} else {
now.Next = &ListNode{Val: s}
i = 0
}
now = now.Next
// 当 l1 和 l2 移到最后
if l1.Next == nil && l2.Next == nil {
// 如果 l1 l2 最后的和大于10 即i==1 那么后面还需要加一个 1
if i == 1 {
now.Next = &ListNode{Val: 1}
}
break;
}
// l1 到最后 如果是 l2 没结束，把 l1 当前结点设置为0 继续和 l2 相加，否则后移指针
if l1.Next == nil {
l1.Val = 0
} else {
l1 = l1.Next
}
// 同理 对 l2 有
if l2.Next == nil {
l2.Val = 0
} else {
l2 = l2.Next
}
}
// 返回头结点的下一个结点指针
return res.Next
}
leetcode020-有效的括号
题目重述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
题解
c***6(c++) chris(go)
C++版本思路及代码
- 使用
vector来模拟栈 - 每次取前半括号包括
(、[、{都将其入栈 - 如果取到的是后半括号
)、]、}就与取栈顶元素进行匹配，如果匹配就进行出栈操作，不匹配就返回错误
class Solution {
public:
bool isValid(string s) {
int len = s.length();
int tmp;
// 用 vector 模拟栈
vector<char> hp;
for (int i = 0; i < len; i++) {
// 入栈
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
hp.push_back(s[i]); // 进栈
else {
// 栈空
if (hp.size() == 0)return false;
// 取栈顶元素，注意这不是出栈
tmp = hp.back();
// 出栈
if (tmp == '(' && s[i] == ')' || tmp == '[' && s[i] == ']' || tmp == '{' && s[i] == '}')
hp.pop_back(); // 出栈
else
return false;
}
}
return hp.size() == 0;
}
};
Go版本思路及代码
利用数组切片模拟栈进行操作。
- 使用
map用symbol变量保存匹配规则，只有到右括号的时候才取左括号 - 申请
c保存左括号 - 依次对字符串
s进行遍历- 用
clen保存c的长度，先判断clen长度是否大于零- 不大于零，将这个字符
value加入 - 大于零，同时如果
symbol中存在这个字符的key，就和clen最新加入的值进行匹配，匹配成功对c进行切片，把最新加入的值切掉
- 不大于零，将这个字符
- 用
- 最后判断
c是否为空，空了说明都匹配了
func isValid(s string) bool {
var c []byte
symbol := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
for _, value := range s {
clen := len(c)
if clen > 0 {
if _, ok := symbol[byte(value)]; ok {
if c[clen-1] == symbol[byte(value)] {
c = c[:clen-1]
continue
}
}
}
c = append(c, byte(value))
}
return len(c) == 0
leetcode026-删除排序数组中的重复项
题目重述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
题解
题解：陈乐乐(C++) BeYanJin(Go)
这个题目两种代码版本的思路基本相同，以Golang代码为例。
使用快慢指针的思想来操作数组元素。
- 定义慢指针
low让它始终指向数组的有序无重复序列的最后一项，即其所指位置的后一项就是有重复元素的项 - 定义快指针
fast让它始终指向数组中没有加入有序无重复序列的第一项 - 如果
nums[fast] != nums[low]，就有nums[low+1] = nums[fast]，然后low++；否则fast++，寻找没有加入无重复序列的那项
C++版本思路及代码
class Solution {
public:
int removeDuplicates(vector<int> &nums) {
if (nums.size() == 0) return 0;
int i = 0;
for (int j = 1; j < nums.size(); ++j) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
};
Go版本思路及代码
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
low := 0
for fast := 0; fast < len(nums); fast++ {
if nums[low] != nums[fast] {
nums[low+1] = nums[fast]
low++
}
}
return low + 1
}
leetcode053-最大子序和
题目重述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题解
题解：pinku-2
动态规划
- 动态规划的关键点我认为有两个部分：
- 确定dp数组：
dp[i]表示以i结尾的字段的和的最大值 - 建立状态转移方程：
dp[i]的值等于max(dp[i-1],0)+nums[i]，这是因为：如果dp[i]最大并且dp[i-1]大于0，那么dp[i-1]也最大；如果dp[i-1]小于0，那么前面的数就不用加上去了，所以干脆直接取nums[i]。
- 确定dp数组：
- 故有递推公式：$ dp[i] = max(dp[i-1], 0) + nums[i] $
class Solution1 {
public:
int maxSubArray(vector<int> &nums) {
int result = INT_MIN;
int numsSize = int(nums.size());
vector<int> dp(numsSize); // dp[i]表示nums中以nums[i]结尾的最大子序和
dp[0] = nums[0];
result = dp[0];
for (int i = 1; i < numsSize; ++i) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
result = max(result, dp[i]);
}
return result;
}
};
分治法
最大子序和是使用分治法解决问题的典型的例子，并且可以用与合并排序相似的算法求解。下面是用分治法解决问题的模板：
- 定义基本情况。
- 将问题分解为子问题并递归地解决它们。
- 合并子问题的解以获得原始问题的解。
当最大子数组有 n 个数字时：
- 若
n==1，返回此元素。 left_sum为最大子数组前n/2个元素，在索引为(left + right) / 2的元素属于左子数组。right_sum为最大子数组的右子数组，为最后n/2的元素。mid_sum是包含左右子数组且含索引(left + right) / 2的最大值。
class Solution2 {
public:
int maxSubArray(vector<int> &nums) {
int result = INT_MIN;
int numsSize = int(nums.size());
result = maxSubArrayHelper(nums, 0, numsSize - 1);
return result;
}
int maxSubArrayHelper(vector<int> &nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) / 2;
int leftSum = maxSubArrayHelper(nums, left, mid);
int rightSum = maxSubArrayHelper(nums, mid + 1, right);
int midSum = findMaxCrossingSubarray(nums, left, mid, right);
int result = max(leftSum, rightSum);
result = max(result, midSum);
return result;
}
int findMaxCrossingSubarray(vector<int> &nums, int left, int mid, int right) {
int leftSum = INT_MIN;
int sum = 0;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = max(leftSum, sum);
}
int rightSum = INT_MIN;
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = max(rightSum, sum);
}
return (leftSum + rightSum);
}
};