37~47
难度中等588
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
回溯算法:
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 27 28 29 30 31 32 33 34 35 class Solution { char[]chars; boolean[]vis=new boolean[128]; List<String> list=new ArrayList<>(); public String[] permutation(String s) { chars=s.toCharArray(); dfs(0); return list.toArray(new String[list.size()]);// 预设数组大小 } //循环 , 每次交换 下标, void dfs(int idx){ // idx 表示的是当前的下标 if(idx==chars.length-1){// 此时已经遍历完了一种情况 list.add(String.valueOf(chars)); return ; } //Arrays.fill(vis,false); Set<Character> set=new HashSet<>(); for(int i=idx;i<chars.length;i++){ // i直接从idx 的位置开始, 因为前面的字符已经确定了 //if(vis[chars[i]]){ if(set.contains(chars[i])){ continue; // 有重复字符, 跳过本轮循环 } set.add(chars[i]); swap(chars,i,idx); // 交换 , 出现新的情况 // vis[chars[i]]=true; dfs(idx+1); swap(chars,i,idx); } }// 需要去重 void swap(char[]chars,int i,int j){ char temp=chars[i]; chars[i]=chars[j]; chars[j]=temp; } }
难度简单304
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
首先定义res 作为众数, vote 表示投票数
当遍历到
时
如果vote==0 , 那么我们就直接假设当前的这个num 就是众数 ,并且vote+1
如果vote!=0 , 那么就直接进行运算, 如果num与当前假设的众数相同, 那么就vote+1 ,反之 vote-1
因为题目给的众数的个数超过数组长度的一半, 所以可以假设数组中只有两种数值的数字
如果前面都是其他的数字, 那么 就相当于这些数字在内耗, 3,2,4,6,5,6,2,2,7,8,1,1,1,2,2,2,2,2,2
如果众数的分布比较集中, 那么就是数量碾压(**数组中有一个数字出现的次数超过数组长度的一半 **)
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int majorityElement(int[] nums) { int res=0,vote=0; for(int num:nums){ if(vote==0){ //说明之前的选票全部都抵消了 , 那么剩下的部分的数组的众数依然是不变的 res=num; //我们假设这个数字是众数 } vote+=num==res?1:-1; } return res; } } //3,2,4,6,5,6,2,2,2,2,2,7,8,1,1,1,2,2,2
难度简单469
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
1 2 3 4 5 6 class Solution { public int[] getLeastNumbers(int[] arr, int k) { Arrays.sort(arr); return Arrays.copyOf(arr,k); } }
更快的做法是用快排 , 只需要保证前 k 个数字的是最小的 ,不需要保证他们的顺序, 因此
找前 K 大/前 K 小问题不需要对整个数组进行 O(NlogN) 的排序
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 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k == 0 || arr.length == 0) { return new int[0]; } // 最后一个参数表示我们要找的是下标为k-1的数 return quickSearch(arr, 0, arr.length - 1, k - 1); } private int[] quickSearch(int[] nums, int lo, int hi, int k) { // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数； int j = partition(nums, lo, hi); if (j == k) { return Arrays.copyOf(nums, j + 1); } // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。 return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k); } // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。 private int partition(int[] nums, int lo, int hi) { int v = nums[lo]; int i = lo, j = hi + 1; while (true) { while (++i <= hi && nums[i] < v); while (--j >= lo && nums[j] > v); if (i >= j) { break; } int t = nums[j]; nums[j] = nums[i]; nums[i] = t; } nums[lo] = nums[j]; nums[j] = v; return j; } }
难度简单583
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
dp[i] 表示以 i 为结尾的子数组的最大和 , 由于 dp[i] 只跟 nums[i-1]以及nums[i]有关, 因此直接在原数组上面dp , 可以吧空间复杂度降低到O(1)
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int maxSubArray(int[] nums) { int res=nums[0]; for( int i=1;i<nums.length;i++) { nums[i]+=Math.max(0,nums[i-1]); res=Math.max(nums[i],res); } return res; } }
难度中等276
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
找规律:
数字(start)
位数(digit)
数位(cnt)
1~9
1
9*1
10~99
2
90*2
100~999
3
900*3
1000~9999
4
9000*4
每次都减去cnt , 然后扩大start以及digit ,直到n<cnt
此时即可得出n的区间, 以及n 的位数
需要注意的是
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int findNthDigit(int n) { int digit=1;start=1; long cnt=start*digit*9; while (n>cnt){ n-=cnt; start*=10; digit++; cnt=start*digit*9; } //此时可以求出n 的位数,起始数字, long res= start + (n - 1) / digit; // 由于题目给的数列还有一个0 , 因此要减去一位 return Long.toString(res).charAt((n-1)%digit)-'0'; // 由于数组的性质, 需要减去一位, 数组从0 开始, 而n的位数是从1 开始数的 } }
难度中等517
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
此题求拼接起来的最小数字，本质上是一个排序问题。设数组 numsnums 中任意两数字的字符串为 xx 和 yy ，则规定 排序判断规则 为：
若拼接字符串 x + y > y + x 则 x “大于” y ；x + y < y + x ，则 x “小于” y ；
初始化字符串数组, 保存数字的字符串格式
自定义排序规则排序
拼接数组中的字符串, 返回
实测发现 StringBuilder 比StringBuffer 快了一点
使用Arrays.sort 自定义Comparator
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public String minNumber(int[] nums) { String[]strings=new String[nums.length]; int cnt=0; for (int num : nums) { strings[cnt++]=String.valueOf(num); } Arrays.sort(strings, new Comparator<String>() { @Override public int compare(String o1, String o2) { String temp=o1; o1+=o2; o2+=temp; return (int)(Long.parseLong(o1)-Long.parseLong(o2)); } }); StringBuffer res= new StringBuffer(); for (String string : strings) { res.append(string); } return res.toString(); } } public String minNumber(int[] nums) { String[]strings=new String[nums.length]; int cnt=0; for (int num : nums) { strings[cnt++]=String.valueOf(num); } //使用lambda表达式 Arrays.sort(strings, (o1, o2) -> { String temp=o1; o1+=o2; o2+=temp; return (int)(Long.parseLong(o1)-Long.parseLong(o2)); }); StringBuffer res= new StringBuffer(); for (String string : strings) { res.append(string); } return res.toString(); }
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 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public String minNumber(int[] nums) { String[]strings=new String[nums.length]; int cnt=0; for (int num : nums) { strings[cnt++]=String.valueOf(num); } sort(strings,0,strings.length-1); StringBuilder res= new StringBuilder(); for (String string : strings) { res.append(string); } return String.valueOf(res); } public void sort(String[]strings, int left, int right) { if (left > right) return; int i = left, j = right; String benchmark = strings[left]; // 判断大小的方式, 基准大: 基准+当前 -(当前+基准) >0 while (i != j) { // 右边的哨兵 的数字如果一直都比基准大, 那么j-- while((strings[j] + benchmark).compareTo(benchmark + strings[j]) >= 0 && i < j) j--; // 左边的哨兵 的数字如果一直都比基准小,那么i++ while((strings[i] + benchmark).compareTo(benchmark + strings[i]) <= 0 && i < j) i++; if (i < j) { // 如果哨兵仍然没有相遇 , 就交换然后继续走 String temp = strings[i]; strings[i] = strings[j]; strings[j] = temp; } } // 最后再将基准 归位(原本的基准一直是在第一位, 此时 i哨兵 左边的元素都小于基准) // 然后递归处理 左右两边的部分 strings[left]=strings[i]; strings[i]=benchmark; sort(strings,left,i-1); sort(strings,i+1,right); } }
难度中等468
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int translateNum(int num) { String s=String.valueOf(num); if(s.length()==1) return 1; int []dp=new int[s.length()]; char[]chars=s.toCharArray(); dp[0]=1; dp[1]=1; if(chars[0]!='0'&&new String(chars,0,2).compareTo("26")<0) dp[1]=2; for (int i = 2; i < chars.length; i++) { //chars[i-1]+chars[i]!="26" if (chars[i-1]!='0'&&new String(chars,i-1,2).compareTo("26")<0){ dp[i]=dp[i-1]+dp[i-2]; }else{ dp[i]=dp[i-1]; } } return dp[s.length()-1]; } }
难度中等316
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 // class Solution { // int res=0; // public int maxValue(int[][] grid) { // dfs(grid,0,0,0); // return res; // } // void dfs(int[][] grid,int i,int j,int nowValue){ // i 表示行 , j 表示列 // if(i>=grid.length||j>=grid[0].length) { // return ; // } // nowValue+=grid[i][j]; //必定要加 当前的格子的value // if(i==grid.length-1&&j==grid[0].length-1){ // res=res>nowValue?res:nowValue; // } // dfs(grid,i,j+1,nowValue); // dfs(grid,i+1,j,nowValue); // } // }
对于左边界以及又边界, 结果只能是上一个格子的累加
对于其他的格子, 取上方或者左方较大的那个格子即可
dp数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int maxValue(int[][] grid) { int m=grid.length,n=grid[0].length; int[][]dp=new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if(i==0&&j==0) dp[i][j]=grid[i][j]; else if(i==0) dp[i][j]=grid[i][j]+dp[i][j-1]; else if(j==0) dp[i][j]=grid[i][j]+dp[i-1][j]; else dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]); } } return dp[m-1][n-1]; } }
直接在原数组dp
当 gridgrid 矩阵很大时， i = 0或 j = 0 的情况仅占极少数，相当循环每轮都冗余了一次判断。
因此，可先初始化矩阵第一行和第一列，再开始遍历递推。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int maxValue(int[][] grid) { int m=grid.length,n=grid[0].length; for (int i = 1; i < m; i++) { grid[i][0]+=grid[i-1][0]; } for (int j = 1; j < n; j++) { grid[0][j]+=grid[0][j-1]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j]=grid[i][j]+Math.max(grid[i-1][j],grid[i][j-1]); } } return grid[m-1][n-1]; } }
image-20220805160319600如果start以及cnt 使用int 会溢出, 需要使用long.
