【LEETCODE】55、配列分類、適当レベル、タイトル:79、611、950
21978 ワード
第950題、この問題は私は本当に意外にも行列を使ってすると言って、大神の答え、持ってきて見てみます
package y2019.Algorithm.array;
import java.util.HashMap;
import java.util.Map;
/**
* @ClassName Exist
* @Description TODO 79. Word Search
*
* Given a 2D board and a word, find if the word exists in the grid.
* The word can be constructed from letters of sequentially adjacent cell,
* where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
*
* board =
* [
* ['A','B','C','E'],
* ['S','F','C','S'],
* ['A','D','E','E']
* ]
* Given word = "ABCCED", return true.
* Given word = "SEE", return true.
* Given word = "ABCB", return false.
*
* ， 。
* ， ， “ ” 。 。
* ： （LeetCode）
* ：https://leetcode-cn.com/problems/word-search
* 。 ， 。
*
* @Author xiaof
* @Date 2019/7/14 22:50
* @Version 1.0
**/
public class Exist {
public boolean solution(char[][] board, String word) {
//1. Word， ，
// word
char[] w = word.toCharArray();
for (int y=0; y) {
for (int x=0; x) {
if (exist1(board, y, x, w, 0)) return true;
}
}
return false;
}
//i , ， , 256 ，
private boolean exist1(char[][] board, int y, int x, char[] word, int i) {
if(i == word.length) return true;
// ， ，x,y
if(y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
if(board[y][x] != word[i]) return false;
// ,
board[y][x] = (char) ~board[y][x];
//
boolean exist = exist1(board, y, x - 1, word, i + 1)
|| exist1(board, y, x + 1, word, i + 1)
|| exist1(board, y - 1, x, word, i + 1)
|| exist1(board, y + 1, x, word, i + 1);
// ， ，
board[y][x] = (char) ~board[y][x]; //
return exist;
}
} package y2019.Algorithm.array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @ClassName TriangleNumber
* @Description TODO 611. Valid Triangle Number
* Given an array consists of non-negative integers,
* your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
*
* Input: [2,2,3,4]
* Output: 3
* Explanation:
* Valid combinations are:
* 2,3,4 (using the first 2)
* 2,3,4 (using the second 2)
* 2,2,3
*
* ， 。
*
* @Author xiaof
* @Date 2019/7/14 23:38
* @Version 1.0
**/
public class TriangleNumber {
public int solution(int[] nums) {
//1.
quikSort(nums, 0, nums.length);
// Arrays.sort(nums);
//2.
int count = 0;
for(int i = nums.length - 1; i >= 2; --i) {
int b1 = 0, b2 = i - 1, b3 = nums[i];
//3. ， 2 ，
while(b1 < b2) {
// ，
if(nums[b1] + nums[b2] > b3) {
//
count += b2 - b1; // ， ，
//
b2--;
} else {
// ，
b1++;
}
}
}
return count;
}
private void quikSort(int[] nums, int begin, int end) {
if(begin < end) {
int midSite = midSite(nums, begin, end);
quikSort(nums, begin, midSite);
quikSort(nums, midSite + 1, end);
}
}
private int midSite(int[] nums, int left, int right) {
if(left >= right) {
return nums[left];
}
// ，
int midValue = nums[left], l1 = left, r1 = right;
do {
// , do-while， ++， 0
do { ++ l1; } while(l1 < right && nums[l1] < midValue);
do { --r1; } while (left < r1 && nums[r1] > midValue);
if(l1 < r1) {
//
int temp = nums[l1];
nums[l1] = nums[r1];
nums[r1] = temp;
}
} while(l1 < r1);
// ，
nums[left] = nums[r1];
nums[r1] = midValue;
return r1;
}
public static void main(String[] args) {
int data[] = {10,20,11,30,5,40};
int data1[] ={2,2,3,4};
int data2[] = {82,15,23,82,67,0,3,92,11};
TriangleNumber fuc = new TriangleNumber();
fuc.quikSort(data2, 0, data2.length);
// System.out.println(fuc.solution(data2));
System.out.println(data);
}
}package y2019.Algorithm.array.medium;
import y2019.Algorithm.array.TriangleNumber;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**
* @ProjectName: cutter-point
* @Package: y2019.Algorithm.array.medium
* @ClassName: DeckRevealedIncreasing
* @Author: xiaof
* @Description: TODO 950. Reveal Cards In Increasing Order
* In a deck of cards, every card has a unique integer. You can order the deck in any order you want.
* Initially, all the cards start face down (unrevealed) in one deck.
* Now, you do the following steps repeatedly, until all cards are revealed:
* Take the top card of the deck, reveal it, and take it out of the deck.
* If there are still cards in the deck, put the next top card of the deck at the bottom of the deck.
* If there are still unrevealed cards, go back to step 1. Otherwise, stop.
* Return an ordering of the deck that would reveal the cards in increasing order.
* The first entry in the answer is considered to be the top of the deck.
*
* Input: [17,13,11,2,3,5,7]
* Output: [2,13,3,11,5,17,7]
* Explanation:
* We get the deck in the order [17,13,11,2,3,5,7] (this order doesn't matter), and reorder it.
* After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
* We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].
* We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].
* We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].
* We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].
* We reveal 11, and move 17 to the bottom. The deck is now [13,17].
* We reveal 13, and move 17 to the bottom. The deck is now [17].
* We reveal 17.
* Since all the cards revealed are in increasing order, the answer is correct.
*
* 。 。
* ， （ ， ）。
* ， ， ：
* ， ， 。
* ， 。
* ， 1。 ， 。
* 。
* 。
* ： （LeetCode）
* ：https://leetcode-cn.com/problems/reveal-cards-in-increasing-order
* 。 ， 。
*
* @Date: 2019/7/15 10:27
* @Version: 1.0
*/
public class DeckRevealedIncreasing {
public int[] solution(int[] deck) {
// ， ，
Arrays.sort(deck);
// ， ， ， ，
// ，
int[] res = new int[deck.length];
if(deck.length % 2 == 0) {
//
for(int i = 0, j = 0, k = deck.length - 1; i < deck.length; i += 2) {
res[i] = deck[j++];
res[deck.length - i - 1] = deck[k--];
}
} else {
//
if(deck.length > 2)
res[deck.length - 2] = deck[deck.length - 1];
for(int i = 0, j = 0, k = deck.length - 2; i < deck.length; i += 2) {
res[i] = deck[j++];
if(i + 1 < deck.length && i != deck.length - 3)
res[i + 1] = deck[k--];
}
}
return res;
}
/**
*
* @program: y2019.Algorithm.array.medium.DeckRevealedIncreasing
* @description: ：https://leetcode.com/problems/reveal-cards-in-increasing-order/discuss/200526/Java-Queue-Simulation-Step-by-Step-Explanation
*/
public int[] solution2(int[] deck) {
int n= deck.length;
Arrays.sort(deck);
Queue q= new LinkedList<>();
//
for (int i=0; i) q.add(i);
int[] res= new int[n];
for (int i=0; i){
// ，
res[q.poll()]=deck[i];
// ， ， ，
q.add(q.poll());
}
return res;
}
public static void main(String[] args) {
int data[] = {17,13,11,2,3,5,7};
int data1[] = {1,2,3,4,5,6};
DeckRevealedIncreasing fuc = new DeckRevealedIncreasing();
System.out.println(fuc.solution2(data1));
System.out.println();
}
}