初级算法
一、删除排序数组的重复项
题目：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
public int removeDuplicates(int[] nums) {
int count = 0;
for (int i = 1; i < nums.length; i++) {
if(nums[i] == nums[i - 1]){
count ++;
}else {
nums[i - count] = nums[i];
}
}
return nums.length - count;
}
二、买卖股票的最佳时机
给定一个数组 prices ，其中?prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
示例：
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
? 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3
解法1：
public static int maxProfit(int[] prices) {
int money = 0;
if(prices == null || prices.length < 2){
return 0;
}
boolean a = true;
for (int i = 0; i < prices.length - 1; i++) {
if(prices[i] >= prices[i + 1] && !a){
money = money + prices[i];
a = true;
}
if(prices[i] < prices[i + 1] && a){
money = money - prices[i];
a = false;
}
}
if(prices[prices.length - 1] > prices[prices.length - 2]){
money = money + prices[prices.length - 1];
}
return money;
}
三、旋转数组
问题：数组中元素向右轮转k个位置，其中k是非负数
案例1：
int[] array = {1,2,3,4,5,6,7,8,9,10};
k 旋转位数
k = 3
输出：[8,9,10,1,2,3,4,5,6,7]
public static int[] xuanZhuan(int[] array,int k){
int[] temp = array.clone();
for (int i = 0; i < array.length; i++) {
int a = (i + k) % array.length;
array[a] = temp[i];
}
return array;
}
四、存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
解法1：暴力
public static boolean method(int[] array){
if(array == null){
return true;
}
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if(array[j] == array[i]){
return true;
}
}
}
return false;
}
解法2：
利用set集合特性
set中不能有重复的元素，添加相同元素失败
public static boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num))
return true;
}
return false;
}
解法3：
先排序后比较前后元素是否一致
public static boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
五、只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例：
输入: [4,1,2,1,2]
输出: 4
思路：使用异或运算，将所有值进行异或
public int singleNumber(int[] nums) {
int reduce = 0;
for (int num : nums) {
reduce = reduce ^ num;
}
return reduce;
}
六、两个数组的交集
给你两个整数数组?nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
思路：先对两个数组进行排序，后判断
public static int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList<Integer> list = new ArrayList<>();
int i = 0,j = 0;
while (i < nums1.length && j <nums2.length) {
if(nums1[i] < nums2[j]){
i ++;
}else if(nums1[i] > nums2[j]){
j ++;
}else {
list.add(nums1[i]);
i ++;
j ++;
}
}
int[] target = new int[list.size()];
for (int z = 0; z < list.size(); z++) {
target[z] = list.get(z);
}
return target;
}
七、加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
数组所有元素看成是一个数字：123 + 1 = 124
9 + 1 = 10
99 + 1 = 100
235 + 1 = 236
解决：
public static int[] plusOne(int[] digits) {
if(digits[digits.length - 1] == 9){
for (int i = digits.length - 1; i >= 0; i--) {
if(digits[i] == 9){
digits[i] = 0;
}else {
digits[i] ++;
return digits;
}
}
int[] temp = new int[digits.length + 1];
temp[0] = 1;
return temp;
}
digits[digits.length - 1] ++;
return digits;
}
八、移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例：
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
解法1：
public static void moveZeroes(int[] nums) {
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] == 0){
pos ++;
}else if(pos > 0){
nums[i - pos] = nums[i];
}
}
if(pos > 0){
for (int i = 1; i <= pos; i++) {
nums[nums.length - i] = 0;
}
}
}
解法2：
public static void moveZeroes2(int[] nums) {
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] != 0){
nums[pos ++] = nums[i];
}
}
while(pos < nums.length){
nums [pos++] = 0;
}
}
九、两数之和
给定一个整数数组 nums?和一个整数目标值 target，请你在该数组中找出 和为目标值 target? 的那?两个?整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
实例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
解法1：暴力算法
public static int[] twoSum(int[] nums, int target){
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] == target){
return new int[]{i,j};
}
}
}
return new int[]{-1,-1};
}
解法2：HashMap
思路：
新建一个HashMap存储元素
存储方式：key（存储元素值）:nums[i]，value(存储数组下标)：i
判断条件 m.get(target - nums[i]) != null，其中target - nums[i]得到是与之匹配的第二个元素值，假如能HashMap中找到对应的key则说明存在该两个元素之和等于target，同时也可得到对应元素的数组下标。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (m.get(target - nums[i]) != null) {
return new int[]{m.get(target - nums[i]), i};
}
m.put(nums[i], i);
}
return new int[]{0, 0};
}
十、有效的数独
请你判断一个?9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字?1-9?在每一行只能出现一次。
数字?1-9?在每一列只能出现一次。
数字?1-9?在每一个以粗实线分隔的?3x3?宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用?‘.’?表示。
示例1：
输入：
char[][] board = {{'8','3','.','.','7','.','.','.','.'}
,{'6','.','.','1','9','5','.','.','.'}
,{'.','9','8','.','.','.','.','6','.'}
,{'8','.','.','.','6','.','.','.','3'}
,{'4','.','.','8','.','3','.','.','1'}
,{'7','.','.','.','2','.','.','.','6'}
,{'.','6','.','.','.','.','2','8','.'}
,{'.','.','.','4','1','9','.','.','5'}
,{'.','.','.','.','8','.','.','7','9'}};
输出：false
解法1：暴力解
思路：
- line col box三张二维表作用是记录元素占用的位置
- line表可以看做是原board[][]字符数组表
- col表的行可以当做是line表中的列
- box表的行可以看做是，原board[][]字符数组的3x3单元格(9x9宫格分成9个3x3单元格，从左往右按顺序排列)
- 单元格如下表示：
- pos0,pos1,pos2,
- pos3,pos4,pos5,
- pos6,pos7,pos8
- 三张表元素按照指定的排序规则，排序在表内
- 即相同元素的排序位置是固定的
- 举个例子，在board[0][]字符数组第一行内有两个相同的元素[,9,3,4,6,8,9]
- 可以看出上述有相同元素9，即board[0][1] = 9 ，board[0][8] = 9
- 我们根据排序规则 int pos = board[i][j] - ‘1’;
- pos = board[0][1] - ‘1’ = 8
- pos = board[0][8]- ‘1’ = 8
- 得到pos都是等于8，所以当第一次位置未被占用时，board[0][1]的元素占用该位置，
- 在执行到board[0][8]时，发现位置已经被占用，所以这是一个无效的数独
public static boolean isValidSudoku(char[][] board){
int[][] line = new int[board.length][board[0].length];
int[][] col = new int[board.length][board[0].length];
int[][] box = new int[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(board[i][j] == '.')continue;
int pos = board[i][j] - '1';
int boxIndex = i/3 * 3 + j/3;
if((line[i][pos] != 0) || (col[j][pos] != 0) || (box[boxIndex][pos] != 0))return false;
line[i][pos] = col[j][pos] = box[boxIndex][pos] = 1;
}
}
return true;
}
十一、旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
解法1：
思路：首先将二维矩阵上下对称交换，然后按照对角线交换
123 789 741
456 对称交换---> 456 对角线交换---> 852
789 123 963
public static void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length / 2; i++) {
for (int j = 0; j < matrix[0].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[matrix.length - 1 - i][j];
matrix[matrix.length - 1 - i][j] = temp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if(i == j)break;
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
|