1.组合总和II
这个题目与在线OJ(十)里面的第十题的区别在：
第一个区别：这个题目里面所使用的元素，不可重复（数组中有几个用几个，比如，数组中有两个1，target=8,其中一个组合是:{1,1,6},只能用两个1，不能多用），所以，在回溯调用函数的时候，start发生了变化，start=i+1,从下一个下标元素开始看。
第二个区别：这个题目所给的数组元素有重复的，所以，在遍历的过程中，需要判断是否满足:i>start && candidates[i]==candidates[i-1],如果满足就continues，这种情况是为了result中出现重复的list,如果不加这个判定条件，结果会出现这种状况：
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> list=new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
Adjust(candidates,0,target);
return result;
}
public void Adjust(int[] candidates,int start,int target){
if(target==0){
result.add(new ArrayList<>(list));
return;
}
for(int i=start;i<candidates.length;i++){
if(candidates[i]>target){
break;
}
if(i>start && candidates[i]==candidates[i-1]){
continue;
}
list.add(candidates[i]);
Adjust(candidates,i+1,target-candidates[i]);
list.remove(list.size()-1);
}
}
}
2.全排列
解题思路：
class Solution {
List<List<Integer>> list=new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums==null || nums.length==0){
return list;
}
List<Integer> ret=new ArrayList<>();
back(nums,ret);
return list;
}
public void back(int[] nums,List<Integer> ret){
if(ret.size()==nums.length){
list.add(new ArrayList<>(ret));
return;
}
for(int i=0;i<nums.length;i++){
if(ret.contains(nums[i])){
continue;
}
ret.add(nums[i]);
back(nums,ret);
ret.remove(ret.size()-1);
}
}
}
3.旋转图像
解题思路：
class Solution {
public void rotate(int[][] matrix) {
Adjust(matrix);
}
public void Adjust(int[][] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++){
if(i<j){
int temp=arr[i][j];
arr[i][j]=arr[j][i];
arr[j][i]=temp;
}
}
}
Adjust2(arr);
}
public void Adjust2(int[][] arr){
for(int i=0;i<arr.length;i++){
int left=0;
int right=arr[0].length-1;
while(left<right){
int temp=arr[i][left];
arr[i][left]=arr[i][right];
arr[i][right]=temp;
left++;
right--;
}
}
}
}
4.字母异位词分组
利用hashMap来解决此题目
1.取出数组中的每一个元素，将string类型的字符串转换成char类型的数组,利用Arrays.sort(),去调整，如果hashMap中已经存在这个字符串，就在对应的value后面添加这个新的元素，如果hashMap中不存在这个字符串，就new 一个list,在这个list当中添加这个数组元素，然后，将这个Arrays.sort(),调整过后的元素和对应的list放在hashMap当中。
然后再新new一个List,将hashMap当中的元素都放在这个新的list当中。
最后，再将新的list放在result当中。
class Solution {
List<List<String>> result=new ArrayList<>();
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> hashMap=new HashMap<>();
for(int i=0;i<strs.length;i++){
char[] temp=strs[i].toCharArray();
Arrays.sort(temp);
String newSorted=new String(temp);
if(hashMap.containsKey(newSorted)){
hashMap.get(newSorted).add(strs[i]);
}else{
List<String> list=new ArrayList<>();
list.add(strs[i]);
hashMap.put(newSorted,list);
}
}
for(String s:hashMap.keySet()){
List<String> ret=new ArrayList<>();
for(String t:hashMap.get(s)){
ret.add(t);
}
result.add(ret);
}
return result;
}
}
5.跳跃游戏
解题：
class Solution {
public boolean canJump(int[] nums) {
int max=0;
for(int i=0;i<nums.length;i++){
if(max<i){
return false;
}
int ret=i+nums[i];
if(max<ret){
max=ret;
}
}
return max>=nums.length-1;
}
}
6.合并区间
解题思路：
class Solution {
public static int[][] merge(int[][] intervals) {
if(intervals.length<2){
return intervals;
}
//对二维数组进行排序
Arrays.sort(intervals, new Comparator<int[]>() { // 匿名内部类
@Override
public int compare(int[] e1, int[] e2) {
// 如果第一列元素相等，则比较第二列元素
if (e1[0]==e2[0]) return e1[1]-e2[1]; // e1[1]-e2[1]表示对于第二列元素进行升序排序
return e1[0]-e2[0]; // e1[0]-e2[0]表示对于第一列元素进行升序排序
}
});
int start=intervals[0][0];
int end=intervals[0][1];
int i=1;
List<int[]> list=new ArrayList<>();
while(i<intervals.length){
int [] temp=intervals[i];
if(temp[0]>end){
list.add(new int[]{start,end});
start=temp[0];
end=temp[1];
}else{
end=Math.max(end,temp[1]);
}
i++;
}
list.add(new int[]{start,end});
int[][] result=new int[list.size()][];
for(int j=0;j<list.size();j++){
result[j]=list.get(j);
}
return result;
}
}
7.不同路径
解题：
class Solution {
public int uniquePaths(int m, int n) {
int[][] temp=new int[m][n];
temp[0][0]=1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i+1<m){
temp[i+1][j]+=temp[i][j];
}
if(j+1<n){
temp[i][j+1]+=temp[i][j];
}
}
}
return temp[m-1][n-1];
}
}
8.最小路径和
解题思路：
class Solution {
public int minPathSum(int[][] grid) {
int[][] result=new int[grid.length][grid[0].length];
for(int i=grid.length-1;i>=0;i--){
for(int j=grid[0].length-1;j>=0;j--){
if(i!=grid.length-1&&j==grid[0].length-1){
0000 result[i][j]=grid[i][j]+result[i+1][j];
}else if(i==grid.length-1 && j!=grid[0].length-1){
result[i][j]=grid[i][j]+result[i][j+1];
}else if(i!=grid.length-1 && j!=grid[0].length-1){
result[i][j]=grid[i][j]+Math.min(result[i+1][j],result[i][j+1]);
}else{
result[i][j]=grid[i][j];
}
}
}
return result[0][0];
}
}
9.翻转二叉树
解题思路：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode temp=invertTree(root.left);
root.left=invertTree(root.right);
root.right=temp;
return root;
}
}
10.颜色分类
class Solution {
public void sortColors(int[] nums) {
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length-1;j++){
if(nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}
}
