算法题（一）按奇偶排序数组、两数之和、回文数、两数相加、无重复字符的最长子串
发布时间：2024-08-10 11:01
文章目录
- 按奇偶排序数组（905 简单）
- 两数之和（1 简单）
- 回文数 （9 简单）
- 两数相加(2 中等)
- 无重复字符的最长子串（3 中等)
按奇偶排序数组（905 简单）
题目描述：
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
提示：
1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000
思路：
扫描整个数组，当发现偶数就将该偶数用临时变量保存，并将该偶数前面的往后移动一位，然后把该偶数放在数组的第一位。按此方法一次遍历整个数组。
算法:
Java
class Solution {
public int[] sortArrayByParity(int[] nums) {
for(int i=0;i<nums.length;i++){
if(nums[i]%2 == 0){
int temp = nums[i];
for(int j=i;j>0;j--){
nums[j] = nums[j-1];
}
nums[0] = temp;
}
}
return nums;
}
}
更好的解法：
两数之和（1 简单）
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
**示例 1：**
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] A = new int[2];
int k=0;
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if((nums[i] + nums[j]) == target){
A[k] = i;
A[++k] = j;
}
}
}
return A;
}
}
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
方法二：
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
回文数 （9 简单）
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
Java
class Solution {
public boolean isPalindrome(int x) {
if(x<0 || (x % 10 == 0 && x != 0))
return false;
int t=0;
while (x > t){
t = t*10 + x%10;
x = x/10;
}
return x==t || x==t/10;
}
}
两数相加(2 中等)
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
C++
/**
* 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) {
ListNode *head = nullptr;
ListNode *cur = nullptr;
// t表示进位后剩下的数
int t = 0;
while(l1 || l2){
// 如果没有结点了就用0代替
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
if(l1){
l1 = l1->next;
}
if(l2){
l2 = l2->next;
}
int sum = n1+n2+t;
if(!head){
// 开始的时候，使head和cur指向同一位置
head = cur = new ListNode(sum%10);
}else{
// cur不断的后移
cur->next = new ListNode(sum%10);
cur = cur->next;
}
t = sum/10;
if(t>0){
cur->next = new ListNode(t);
}
}
return head;
}
};
无重复字符的最长子串（3 中等)
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> tp;
//右指针为-1，左指针为0
int rg = -1,lf = 0;
for(int i=0;i<s.size();++i){
if(i != 0){
// 左指针向右移动一格，移除一个字符
tp.erase(s[i-1]);
}
while(rg+1 < s.size() && !tp.count(s[rg+1])){
// 不断地移动右指针
tp.insert(s[rg+1]);
rg++;
}
// 第 i 到 rg 个字符是一个极长的无重复字符子串
lf = max(lf,rg-i+1);
}
return lf;
}
};
来自于力扣