两道题都AC了,这两天的笔试都还行,挺开心的哈哈哈。
1、给定一个字符串,要求字母按照频率由高到低打印,要求时间复杂度为O(N)。
思路:构建一个堆,然后就可以了。
public static String frequencySort(String s) { // write code here PriorityQueue<String> priorityQueue = new PriorityQueue<String>(); for (int i = 0; i < s.length(); i++) { priorityQueue.add(s.substring(i,i+1)); } String str = ""; while (!priorityQueue.isEmpty()){ str+=priorityQueue.poll(); } return str; }2、给定一个n*m的矩阵,求从左上角到右下角的路径的和的最小值(每次只能往右或者往下走)
思路:动态规划解决,对于第一行的第一列而言,每一个坑就是当前位置的到起点的和(直线走),其他的坑则是 当前值和左边那个坑 与 当前值和上边那个坑的最小值即可。
定义状态方程:dp[i][j] = Math.min(dp[i-1][j] +arr[i][j],dp[i][j-1] + arr[i][j]);
public static int uniquePaths(int[][] arr) { // write code here int m = arr.length; int n = arr[0].length; int[][] dp = new int[m][n]; dp[0][0] = arr[0][0]; for (int i = 1; i < dp[0].length; i++) { int sum = 0; for (int j = i; j >= 0; j--) { sum += arr[0][j]; } dp[0][i] = sum; } for (int i = 1; i < dp.length; i++) { int sum = 0; for (int j = i; j >= 0; j--) { sum += arr[j][0]; } dp[i][0] = sum; } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[i].length; j++) { dp[i][j] = Math.min(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]); }//最上面和最左边 } for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } return dp[m-1][n-1]; }
全部评论
(7) 回帖