20. Valid brackets
Given a string containing only ‘(‘,’) ‘, ‘{‘,’} ‘, ‘[‘,’] ‘, check whether the string is valid.
A valid string must meet the following requirements:
An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string.
Example 1:
Input: () Output: true Example 2:
Input: ()[]{} Output: true Example 3:
Input: (] Output: false Example 4:
Input: ([)] Output: false Example 5:
Input: {[]} Output: true
If so, remove the last one and check whether the list is empty.
class Solution {
public boolean isValid(String s) {
ArrayList<Character> res = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
if (res.size() == 0) {
res.add(s.charAt(i));
continue;
}
if (res.get(res.size() - 1).equals('(') && s.charAt(i) == ') ') {
res.remove(res.size() - 1);
continue;
}
if (res.get(res.size() - 1).equals('{') && s.charAt(i) == '} ') {
res.remove(res.size() - 1);
continue;
}
if (res.get(res.size() - 1).equals('[') && s.charAt(i) == '] ') {
res.remove(res.size() - 1);
continue;
}
res.add(s.charAt(i));
}
return res.size() <= 0; }}Copy the code21. Merge two ordered lists
Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Store the sorted values of two linked lists and assign them one by one
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null && l2==null) return l1;
if(l1==null || l2==null) return l1==null? l2:l1;
ArrayList<Integer> res = new ArrayList<>();
ListNode l11 = l1;
ListNode l22 = l2;
while(l11! =null|| l22! =null) {if(l11==null){
res.add(l22.val);
l22 = l22.next;
continue;
}
if(l22==null ){
res.add(l11.val);
l11 = l11.next;
continue;
}
if(l11! =null&& l22! =null) {if(l11.val<=l22.val){
res.add(l11.val);
l11 = l11.next;
continue;
}
if(l11.val>l22.val){
res.add(l22.val);
l22 = l22.next;
continue;
}
}
}
ListNode number = l1;
ListNode head = l1;
while(number.next! =null){
number = number.next;
}
number.next = l2;
int i =0;
System.err.println(res.size());
while(l1! =null){
l1.val = res.get(i);
i++;
l1 = l1.next;
}
returnhead; }}Copy the code26. Remove duplicates from sorted array
Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.
Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.
Example 1:
Given array nums = [1,1,2],
The function should return a new length of 2, and the first two elements of the original nums array should be changed to 1, 2.
You don’t need to worry about the element after the new length in the array. Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
The function should return a new length of 5, and the first five elements of the original nums array should be changed to 0, 1, 2, 3, 4.
You don’t need to worry about the element after the new length in the array.
If the left pointer is equal to the right pointer, the next position of the left pointer is equal to the right pointer, and then add one to both Pointers
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0) return 0;
if(nums.length==1) return 1;
int l = 0 , r = 1;
while (r < nums.length) {
if(nums[r]! =nums[l]){ nums[l+1] = nums[r];
r++;
l++;
continue;
}
if(nums[r]==nums[l]){ r++; }}return l+1; }}Copy the code27. Remove elements
Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array.
Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.
The order of elements can be changed. You don’t need to worry about the element after the new length in the array.
Example 1:
Given nums = [3,2,2,3], val = 3,
The function should return a new length of 2, and the first two elements in nums are both 2.
You don’t need to worry about the element after the new length in the array. Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2,
The function should return a new length of 5, and the first five elements in nums are 0, 1, 3, 0, 4.
Notice that these five elements can be in any order.
You don’t need to worry about the element after the new length in the array.
Determine the length of the array returned, then move each number by this length, if the number traversed is not equal to val next, if you want to wait, find the next unequal swap, traversal until the desired length is reached.
class Solution {
public int removeElement(int[] nums, int val) {
int length = nums.length;
for (int num : nums) {
if (num == val) length--;
}
for (int i = 0; i < length; i++) {
if (nums[i] == val) {
for (int j = i; j < nums.length; j++) {
if(nums[j] ! = nums[i]) {int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
break; }}}}returnlength; }}Copy the code