思路:这个题最容易想到双重循环的暴力法,O(n^2)的时间复杂度肯定超时,所以我们使用头尾双指针,找出面积最大即可。
AC代码如下:
class Solution { public int maxArea(int[] height) { int max = 0 ; int l = 0 ; int r = height.length - 1 ; while(l
2-加油站
题目链接:题目链接戳这里!!!思路:如果总的汽油量大于总的消耗量,则一定能环绕一周,我们只需要找到一个出发点就可以,从后向前遍历,所剩余的汽油量最多的点就是我们要出发的点。
AC代码如下:
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { //只有总的汽油量大于消耗量就一定能绕一周,就是需要确定从那绕,从后往前剩余汽油最多的地方出发 int left = 0, idx = 0 ; int max = Integer.MIN_VALUE ; for(int i=gas.length-1; i>=0; i--){ left += gas[i]-cost[i] ; if(left >= max){ max = left ; idx = i ; } } if(left>=0){ return idx ; }else{ return -1 ; } } }
3-最大数
题目链接:题目链接戳这里!!!思路:将所有的整数转换成字符串数组,根据字符串的两两相加进行排序,然后由大到小取出即可。
AC代码如下:
class Solution { public String largestNumber(int[] nums) { String [] str = new String [nums.length] ; for(int i=0; i(o1+o2).compareTo(o2+o1)) ; StringBuilder s = new StringBuilder() ; for(int i=str.length-1; i>=0; i--){ s.append(str[i]) ; } if(s.charAt(0)=='0'){ return "0" ; } return new String(s) ; } } 4-递增的三元子序列
题目链接:题目链接戳这里!!!思路:每次找出最小的和第二个的,如果出现一个比第二小的大,则是递增三元组。
AC代码如下:
class Solution { public boolean increasingTriplet(int[] nums) { int a = Integer.MAX_VALUE ; int b = Integer.MAX_VALUE ; for(int i=0; i
5-去除重复字母
题目链接:题目链接戳这里!!!思路:借助栈实现,每次正常进栈,当当前元素比栈顶元素小,并且栈顶元素在后面的字符串中出现,则栈顶元素出栈,当前元素入栈。
AC代码如下:
class Solution { public String removeDuplicateLetters(String s) { //借助栈实现 Stackstack = new Stack<>() ; for(int i=0; i c && s.indexOf(stack.peek(),i)!=-1){ stack.pop() ; } stack.push(c) ; } String s1 = "" ; for(int i=0; i
6-最长回文串
题目链接:题目链接戳这里!!!思路:将字符的数量分别存储HashMap中,然后偶数个的字符肯定可以凑成回文,奇数个的减去一个变成偶数也能凑成回文数,最后保留有一个最长的奇数也能凑成回文。
AC代码如下:
class Solution { public int longestPalindrome(String s) { Mapmap = new HashMap<>() ; for(int i=0; i
7-摆动序列
题目链接:题目链接戳这里!!!思路:利用摆动序列波峰和波谷的差值最大为1的特点,找出波峰或者波谷的最大值即可。
AC代码如下:
class Solution { //利用摆动序列的波峰和波谷差值最大为1的特点 public int wiggleMaxLength(int[] nums) { if(nums.length==1){ return 1 ; } int up = 1, down = 1, max = 0 ; for(int i=1; inums[i]){ up = down + 1 ; } if(nums[i-1]
8-整数替换
题目链接:题目链接戳这里!!!思路:如果是偶数直接除以2,如果二进制是最后两位是11且不是3,则加1,否则减1.
AC代码如下:
class Solution { public int integerReplacement(int n) { long temp = n ; int cnt = 0 ; while(temp!=1){ if((temp&3)==3 && temp!=3){ temp++; }else if((temp&1)==1){ temp--; }else{ temp >>= 1 ; } cnt ++ ; } return cnt ; } }
递归解法如下:class Solution { public int integerReplacement(int n) { return (int)f((long)n); } public long f(long n){ if(n==1){ return 0 ; } if((n&1)==0){ return 1+ f(n/2) ; }else{ return 1 + Math.min(f(n+1),f(n-1)) ; } } }
9-移掉k位数字
题目链接:题目链接戳这里!!!思路:找出第一个右边比左边小的,删除,如果右边的都比左边的大,则删除最后一个。如果前面的有多余的零,清掉。
AC代码如下:
class Solution { public String removeKdigits(String num, int k) { if(num.length()<=k){ return "0" ; } StringBuilder str = new StringBuilder(num) ; for(int i=0; i=str.charAt(j-1); j++){ idx = j ; } str.deleteCharAt(idx) ; } while(str.length() > 1 && str.charAt(0)=='0'){ str.deleteCharAt(0) ; } return str.toString() ; } }
10-最大交换
题目链接:题目链接戳这里!!!思路:将数字由大到小排序,第一个与原来位置不一样的就是要交换的,要是都有原来一样,则是最大,不需要交换。
AC代码如下:
class Solution { public int maximumSwap(int num) { String s1 = new String(num+""); char [] r = s1.toCharArray() ; char [] r1 = new char[r.length] ; Arrays.sort(r) ; int k=0 ; for(int i=r.length-1; i>=0; i--){ r1[k++] = r[i] ; } String s2 = String.valueOf(r1) ; if(s1.equals(s2)){ return num ; }else{ char [] a = s1.toCharArray() ; char [] b = s1.toCharArray() ; //原来的 char [] c = new char [a.length] ;//有大到小排序的 Arrays.sort(a) ; int j=0 ; for(int i=a.length-1; i>=0; i--){ c[j++] = a[i] ; } char v1='0', v2='0' ; int index1 = 0; for(int i=0; i欢迎分享,转载请注明来源:内存溢出
评论列表(0条)