hahah, the first time to pass the hard difficulty problem.
缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public int firstMissingPositive(int[] nums) { Set<Integer> set1 = new HashSet<Integer>(); int temp = 0; for(int num: nums){ set1.add(num); } for(int i = 1;i <= nums.length+1; i++){ if(!set1.contains(i)){ temp = i; break; } } return temp; } }
|
最大子数组的和
感觉貌似使用的算法叫贪心算法,设置一个max值,如果对于cur位上的数进行相加的时候大于max,那么max就等于cur上的数,否则max就等于max加上cur上的数,最后返回max即可.
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; max = Math.max(max, sum); sum = Math.max(sum, 0); } return max; } }
|
只出现一次的数字
多数元素
两道题可以使用无敌的hash来解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int singleNumber(int[] nums) { int temp = 0; Map<Integer,Integer> map1 =new HashMap<Integer,Integer>(); for(int num : nums){ map1.put(num,map1.getOrDefault(num,0)+1); } for(int num : map1.keySet()){ if(map1.get(num)==1){ temp = num; } } return temp; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int majorityElement(int[] nums) { int temp = 0; Map<Integer,Integer> map1 = new HashMap<Integer,Integer>(); for(int num: nums){ map1.put(num,map1.getOrDefault(num,0)+1); } for(int num:map1.keySet()){ if(map1.get(num)>nums.length/2){ temp = num; } } return temp; } }
|
括号匹配
没啥说的,注意字符串转字符型
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| import java.util.Stack;
class Solution { public boolean isValid(String s) { Stack<Character> nstack = new Stack<>(); char[] ca = s.toCharArray(); for (char c : ca) { if (c == '(' || c == '[' || c == '{') { nstack.push(c); } else if (c == ')') { if (nstack.isEmpty() || nstack.pop() != '(') { return false; } } else if (c == '}') { if (nstack.isEmpty() || nstack.pop() != '{') { return false; } } else if (c == ']') { if (nstack.isEmpty() || nstack.pop() != '[') { return false; } } } return nstack.isEmpty(); } }
|
删除链表的中间节点
无敌的快慢指针,此题应该快指针从头开始
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public ListNode deleteMiddle(ListNode head) { if(head==null||head.next==null){ return null; } ListNode fast = head; ListNode low = head;
while(fast!=null&&fast.next!=null){ low = low.next; fast = fast.next.next; } ListNode cur = head; while(cur.next != low){ cur = cur.next; } cur.next = low.next; low.next = null; return head; } }
|