两道题都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) 回帖