27. 移除元素
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
答案
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[slow++] = nums[i];
}
}
return slow;
}
}
344. 反转字符串
题目
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
答案
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length-1;
while(left<right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
替换数字
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
答案
import java.util.Scanner
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++){
if(Character.isDigit(s.charAt(i))){
sb.append("number");
}else{
sb.append(s.charAt(i);
}
}
System.out.println(sb.toString());
}
}
151. 反转字符串中的单词
题目
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
答案
class Solution {
public String reverseWords(String s) {
char[] temp = s.toCharArray();
int len = temp.length;
char[] res = new char[len+1];
int index = 0;
for(int i=len-1;i>=0;i--){
while(i>=0 && temp[i]==' ') i--;
int right = i;
while(i>=0 && temp[i]!=' ') i--;
int left = i + 1;
while(left<=right){
res[index++] = temp[left];
if(left==right){
res[index++] = ' ';
}
left++;
}
}
return new String(res,0,index-1);
}
}
206. 反转链表
题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
答案
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
ListNode post = null;
while(curr!=null){
post = curr.next;
curr.next = pre;
pre = curr;
curr = post;
}
return pre;
}
}
19. 删除链表的倒数第 N 个结点
题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
答案
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
ListNode slow = dummy;
ListNode fast = dummy;
for(int i=0;i<=n;i++){
fast = fast.next;
}
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
面试题 02.07. 链表相交
题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
答案
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
List<ListNode> list = new ArrayList();
while(headA!=null){
list.add(headA);
headA = headA.next;
}
while(headB!=null){
if(list.contains(headB)){
return headB;
}
headB = headB.next;
}
return null;
}
}
142. 环形链表 II
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
答案
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow==fast){
ListNode node1 = head;
ListNode node2 = slow;
while(node1!=node2){
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
}
return null;
}
}
15. 三数之和
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要
答案
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
for(int i=0;i<nums.length;i++){
if(nums[i] > 0){
return res;
}
if(i>0 && nums[i]==nums[i-1]) continue;//if + continue 去重
int left = i + 1;
int right = nums.length - 1;
while(left<right){
int sum = nums[i] + nums[left] + nums[right];
if(sum>0){
right--;
}else if(sum<0){
left++;
}else{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left<right && nums[left]==nums[left+1]) left++;//while 去重
while(left<right && nums[right]==nums[right-1]) right--;
left++;
right--;
}
}
}
return res;
}
}
18. 四数之和
题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
答案
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
for(int i=0;i<nums.length;i++){
if(nums[i]>0 && nums[i]>target){//注意 num[i]>0
return res;
}
if(i>0 && nums[i]==nums[i-1]){
continue;
}
for(int j=i+1;j<nums.length;j++){
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
int left = j + 1;
int right = nums.length - 1;
while(left<right){
long sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum>target){
right--;
}else if(sum<target){
left++;
}else{
res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left<right && nums[left]==nums[left+1]) left++;
while(left<right && nums[right]==nums[right-1]) right--;
left++;
right--;
}
}
}
}
return res;
}
}
