胶州网站建设/seo资源咨询

25. K 个一组翻转链表(困难)

思路：栈存一下，每k个转制一下，数组存储，然后末尾再新增一个栈逆置一下

问题：

class Solution {public ListNode reverseKGroup(ListNode head, int k) {List<ListNode> array = new ArrayList();Stack<ListNode> stack = new Stack();Stack<ListNode> stack2 = new Stack();int cnt = 0;while(head!=null){stack.push(head);cnt++;if(cnt==k){cnt = 0;while(!stack.isEmpty()){array.add(stack.pop());}}head = head.next;}while(!stack.isEmpty()){stack2.push(stack.pop());}while(!stack2.isEmpty()){array.add(stack2.pop());}head = array.get(0);array.get(array.size()-1).next = null;ListNode last = head;for(int i=1;i<array.size();i++){last.next = array.get(i);last = array.get(i);}return head;}
}

72. 编辑距离（困难）

思路：dp，当s - > p，当s[j]和p[i]进行比较的时候，如果相等则什么都不做，dp[i][j] = dp[i-1][j-1]

如果不相等：替换则为dp[i][j] = dp[i-1][j-1]+1 ；插入则为dp[i][j] = dp[i-1][j]+1 ； 删除则为dp[i][j] = dp[i][j-1]+1

同时注意，其实状态dp[0][0] = 0，这里为了方便，直接在s和p的前面各插入一个‘*’，用以模拟两个空串时不需要进行操作，同时也避免了判空操作。然后需要对dp[i][0]和dp[0][j] 分别初始化成i和j，由于前面加了*,在操作字符串数组和dp数组的时候，下标相等，不需要考虑转换到问题。

class Solution {public int minDistance(String word1, String word2) {word1 = '*'+ word1;word2 = '*'+ word2;int dp[][]  = new int[word2.length()][word1.length()];for(int i=0;i<word2.length();i++)dp[i][0] = i;for(int j=0;j<word1.length();j++)dp[0][j] = j;for(int i=1;i<word2.length();i++){for(int j=1;j<word1.length();j++){if(word2.charAt(i)==word1.charAt(j)){dp[i][j] = dp[i-1][j-1];}else {dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1;}}}return dp[word2.length()-1][word1.length()-1];}
}

931. 下降路径最小和(中等)

思路：两层for算一下

问题：

class Solution {public int minFallingPathSum(int[][] matrix) {int n = matrix.length;int dp[][] = new int[n][n];for(int i=0;i<n;i++)dp[0][i] = matrix[0][i];for(int i=1;i<n;i++){for(int j=0;j<n;j++){int left = j>0?dp[i-1][j-1]:10001;int above = Math.min(dp[i-1][j],left);int right = Math.min(j<n-1?dp[i-1][j+1]:10001,above);dp[i][j] = matrix[i][j] + right;}}int min = 10001;for(int j=0;j<n;j++){if(dp[n-1][j] < min)min = dp[n-1][j];}return min;}
}